Toward More Realistic Pathfinding
April 21, 2019
Press Releases
April 21, 2019
Games Press

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

Toward More Realistic Pathfinding

March 14, 2001 Page 6 of 7

A Better Smoothing Pass

The smoothing algorithm given earlier is less than ideal when used by itself. There are two reasons for this. Figure 17 demonstrates the first problem. The algorithm stops at point q and looks ahead to see how many nodes it can skip while still conducting a legal move. It makes it to point r, but fails to allow a move from q to s because of the blocker near q. Therefore it simply starts again at r and skips to the destination. What we'd really like to see is a change of direction at p, which cuts diagonally to the final destination, as shown with the dashed line.

The second problem exhibits itself only when we have created a path using the simple (non-directional) method, and is demonstrated by the green line in Figure 18. The algorithm moves forward linearly, keeping the direction of the ship pointing straight up, and stops at point p. Looking ahead to the next point (q), it sees that the turning radius makes the turn impossible. The smoothing algorithm then proceeds to "cheat" and simply allow the turn. However, had it approached p from a diagonal, it could have made the turn legally as evidenced by the blue line.

To fix these problems, we introduce a new pre-smoothing pass that will be executed after the A* search process, but prior to the simple smoothing algorithm described earlier. This pass is actually a very fast version of our Directional-48 algorithm, with the difference that we only allow nodes to move along the path we previously found in the A* search, but we consider the neighbors of any node to be those waypoints which were one, two, or three tiles ahead in the original path. We also modify the cost heuristic to favor the direction of the original path (as opposed to the direction toward the goal). The algorithm will automatically search through various orientations at each waypoint, and various combinations of hopping in two- or three-tile steps, to find the best way to reach the goal.

 FIGURE 17. One shortcoming of the simple smoothing algorithm.

Because this algorithm sticks to tiles along the previous path, it runs fairly quickly, while also allowing us to gain many of the benefits of a Directional-48 search. For example, it will find the legal blue line path shown in Figure 18. Of course it is not perfect, as it still will not find paths that are only visible to a full Directional-48 search, as seen in Figure 19.

 FIGURE 18. Another shortcoming: the simple smoothing algorithm is unable to find and execute a turn within the legal turning radius.

The original, nondirectional search finds the green path, which executes illegal turns. There are no legal ways to perform those turns while still staying on the path. The only way to arrive at the destination legally is via a completely different path, as shown with the blue line. This pre-smoothing algorithm cannot find that path: it can only be found using a true Directional search, or by one of the hybrid methods described later. So the pre-smoothing algorithm fails under this condition. Under such a failure condition, and especially when the illegal move occurs near the destination, the pre-smoothing algorithm may require far more computation time than we desire, because it will search back through every combination of directional nodes along the entire path. To help alleviate this and improve performance, we add an additional feature such that once the pre-smoothing algorithm has reached any point p along the path, if it ever searches back to a point that is six or more points prior to p in the path, it will fail automatically.

 FIGURE 19. The blue line shows the only truly legal path, which the pre-smoothing algorithm can't find, but the Directional search can.

Path Failure and Timeslicing

Depending on the pathfinding method chosen, it is possible for failure to be reported either when there is truly no possible path, or when the chosen solution simply has not found the path (which is more likely to occur when utilizing fast, informal methods.) What to do in the case of failure is entirely dependent on the specifics of the game. Typically, it simply means that the current goal -- a food source, ammunition depot, or enemy base -- is not attainable from the current position, and the unit must choose a different goal. However, it is possible that in certain circumstances we know the goal is achievable, and it is important to find it for gameplay. In these cases we might have started with a faster search method, but if that fails, we can proceed from scratch with a slower, methodical search, such as the standard Directional-24.

