Toward More Realistic Pathfinding
March 14, 2001 Page 7 of 7
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.
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.
FIGURE 21. Faster hybrid paths.
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:
Do a standard A* search and subsequently apply decelerations as appropriate before turns, as described in "Basic Methods" section, or;
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.
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
Sample application and source
Game Developer magazine
Pottinger, Dave C. "Coordinated Unit Movement" (January 1999).
Pottinger, Dave C. "Implementing Coordinated Movement" (February 1999).
Pottinger, Dave C. "The Future of Game AI" (August 2000).
Stout, W. Bryan. "Smart Moves: Intelligent Pathfinding" (October/November 1996).
Steven Woodcock's Game AI Page
Game Programming Gems (Charles River Media, 2000)
Refer to chapters 3.3, 3.4, 3.5, and 3.6.
Page 7 of 7