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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
- 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.
- 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.
- 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.
- 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.