Escape and Evasion

An important behavior to get monsters to do in game AI (properly Game AI is PI or Pseudo Intelligence rather than real AI or Artificial Intelligence, but ‘game AI’ is what they call it…) is to flee from the player (and possibly the player’s allies, if you have such). But it’s difficult to get them to do it well.

By “well”, I mean effectively and convincingly. The most obvious way of fleeing from the player would be to maximize the distance from the player, right? Well, as it turns out, that just results in the creature going to the corner of the room and standing there, which is kind of stupid-looking. And you’d prefer to have at least some of your monsters not look stupid.

The problem the poor critter needs to solve is that it has to take two different things into account when it plans its path. Its goal is to reach safety. The thing it’s treating as its goal, maximizing its distance from the player in the short term, is actually an attempt to minimize an obstacle. The obstacle is that the adversary it needs safety from is likely to kill it, depriving it of the ability to reach its goal. Going to the corner of the room is the result of confusing the goal (reaching safety) with the obstacle to that goal (avoiding immediate danger).

Accordingly, prepare two different maps. The first map is a map of the obstacle, or immediate danger. Start by marking squares where the creature can immediately get killed with a large number, and squares where it is likely to get injured with smaller numbers depending on how dangerous it would be to stand on that square for one turn. Finally, mark any additional squares with a 1. This is your danger map, and avoiding getting killed means staying away from the big numbers on this map. As a rule of thumb, assume the “right” score for a given square on the danger map will be one, plus one thousand divided by the number of turns the creature could probably stand there without being killed.

The second map is a map of the squares the creature would consider to be “a safe place”. The simplest notion of a ‘safe place’ is a place far from the source of danger, or a place where the creature can escape from the danger, like a staircase or a teleporter or something. So find the goal squares using whatever criteria of safety seems relevant.

Now, finally, we have a cleanly expressible goal; The fleeing monster is trying to reach any of the safety goal squares, while exposing itself to the least possible total cumulative danger on its danger map. It should plan its movement using A-Star or Dijkstra’s algorithm, using the values on the danger map as its cost of movement, and filling in the cumulative costs of movement on the map it’s just marked its goal squares on.

A-Star is expensive, and Dijkstra’s algorithm is even more expensive. But we can distribute the compute costs over a lot of monsters if we plan our implementation well. Both of these algorithms work by calculating the minimum cumulative costs of movement from one endpoint to the other, for all squares along the possible paths being considered. This is normally done in the direction of movement, which would be from the monster to the safety square. But in this case the movement costs in terms of exposure to danger are the same in both directions, so the direction doesn’t matter. And we’ve already marked the cumulative movement costs to the goal squares from the goal squares themselves — ie, we’ve marked them with a zero.

For any set of monsters that have the same danger map and the same safety squares, if you calculate cost of cumulative movement starting at the goal squares rather than at the monsters, you’ll be marking the squares with the remaining minimum movement cost (where cost is danger) required to get to the goal – and that’s the same for every member of that set of monsters. That means you can start calculations for each monster that’s fleeing, using the same cumulative-movement-cost map already used by any other monsters (of its own set) who are already fleeing.

So you will do A-Star or Dijkstra’s algorithm, except wherever you encounter a square that was already considered when the other monster was planning its flight. At such squares, you can cut off calculation and use the value that was calculated for the previous fleeing monster. Usually this means that if you have a pack of monsters, who are all fleeing, most of them won’t have to do more than two or three steps of A-Star or Dijkstra.

Now what constitutes a good safety goal square?

I’ve already mentioned maximal distance from the player, staircases, and teleporters. But there are others, depending on what the creature is, whether it’s smart, and what it can do.

A flying creature might have a much shorter path to some square than the threat – and such squares constitute a good safety goal as regards non-flying threats.

A creature whose movement is noticeably faster than the threat’s movement can interpret a “loop” of hallway where it can stay away from the threat by leading it in circles as a good safety goal. Such squares can even be discovered at very short range, for example by “pillar dancing” to keep a pillar between itself and the threat.

Any creature which is smart could regard a healing potion or other means of being healed as a good safety goal.

An unarmed creature capable of using weapons might regard a good weapon as a safety goal.

What constitutes a good danger map?

A creature which is intelligent can mark areas subject to ranged-weapon fire when it’s making its danger map. An animal or mindless undead shouldn’t, even though it is in legitimate danger in the those squares. Normally, even intelligent creatures shouldn’t know exactly how much danger the ranged weapon represents; they might guess high or guess low, depending on their bravado or timidity or if they’ve observed the weapon in action.

If a fleeing creature knows that the threat can use an area affecting attack such as a fireball, then it might consider packing together with too many other creatures as a danger hazard; otherwise, the ‘safety in numbers’ reasoning seems more appropriate.

Creatures whose movement is noticeably slower than the threat’s movement should use a number higher than one for the “danger free” squares, on the assumption that, if they run that way, something faster than they are will be chasing them and doing them damage as they run.

Small variations in danger mapping and safety goal mapping will lead to noticeably different flight and escape behavior for different sets of creatures – differences which, if you’re careful, actually make sense, use your monsters’ capabilities effectively, and let an alert player learn something important about each type of monsters.

Finally, how does a creature react when it’s in a hopeless situation? If we’re using one-thousand as the value for ‘lethal’ squares in the danger map, we can have a smart creature recognize a hopeless situation when the best available flight and escape path has a movement cost measured in danger of, say, five thousand or more. Should it make a heroic sacrifice and charge the threat, hoping to buy some of its teammates time to flee? Should it launch a suicide attack with an area-affecting weapon? Or should it try to surrender, lay down it’s sword and yell, “please don’t kill me!” Different monsters, different possibilities.