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: