informa
/
Programming
Features

Toward More Realistic Pathfinding

Few things will jar players out of their immersion in a game faster than sloppy-looking AI. While sufficient CPU cycles are increasingly available to help craft better AI/player interaction, relatively few advancements have been made in recent years in game pathfinding. Pinter walks you through some modifications to the A* algorithm that can refine the movements of your game's units.

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:

  1. 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).
  2. 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.)

 


A Faster Implementation of the Standard A*

Before proceeding with turning and smoothing modifications to the A* algorithm, let's start with some basic optimizations that can speed up the standard A* algorithm by a factor of 40 or more. To start with, the standard A* algorithm uses a sorted linked list (or two linked lists) to track nodes that are checked. Instead, we'll use a 60x60 fixed matrix. When starting a search from point a to point b, we find the midpoint between those two and place it at point [30,30] on our matrix. Each point on the matrix stores:

  • The cost to get to the point
  • The total cost through that point to the goal
  • The [x,y] location of its "parent" tile (the tile before it on the path)
  • A Boolean stating whether or not it is on the "Open" list of actively pursued nodes, and
  • The [x,y] locations of the Previous and Next nodes in the Open list.

We also keep a separate array of 1-bit Booleans, which store whether or not each node in our matrix has been touched yet during this search. That way, we can very rapidly initialize at the beginning of the search without needing to clear the entire matrix.

Whereas the original algorithm maintains a separate sorted Open list (actually a Priority Queue), we instead maintain basic list functionality simply by using Previous and Next pointers within the fixed array. Note that we do have the memory requirement for our 60x60 matrix, but our compacted data structure requires only 16 bytes per node, for a total of 57K. (Even expanding the matrix to 120x120 will only require 230K of memory.)

Note additionally that the "list" can be implemented as a binary tree (by having two Next node pointers at each element), but we've actually found it to be substantially faster to have a simple (non-priority) list. While this does result in time O(n) for the search for the lowest cost node at the top of the A* loop (rather than O(log n) for a priority queue), it excels in that all insertions and deletions, of which there are many, are only O(1). Best of all, it eliminates the inner loop search that checks if neighboring nodes yet exist on the Open or Closed lists, which otherwise would take O(n) (or maybe a bit better if a hash table is used).

Overall, by avoiding all memory allocations and list insertions, this method turns out to be dramatically faster. I have profiled it to be as much as 40 times faster than standard A* implementations.

Note that for the Directional search described later in this article, eight times the number of nodes are necessary, so the memory requirement will all increase by a factor of eight.

Smoothing the A* Path

The first and most basic step in making an A* path more realistic is getting rid of the zigzag effect it produces, which you can see in Figure 2a. This effect is caused by the fact that the standard A* algorithm searches the eight tiles surrounding a tile, and then proceeds to the next tile. This is fine in primitive games where units simply hop from tile to tile, but is unacceptable for the smooth movement required in most games today.

FIGURE 2. The common zigzag effect of the standard A* algorithm (a); a modification with fewer, but still fairly dramatic, turns (b); and the most direct -- and hence desired -- route (c). To achieve the path shown in Figure 2c, the four waypoints shown in red in Figure 2a were eliminated.

One simple method of reducing the number of turns is to make the following modification to the A* algorithm: Add a cost penalty each time a turn is taken. This will favor paths which are the same distance, but take fewer turns, as shown in Figure 2b. Unfortunately, this simplistic solution is not very effective, because all turns are still at 45-degree angles, which causes the movement to continue to look rather unrealistic. In addition, the 45-degree-angle turns often cause paths to be much longer than they have to be. Finally, this solution may add significantly to the time required to perform the A* algorithm.

