implementing A* in game
Posted 16 October 2006 - 07:50 PM
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:
Posted 16 October 2006 - 08:00 PM
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.
Posted 16 October 2006 - 09:42 PM
Posted 17 October 2006 - 07:25 AM
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?
Posted 18 October 2006 - 05:45 PM
(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)
Posted 18 October 2006 - 06:05 PM
Posted 18 October 2006 - 07:14 PM
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.
Posted 18 October 2006 - 10:32 PM
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)
Posted 19 October 2006 - 02:52 PM
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...
1 user(s) are reading this topic
0 members, 1 guests, 0 anonymous users