Pathfinding for fleeing

Question

As you know there are plenty of solutions when you wand to find the best path in a 2-dimensional environment which leads from point A to point B.

But how do I calculate a path when an object is at point A, and wants to get away from point B, as fast and far as possible?

A bit of background information: My game uses a 2d environment which isn't tile-based but has floating point accuracy. The movement is vector-based. The pathfinding is done by partitioning the game world into rectangles which are walkable or non-walkable and building a graph out of their corners. I already have pathfinding between points working by using Dijkstras algorithm. The use-case for the fleeing algorithm is that in certain situations, actors in my game should perceive another actor as a danger and flee from it.

The trivial solution would be to just move the actor in a vector in the direction which is opposite from the threat until a "safe" distance was reached or the actor reaches a wall where it then covers in fear.

The problem with this approach is that actors will be blocked by small obstacles they could easily get around. As long as moving along the wall wouldn't bring them closer to the threat they could do that, but it would look smarter when they would avoid obstacles in the first place:

Another problem I see is with dead ends in the map geometry. In some situations a being must choose between a path which gets it faster away now but ends in a dead end where it would be trapped, or another path which would mean that it wouldn't get that far away from the danger at first (or even a bit closer) but on the other hand would have a much greater long-term reward in that it would eventually get them much further away. So the short-term reward of getting away fast must be somehow valued against the long-term reward of getting away far.

