Dealing with moving obstacles

A path-finding 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. One way to deal with this problem is to abandon path-finding and instead use movement algorithms that do not look far ahead; this approach will be discussed in a later section. This section will cover modifications to the path finding approach that could be used to handle moving obstacles.

Recalculating paths

In most cases, as time passes we can expect an increase in the difference between the world and the world at the time the path was found. At some point in time, it may be worth recalculating the remaining path with up-to-date 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 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 is often to go around nearby obstacles, not for distant obstacles. If distant obstacles are held constant, we could assume that the distant path will not change much. Therefore only the nearby portion of the path will change. Instead of recalculating the entire path, we can recalculate the first M steps of the path:

  1. Let p[1]..p[N] be the remaineder 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 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 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; 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.


Implementation Note:
Store the path in reverse order: it is easy to remove the beginning of the path and splice in a new path with a different length; because both operations occur at the end of the array. Essentially you treat the array as a stack where the top element is the next move to make.

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 resond 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.

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.

Dealing with clashes

In general, moving obstacles can include friendly unit movement, enemy unit movement, and other changes to the map (such as the addition or removal of a wall). For the specific case of friendly unit movement, some additional techniques may be useful.

Predicting obstacle movement

If obstacle movement can be predicted, it is possible to take into account future position of obstacles for path-finding. 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.

Waiting for movement

An easily implemented technique is based on the assumption that the other obstacle will move first. When an obstacle is in the way, just wait some amount of time for it to move. If it still hasn't moved after that period of time, recalculate a path around it or to the destination. If the obstacle is detected ahead of time, your unit can simply walk slower to give the other unit more time to get out of the way.

It is possible that two units will bump into each other, and each will wait for the other to proceed. In this case, a priority scheme can be used: assign each unit a unique number, and then make the lower numbered unit wait for the higher numbered unit. This will force one of the units to proceed if both are waiting. When obstacles are detected ahead of time, the lower numbered unit should slow down before reaching the expected point of collision.

Coordinated movement

The technique described above does not work when units are trying to move through a narrow corridor. If one unit stands still while the other tries to go around, the corridor can't be used by both units. One unit will block it while the other one will take a long path around.

It should be possible for the second unit to communicate with the first one, and ask it to back up. Once the corridor is clear, the second unit can pass through, and then the first unit can go through. This may be complicated to implement unless you can identify the corridors beforehand. For randomly generated maps, it could be very difficult to determine where the corridor is and how far the first unit needs to back up.


Last modified: Sun Nov 18 11:32:17 2001
From Amit's Game Programming Site
Copyright (C) 2000, Amit J. Patel