Gamasutra - Features - "Toward More Realistic Pathfinding" [03.14.01]

Toward More Realistic Pathfinding

Adding Realistic Turns

The next step is to add realistic curved turns for our units, so that they don't appear to change direction abruptly every time they need to turn. A simple solution involves using a spline to smooth the abrupt corners into turns. While this solves some of the aesthetic concerns, it still results in physically very unrealistic movement for most units. For example, it might change an abrupt cornering of a tank into a tight curve, but the curved turn would still be much tighter than the tank could actually perform.



	FIGURE 5. Determining the shortest path from the origin to the destination.

For a better solution, the first thing we need to know is the turning radius for our unit. Turning radius is a fairly simple concept: if you're in a big parking lot in your car, and turn the wheel to the left as far as it will go and proceed to drive in a circle, the radius of that circle is your turning radius. The turning radius of a Volkswagen Beetle will be substantially smaller than that of a big SUV, and the turning radius of a person will be substantially less than that of a large, lumbering bear.

Let's say you're at some point (origin) and pointed in a certain direction, and you need to get to some other point (destination), as illustrated in Figure 5. The shortest path is found either by turning left as far as you can, going in a circle until you are directly pointed at the destination, and then proceeding forward, or by turning right and doing the same thing.

In Figure 5 the shortest route is clearly the green line at the bottom. This path turns out to be fairly straightforward to calculate due to some geometric relationships, illustrated in Figure 6.



	FIGURE 6. Calculating the length of the path.

First we calculate the location of point P, which is the center of our turning circle, and is always radius r away from the starting point. If we are turning right from our initial direction, that means P is at an angle of (initial_direction - 90) from the origin, so:

angleToP = initial_direction - 90
P.x = Origin.x + r * cos(angleToP)
P.y = Origin.y + r * sin(angleToP)

Now that we know the location of the center point P, we can calculate the distance from P to the destination, shown as h on the diagram:

dx = Destination.x - P.x
dy = Destination.y - P.y
h = sqrt(dx*dx + dy*dy)

At this point we also want to check that the destination is not within the circle, because if it were, we could never reach it:

if (h < r)
return false

Now we can calculate the length of segment d, since we already know the lengths of the other two sides of the right triangle, namely h and r. We can also determine angle from the right-triangle relationship:

d = sqrt(h*h - r*r)
theta = arccos(r / h)

Finally, to figure out the point Q at which to leave the circle and start on the straight line, we need to know the total angle + , and is easily determined as the angle from P to the destination:

phi = arctan(dy / dx) [offset to the correct quadrant]
Q.x = P.x + r * cos(phi + theta)
Q.y = P.y + r * sin(phi + theta)

The above calculations represent the right-turning path. The left-hand path can be calculated in exactly the same way, except that we add 90 to initial_direction for calculating angleToP, and later we use - instead of + . After calculating both, we simply see which path is shorter and use that one.

In our implementation of this algorithm and the ones that follow, we utilize a data structure which stores up to four distinct "line segments," each one being either straight or curved. For the curved paths described here, there are only two segments used: an arc followed by a straight line. The data structure contains members which specify whether the segment is an arc or a straight line, the length of the segment, and its starting position. If the segment is a straight line, the data structure also specifies the angle; for arcs, it specifies the center of the circle, the starting angle on the circle, and the total radians covered by the arc.

Once we have calculated the curved path necessary to get between two points, we can easily calculate our position and direction at any given instant in time, as shown in Listing 2.

LISTING 2. Calculating the position and orientation at a particular time.

distance = unit_speed * elapsed_time
loop i = 0 to 3:
   if (distance < LineSegment[i].length)
      // Unit is somewhere on this line segment
      if LineSegment[i] is an arc
         determine current angle on arc (theta) by adding or
            subtracting (distance / r) to the starting angle
            depending on whether turning to the left or right
         position.x = LineSegment[i].center.x + r*cos(theta)
         position.y = LineSegment[i].center.y + r*sin(theta)
         determine current direction (direction) by adding or
            subtracting 90 to theta, depending on left/right
      else
         position.x = LineSegment[i].start.x
          + distance * cos(LineSegment[i].line_angle)
         position.y = LineSegment[i].start.y
          + distance * sin(LineSegment[i].line_angle)
         direction = theta
      break out of loop
   else
      distance = distance - LineSegment[i].length

Legal Turns: The Basic Methods

So now that we know how to find and follow an efficient curved line between two points, how do we use this in our pathing? The methods discussed in this section are all postprocessing techniques. In other words, they involve using the standard A* algorithm during initial pathfinding, and then adding curved turns later in some fashion, either in an extended pathfinding or during actual unit movement.



	FIGURE 7. Decreasing the turning radius (a), and making a three-point turn (b).