The key problem is that A* and its derivative methods of pathfinding perform very poorly if pathfinding fails. To alleviate this problem, it is important to minimize failures. This can be done by dividing up the map into small regions in advance (let's say 1,000 total), and precomputing whether it's possible, given two regions ra and rb, to get from some tile in ra to some tile in rb. We need only one bit to store this, so in our example this uses a 128K table. Then before executing any pathfind, we first check the table. If travel between the regions is impossible, we immediately report failure. Otherwise, it is probably possible to get from our specific source tile to our specific destination tile, so we proceed with the pathfinding algorithm.

In the next section, I'll discuss the time performance for the different algorithms presented here, and how to mix and match techniques to achieve faster times. Note that it is possible to timeslice the search algorithm so that it can be interrupted and restarted several times, and thereby take place over a number of frames, in order to minimize overall performance degradation due to a slow search. The optimized algorithm presented earlier uses a fixed matrix to keep track of the intermediate results of a search, so unfortunately this means that any other units requiring a pathfinding search during that time will be "starved" until the previous pathing is complete. To help alleviate this, we can instead allocate two matrices, one for the occasional slow search that takes several timesliced frames and the other for interspersed fast searches. Only the slow searches, then, will need to pause (very briefly) to complete. In fact, it is actually quite reasonable that a unit "stop and think" for a moment to figure out a particularly difficult path.

Performance and Hybrid Solutions

In this section, I'll discuss performance of many of the techniques presented earlier and how to utilize that knowledge to choose the best algorithms for a particular application.
The major observation testing the various techniques presented here was that the performance of the Directional algorithm is slow, probably too slow for many applications. Perhaps most units in a particular game can utilize the simple A* algorithm with smoothing passes, while a particular few large units could utilize a Directional algorithm. (It is nice to note, however, that only a few years ago, system performance would have prohibited implementation of anything but the simplest A* algorithm, and perhaps a few years from now, the performance issues discussed here will not be significant.)

 FIGURE 20 (a, b and c from top to bottom) The (fast) hybrid Directional A* pathfinding technique.

Knowing the performance limitations, there are also hybrid solutions that can be devised which are often as fast as a simple A* algorithm (with smoothing), but also utilize some of the power of a formal Directional search. One excellent such solution, which is incorporated into the sample program provided, is presented below. (Note that this particular solution will not be useful if a unit is greater than one tile wide.)

1. Start by performing a simple A* search, only searching the surrounding four tiles at every node. If this search fails, report failure. (The result of such a search is illustrated in Figure 20a.)
2. Perform the Smoothing-48 pass. If it is successful, skip to (6). Otherwise, check the search matrix to see what was the farthest node hit, and continue to (3). (This step is illustrated by the brown path in Figure 20b.)
3. Perform another Smoothing-48 pass, this time starting from the destination and working backward. This one will also fail, so check the search matrix to see the farthest node hit. (This step is illustrated by the green path in Figure 20b.)
4. Look at the failure points from both smoothing passes (points a and b in the figure.) This is the section that needs to be searched for an alternate route. If the points are more than 12 tiles distant in the X or Y directions, report failure immediately. Otherwise, step away one tile at a time in each smoothing list (the one starting from the origin and the one starting from the destination) until the points are approximately (but not more than) 12 tiles distant from one another. (Note that this step is not performed in Figure 20.)
5. Perform the Directional-8 algorithm between the two points determined above. If the search fails, report failure. (This step is illustrated by the blue line in Figure 20b.) Otherwise, attach the three path segments found and proceed to (6).
6. Perform the final (simple) smoothing algorithm on the resultant path. (The resultant path is shown in Figure 20c.)

For most searches (99 percent in some applications, less in others, depending on the terrain layout), this hybrid solution will run exactly as fast as a simple A* algorithm with Smoothing-48 and simple smoothing. In the other rare cases, it will require the additional time necessary to do a (difficult) Directional-8 search on points which are 12 tiles apart. As discussed earlier, those cases can be timesliced over multiple frames.

Note that the circuitous route required for the path in Figure 20 is somewhat complex, and the search required around 200ms when tested. Figure 21a shows a simpler version that only required 85ms. Finally, by simply adding one blocking tile, as shown in Figure 21b, the time is reduced to under 6ms, because the initial A* search was able to find a valid route and was not "misled" into an impossible section of terrain.

Page 6 of 7

Related Jobs

Insomniac Games — Burbank CA or Durham NC, California, United States
[04.19.19]

Sr. Engine Programmer
Insomniac Games — Burbank CA or Durham NC, California, United States
[04.19.19]

Mid to Senior Engine Programmer (Tools)
Remedy Entertainment — Espoo, Finland
[04.19.19]

Software Developer for DevOps
Paradox Tectonic — Berkeley, California, United States
[04.18.19]

Senior PC/Console Graphics Programmer