Dealing with moving obstacles

  From Amit’s Thoughts on Pathfinding

A pathfinding algorithm will compute a path around stationary obstacles, but what if the obstacles move? By the time a unit reaches a particular point, an obstacle may no longer be there, or a new obstacle may be there. If the typical obstacle can be routed around, use a separate obstacle avoidance algorithm (steering) along with your pathfinder. The pathfinder will find the desired path, and then while following it, move around obstacles. If however obstacles can cause the path to change significantly, consider using the pathfinder for obstacle avoidance.

Recalculating paths#

As time passes we expect the game world to change. A path found some time ago may no longer be the optimal path. It may be worth updating old paths with new information. Listed below are some criteria that could be used for determining when a recalculation is needed:

The main drawback of path recalculation is that a lot of path information is thrown away. For example, if the path is 100 steps long and it is recalculated every 10 steps, the total number of path steps is 100+90+80+70+60+50+40+30+20+10 = 550. For a path of M steps, approximately M^2 path steps are computed over time. Therefore path recalculation is not a good idea if you expect to have many long paths. It would be better to reuse the path information instead of throwing it away.

Path splicing#

When a path needs to be recalculated, it means the world is changing. Given a changing world, nearby parts of the map are better known than faraway parts of the map. We can follow a local repair strategy: find a good path nearby, and assume the path farther away need not be recomputed until we get closer to it. Instead of recalculating the entire path, we can recalculate the first M steps of the path:

  1. Let p[1]..p[N] be the remainder of the path (N steps)
  2. Compute a new path from p[1] to p[M]
  3. Splice this new path into the old path by removing p[1]..p[M] and inserting the new path in its place

Since p[1] and p[M] are fewer than M steps apart, it’s unlikely that the new path will be long. Unfortunately, situations can arise in which the new path is long and not very good. The accompanying figure shows such a situation. The original red path is 1-2-3-4; brown areas are obstacles. If we reach 2 and discover that the path from 2 to 3 has been blocked, path splicing would replace 2-3 with the green path 2-3-5 and splice it in, resulting in the unit moving along path 1-2-5-3-4. We can see this is not a good path; the blue path 1-2-5-4 would be better.

Bad paths can often be detected by looking at the length of the new path. If it is significantly longer than M, it could be bad. A simple solution is to add a limit (maximum path length) to the path finding algorithm. If a short path isn’t found, the algorithm returns an error code; in this case, use path recalculation instead of path splicing to get a path such as 1-2-5-4.

For cases not involving these situations, for a path with N steps, path splicing will compute 2N to 3N path steps, depending on how often a new path is spliced in. This is a fairly low cost for the ability to respond to changes in the world. Surprisingly, the cost is independent of M, the number of steps for splicing. Instead of affecting CPU time, M controls a tradeoff between responsiveness and path quality. If M is high, the unit’s movement will not respond quickly to changes in the map. If M is too low, the paths being spliced out may be too short to allow the replacement path to go around the obstacle cleanly; more suboptimal paths (such as 1-2-5-3-4) will be found. Try different values of M and different criteria for splicing (such as every 3/4 M steps) to see what’s right for your map.

Path splicing is significantly faster than path recalculation, but it does not respond well to major changes in the path. It is possible to detect many of these situations and use path recalculation instead. It also has a few variables that can be adjusted, such as M and the choice of when to find a new path, so it can be adjusted (even at run-time) for different conditions. Path splicing also does not handle situations where the units must coordinate in order to pass each other.

Watching for map changes#

An alternative to recalculating all or part of the path at certain intervals is to have changes to the map trigger a recalculation. The map can be divided into regions, and every unit can express an interest in certain regions. (All the regions that contain part of the path could be of interest, or only nearby regions that contain part of the path.) Whenever an obstacle enters or leaves a region, that region is marked changed, and all units that have an interest in that region are notified, so that paths can be recalculated to take into account the change in obstacles.

Many variations of this technique are possible. For example, instead of immediately notifying the units, only notify them at regular intervals. Many changes can be grouped into one notification, so that excessive path recalculations are not needed. Another example is for the unit to poll the regions instead of the regions notifying the unit.

Watching for map changes allows units to avoid recalculation whenever the obstacles on the map do not change, so consider it if you have many regions that do not change often.

Predicting obstacle movement#

If obstacle movement can be predicted, it is possible to take into account future position of obstacles for pathfinding. An algorithm such as A* has a cost function that determines how difficult it is to pass a point on the map. A* can be modified to keep track of the time required to reach a point (determined by current path length), and this time can be passed in to the cost function. The cost function can then take time into account, and use the predicted obstacle position at that time to determine whether the map space is impassable. This modification is not perfect, however, as it will not take into account the possibility of waiting at a point for the obstacle to move out of the way, and A* is not designed to differentiate between paths along the same route, but at different points in time.

Cooperative Pathfinding A*[1] formalizes this, building a table of the paths of all other units and treating them as obstacles. Also see the Windowed Hierarchical Cooperative A* algorithm[2].

Another option is to find paths for all the units simultaneously, where the pathfinder can take into account all of their movements. See Multi-Agent Path Finding[3] for more.

Email me , or tweet @redblobgames, or comment: