Toward More Realistic Pathfinding

A Better Smoothing Pass

The smoothing algorithm given earlier is less than ideal when used by itself. There are two reasons for this. Figure 17 demonstrates the first problem. The algorithm stops at point q and looks ahead to see how many nodes it can skip while still conducting a legal move. It makes it to point r, but fails to allow a move from q to s because of the blocker near q. Therefore it simply starts again at r and skips to the destination. What we'd really like to see is a change of direction at p, which cuts diagonally to the final destination, as shown with the dashed line.

FIGURE 17. One shortcoming of the simple smoothing algorithm.

The second problem exhibits itself only when we have created a path using the simple (non-directional) method, and is demonstrated by the green line in Figure 18. The algorithm moves forward linearly, keeping the direction of the ship pointing straight up, and stops at point p. Looking ahead to the next point (q), it sees that the turning radius makes the turn impossible. The smoothing algorithm then proceeds to "cheat" and simply allow the turn. However, had it approached p from a diagonal, it could have made the turn legally as evidenced by the blue line.

To fix these problems, we introduce a new pre-smoothing pass that will be executed after the A* search process, but prior to the simple smoothing algorithm described earlier. This pass is actually a very fast version of our Directional-48 algorithm, with the difference that we only allow nodes to move along the path we previously found in the A* search, but we consider the neighbors of any node to be those waypoints which were one, two, or three tiles ahead in the original path. We also modify the cost heuristic to favor the direction of the original path (as opposed to the direction toward the goal). The algorithm will automatically search through various orientations at each waypoint, and various combinations of hopping in two- or three-tile steps, to find the best way to reach the goal.

FIGURE 18. Another shortcoming: the simple smoothing algorithm is unable to find and execute a turn within the legal turning radius.

Because this algorithm sticks to tiles along the previous path, it runs fairly quickly, while also allowing us to gain many of the benefits of a Directional-48 search. For example, it will find the legal blue line path shown in Figure 18. Of course it is not perfect, as it still will not find paths that are only visible to a full Directional-48 search, as seen in Figure 19.

The original, nondirectional search finds the green path, which executes illegal turns. There are no legal ways to perform those turns while still staying on the path. The only way to arrive at the destination legally is via a completely different path, as shown with the blue line. This pre-smoothing algorithm cannot find that path: it can only be found using a true Directional search, or by one of the hybrid methods described later. So the pre-smoothing algorithm fails under this condition. Under such a failure condition, and especially when the illegal move occurs near the destination, the pre-smoothing algorithm may require far more computation time than we desire, because it will search back through every combination of directional nodes along the entire path. To help alleviate this and improve performance, we add an additional feature such that once the pre-smoothing algorithm has reached any point p along the path, if it ever searches back to a point that is six or more points prior to p in the path, it will fail automatically.

FIGURE 19. The blue line shows the only truly legal path, which the pre-smoothing algorithm can't find, but the Directional search can.

Path Failure and Timeslicing

Depending on the pathfinding method chosen, it is possible for failure to be reported either when there is truly no possible path, or when the chosen solution simply has not found the path (which is more likely to occur when utilizing fast, informal methods.) What to do in the case of failure is entirely dependent on the specifics of the game. Typically, it simply means that the current goal -- a food source, ammunition depot, or enemy base -- is not attainable from the current position, and the unit must choose a different goal. However, it is possible that in certain circumstances we know the goal is achievable, and it is important to find it for gameplay. In these cases we might have started with a faster search method, but if that fails, we can proceed from scratch with a slower, methodical search, such as the standard Directional-24.

