Speed of precalculated paths vs. step-taking

The general impression of path-finding algorithms appears to be that they are significantly slower than step-taking approaches. Although calculating a long path is significantly more time consuming than taking a step, in a comparison we must instead look at a series of steps.

Predictable behavior vs. potential speed

Step-taking usually involves a constant amount of time per step taken, whereas path-finding involves an unknown amount of time per step taken, because it may be difficult to predict how many map spaces are going to be searched. It is a good idea to try your path-finder on some sample maps to get an idea of how much of the map is being searched. However, even if you tune the average case to be good (fast), the worst case scenario in a path-finder can be worse than a step-taker.

A step-taker's CPU usage is fairly easy to predict. This can be an advantage in many games, especially when timing is important. Although easy to predict, the time taken may be somewhat large, especially if sophisticated analysis is needed to determine what step to take. A step-taker usually recalculates information at each step: Unless the analysis is simple, the step-taker will have to analyze the neighboring area to determine where to move; at the next step, the analyzed area will overlap the area analyzed previously. A path-finder on the other hand can perform calculations once and use the results to analyze many steps. If the required analysis is complex, a path-finder may use less time overall than a step-taker.

Load spikes

One situation to take into account is in a game that allows the player to select multiple units and select a destination for all of them. With path-finding, there will be many paths to compute at the same time, so you will get a load spike, a short period of very high load (CPU usage). Handling movement step-by-step wouldn't produce a load spike, because the load is distributed over a long period of time.

One way to avoid the load spike is to delay path-finding. Units can be programmed to follow either their instincts (simple movement) or their brains (a precalculated path). Units will follow their instincts unless their brains tell them otherwise. (This approach is used in nature and also in insect-like robots at MIT labs.) Instead of calculating all the paths at once, limit the game to finding one path every one, two, or three game cycles. Then let the units start walking according to instinct (which could simply be moving in a straight line towards the goal), and come back later to find paths for them. This approach allows you to even out the cost of path-finding so that it doesn't occur all at once.

Waypoints

Step-takers take a similar amount of time no matter how long the path is. Path-finders however take more than twice as much time to find a path that is twice as long. Remember that path-finding is searching an area, and areas for a circle of diameter N grow in proportion to N^2. Also, the data structures used in A* (such as a heap) grow at rate N log N rather than simply N.

One way to reduce the growth is two split a long path into two shorter paths. You may ask the user to mark waypoints on the path: instead of simply clicking on a destination, ask the user to click on two or three points along the way to the destination. You now have three or four smaller paths to compute, and you save some time. The user also has some control over the overall path---for example, your path-finder may have found a path to the west of some mountains, but for safety's sake, the user wants to stay to the east of the mountains (near friendly guard towers).

The main change in unit movement code will be that instead of a single destination, you will have a list of destinations. Find a path to the first destination. Once you get there, remove it from the list and find a path to the next destination.

Path recalculation

Unfortunately, a path-finder cannot reuse the results of analysis indefinitely. After some time, the results may be invalidated by updates to the map. The step-taker can respond immediately to the changes, but a calculated path is not going to reflect the most recent map. For a path-finder, the path may have to be verified or recalculated periodically; this can be a disadvantage if paths are long or if path updates are frequent. For example, in a game that allows walls and other obstacles to be blown up, a path may not be valid for long. Also, if the path calculation took into account enemy positions, those would not be valid for long. On the other hand, if your path-finder does not take into account faraway enemy positions, and if the obstacles on the map are fairly static, the path is likely to be good for a longer period of time. The more often information used for movement changes, the more of an advantage step-taking has over path-finding.

Idle-time recalculation

To smooth out the varying CPU load that may occur with path-finding, the approach used to smooth out load spikes can be used with path recalculation. Paths can be calculated when the CPU load is low, and recalculation can be delayed if the CPU load is high. This puts idle cycles to good use, and avoids slowing down the game when there's a lot going on.

Redundancy in path-finding

Sometimes, the path found by a path-finder can be used more than once. This reduces the cost of path-finding, since you can amortize one search over several uses.

Networked games

Path-Finders produce a lot of information at the beginning, while step-takers produce a small amount of information at each step. For networked games, the path determined by the path-finder can be transmitted to the other machines on the network, so that the path need be calculated only once, rather than once per machine.

Multiple units


See Also: Putting paths together is called path splicing in another section of these notes.

If many units are in or near the same location, and have the same destination (or destinations close to each other), it is very likely that the path found for one will be useful for other units. One idea is to find a path P from the center of the units to the center of the destinations. Then, use most of that path for all the units, but replace the first 10 steps and the last 10 steps by paths that are found for each individual unit. Unit i will receive a path from its starting location to P[10], followed by the shared path P[10..len(P)-10], followed by a path from P[len(P)-10] to the destination.

The paths found for each unit are short (approximately 10 steps on average), and the long path is shared. Most of the path is found only once and shared among all the units. However, the user may not be impressed if he sees all the units moving on the same path. To improve the appearance of the system, make the units follow slightly different paths. One way to do this is to alter the paths themselves, by choosing adjacent locations.

Another approach is to make the units aware of each other (perhaps by picking a "leader" unit randomly, or by picking the one with the best sense of what's going on), and only find a path for the leader. Then use a flocking algorithm to make them move in a group.

Summary

Try your path-finder on sample maps to see how many spaces are searched in relation to how many steps are taken. Some algorithms, such as A* using a very high heuristic, lead to a constant amount of searching per step in common cases. Other algorithms, such as Dijkstra's, use a lot of searching per step. The results will depend on your algorithm, your heuristic, and your map characteristics, so run some experiments.

  1. If there is a lot of work that has to be done per step taken, a path-finder's CPU usage may be difficult to predict. A more predictable, although sometimes slower, step-taker may be a better choice. If there is a small amount of work per step, then a path-finder's cost can be predicted, and directly compared to a step-taker.
  2. Also, ask yourself how often map changes will affect a path. If such changes are common, path-finding will be more costly, and step-taking may be better. If such changes are rare, path-finding may be inexpensive relative to step-taking because analysis can be performed once and reused for the entire path.
  3. If varying CPU load is a problem, consider load balancing by allowing units to continue moving with less information, until CPU load decreases, and a path can be found for the unit.
  4. Re-using the path found by the path-finder decreases the cost of path-finding, so look for ways to save and reuse the paths.

Last modified: Sun Nov 18 11:32:17 2001
From Amit's Game Programming Site
Copyright (C) 2000, Amit J. Patel