Gamasutra: The Art & Business of Making Gamesspacer
Toward More Realistic Pathfinding
arrowPress Releases
August 22, 2014
PR Newswire
View All





If you enjoy reading this site, you might also want to check out these UBM Tech sites:


 
Toward More Realistic Pathfinding

March 14, 2001 Article Start Previous Page 4 of 7 Next
 

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:

  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[47] = <-3,+3>.


Article Start Previous Page 4 of 7 Next

Related Jobs

Goodgame Studios
Goodgame Studios — Hamburg, Germany
[08.22.14]

Game Developer – C++ and Unreal Engine 4 (m/f)
Bigpoint
Bigpoint — Berlin, Germany
[08.22.14]

Associate / Senior UI Game Developer Scaleform (m/f)
Bigpoint GmbH
Bigpoint GmbH — Hamburg, Germany
[08.22.14]

Game Developer Mobile
Retro Studios - Nintendo
Retro Studios - Nintendo — Austin, Texas, United States
[08.21.14]

Gameplay Engineer






Comments


marq black
profile image
I know this article is quite old but the link to the source code doesn't work, could this be fixed?

Joao Carlos
profile image
For the past week, i have been trying to implement page 3 of this article and no luck. The source code would be nice, since, at least page 3 is not very complete.

Barry Brooks
profile image
http://wayback.archive.org/web/20060801000000*/http://www.gamasut
ra.com/features/20010314/pinter.zip

marq black
profile image
Yea, I have a different implementation of the algorithm but would like to implement the speed enhancements.

Fredrik Sundstrom
profile image
Bump! Yes please, the sourcefiles would be most appreciated :o)

Barry Brooks
profile image
http://wayback.archive.org/web/20060801000000*/http://www.gamasut
ra.com/features/20010314/pinter.zip

Lily Lee
profile image
Can you please once again post the source files? Thank you very much.

Adam Brzozowski
profile image
I found the source code on the wayback url above but had to switch to Nov 2011 to find a valid download.

Major Johnson
profile image
For those trying to use the links to the wayback machine to get the original source:
Make sure when you copy you don't pick up the space present in the formatted link. It will 404. Took me a minute to realize it wasn't copying correctly.

For convenience, here's a tiny url http://tinyurl.com/ouo3k8f


none
 
Comment: