Toward More Realistic Pathfinding
March 14, 2001 Page 4 of 7
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.
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.
FIGURE 9. Arriving at the destination facing a certain direction. 
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:

The line from P1 to P2 has the same length and slope as the (green) path line below it.

The arc angle at which the line touches the first circle is simply 90 degrees different from the slope of the line.

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:

Observe that we can draw a right triangle between P1, P2, and P3.

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

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 pointsampling 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 tilecentering 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 Directional8 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 Directional8 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 Directional8 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 Directional24 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 Directional48 search. The main problem with these extended searches is computation time. A node in a Directional8 search has 8 x 8 = 64 child nodes, but a node in a Directional24 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 Directional48 search, we loop through directions 0 > 47, and a sample table entry would be:
DirTable[47] = <3,+3>.
Page 4 of 7