The actual desired path is that shown in Figure 2c, which takes the most direct route, regardless of the angle. In order to achieve this effect, we introduce a simple smoothing algorithm which takes place after the standard A* algorithm has completed its path. The algorithm makes use of a function Walkable(pointA, pointB), which samples points along a line from point A to point B at a certain granularity (typically we use one-fifth of a tile width), checking at each point whether the unit overlaps any neighboring blocked tile. (Using the width of the unit, it checks the four points in a diamond pattern around the unit's center.) The function returns true if it encounters no blocked tiles and false otherwise. See Figure 3 for an illustration, and Listing 1 for pseudocode.

LISTING 1. Pseudocode for the simple smoothing algorithm. The smoothing algorithm simply checks from waypoint to waypoint along the path, trying to eliminate intermediate waypoints when possible.

checkPoint = starting point of path
currentPoint = next point in path
while (currentPoint->next != NULL)
if Walkable(checkPoint, currentPoint->next)
// Make a straight path between those points:
temp = currentPoint
currentPoint = currentPoint->next
delete temp from the path
else
checkPoint = currentPoint
currentPoint = currentPoint->next

FIGURE 3. Illustration of the Walkable() function which checks for path collisions.

The smoothing algorithm simply checks from waypoint to waypoint along the path, trying to eliminate intermediate waypoints when possible. To achieve the path shown in Figure 2c, the four waypoints shown in red in Figure 2a were eliminated.

Since the standard A* algorithm searches the surrounding eight tiles at every node, there are times when it returns a path which is impossible, as shown with the green path in Figure 4. In these cases, the smoothing algorithm presented above will smooth the portions it can (shown in purple), and leave the "impossible" sections as is.

This simple smoothing algorithm is similar to "line of sight" smoothing, in which all waypoints are progressively skipped until the last one that can be "seen" from the current position. However, the algorithm presented here is more accurate, because it adds collision detection based on the width of the character and also can be used easily in conjunction with the realistic turning methods described in the next section.

FIGURE 4. This smoothing algorithm will leave impossible paths alone.

Note that the simple smoothing algorithm presented above, like other simple smoothing methods, is less effective with large units and with certain configurations of blocking objects. A more sophisticated smoothing pass will be presented later.


Adding Realistic Turns

The next step is to add realistic curved turns for our units, so that they don't appear to change direction abruptly every time they need to turn. A simple solution involves using a spline to smooth the abrupt corners into turns. While this solves some of the aesthetic concerns, it still results in physically very unrealistic movement for most units. For example, it might change an abrupt cornering of a tank into a tight curve, but the curved turn would still be much tighter than the tank could actually perform.

For a better solution, the first thing we need to know is the turning radius for our unit. Turning radius is a fairly simple concept: if you're in a big parking lot in your car, and turn the wheel to the left as far as it will go and proceed to drive in a circle, the radius of that circle is your turning radius. The turning radius of a Volkswagen Beetle will be substantially smaller than that of a big SUV, and the turning radius of a person will be substantially less than that of a large, lumbering bear.

Let's say you're at some point (origin) and pointed in a certain direction, and you need to get to some other point (destination), as illustrated in Figure 5. The shortest path is found either by turning left as far as you can, going in a circle until you are directly pointed at the destination, and then proceeding forward, or by turning right and doing the same thing.

FIGURE 5. Determining the shortest path from the origin to the destination.

In Figure 5 the shortest route is clearly the green line at the bottom. This path turns out to be fairly straightforward to calculate due to some geometric relationships, illustrated in Figure 6.

FIGURE 6. Calculating the length of the path.

First we calculate the location of point P, which is the center of our turning circle, and is always radius r away from the starting point. If we are turning right from our initial direction, that means P is at an angle of (initial_direction - 90) from the origin, so:

angleToP = initial_direction - 90
P.x = Origin.x + r * cos(angleToP)
P.y = Origin.y + r * sin(angleToP)

Now that we know the location of the center point P, we can calculate the distance from P to the destination, shown as h on the diagram:

dx = Destination.x - P.x
dy = Destination.y - P.y
h = sqrt(dx*dx + dy*dy)

At this point we also want to check that the destination is not within the circle, because if it were, we could never reach it:

if (h < r)
return false

Now we can calculate the length of segment d, since we already know the lengths of the other two sides of the right triangle, namely h and r. We can also determine angle from the right-triangle relationship:

d = sqrt(h*h - r*r)
theta = arccos(r / h)

Finally, to figure out the point Q at which to leave the circle and start on the straight line, we need to know the total angle + , and is easily determined as the angle from P to the destination:

phi = arctan(dy / dx) [offset to the correct quadrant]
Q.x = P.x + r * cos(phi + theta)
Q.y = P.y + r * sin(phi + theta)

The above calculations represent the right-turning path. The left-hand path can be calculated in exactly the same way, except that we add 90 to initial_direction for calculating angleToP, and later we use - instead of + . After calculating both, we simply see which path is shorter and use that one.

In our implementation of this algorithm and the ones that follow, we utilize a data structure which stores up to four distinct "line segments," each one being either straight or curved. For the curved paths described here, there are only two segments used: an arc followed by a straight line. The data structure contains members which specify whether the segment is an arc or a straight line, the length of the segment, and its starting position. If the segment is a straight line, the data structure also specifies the angle; for arcs, it specifies the center of the circle, the starting angle on the circle, and the total radians covered by the arc.

Once we have calculated the curved path necessary to get between two points, we can easily calculate our position and direction at any given instant in time, as shown in Listing 2.

LISTING 2. Calculating the position and orientation at a particular time.

distance = unit_speed * elapsed_time
loop i = 0 to 3:
if (distance < LineSegment[i].length)
// Unit is somewhere on this line segment
if LineSegment[i] is an arc
determine current angle on arc (theta) by adding or
subtracting (distance / r) to the starting angle
depending on whether turning to the left or right
position.x = LineSegment[i].center.x + r*cos(theta)
position.y = LineSegment[i].center.y + r*sin(theta)
determine current direction (direction) by adding or
subtracting 90 to theta, depending on left/right
else
position.x = LineSegment[i].start.x
+ distance * cos(LineSegment[i].line_angle)
position.y = LineSegment[i].start.y
+ distance * sin(LineSegment[i].line_angle)
direction = theta
break out of loop
else
distance = distance - LineSegment[i].length

Legal Turns: The Basic Methods

So now that we know how to find and follow an efficient curved line between two points, how do we use this in our pathing? The methods discussed in this section are all postprocessing techniques. In other words, they involve using the standard A* algorithm during initial pathfinding, and then adding curved turns later in some fashion, either in an extended pathfinding or during actual unit movement.

FIGURE 7. Decreasing the turning radius (a), and making a three-point turn (b).

  1. Simple solution: ignoring blocked tiles. We start with the simplest solution. First use the A* algorithm to calculate the path. Then progress from point to point in the path as follows: At any waypoint, a unit has a position, an orientation, and a destination waypoint. Using the algorithm described in the preceding section, we can calculate the fastest curved path to get from the current waypoint to the next waypoint. We don't care what direction we are facing when we reach the destination waypoint, though that will turn out to be the starting orientation for the following waypoint. If we skim some obstacles along the way, so be it -- this is a fast approximation, and we are willing to overlook such things. Figure 1c shows the result of this method. The curves are nice, but on both turns, the side of the ship will overlap a blocking tile.

This solution is actually

Latest Jobs

Sucker Punch Productions

Bellevue, Washington
08.27.21
Combat Designer

Xbox Graphics

Redmond, Washington
08.27.21
Senior Software Engineer: GPU Compilers

Insomniac Games

Burbank, California
08.27.21
Systems Designer

Deep Silver Volition

Champaign, Illinois
08.27.21
Senior Environment Artist
More Jobs   

CONNECT WITH US

Register for a
Subscribe to
Follow us

Game Developer Account

Game Developer Newsletter

@gamedevdotcom

Register for a

Game Developer Account

Gain full access to resources (events, white paper, webinars, reports, etc)
Single sign-on to all Informa products

Register
Subscribe to

Game Developer Newsletter

Get daily Game Developer top stories every morning straight into your inbox

Subscribe
Follow us

@gamedevdotcom

Follow us @gamedevdotcom to stay up-to-date with the latest news & insider information about events & more