Hello, I have just made the A-Star algorith for pathfinding in my RTS game and it works fine, but... If the destination node are on a island or in a vallay compleatly surrounded by blocked nodes (and the map are big) the search takes more then 5 minutes! I think this can be solved by first find out if the destination node can be reached. But how to do that? [edited by - Gandalf on March 30, 2003 9:47:11 AM]

You could do a bi-directional search. *shrug*

Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"

or you could cache it ( ok, 5 minutes are 5 minutes, but then you won''t do that again ), you could preprocess the navigation map with some other algorithm like floyd warshall for example to see where are possible ways. ( would take really long when one nonexisting path takes 5 min )
Last but not least, you should think about some cancel criteria for your pathfinder an/or thinking about hirachial pathfinding.

@$3.1415rin

I guess you could generate some kind of 2D byte array, where each element corresponds to a map cell. Then you''d calculate during loading time which landmass each cell was. If during play time the source and targets points of a pathsearch were of different landmasses, you wouldn''t even bother to perform the A* calculation.

Unwise owl: Yes, I think I will do something like that. But the problem remains if the destination point is on the same landmass but but surroounded by trees.

I think heirarchial pathfinding mimght be a good way to fix your problem. You first find a course path and then find the path from each large grid area to the next one on the course path. You can limit the search depth to something like twice the number of waypoints in a diagonal in the course grid. It should be a lot faster than a full search (since the course grid has only a fraction of the nodes, and then each search after that{from course node to course node} only needs to search a few nodes each).

Extrarius: Sound intresting. Where can I read more about this?

Really, I don''t have any idea. I don''t remeber any papeers, tutorials, sites, etc on it. I''ve seen it mentioned all over the place but I haven''t seen any detailed information about it and I looked around because I haven''t had a need for it yet.

How large is your map? I''d check your implementation because unless your map is huge, five minutes is a really long time, even to search the entire map.

tj963

Only 256x256 squares...