Toward More Realistic Pathfinding
March 14, 2001 Page 5 of 7
The modified heuristic. Our modified A* algorithm will also need a modified heuristic (to estimate the cost from an intermediate node to the goal). The original A* heuristic typically just measures a straightline distance from the current position to the goal position. If we used this, we would end up equally weighing every compass direction at a given location, which would make the search take substantially longer in most cases. Instead, we want to favor angles that point toward the goal, while also taking turning radius into account. To do this, we change the heuristic to be the distance of the shortest curve from the current location and angle to the destination location, as calculated in the "Adding Realistic Turns" section earlier.
To avoid making this calculation each time, we set up a heuristic table in advance. The table contains heuristic values for any destination tile within a 10tile distance (with a granularity of 1/64th tile), and at any angle relative to the current direction (with a granularity of eight angles.) Any destination tile beyond 10 tiles is computed with the 10tile value, plus the difference in actual distance, which turns out to be a very close approximation. The total data size of the table is thus 640 (distance) x 8 (directions) x 4 (bytes) = 20K. Since the table is dependent on the turn radius of the unit, if that turn radius changes, we need to recalculate the table.
Using a hitcheck table. The trigonometric calculations described above to determine the path from one node to another are not trivial and take some computational time. Pair this with the requirement of "walking" through the resultant path to see if any tiles are hit, and the fact that this whole process needs to be performed at every possible node combination in the search. The result is a total computation time that would be absurdly long. Instead, we use a special table which substantially reduces the computation time. For any given starting direction (8 total), ending direction (8 total), and ending position (up to 48, for a Directional48 search), the table stores a 121bit value. This value represents an 11x11 grid surrounding the origin, as seen in Figure 13.
FIGURE 13. Illustration of the hitcheck table. 
Any tiles that would be touched by a unit traveling between those nodes (other than the origin and destination tiles themselves) will be marked by a "1" in the appropriate bitfield, while all others will be "0." Then during the search algorithm itself, the table will simply be accessed, and any marked nodes will result in a check to see if the associated node in the real map is blocked or not. (A blocked node would then result in report of failure to travel between those nodes.) Note that the table is dependent on both the size and turn radius of the unit, so if those values change, the table will need to be recomputed.
Earlier, I mentioned how the very first position in a path may not be at the precise center location of a tile or at a precise compass direction. As a result, if we happen to be specifically checking neighbors of that first tile, the algorithm needs to do a full computation to determine the path, since the table would not be accurate.
Other options: backing up. Finally, if your units are able to move in reverse, this can easily be incorporated into the Directional A* algorithm to allow further flexibility in finding a suitable path. In addition to the eight forward directions, simply add an additional eight reverse directions. The algorithm will automatically utilize reverse in its path search. Typically units shouldn't be traveling in reverse half the time though, so you can also add a penalty to the distance and heuristic computations for traveling in reverse, which will "encourage" units to go in reverse only when necessary.
Correctness of Directional A*
The standard A* algorithm, if used in a strict tilebased world with no turning restrictions, and in a world where a unit must always be at the center of a tile, is guaranteed to find a solution if one exists. The Directional A* algorithm on the other hand, when used in a more realistic world with turning restrictions and nondiscrete positions, is not absolutely guaranteed to find a solution. There are a couple reasons for this.
Earlier we saw how the Directional8 algorithm could occasionally miss a valid path, and this was illustrated in Figure 12. The conclusion was to use a Directional24 search or even a Directional48 search. However, in very rare circumstances, the same problem could occur with a Directional48 search. We could extend even further to a Directional80 search, but at that point the computation time required would probably be too high.
The other problem is that the shortest legal curved path between two points, which we compute in our algorithm, is not the only legal curved path. For one thing, there are the four possible paths shown in Figure 9. Our algorithm simply picks the shortest and assumes that is the correct one. Yet possibly that one path may fail, while one of the other three may have succeeded. (Though when I tried to fabricate such a condition, it proved almost impossible. Another route was always found by the algorithm.) Furthermore, the four paths shown in that figure are not the only legal paths, either. There are theoretically an infinite number of paths that twist and turn in many different ways.
In practice, though, it is very rare for the Directional24 search to fail to find a valid path. And it is almost impossible for the Directional48 search to fail.
FixedAngle Character Art
Until now, the discussion has assumed that units can face any direction: 27 degrees, 29 degrees, 133 degrees, and so on. However, certain games which do not use realtime 3D art do not have this flexibility. A unit may be prerendered in only eight or 16 different angles. Fortunately, we can deal with this without too much trouble. In fact, the accompanying test program includes an option of 16angle fixed art, to illustrate the process.
The trivial way of dealing with the problem is to do all of the calculations assuming continuous angles, and then when rendering to the screen, simply round to the nearest legal direction (for example, a multiple of 22.5 degrees for 16angle art) and draw the appropriate frame. Unfortunately, this usually results in a visible "sliding" effect for the unit, which typically is unacceptable.
FIGURE 14. Turning with fixedangle character art. 
What we really want is a solution which can modify a continuous path, like the one shown at the bottom of Figure 14, and create a very similar path using just discrete lines, as shown in the top of the figure.
The solution involves two steps. First, for all arcs in the path, follow the original circle as closely as possible, but staying just outside of it. Second, for straight lines in the path, create the closest approximation using two line segments of legal angles. These are both illustrated in Figure 15. For the purposes of studying the figure, we have allowed only eight legal directions, though this can easily be extended to 16.
On the left, we see that we can divide the circle into 16 equivalent right triangles. Going one direction on the outside of the circle (for example, northeast) involves traversing the bases of two of these triangles. Each triangle has one leg which has the length of the radius, and the inside angle is simply /8 or 22.5 degrees. Thus the base of each triangle is simply:
base = r * tan(22.5)
We can then extrapolate any point on the original arc (for example, 51.2 degrees) onto the point where it hits one of the triangles we have just identified. Knowing these relationships, we can then calculate (with some additional work) the starting and ending point on the modified arc, and the total distance in between.
FIGURE 15. Geometry of fixedangle turning. 
For a straight line, we simply find the two lines of the closest legal angles, for example 0 degrees and 45 degrees, and determine where they touch. As shown in the figure, there are actually two such routes (one above the original line and another below), but in our sample program we always just pick one. Using basic slope and intercept relationships, we simply calculate intersection of the two lines to determine where to change direction.
Note that we still use the "line segment" storage method introduced earlier to store the modified path for fixed character art. In fact, this is why I said earlier we would need up to four line segments. The starting and ending arc remain one line segment each (and we determine the precise position of the unit on the modified "arc" while it is actually moving), but the initial straight line segment between the two arcs now becomes two distinct straight line segments.
The Road Problem
The approach we have taken thus far is to find the shortest curve possible between any two points in a path. So if a unit is headed due east to a point p (and thus is pointing east when it hits p), and then needs to go due north for five tiles to hit a point q, the unit will first need to turn left for approximately 105 degrees of its turning circle, and then head at an approximate direction of northnorthwest until it arrives at point q. Note that we could alternatively have defined the path to turn substantially further around the circle and then travel due north, but that would have been a longer path. See the vertical path portions of Figure 16 for an illustration.
A

B


FIGURE 16. (a) Standard cornering, and (b) Modified tight cornering for roads. 
At certain times, even though it is longer, the path in Figure 16b may be what is desired. This most often occurs when units are supposed to be traveling on roads. It simply is not realistic for a vehicle to drive diagonally across a road just to save a few feet in total distance.
There are a few ways of achieving this.

When on roads, make sure to do only a regular A* search or a Directional8 search, and do not apply any smoothing algorithm afterwards. This will force the unit to go to the adjacent tile. However, this will only work if the turning radius is small enough to allow such a tight turn. Otherwise, the algorithm will find an adjacent tile which is off the road.

Temporarily disallow movement to any offroad tile. This has the same constraints as the above method.

Same as (1), but for units that have too wide a turning radius to turn into an adjacent road tile, do a Directional24 or Directional48 search as appropriate. For example, the unit shown in Figure 16b apparently requires two tiles to make a 90degree turn, so a Directional24 search would be appropriate.

Determine the number of tiles needed for a turn (for example two tiles, as in the figure), and temporarily place blocking tiles adjacent to the road after that number of tiles has gone by, beyond every turn. These temporary blockers are in fact displayed in Figure 16b. This method is analogous to placing "cones" by the road.
Page 5 of 7