AStar problem
March 30, 2003 08:46 AM
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]
Gandalf the Black
March 30, 2003 08:56 AM
You could do a bi-directional search. *shrug*
Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"
Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"
Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-founder and 10 year advisor of the GDC AI Summit
Author of the book, Behavioral Mathematics for Game AI
Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play
"Reducing the world to mathematical equations!"
122
March 30, 2003 10:43 AM
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
Last but not least, you should think about some cancel criteria for your pathfinder an/or thinking about hirachial pathfinding.
@$3.1415rin
158
March 30, 2003 11:14 AM
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.
March 30, 2003 11:26 AM
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.
Gandalf the Black
1,412
March 30, 2003 12:10 PM
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).
"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk
March 30, 2003 01:19 PM
Extrarius: Sound intresting. Where can I read more about this?
Gandalf the Black
1,412
March 30, 2003 03:22 PM
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.
"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk
234
March 30, 2003 03:30 PM
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
tj963
tj963
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
