Hehe... sorry for luring you guys in here, but I'm wondering about some pathfinding stuff for RTS games. :) I have made a A*star (sort of slow) function. My nodes (waypoints) are not aligned in a grid, but they know their neighbour nodes and their costs. Since it's kinda slow to find a longer path (and a lot of units are selected) I'm thinking of limiting the search time for each pathfinding, so that every unit can maximum search for x amount of time per frame - how would you go about this? My initial idea was to simply do "if (nrofsearchednodes < 10) ContinueSearch" etc... but this would require that every unit that will use pathfinding has it's own Open and Closedlist, right? this will greatly increase the memory usage thou, so I'm wondering if it's doable...? but then again, I'd much rather use 200 units that can roam the lands without annoying stops in gameplay, than 2000 units and go get a cup of coffee everytime they should be going somewhere! :D

I have similar problems with my game. Whenever a bot wants to move and run the A* algorithm the game freezes a bit. This is very annoying.

I solved the problem using a queue, that collects all the pathfind queries posted by the bots. Only the top query is processed with a time limit per frame. When the query is completed the results are given to the bot and the query is removed from the queue. Since only one search is performed at a time you have to keep only one Open and Closed list.

The advantages of this approach:
- you can have plenty of pathfind queries and your game never hangs;
- the bots can change their query (eg. the destination) or cancel the query if it isn't processed yet.

Disadvantages:
- the A* implementation is a bit messy, because you have to keep the current state for the next call and you have to check periodically if you hit the time limit. This will cause the A* algorithm to run a bit slower.
- when the queue becomes pretty full the last added queries might wait a long time (maybe 1-2 seconds) before being processed, thus leaving the bot without the answer for some time. In my game the bots are not commanded by a human and it's not a problem if they go idle for a couple of seconds. In a RTS game, I agree, I want my units to move as soon as I give the destination. Maybe you can move the units along the direct line to destination while you are waiting for the pathfinder result.

Hope that helps.

Quote:

Original post by Rasmadrak Since it's kinda slow to find a longer path (and a lot of units are selected) I'm thinking of limiting the search time for each pathfinding, so that every unit can maximum search for x amount of time per frame - how would you go about this?

Firstly, you might want to check the other thread for some tips on optimising it for speed.

Quote:

My initial idea was to simply do "if (nrofsearchednodes < 10) ContinueSearch" etc... but this would require that every unit that will use pathfinding has it's own Open and Closedlist, right? this will greatly increase the memory usage thou, so I'm wondering if it's doable...?

Yes... it's doable. The list is likely to be pretty small compared to other data you store.

However, may I suggest that instead of having lots of units all calculate a part of a path each frame, why not have just a few units calculate an entire path each frame?

Quote:

Original post by Kylotan However, may I suggest that instead of having lots of units all calculate a part of a path each frame, why not have just a few units calculate an entire path each frame?

I tried this before, but if the path was long enough there would still be annoying freezes... so that's why I want to try to limit the time spent searching. :)


I think that the queue idea is something worth implementing.. I'll try this! thanks! :)
Maybe this is even easier for networking too, since only the processed path needs to be sent to the other players etc..

Another optimization for RTS engines might be to search the primary path per groups and have selected units try to follow this path together. This can be a big optimization if done correctly.

First of all, it is definitely worth optimizing. Read my response in the "A* optimisasions [sic]?" thread. I optimized my A* to be over 10,000 times as fast as my original basic implementation. I'm thinking of rewriting it and releasing it as a library in a few months. All you'd have to do is derive from my base finder class and then implement a few simple virtual functions like heuristic, cost, etc, and anyone can solve paths with what I believe to be a fast imeplentation :)

Secondly, a priority queue is a good way of having multiple units pathfind all at once without bogging down the system. Each unit gets a slice of time based on its "need." The higher the unit's need, the more time it gets. You'll want to base need on how long it's been in the queue, so that you don't have a unit going 10 minutes without ever figuring out a solution :) You might also have a need for a particular unit to finish extra fast, and this will accommodate that.

Last, here's a trick to allow your unit to move without appearing to wait 1-2 seconds for the path. Calculate a straight line to his goal in one frame, and start moving him there. Then calculate the A* path. Finally, have him move from wherever he is to the closest node he can walk a straight line to (so he doesn't backtrack to the first few nodes in the solution).

Hope this helps you :)

I wrote a program that uses connectivity matrices to do pathfinding. You don't have to calculate the entire path in order to know which next move to take. You can view a demo and paper that I wrote describing it here (I'm bobmcgee at cprog.com)

cprog