Simple solution: ignoring blocked tiles. We start with the simplest solution. First use the A* algorithm to calculate the path. Then progress from point to point in the path as follows: At any waypoint, a unit has a position, an orientation, and a destination waypoint. Using the algorithm described in the preceding section, we can calculate the fastest curved path to get from the current waypoint to the next waypoint. We don't care what direction we are facing when we reach the destination waypoint, though that will turn out to be the starting orientation for the following waypoint. If we skim some obstacles along the way, so be it -- this is a fast approximation, and we are willing to overlook such things. Figure 1c shows the result of this method. The curves are nice, but on both turns, the side of the ship will overlap a blocking tile.

This solution is actually quite acceptable for many games. However, we often don't want to allow any obviously illegal turns where the unit overlaps obstacles. The next three methods address this problem.

Path recalculations. With this method, after the A* has completed, we step through the path, making sure every move from one waypoint to the next is valid. (This can be done as part of a smoothing pass.) If we find a collision, we mark the move as invalid and try the A* path search again. In order to do this, we need to store one byte for every tile (or add an additional byte to the matrix elements described in the optimization section above). Each bit will correspond to one of the eight tiles accessible from that tile. Then we modify the A* algorithm slightly so that it checks whether a particular move is valid before allowing it. The main problem with this method is that by invalidating certain moves, a valid path approaching the tile from a different direction can be left unfound. Also, in a worst-case scenario, this method could need to recalculate the path many times over.
Making tighter turns. Another solution is that whenever we need to make a turn that would normally cause a collision, we allow our turning radius to decrease until the turn becomes legal. This is illustrated with the first turn in Figure 7a. One proviso is that when we conduct the A* search, we need to search only the surrounding four tiles at every node (as opposed to eight), so we don't end up with impossible situations like the one illustrated in Figure 4. In the case of vehicles, this method may look odd, whereby some lumbering tank suddenly makes an unbelievably tight turn. However, in other cases this may be exactly what you want. Unlike vehicles, which tend to have a constant turning radius, if your units are people, they are able to turn much more tightly if they are creeping along than if they are running. So in order to follow the simple path, you simply need to decelerate the unit as it approaches the turn. This can yield very realistic movement. (See the sections on "Speed and People Movement" for a further discussion.)
Backing up. Our final solution comes from real-world experience. How do we make a very tight turn into a driveway? We back up and make a three-point turn, of course, as illustrated in Figure 7b. If your units are able to perform such maneuvers, and if this is consistent with their behavior, this is a very viable solution.

Legal Turns: The Directional A* Algorithm

None of the methods presented in the above section is formally correct. Method two can often fail to find valid paths, and methods one, three, and four are all basically cheats. Comparing Figures 1c and 1d, we see that the only valid solution which takes turning radius into account may require a completely different route from what the basic A* algorithm provides. To solve this problem, I'll introduce a significant modification to the algorithm, which I'll term the Directional A*.

The main change to the algorithm is the addition of a third dimension. Instead of having a flat grid of nodes, where each node represents an XY grid position, we now have a three-dimensional space of nodes, where a node <X,Y,orientation> represents the position at that node, as well as the compass orientation of the unit (N, S, E, W, NE, NW, SE, SW.) For example, a node might be [X = 92, Y = 142, orientation = NW]. Thus there are eight times as many nodes as before. There are also 64 times as many ways of getting from one <X,Y> location to another, because you can start at the first node pointing any one of eight directions, and end at the next node pointing any one of eight directions.

During the algorithm, when we're at a parent node p and checking a child node q, we don't just check if the child itself is a blocked tile. We check if a curved path from p to q is possible (taking into account the orientation at p, the orientation at q, and the turning radius); and if so, we check if traveling on that path would hit any blocked tiles. Only then do we consider a child node to be valid. In this fashion, every path we look at will be legal, and we will end up with a valid path given the size and turning radius of the unit. Figure 8 illustrates this.



	*FIGURE 8. A legal turn wich will only be found with the Directional A technique.**

The shortest path, and the one that would be chosen by the standard A* algorithm, goes from a to c. However, the turning radius of the unit prevents the unit from performing the right turn at c given the surrounding blockers, and thus the standard A* would return an invalid path in this case. The Directional A*, on the other hand, sees this and instead looks at the alternate path through b. Yet even at b, a 90 degrees turn to the left is not possible due to nearby blockers, so the algorithm finds that it can make a right-hand loop and then continue.


				\|\|\|\|

________________________________________________________