There is also another rating problem for situations where an actor should accept to move closer to a minor threat to get away from a much larger threat. But completely ignoring all minor threats would be foolish, too (that's why the actor in this graphic goes out of its way to avoid the minor threat in the upper right area):

Are there any standard solutions for this problem?

Answer 1

This might not be the best solution, but it worked for me to create a fleeing AI for this game.

Step 1. Convert your Dijkstra's algorithm to A*. This should be simple by just adding a heuristic, which measures the minimum distance left to the target. This heuristic is added to the distance traveled so far when scoring a node. You should make this change anyway, as it will boost your path finder significantly.

Step 2. Create a variation of the heuristic, which instead of estimating the distance to the target it measures the distance from the danger(s) and negates this value. This will never reach a target (as there is none), so you need to terminate the search at some point, perhaps after specific number of iterations, after specific distance is reached or when all possible routes are handled. This solution effectively creates a path finder that finds the optimal escaping route with the given limitation.

Answer 2

If you really want your actors to be smart about fleeing, just plain Dijkstra / A* pathfinding won't cut it. The reason for this is that, in order to find the optimal escape path from an enemy, the actor also needs to consider how the enemy will move in pursuit.

The following MS Paint diagram should illustrate a particular situation where using only static pathfinding to maximize distance from the enemy will lead to a suboptimal outcome:

Here, the green dot is fleeing from the red dot, and has two choices for a path to take. Going down the right-hand path would allow it to get much further from the red dot's current position, but would eventually trap the green dot in a dead end. The optimal strategy, instead, is for the green dot to keep running around the circle, trying to stay on the opposite side of it from the red dot.

To correctly find such escape strategies, you'll need an adversarial search algorithm like minimax search or its refinements such as alpha-beta pruning. Such an algorithm, applied to the scenario above with a sufficient search depth, will correctly deduce that taking the dead end path to the right will inevitably lead to capture, whereas staying on the circle will not (as long as the green dot can outrun the red one).

Of course, if there are multiple actors of either type, all of these will need to plan their own strategies — either separately or, if the actors are cooperating, together. Such multi-actor chase/escape strategies can become surprisingly complex; for example, one possible strategy for a fleeing actor is to try to distract the enemy by leading it towards a more tempting target. Of course, this will affect the optimal strategy of the other target, and so on...

In practice, you probably won't be able to perform very deep searches in real time with lots of agents, so you're going to have to rely on heuristics a lot. The choice of these heuristics will then determine the "psychology" of your actors — how smart they act, how much attention they pay to different strategies, how cooperative or independent they are, etc.

Answer 3

You've got pathfinding, so you can reduce the problem to picking a good destination.

If there are absolutely safe destinations on the map (e.g. exits that the threat can't follow your actor through), pick one or more nearby ones, and figure out which one has the lowest path cost.

If your fleeing actor has well-armed friends, or if the map includes hazards which the actor is immune to but the threat isn't, pick an open spot near such a friend or hazard and pathfind to that.

If your fleeing actor is faster than some other actor that the threat might also be interested in, pick a point in the direction of that other actor, but beyond it, and pathfind to that point: "I don't have to outrun the bear, I only have to outrun you."

Without the possibility of escape, or killing or distracting the threat, your actor is doomed, right? So pick an arbitrary point to run to, and if you get there, and the threat is still following you, what the hell: turn and fight.

Answer 4

Since specifying an appropriate target-position might well be tricky in many situations, the following approach based on 2D occupancy grid-maps may be worth considering. It is commonly referred to as "value iteration", and combined with gradient-descent/ascent, it gives a simple and fairly efficient (depending on implementation) path-planning algorithm. Due to its simplicity, it is well-known in mobile robotics, in particular for "simple robots" navigating in indoor environments. As implied above, this approach provides a means of finding a path away from a start-position without explicitly specifying a target-position as follows. Note that a target-position can optionally be specified, if available. Also, the approach/algorithm constitutes a breadth-first search, and is to some degree related to potential field methods with attracting and repelling forces.

In the binary case, the 2D occupancy grid-map is one for occupied grid-cells and zero elsewhere. Note that this occupancy-value can also be continuous in the range [0,1], I'll get back to that below. The value of a given grid-cell g_i is V(g_i).

The Basic Version

1. Assuming that grid-cell g₀ contains the start-position. Set V(g₀)=0, and put g₀ in a FIFO-queue.
2. Take the next grid-cell g_i from the queue.
3. For all neighbors g_j of g_i:
   • If g_j is not occupied and has not been visited previously:
     • V(g_j) = V(g_i)+1
     • Mark g_j as visited.
     • Add g_j to the FIFO-queue.
4. If a given distance-threshold is not reached yet, continue with (2.), otherwise continue with (5.).
5. The path is obtained by following the steepest gradient-ascent starting from g₀.

Notes on Step 4.

• As given above, step (4.) requires to keep track of the maximum distance covered, which has been omitted in the above description for reasons of clarity/brevity.
• If a target-position is given, the iteration is stopped as soon as the target-position is reached, i.e. processed/visited as part of step (3.).
• It is, off course, also possible to simply process the whole grid-map, i.e. to continue until all (free) grid-cells have been processed/visited. The limiting factor is obviously the size of the grid-map in conjunction with its resolution.

Extensions and Further Comments

The update-equation V(g_j) = V(g_i)+1 leaves plenty of room to apply all kinds of additional heuristics by either down-scaling V(g_j) or the additive component in order to reduce the value for certain path-options. Most, if not all, such modifications can nicely and generically be incorporated using a grid-map with continuous values from [0,1], which effectively constitutes a pre-processing step of the initial, binary grid-map. For example, adding a transition from 1 to 0 along obstacle boundaries, causes the "actor" to preferably stay clean of obstacles. Such a grid-map can, for example, be generated from the binary version by blurring, weighted dilation, or similar. Adding the threats and enemies as obstacles with large blurring radius, penalizes paths that come close to these. One can also use a diffusion-process on the overall grid-map like this:

V(g_j) = ( 1/(N+1) ) × [ V(g_j) + sum( V(g_i) ) ]

where "sum" refers to the sum over all neighboring grid-cells. For example, instead of creating a binary map, the initial (integer) values could be proportional to the magnitude of the threats, and obstacles present "small" threats. After applying the diffusion-process, the grid-values should/must be scaled to [0,1], and cells occupied by obstacles, threats, and enemies should be set/forced to 1. Otherwise the scaling in the update-equation may not work as desired.

There are many variations on this general scheme/approach. Obstacles etc. could have small values, while free grid-cells have large values, which may require gradient-descent in the last step depending on the objective. In any case, the approach is, IMHO, surprisingly versatile, fairly easy to implement, and potentially rather fast (subject to grid-map-size/resolution). Finally, as with many path-planning algorithms that don't assume a specific target-position, there is the obvious risk of getting stuck in dead-ends. To some extent, it might be possible to apply dedicated post-processing steps before the last step to reduce this risk.

Here's another brief description with an illustration in Java-Script (?), though the illustration didn't work with my browser :(

http://www.cs.ubc.ca/~poole/demos/mdp/vi.html

Lots more detail on planning can be found in the following book. Value iteration is specifically discussed in Chapter 2, Section 2.3.1 Optimal Fixed-Length Plans.

http://planning.cs.uiuc.edu/

Hope that helps, kind regards, Derik.

Answer 5

How about focusing on predators? Let's just raycast 360 degrees on Predator's position, with appropriate density. And we can have refuge samples. And choose best refuge.

Answer 6

One approach they have in Star Trek Online for herds of animals is to just pick an open direction and head in that, fast, de-spawning the animals after a certain distance. But that is mostly a glorified de-spawn animation for herds you are supposed to scare away from attacking you, and not suitable for actual combat mobs.