Toward More Realistic Pathfinding
March 14, 2001 Page 1 of 7
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.
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.)
Page 1 of 7