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.
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.
FIGURE 5. Determining the shortest path from the origin to the destination. |
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). |
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.
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 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 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.