Toward More Realistic Pathfinding

Directional Curved Paths

In order to implement the Directional A* algorithm, it is necessary to figure out how to compute the shortest path from a point p to a point q, taking into account not only starting direction, orientation, and turning radius, but also the ending direction. This algorithm will allow us to compute the shortest legal method of getting from a current position and orientation on the map to the next waypoint, and also to be facing a certain direction upon arriving there.

Earlier we saw how to compute the shortest path given just a starting orientation and turning radius. Adding a fixed final orientation makes the process a bit more challenging.

FIGURE 9. Arriving at the destination facing a certain direction.

There are four possible shortest paths for getting from origin to destination with fixed starting and ending directions. This is illustrated in Figure 9. The main difference between this and Figure 5 is that we approach the destination point by going around an arc of a circle, so that we will end up pointing in the correct direction. Similar to before, we will use trigonometric relationships to figure out the angles and lengths for each segment, except that there are now three segments in total: the first arc, the line in the middle, and the second arc.

We can easily position the turning circles for both origin and destination in the same way that we did earlier for Figure 6. The challenge is finding the point (and angle) where the path leaves the first circle, and later where it hits the second circle. There are two main cases that we need to consider. First, there is the case where we are traveling around both circles in the same direction, for example clockwise and clockwise (see Figure 10).

FIGURE 10. Case 1: Traveling around both circles in the same direction.

For this case, note the following:

  1. The line from P1 to P2 has the same length and slope as the (green) path line below it.
  2. The arc angle at which the line touches the first circle is simply 90 degrees different from the slope of the line.
  3. The arc angle at which the line touches the second circle is exactly the same as the arc angle at which it touches the first circle.

The second case, where the path travels around the circles in opposite directions (for example, clockwise around the first and counterclockwise around the second), is somewhat more complicated (see Figure 11). To solve this problem, we imagine a third circle centered at P3 which is tangent to the destination circle, and whose angle relative to the destination circle is at right angles with the (green) path line. Now we follow these steps:

  1. Observe that we can draw a right triangle between P1, P2, and P3.
  2. We know that the length from P2 to P3 is (2 * radius), and we already know the length from P1 to P2, so we can calculate the angle as = arccos(2 * radius / Length(P1, P2))
  3. Since we also already know the angle of the line from P1 to P2, we just add or subtract (depending on clockwise or counterclockwise turning) to get the exact angle of the (green) path line. From that we can calculate the arc angle where it leaves the first circle and the arc angle where it touches the second circle.

We now know how to determine all four paths from origin to destination, so given two nodes (and their associated positions and directions), we can calculate the four possible paths and use the one which is the shortest.

FIGURE 11. Case 2: Traveling around the circles in opposite directions.

Note that we can now use the simple smoothing algorithm presented earlier with curved paths, with just a slight modification to the Walkable(pointA, pointB) function. Instead of point-sampling in a straight line between pointA and pointB, the new Walkable(pointA, directionA, pointB, directionB) function samples intermediate points along a valid curve between A and B given the initial and final directions.

Discrete and nondiscrete positions and directions. Some readers may be concerned at this point, since it seems that our algorithm is dependent on movement always starting at exactly the center position of a tile, and at exactly one of eight compass directions. In real games, a character may be in the middle of walking between two tiles at the exact moment we need it to change direction. In fact, we can easily modify the algorithm so that whenever the origin node is the starting point of the search, we do the curve computations based on the true precise position and angle of the character's starting point. This eliminates the restriction.

Nonetheless, the algorithm still requires that the waypoints are at the center of tiles and at exact compass directions. These restrictions can seemingly cause problems where a valid path may not be found. The case of tile-centering is discussed in more detail below. The problem of rounded compass directions, however, is in fact very minimal and will almost never restrict a valid path. It may cause visible turns to be a bit more exaggerated, but this effect is very slight.

Expanded searching to surrounding tiles. So far in this discussion, we have assumed that at every node, you check the surrounding eight locations as neighbors. We call this a Directional-8 search. As mentioned in the preceding paragraph, there are times when this is restrictive. For example, the search shown in Figure 12 will fail for a Directional-8 search, because given a wide turning radius for the ship, it would impossible to traverse a -> b -> c -> d without hitting blocking tiles. Instead, it is necessary to find a curve directly from a -> d.

FIGURE 12. A legal curved path which cannot be found by the Directional-8 algorithm.

Accomplishing this requires searching not just the surrounding eight tiles, which are one tile away, but the surrounding 24 tiles, which are two tiles away. We call this a Directional-24 search, and it was such a search that produced the valid path shown in Figure 12. We can even search three tiles away for a Directional-48 search. The main problem with these extended searches is computation time. A node in a Directional-8 search has 8 x 8 = 64 child nodes, but a node in a Directional-24 search has 24 x 8 = 192 child nodes.

A small optimization we can do is to set up a directional table to tell us the relative position of a child given a simple index. For example, in a Directional-48 search, we loop through directions 0 -> 47, and a sample table entry would be:

DirTable= <-3,+3>.

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 straight-line 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 10-tile 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 10-tile 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 hit-check 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 Directional-48 search), the table stores a 121-bit value. This value represents an 11x11 grid surrounding the origin, as seen in Figure 13.

FIGURE 13. Illustration of the hit-check 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 bit-field, 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 tile-based 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 Directional-8 algorithm could occasionally miss a valid path, and this was illustrated in Figure 12. The conclusion was to use a Directional-24 search or even a Directional-48 search. However, in very rare circumstances, the same problem could occur with a Directional-48 search. We could extend even further to a Directional-80 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 Directional-24 search to fail to find a valid path. And it is almost impossible for the Directional-48 search to fail.

Fixed-Angle 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 real-time 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 16-angle 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 16-angle 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 fixed-angle 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 fixed-angle 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 north-northwest 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.

  1. When on roads, make sure to do only a regular A* search or a Directional-8 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.
  2. Temporarily disallow movement to any off-road tile. This has the same constraints as the above method.
  3. Same as (1), but for units that have too wide a turning radius to turn into an adjacent road tile, do a Directional-24 or Directional-48 search as appropriate. For example, the unit shown in Figure 16b apparently requires two tiles to make a 90-degree turn, so a Directional-24 search would be appropriate.
  4. 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.

________________________________________________________

A Better Smoothing Pass