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