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