Pathfinding
is a core component of most games today. Characters, animals, and vehicles
all move in some goal-directed manner, and the program must be able
to identify a good path from an origin to a goal, which both avoids
obstacles and is the most efficient way of getting to the destination.
The best-known algorithm for achieving this is the A* search (pronounced
"A star"), and it is typical for a lead programmer on a project
simply to say, "We'll use A* for pathfinding." However, AI
programmers have found again and again that the basic A* algorithm can
be woefully inadequate for achieving the kind of realistic movement
they require in their games.
This article
focuses on several techniques for achieving more realistic looking results
from pathfinding. Many of the techniques discussed here were used in
the development of Activision's upcoming Big Game Hunter 5, which
made for startlingly more realistic and visually interesting movement
for the various animals in the game. The focal topics presented here
include:
Achieving
smooth straight-line movement. Figure 1a shows the result of a
standard A* search, which produces an unfortunate "zigzag"
effect. This article presents postprocessing solutions for smoothing
the path, as shown in Figure 1b.
Adding
smooth turns. Turning in a curved manner, rather than making abrupt
changes of direction, is critical to creating realistic movement.
Using some basic trigonometry, we can make turns occur smoothly over
a turning radius, as shown in Figure 1c. Programmers typically use
the standard A* algorithm and then use one of several hacks or cheats
to create a smooth turn. Several of these techniques will be described.
Achieving
legal turns. Finally, I will discuss a new formal technique which
modifies the A* algorithm so that the turning radius is part of the
actual search. This results in guaranteed "legal" turns
for the whole path, as shown in Figure 1d.
FIGURE 1. Some of the techniques discussed in this article. (a)
is the result of a standard A* search, while (b) shows the results
of a postprocess smoothing operation. (c) shows the application
of a turning radius for curved turns. (d) illustrates an A* modification
that will enable searches to include curved turns that avoid collisions.
Dealing
with realistic turns is an important and timely AI topic. In the August
2000 issue of Game Developer ("The
Future of Game AI"), author Dave Pottinger states, "So
far, no one has proffered a simple solution for pathing in true 3D while
taking into account such things as turn radius and other movement restrictions,"
and goes on to describe some of the "fakes" that are commonly
done. Also, in a recent interview on Feedmag.com with Will Wright, creator
of The Sims, Wright describes movement of The Sims' characters:
"They might have to turn around and they kind of get cornered --
they actually have to calculate how quickly they can turn that angle.
Then they actually calculate the angle of displacement from step to
step. Most people don't realize how complex this stuff is..."
In addition
to the above points, I will also cover some important optimization techniques,
as well as some other path-related topics such as speed restrictions,
realistic people movement, and movement along roads. After presenting
the various techniques below, we'll see by the end that there is no
true "best approach," and that the method you choose will
depend on the specific nature of your game, its characters, available
CPU cycles and other factors.
Note that
in the world of pathfinding, the term "unit" is used to represent
any on-screen mobile element, whether it's a player character, animal,
monster, ship, vehicle, infantry unit, and so on. Note also that while
the body of this article presents examples based on tile-based searching,
most of the techniques presented here are equally applicable to other
types of world division, such as convex polygons and 3D navigation meshes.
A Brief Introduction
to A*
The A*
algorithm is a venerable technique which was originally applied to various
mathematical problems and was adapted to pathfinding during the early
years of artificial intelligence research. The basic algorithm, when
applied to a grid-based pathfinding problem, is as follows: Start at
the initial position (node) and place it on the Open list, along with
its estimated cost to the destination, which is determined by a heuristic.
The heuristic is often just the geometric distance between two nodes.
Then perform the following loop while the Open list is nonempty:
Pop
the node off the Open list that has the lowest estimated cost to the
destination.
If
the node is the destination, we've successfully finished (quit).
Examine
the node's eight neighboring nodes.
For
each of the nodes which are not blocked, calculate the estimated cost
to the goal of the path that goes through that node. (This is the
actual cost to reach that node from the origin, plus the heuristic
cost to the destination.)
Push
all those nonblocked surrounding nodes onto the Open list, and repeat
loop.
In the
end, the nodes along the chosen path, including the starting and ending
position, are called the waypoints. The A* algorithm is guaranteed to
find the best path from the origin to the destination, if one exists.
A more detailed introduction to A* is presented in Bryan Stout's Game
Developer article "Smart
Moves: Intelligent Pathfinding" (October/November 1996), which
is also available on Gamasutra.com.
Hierarchical
Pathfinding
Critical
to any discussion of efficient pathfinding within a game is the notion
of hierarchical maps. To perform an efficient A* search, it is important
that the origin and destination nodes of any particular search are not
too far apart, or the search time will become enormous. I recommend
that the distance between origin and destination be constrained to 40
tiles, and that the total search space be no more than 60x60 tiles (creating
a 10-tile-wide buffer behind both origin and destination, allowing the
path to wrap around large obstacles.) If units need to search for more
distant destinations, some method of hierarchical pathfinding should
be used.
In the
real world, people do not formulate precise path plans which stretch
on for miles. Rather, if a person has some domain knowledge of the intermediate
terrain, they will subdivide the path, i.e. "first get to the highway
on-ramp, then travel to the exit for the mall, then drive to the parking
lot." Alternatively, if a person has no domain knowledge, they
will create intermediate points as they see them. For example, if you
wanted to eventually reach some point you knew was far to the North,
you would first look North and pick a point you could see, plan a path
toward it, and only when you got there, you would pick your next point.
Within
a game program, the techniques for creating a map hierarchy include:
Subdivide
the line to the destination into midpoints, each of which is then
used as a subdestination. Unfortunately, this always leaves the possibility
that a chosen midpoint will be at an impossible location, which can
eliminate the ability to find a valid path (see the "Path Failure"
section later in this article).
Preprocess
the map into a large number of regions, for example castles, clearings,
hills, and so on. This can be done by an artist/designer, or even
automated if maps are random. Then start by finding a path on the
"region map" to get from the current position to the destination
region, and then find a tile-based path on the detailed map to get
to the next region. Alternatively, if a unit has no region knowledge
and you want to be completely realistic with its behavior, it can
just choose the next region which lies in the compass direction of
its ultimate destination. (Though again, this can result in path failure.)
Printer-Friendly Version
