wangzhonnew at October 16th, 2006 15:50 — #1
I'm working on a 2d RTS game at this moment.
I'm using A* algorithm to find the path between two location.
But I have a problem here.
With short path A* algorithm works well, but when the destination is far from the source, it will take seconds to half minitues to search the path if the map is kinda complex (for a realtime RTS this is not acceptable).
I'm currently setup a searching thread for each object and divide the path from dest to source to different pieces and push to the object's stack: like 100-200, 50-100, 25-50, 12-25, 6-12, 1-6
the path finding algorithm will popup those data from stack so he can get the path for 1-6 very quick, then when the object moving it will try to calcualte 6-12, 12-25, 25-50...
but there are still a lot of problem, one of them is like if the divided position (like 100, 50) cannot pass, we have to find another position around it, and it also cannot guarentee the bast path (if the object is in a half circle, it will hit the wall, then turn back and go out the half circle).
I think this implementation is pretty nasty and bad efficient, just curious is there any other good ways to do it realtime?
Thanks very much:worthy: :worthy: :worthy:
jare at October 16th, 2006 16:00 — #2
Most RTS games do partial paths, i.e. search a path until N nodes then try it and re-search after some time. Other approaches include using higher level structures to figure out reachability and search optimization, but in the end it depends on the game, the map design and size, the movement abilities of units, etc.
Using separate threads for something like this is never a good idea unless you have plenty of spare extra cores / processors. Also, make sure that your A* data structures are VERY fast, a naive implementation can be as much as 20x slower than it should be... consider that A* was being used successfully in machines 10 years old.
wangzhonnew at October 16th, 2006 17:42 — #3
thanks for quick reply, do you have any sample code of A* algorithm that can search pretty fast?
groundkeeper at October 17th, 2006 03:25 — #4
What kind of structure do you apply you A* to?
A very important aspect of A* is how the datastructure you apply it on looks.
Meaning in most cases you can optimize the search by applying some network approche. If it is as slow as you say I would guess you apply it on a heightfield or something like that?
jare at October 17th, 2006 16:57 — #5
Classic places to look at for A* info and details:
wangzhonnew at October 18th, 2006 13:45 — #6
my current implementation is based on the template that provided by googlecode:
http://a-star-algorithm-implementation.googlecode.com/svn/trunk/ (the data structure of the Node is in findpath.cpp, i didn't change too much about the structure, the A* algorithm is in stlastar.h)
I found out in the code the Successor enumeration doesn't give a good order, so I have sorted (qsort provided by microsoft) the estimated distance between the current successor and the destination before pushing the successors into vector (the code that googlecode provided only provide 4 directions)
I think their implementation is based on the same theory that all A* algorithm described (G,H, F), I found for a search in 200x200 map, it may take thousands steps to find a path if the map is purely randomly generated (in the real game it may possible if the towers or buildings are located everywhere), which usually took more than 20 seconds to complete (here i mean from upper left corner to right down corner). Benchmarking found that searching 800 nodes usually take 5 sec.
I'm thinking to implement it using two tired A*, but defining the upper layer of the map is a problem (if the two island are completely isolated, how can we tell that using program when creating upper layer based on original map)
wangzhonnew at October 18th, 2006 14:05 — #7
maybe i should define "GetMap" as inline function? is that will improve the speed a lot?
reedbeta at October 18th, 2006 15:14 — #8
Benchmarking found that searching 800 nodes usually take 5 sec.
I don't know what's going on there, but that's WAY slower than it should be. I wrote an A* implementation in high school; I never applied it to a graph of more than a few dozen nodes as it was just a demo, but it finished in a few milliseconds then, and I can't believe it would scale so badly as to get up to 5 seconds for a mere 800 nodes.
wangzhonnew at October 18th, 2006 18:32 — #9
maybe i should use normal classes instead of using template and STL? is it going to improve the speed a bit? and i think checking whether a node is in the open list is another bottleneck:
for( openlist_result = m_OpenList.begin(); openlist_result != m_OpenList.end(); openlist_result ++ )
if( (*openlist_result)->m_UserState.IsSameState( (*successor)->m_UserState ) )
so when the openlist growing larger and larger this part will cost a lot of time for each successor.
maybe I should create 2 vector tables link to those nodes if they are in open and closed list, so that it only need to determine if the corresponding pointer is NULL or not NULL, and then compare the g and newg (if not NULL)
reedbeta at October 18th, 2006 21:42 — #10
You could also use a std::set for the open list instead of std::list or std::vector; that would give you logarithmic-time lookup instead of linear.
wangzhonnew at October 19th, 2006 10:52 — #11
this is a good point, but we need to create the heap in order to popup the shortest F in each search.. i'm woundering if std::set can do it.
btw, the cost for searching is creased like n\\^2, if the MAXSEARCHNODE=200, it return almost immediately after call, but for 800 it will be more than 5 sec....
i tried to implemented vector table last night but failed, coz we still need to get the node location in the list when we want to replace the node that already existed in list with a shorter path...if we use some pointers pointing to the location, we cannot also modify the pointer if the order of the list is changed (heapsort)
i guess it seems 2 tired A* is the only choice here, like what Jare said in previous post, we need to do it partially...