The key problem is that A* and its derivative methods of pathfinding perform very poorly if pathfinding fails. To alleviate this problem, it is important to minimize failures. This can be done by dividing up the map into small regions in advance (let's say 1,000 total), and precomputing whether it's possible, given two regions ra and rb, to get from some tile in ra to some tile in rb. We need only one bit to store this, so in our example this uses a 128K table. Then before executing any pathfind, we first check the table. If travel between the regions is impossible, we immediately report failure. Otherwise, it is probably possible to get from our specific source tile to our specific destination tile, so we proceed with the pathfinding algorithm.

In the next section, I'll discuss the time performance for the different algorithms presented here, and how to mix and match techniques to achieve faster times. Note that it is possible to timeslice the search algorithm so that it can be interrupted and restarted several times, and thereby take place over a number of frames, in order to minimize overall performance degradation due to a slow search. The optimized algorithm presented earlier uses a fixed matrix to keep track of the intermediate results of a search, so unfortunately this means that any other units requiring a pathfinding search during that time will be "starved" until the previous pathing is complete. To help alleviate this, we can instead allocate two matrices, one for the occasional slow search that takes several timesliced frames and the other for interspersed fast searches. Only the slow searches, then, will need to pause (very briefly) to complete. In fact, it is actually quite reasonable that a unit "stop and think" for a moment to figure out a particularly difficult path.

Performance and Hybrid Solutions

In this section, I'll discuss performance of many of the techniques presented earlier and how to utilize that knowledge to choose the best algorithms for a particular application.
The major observation testing the various techniques presented here was that the performance of the Directional algorithm is slow, probably too slow for many applications. Perhaps most units in a particular game can utilize the simple A* algorithm with smoothing passes, while a particular few large units could utilize a Directional algorithm. (It is nice to note, however, that only a few years ago, system performance would have prohibited implementation of anything but the simplest A* algorithm, and perhaps a few years from now, the performance issues discussed here will not be significant.)

FIGURE 20 (a, b and c from top to bottom) The (fast) hybrid Directional A* pathfinding technique.

Knowing the performance limitations, there are also hybrid solutions that can be devised which are often as fast as a simple A* algorithm (with smoothing), but also utilize some of the power of a formal Directional search. One excellent such solution, which is incorporated into the sample program provided, is presented below. (Note that this particular solution will not be useful if a unit is greater than one tile wide.)

  1. Start by performing a simple A* search, only searching the surrounding four tiles at every node. If this search fails, report failure. (The result of such a search is illustrated in Figure 20a.)
  2. Perform the Smoothing-48 pass. If it is successful, skip to (6). Otherwise, check the search matrix to see what was the farthest node hit, and continue to (3). (This step is illustrated by the brown path in Figure 20b.)
  3. Perform another Smoothing-48 pass, this time starting from the destination and working backward. This one will also fail, so check the search matrix to see the farthest node hit. (This step is illustrated by the green path in Figure 20b.)
  4. Look at the failure points from both smoothing passes (points a and b in the figure.) This is the section that needs to be searched for an alternate route. If the points are more than 12 tiles distant in the X or Y directions, report failure immediately. Otherwise, step away one tile at a time in each smoothing list (the one starting from the origin and the one starting from the destination) until the points are approximately (but not more than) 12 tiles distant from one another. (Note that this step is not performed in Figure 20.)
  5. Perform the Directional-8 algorithm between the two points determined above. If the search fails, report failure. (This step is illustrated by the blue line in Figure 20b.) Otherwise, attach the three path segments found and proceed to (6).
  6. Perform the final (simple) smoothing algorithm on the resultant path. (The resultant path is shown in Figure 20c.)

For most searches (99 percent in some applications, less in others, depending on the terrain layout), this hybrid solution will run exactly as fast as a simple A* algorithm with Smoothing-48 and simple smoothing. In the other rare cases, it will require the additional time necessary to do a (difficult) Directional-8 search on points which are 12 tiles apart. As discussed earlier, those cases can be timesliced over multiple frames.

Note that the circuitous route required for the path in Figure 20 is somewhat complex, and the search required around 200ms when tested. Figure 21a shows a simpler version that only required 85ms. Finally, by simply adding one blocking tile, as shown in Figure 21b, the time is reduced to under 6ms, because the initial A* search was able to find a valid route and was not "misled" into an impossible section of terrain.

Speed and Other Movement Restrictions

In this article I've focused primarily on turning radius as the main movement restriction and how to deal with it. There are in fact other movement restrictions that are handled by the A* algorithm, either automatically or in conjunction with the methods described here.

FIGURE 21. Faster hybrid paths.

The standard A* algorithm allows for tiles to have a variety of costs. For example, movement on sand is much more "expensive" than movement over pavement, so the algorithm will favor paths on pavement even if the total distance may be longer. This type of terrain costing is fully supported by the Directional A* algorithm and other techniques listed here.

Speed restrictions are a trickier issue. For the map in Figure 22, the algorithms presented here will choose the green path, because it has the shortest distance. However, for a vehicle with slow acceleration/deceleration times, the blue path would be faster, because it only requires two turns instead of eight, and has long stretches for going at high speeds.

The formal way to attack this problem would be to add yet another dimension to the search space. For the Directional algorithm, we added current direction as a third dimension. We could theoretically add current speed as a fourth dimension (rounding to a total of eight or 10 approximate speeds.) When moving from one node to another, we would have to check whether the increase or decrease in speed would be possible given the vehicle's acceleration or braking capability, and any turning which is in progress. Of course, this increases the search space dramatically and will hurt performance quite a bit.

The simplest way of incorporating speed as a factor, though not the most precise, is simply to modify the costs in the Directional search so that any turns are "charged" extra. This will penalize turning, due to the reductions in speed necessary to make turns. Unfortunately, this is only effective in Directional-24 or Directional-48 searches. A Directional-8 search yields lots of extraneous turns which are later dealt with by the smoothing pass, but since the penalties proposed here would occur during the main search phase, the accuracy could suffer quite a bit.

FIGURE 22. Illustration of the speed restriction problem.

People Movement and Friendly-Collision Avoidance

Fluid turning radius. The tables used to optimize the Directional algorithms, discussed earlier, are based on a fixed turning radius and unit size. In the sample program provided, if the turning radius or unit size is changed, the tables are recalculated. However, as mentioned earlier in the "Basic Methods" section, some units may have a more fluid turning radius that depends on their speed or other factors. This is especially true of "people" units, which can easily slow down to make a tighter turn.

Resolving a path under these circumstances can become increasingly complex. In addition to the requirement for much more memory for tables (covering a range of turning radii), a formal search algorithm would in fact need to track an additional speed dimension, and factor acceleration into account when determining on-the-fly turning ability and resultant speed.

Instead, it is much simpler and more efficient to either:

  1. Do a standard A* search and subsequently apply decelerations as appropriate before turns, as described in "Basic Methods" section, or;
  2. Set a very tight turning radius and do a Directional search while penalizing significantly for turns. This will have the result of favoring solutions that don't require overly tight turns, but still allowing such solutions.

Friendly-collision avoidance. Units which are friendly to one another typically need some method of avoiding collisions and continuing toward a goal destination. One effective method is as follows: Every half-second or so, make a quick map of which tiles each unit would hit over the next two seconds if they continued on their current course. Each unit then "looks" to see whether it will collide with any other unit. If so, it immediately begins decelerating, and plans a new route that avoids the problem tile. (It can start accelerating again once the paths no longer cross.) Ideally, all units will favor movement to the right side, so that units facing each other won't keep hopping back to the left and right (as we often do in life). Still, units may come close to colliding and need to be smart enough to stop, yield to the right, back up a step if there's not enough room to pass, and so on.

Final Notes

This article has made some simplifying assumptions to help describe the search methods presented. First, all searches shown have been in 2D space. Most games still use 2D searches, since the third dimension is often inaccessible to characters, or may be a slight variation (such as jumping) that would not affect the search. All examples used here have also utilized simple grid partitioning, though many games use more sophisticated 2D world partitioning such as quadtrees or convex polygons. Some games definitely do require a true search of 3D space. This can be accomplished in a fairly straightforward manner by adding height as another dimension to the search, though that typically makes the search space grow impossibly large. More efficient 3D world partitioning techniques exist, such as navigation meshes. Regardless of the partitioning method used, though, the pathfinding and smoothing techniques presented here can be applied with some minor modifications.

The algorithms presented in this article are only partially optimized. They can potentially be sped up further through various techniques. There is the possibility of more and better use of tables, perhaps even eliminating trigonometric functions and replacing them with lookups. Also, the majority of time spent in the Directional algorithm is in the inner loop which checks for blocking tiles which may have been hit. An optimization of that section of code could potentially double the performance. Finally, the heuristics used in the Directional algorithm and the Smoothing-48 pass could potentially be revised to find solutions substantially faster, or at least tweaked for specific games.

Pathfinding is a complex problem which requires further study and refinement. Clearly not all questions are adequately resolved. One critical issue at the moment is performance. I am confident that some readers will find faster implementations of the techniques presented here, and probably faster techniques as well. I look forward to this growth in the field.

For More Information

Game Developer

Pottinger, Dave C. "Coordinated Unit Movement" (January 1999).
http://www.gamasutra.com/%20features/19990122/movement_01.htm

Pottinger, Dave C. "Implementing Coordinated Movement" (February 1999).
http://www.gamasutra.com/features/19990129/implementing_01.htm

Pottinger, Dave C. "The Future of Game AI" (August 2000).
http://www.gamasutra.com/features/20001108/laird_01.htm

Stout, W. Bryan. "Smart Moves: Intelligent Pathfinding" (October/November 1996).
http://www.gamasutra.com/features/19970801/pathfinding.htm

Web sites

Steven Woodcock's Game AI Page
http://www.gameai.com/

Books

Game Programming Gems (Charles River Media, 2000)
Refer to chapters 3.3, 3.4, 3.5, and 3.6.

Discuss this article in Gamasutra's discussion forum

________________________________________________________

Introduction