Splitting up A* pathing of many units into seperate game frames

Question

So my issues is that, for large groups of units, attempting to pathfind for all of them in the same frame is causing a pretty noticeable slow down. When pathing for 1 or 2 units the slow down is generally not noticeable but for many more than that, depending on the complexity of the path, it can get very slow.

While my A* could probably afford a bit of a tune up, I also know that another way to speed up the pathing is to just divy up the pathfinding over multiple game frames. Whats a good method to accomplish this?

I apologize if this is an obvious or easily searched question, I couldn't really think of how to put it into a searchable string of words.

More info: This is A* on a rectilinear grid, and programmed using C# and the XNA framework. I plan on having potentially up to 50-75 units in need of pathing.

Thanks.

Answer 1

Scalability

There's several ways of optimizing for this situation. For one, you may not have to split up into multiple game frames. To some extent it seems scalability is the issue. 100 units is at least 100 times more expensive than 1 unit.

So, how can we make pathing more optimized for scalability? Well, that does depend on your game design. I'm going to (perhaps wrongly) assume a typical RTS scenario. Several groups of units, with each group being relatively close in proximity. The pathing solution for many units in close proximity will be rather similar. The units could request pathing from some kind of pathing solver. This pathing solver could keep a table of recent pathing requests and their solutions and avoid calculating the same output from the same input multiple times. This is called memoization.

Another addition to this could involve making a hierarchy out of your grid or graph. Solve on the simpler graph first, then switch to a more detailed graph. Multiple units could use the same low-resolution path, taking advantage of memoization, but each calculate their own high-resolution path individually if the high-resolution paths are too numerous to reasonably memoize.

Multi-Frame Calculations

As for trying to split the calculations among frames, there are a few approaches I can think of off hand.

If you want to take the multi-threaded route, you could use a worker-thread-pooling model. Each time a unit requests a path, it is queued for a solution. When a worker-thread is free, it is assigned a task to solve. When the thread solves the task, you could either have a callback to inform the unit or you could have the unit query if the task is complete in some manner, most likely queried each frame.

If there are no dynamic obstacles or they are handled separately, you can have a constant state that the path solver uses. If not, then there will be a non-negligible amount of complexity and perhaps even overheard with having these threads lock mutable game state information. Paths could be rendered invalid from one frame to the next and require re-validation each frame. Multi-threading may end up being a pointless extra-overhead where, due to locking and synchronization, threads rarely run parallel. It's just a possibility.

Alternatively, you could design your path finding algorithms to run in discrete steps. After n number of steps, check the amount of time elapsed since the start of the algorithm. If it exceeds a certain amount of time, the pathing algorithm saves its progress and returns. The calling code could then check if the algorithm completed or not. On the next frame, resume the pathing algorithm from where it was. Repeat until solved.

Even with the single-threaded, voluntary approach to solving paths, if changes in game state affect the validity of a paths from frame to frame, you're going to run into having to re-validate current solutions on a frame to frame basis.

Use Partial Solutions

With either of the above approaches, you could run into the issue of units commanded to go somewhere idling for multiple frames before having a complete pathing solution. This may be acceptable and practically undetectable under typical circumstances. If it isn't, you could attempt to use the incomplete solution as is. If each incomplete solution differs too greatly, units will behave rather indecisively however. In practice, this "indecisiveness" may also not happen often enough to cause concern.