Enemies that think in JavaScript

Problem

The goblin that bumps into the wall

Until now the enemies in the mine stood where the map put them. A player who sees that knows at once that the game is made of cardboard. A living enemy has to do three things: decide what to do (sleep, wander, chase, flee), find its way, and choose in battle.

The simplest chase is: "take the step that brings you closest to the hero". Here are a goblin (g) and a hero (@) on two sides of a wall with a gap at the bottom:

################
#......#.......#
#......#.......#
#.@....#g......#
#......#.......#
#..............#
################

In a straight line they are 6 cells apart, but the wall is between them. The simple chase compares only the distance: the goblin wants to go left, there is a wall, and it stands pressed against it. This is where it stops:

################
#......#.......#
#......#.......#
#.@....#g......#
#......#.......#
#..............#
################

A straight line knows nothing about walls. We need a path that goes around them, and the shortest path on a grid is found with breadth-first search. The lesson first builds it on the small 16 × 7 level (the gap is at the bottom), then puts a state machine on top that decides when the enemy moves, and finally shows the game's second brain: utility scoring in battle.

The idea

The wave: how many steps each cell is

Imagine dropping a stone into water: circles spread out from where it fell. Breadth-first search does the same over a grid. It starts at the goblin: that cell is at distance 0. Its neighbours are at 1. The neighbours of the neighbours (not yet seen) are at 2. And so on, until the wave covers everything. Every cell gets a number: how many steps it is from the goblin along the floor, not in a straight line.

You need a queue: the cells the wave has reached but has not looked at yet. The oldest cell is taken from the front of the queue (that is why the wave goes in order), and its new neighbours go to the back. A cell that already has a number is not added a second time.

const MAP = `
################
#......#.......#
#......#.......#
#......#.......#
#......#.......#
#..............#
################`.trim();

const DIRECTIONS = [[0, -1], [1, 0], [0, 1], [-1, 0]];

// The wave: how many steps each cell is from the start.
function distances(level, startX, startY) {
  const dist = Array.from({ length: level.height }, () => new Array(level.width).fill(-1));
  dist[startY][startX] = 0;
  const queue = [{ x: startX, y: startY }];
  let head = 0;
  while (head < queue.length) {
    const cell = queue[head];
    head++;
    for (const [dx, dy] of DIRECTIONS) {
      const nextX = cell.x + dx;
      const nextY = cell.y + dy;
      if (!level.walkable(nextX, nextY) || dist[nextY][nextX] !== -1) continue;
      dist[nextY][nextX] = dist[cell.y][cell.x] + 1;
      queue.push({ x: nextX, y: nextY });
    }
  }
  return dist;
}

const level = new Level(MAP);
const dist = distances(level, ENEMY_X, ENEMY_Y);
console.log("The wave from the enemy (a = 10, b = 11, ...):");
printWave(level, dist);

The wave from the enemy (a = 10, b = 11, ...):
################
#dcba98#2345678#
#cba987#1234567#
#ba9876#0123456#
#a98765#1234567#
#98765432345678#
################

a is 10, b is 11, and so on. The goblin is at 0 (next to the wall, at the left edge of the right-hand room), and the wall is #. The wave first fills the right room, then passes through the gap at the bottom, and only then climbs into the left one. The hero at (2, 3) is on a, that is 10 steps from the goblin, although in a straight line it is 6: the number is the real distance along the floor.

We do not use shift(): taking from the start of an array shifts all the other elements, so we walk with an index head instead.

The check dist[nextY][nextX] != -1 is the whole "already been there": the cell has a number, so it is in the queue or has been in it. Without the check the wave would flow back and never end.

More precisely, if you are curious

The four directions are in a fixed order: up, right, down, left. The order does not change the distances (they are the same in any order), but it changes which of the equal paths is found. In the game the order is fixed for exactly this reason: the same input must give the same path in Java, C#, Python and JavaScript, otherwise the battle record and the check against the recorded playthrough would drift apart.

This wave of distances is called a distance field (also a Dijkstra map): one search from the hero gives a number for every cell, and every enemy simply steps to the neighbour with the smaller number. With many enemies this is much cheaper than a search for each one.

The idea

The path: where each cell came from

The numbers show the distance, but the enemy wants the steps. We add one table: for every cell we remember which cell the wave came from. When the wave reaches the goal, we walk backwards: the goal, where it came from, where that one came from, and so on to the start. That gives the path back to front, so at the end we reverse it.

function findPath(level, startX, startY, goalX, goalY) {
  const cameFrom = new Array(level.width * level.height).fill(-1);
  const start = startY * level.width + startX;
  cameFrom[start] = start;
  const queue = [start];
  let head = 0;
  while (head < queue.length) {
    const current = queue[head];
    head++;
    const x = current % level.width;
    const y = Math.floor(current / level.width);
    if (current !== start && x === goalX && y === goalY) {
      const path = [];
      let index = current;
      while (index !== start) {
        path.push({ x: index % level.width, y: Math.floor(index / level.width) });
        index = cameFrom[index];
      }
      path.reverse();
      return path;
    }
    for (const [dx, dy] of DIRECTIONS) {
      const nextX = x + dx;
      const nextY = y + dy;
      if (!level.walkable(nextX, nextY)) continue;
      const next = nextY * level.width + nextX;
      if (cameFrom[next] !== -1) continue;
      cameFrom[next] = current;
      queue.push(next);
    }
  }
  return null;
}

function distance(ax, ay, bx, by) {
  return Math.abs(ax - bx) + Math.abs(ay - by);
}

const level = new Level(MAP);
const path = findPath(level, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y);
console.log("the enemy (" + ENEMY_X + ", " + ENEMY_Y + "), the hero (" + HERO_X + ", " + HERO_Y + "): in a straight line " +
  distance(ENEMY_X, ENEMY_Y, HERO_X, HERO_Y) + ", by path " + path.length);
const dist = distances(level, ENEMY_X, ENEMY_Y);
console.log("The wave from the enemy (a = 10, b = 11, ...):");
printWave(level, dist);
console.log("The path to the hero (*):");
printPath(level, path, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y);

the enemy (8, 3), the hero (2, 3): in a straight line 6, by path 10
The wave from the enemy (a = 10, b = 11, ...):
################
#dcba98#2345678#
#cba987#1234567#
#ba9876#0123456#
#a98765#1234567#
#98765432345678#
################
The path to the hero (*):
################
#......#.......#
#......#.......#
#.@****#g......#
#.....*#*......#
#.....***......#
################

The path (*) goes down through the gap, climbs along the wall into the left room and walks left to the hero: 10 steps against 6 in a straight line. The wall does not bother the algorithm, because the wave simply does not enter it.

The search stops as soon as it takes the goal out of the queue: it needs nothing after that. That is why the first goal found is the nearest. And if there is no path (the hero is behind a wall with no gap), the queue runs out and the function returns null.

More precisely, if you are curious

The first step of the path is only one cell, but the enemy takes it and asks again on the next turn. So it cannot get stuck on an old path: the hero has moved, another enemy has taken the cell, the door has closed.

The cost is low. The game level is 50 × 20, about 1000 cells, and even if all of them are visited, that is a few thousand simple checks per enemy per turn.

The idea

A state machine: asleep, wandering, chasing, fleeing

When does the enemy use the path? It depends on what it is now. A sleeper does not move. A wanderer roams. A chaser follows the path. A fleer moves away. This is a state machine: an enemy has a state (a string: "sleep", "wander", "chase", "flee"), and every turn says "in this state, in this situation, what do I do and which state do I go to".

From	To	When
`sleep`	`chase`	the path to the hero is at most 5
`wander`	`chase`	the enemy "sees" the hero: the path is at most 8
`chase`	`wander`	more than 3 turns without sight (`lost > LOST`)
`chase`	`flee`	life × 4 < max life (under a quarter)

The program uses the same map and an enemy with 16 life. "Sees" is simplified: an enemy sees the hero if the path to the hero is at most 8. In the game this is a line of sight from the map lesson (up to 8 cells), and here the path gives the same without another algorithm. The scenario is in SCRIPT: the hero approaches, ducks behind a corner (hidden), shows up again, and finally gets hit (hit).

const SIGHT = 8;
const WAKE = 5;
const LOST = 3;
const FAR = 20;
const NONE = 99;
const ENEMY_LIFE = 16;

// The enemy "sees" the hero if the path to the hero is short (in the game: the line of sight from the map lesson).
function enemyTurn(level, enemy, heroX, heroY, turn, hidden) {
  const path = findPath(level, enemy.x, enemy.y, heroX, heroY);
  const pathLength = path === null ? NONE : path.length;
  const sees = !hidden && pathLength <= SIGHT;
  if (enemy.state === "sleep") {
    if (sees && pathLength <= WAKE) enemy.state = "chase";
    return;
  }
  if (enemy.state === "wander") {
    if (sees) {
      enemy.state = "chase";
      enemy.lost = 0;
      return;
    }
    // Wanders in the order of the directions (the game rolls a die).
    const [dx, dy] = DIRECTIONS[turn % 4];
    const nextX = enemy.x + dx;
    const nextY = enemy.y + dy;
    if (level.walkable(nextX, nextY) && !(nextX === heroX && nextY === heroY)) {
      enemy.x = nextX;
      enemy.y = nextY;
    }
    return;
  }
  if (enemy.state === "chase") {
    if (enemy.life * 4 < enemy.maxLife) {
      enemy.state = "flee";
      return;
    }
    if (!sees) {
      enemy.lost++;
      if (enemy.lost > LOST) {
        enemy.state = "wander";
        return;
      }
    } else {
      enemy.lost = 0;
    }
    if (pathLength <= 1) return;
    if (pathLength <= FAR) {
      enemy.x = path[0].x;
      enemy.y = path[0].y;
    }
    return;
  }
  // Flees: the step that takes it farthest from the hero.
  let bestX = enemy.x;
  let bestY = enemy.y;
  let bestDistance = distance(enemy.x, enemy.y, heroX, heroY);
  for (const [dx, dy] of DIRECTIONS) {
    const nextX = enemy.x + dx;
    const nextY = enemy.y + dy;
    if (!level.walkable(nextX, nextY) || (nextX === heroX && nextY === heroY)) continue;
    const away = distance(nextX, nextY, heroX, heroY);
    if (away > bestDistance) {
      bestDistance = away;
      bestX = nextX;
      bestY = nextY;
    }
  }
  enemy.x = bestX;
  enemy.y = bestY;
}

Each state is a branch of one if that returns at its end: exactly one thing happens in one turn. It reads from top to bottom like the table. The counter lost is the memory of the machine: without it the enemy would forget the hero at the first moment out of sight.

const level = new Level(MAP);
const enemy = new Enemy(ENEMY_X, ENEMY_Y, "sleep", ENEMY_LIFE);
SCRIPT.forEach(([heroX, heroY, hit, hidden], i) => {
  enemy.life = Math.max(0, enemy.life - hit);
  const before = enemy.state;
  enemyTurn(level, enemy, heroX, heroY, i + 1, hidden);
  const path = findPath(level, enemy.x, enemy.y, heroX, heroY);
  const length = path === null ? NONE : path.length;
  const state = before === enemy.state ? before : before + " → " + enemy.state;
  console.log("turn " + (i + 1) + ": " + state + ", enemy (" + enemy.x + ", " + enemy.y + "), path " + length + ", life " + enemy.life);
});

turn 1: sleep, enemy (8, 3), path 7, life 16
turn 2: sleep, enemy (8, 3), path 6, life 16
turn 3: sleep → chase, enemy (8, 3), path 5, life 16
turn 4: chase, enemy (8, 4), path 4, life 16
turn 5: chase, enemy (8, 5), path 3, life 16
turn 6: chase, enemy (7, 5), path 2, life 16
turn 7: chase, enemy (6, 5), path 1, life 16
turn 8: chase → wander, enemy (6, 5), path 1, life 16
turn 9: wander, enemy (7, 5), path 2, life 16
turn 10: wander → chase, enemy (7, 5), path 2, life 16
turn 11: chase, enemy (6, 5), path 1, life 16
turn 12: chase → flee, enemy (6, 5), path 1, life 3
turn 13: flee, enemy (7, 5), path 2, life 3
turn 14: flee, enemy (8, 5), path 3, life 3
turn 15: flee, enemy (9, 5), path 4, life 3

Turn 3: the path becomes 5 and sleep → chase. Turns 4–7: the goblin walks along the path. On turn 8 lost exceeds 3 and it goes to wander; on turn 9 it takes a step like a wanderer, and on turn 10 it sees the hero again. On turn 12 the hero hits it and takes 13 of its 16 life: 3 × 4 = 12 < 16 and chase → flee. Fleeing does not use the path: of the four neighbours it takes the one that moves it farthest away (away > bestDistance).

More precisely, if you are curious

Why strings and not an enum? The canon uses strings because the states are written into the game's save and read back from a file. That way a new kind of enemy with a new state needs no new type. The cost is that a typo in a name ("chaes") is not caught at compile time.

A state machine is the simplest way to describe behaviour, but it grows: ten states with five transitions each are fifty lines that are hard to read. Then you move to a behavior tree or to utility scoring, like the one in battle below.

See it

The chase in action

Here is the same thing turn by turn. The goblin sleeps on the other side of the wall. The hero approaches; the path becomes 5 and the goblin wakes up. Then you see the search: a wave starts from the goblin and goes around the wall through the gap until it reaches the hero. After that the goblin walks, loses the hero, notices again, and finally flees.

function findPath(level, startX, startY, goalX, goalY) {
  const cameFrom = new Array(level.width * level.height).fill(-1);
  const start = startY * level.width + startX;
  cameFrom[start] = start;
  const queue = [start];
  let head = 0;
  while (head < queue.length) {
    const current = queue[head];
    head++;
    const x = current % level.width;
    const y = Math.floor(current / level.width);
    if (current !== start && x === goalX && y === goalY) {
      const path = [];
      let index = current;
      while (index !== start) {
        path.push({ x: index % level.width, y: Math.floor(index / level.width) });
        index = cameFrom[index];
      }
      path.reverse();
      return path;
    }
    for (const [dx, dy] of DIRECTIONS) {
      const nextX = x + dx;
      const nextY = y + dy;
      if (!level.walkable(nextX, nextY)) continue;
      const next = nextY * level.width + nextX;
      if (cameFrom[next] !== -1) continue;
      cameFrom[next] = current;
      queue.push(next);
    }
  }
  return null;
}

// The enemy "sees" the hero if the path to the hero is short (in the game: the line of sight from the map lesson).
function enemyTurn(level, enemy, heroX, heroY, turn, hidden) {
  const path = findPath(level, enemy.x, enemy.y, heroX, heroY);
  const pathLength = path === null ? NONE : path.length;
  const sees = !hidden && pathLength <= SIGHT;
  if (enemy.state === "sleep") {
    if (sees && pathLength <= WAKE) enemy.state = "chase";
    return;
  }
  if (enemy.state === "wander") {
    if (sees) {
      enemy.state = "chase";
      enemy.lost = 0;
      return;
    }
    // Wanders in the order of the directions (the game rolls a die).
    const [dx, dy] = DIRECTIONS[turn % 4];
    const nextX = enemy.x + dx;
    const nextY = enemy.y + dy;
    if (level.walkable(nextX, nextY) && !(nextX === heroX && nextY === heroY)) {
      enemy.x = nextX;
      enemy.y = nextY;
    }
    return;
  }
  if (enemy.state === "chase") {
    if (enemy.life * 4 < enemy.maxLife) {
      enemy.state = "flee";
      return;
    }
    if (!sees) {
      enemy.lost++;
      if (enemy.lost > LOST) {
        enemy.state = "wander";
        return;
      }
    } else {
      enemy.lost = 0;
    }
    if (pathLength <= 1) return;
    if (pathLength <= FAR) {
      enemy.x = path[0].x;
      enemy.y = path[0].y;
    }
    return;
  }
  // Flees: the step that takes it farthest from the hero.
  let bestX = enemy.x;
  let bestY = enemy.y;
  let bestDistance = distance(enemy.x, enemy.y, heroX, heroY);
  for (const [dx, dy] of DIRECTIONS) {
    const nextX = enemy.x + dx;
    const nextY = enemy.y + dy;
    if (!level.walkable(nextX, nextY) || (nextX === heroX && nextY === heroY)) continue;
    const away = distance(nextX, nextY, heroX, heroY);
    if (away > bestDistance) {
      bestDistance = away;
      bestX = nextX;
      bestY = nextY;
    }
  }
  enemy.x = bestX;
  enemy.y = bestY;
}

Step by step, in words

The goblin sleeps at (8, 3). The hero is on the other side of the wall. On turn 2 the path to the hero is 6, and waking needs at most 5: the goblin keeps sleeping, though in a straight line the hero is only 4 cells away.
Turn 3: the hero is at (6, 4). In a straight line, through the wall, that is 3 cells, but the path is 5 ≤ 5: sleep → chase.
Breadth-first search from the goblin: a queue, and the oldest cell comes out first. The wave spreads over the floor cell by cell and goes around the wall through the gap. 27 of 66 cells come out of the queue before the hero is reached.
The hero is found. From the hero we walk backwards through cameFrom, cell by cell to the goblin, and reverse the path: 5 steps. The goblin will take the first one.
Every turn the goblin asks again and takes only the first step of the path: 4, 3, 2, 1 to the hero. If the hero moves, the path is different.
The hero ducks behind a corner (the pale ball). The goblin still walks toward the hero, but it counts: after 3 turns without sight (lost > 3) on turn 8 chase → wander.
Turn 9: the goblin wanders. The direction comes from the turn number (the game rolls a die), so to the hero it looks random, not aimed.
Turn 10: the hero shows up again, the path is 2 ≤ 8: wander → chase. The goblin chases again and reaches the hero.
Turn 12: the hero’s blow leaves the goblin with 3 of 16 life. The test is life × 4 < max life: 12 < 16, so chase → flee.
Fleeing needs no path and no search: of the four neighbours it takes the one that moves it farthest from the hero (2, 3, 4 cells).

The code next to the scene is findPath and enemyTurn from the program. On every step the lines that are working at that moment light up.

The idea

In the game

What we built is the same as in the canon, only smaller. Here is the real breadth-first search. It takes two functions instead of a ready goal and a ready map of what can be walked: isPassable says where an enemy may step (not through other enemies and not through the hero), and isGoal says which cell is the target:

// Breadth-first search: a queue of cells, each remembers where it came from. The first goal found is
// the nearest one. The directions are in a fixed order (up, right, down, left), so the path is the same
// in every language.
const DIRECTIONS = [[0, -1], [1, 0], [0, 1], [-1, 0]];

// isPassable(x, y) and isGoal(x, y) are functions; returns the path without the start, or null.
function findPath(level, startX, startY, isPassable, isGoal) {
  const cameFrom = new Array(level.width * level.height).fill(-1);
  const startIndex = startY * level.width + startX;
  cameFrom[startIndex] = startIndex;
  const queue = [startIndex];
  let head = 0;
  while (head < queue.length) {
    const current = queue[head];
    head++;
    const x = current % level.width;
    const y = Math.floor(current / level.width);
    if (current !== startIndex && isGoal(x, y)) {
      const path = [];
      let index = current;
      while (index !== startIndex) {
        path.push({ x: index % level.width, y: Math.floor(index / level.width) });
        index = cameFrom[index];
      }
      path.reverse();
      return path;
    }
    for (const direction of DIRECTIONS) {
      const nextX = x + direction[0];
      const nextY = y + direction[1];
      if (!level.inBounds(nextX, nextY)) continue;
      const nextIndex = nextY * level.width + nextX;
      if (cameFrom[nextIndex] !== -1) continue;
      if (!isPassable(nextX, nextY) && !isGoal(nextX, nextY)) continue;
      cameFrom[nextIndex] = current;
      queue.push(nextIndex);
    }
  }
  return null;
}

function distance(ax, ay, bx, by) {
  return Math.abs(ax - bx) + Math.abs(ay - by);
}

And here is the state machine on the map. Besides our states there is guard (a guard at a post), calm (after the hero escapes from a battle the enemies wander and do not notice the hero for 6 turns) and a die for waking up:

// The map AI is a state machine: sleeps → wanders → chases → flees when low on life.
// The Warden stays at its post (guard) until it sees the hero.
function enemySeesHero(level, enemy, hero) {
  if (distance(enemy.x, enemy.y, hero.x, hero.y) > 8) return false;
  return lineOfSight(level, enemy.x, enemy.y, hero.x, hero.y);
}

function canEnemyStep(game, level, x, y) {
  if (!level.isWalkable(x, y)) return false;
  if (level.enemyAt(x, y) !== null || level.npcAt(x, y) !== null) return false;
  return !(game.hero.x === x && game.hero.y === y);
}

function moveEnemy(game, level, enemy, x, y) {
  if (enemy.hasEffect('bleed')) level.addBlood(enemy.x, enemy.y);
  enemy.x = x;
  enemy.y = y;
}

function enemyTurnOnMap(game, level, enemy) {
  const hero = game.hero;
  const rng = game.rng;
  const sees = enemySeesHero(level, enemy, hero);
  const heroSeesIt = level.visible[enemy.y][enemy.x];
  if (enemy.calm > 0) enemy.calm -= 1;
  if (enemy.state === 'sleep') {
    if (sees && distance(enemy.x, enemy.y, hero.x, hero.y) <= 5 && rng.chance(50)) {
      enemy.state = 'chase';
      if (heroSeesIt) game.say(t('ai.wakes', { name: enemy.name }));
    }
    return;
  }
  if (enemy.state === 'guard') {
    if (sees && distance(enemy.x, enemy.y, hero.x, hero.y) <= 6) {
      enemy.state = 'chase';
      game.say(t('ai.guard', { name: enemy.name }));
    }
    return;
  }
  if (enemy.state === 'wander') {
    if (sees && enemy.calm === 0) {
      enemy.state = 'chase';
      enemy.lostTurns = 0;
      if (heroSeesIt) game.say(t('ai.notices', { name: enemy.name }));
      return;
    }
    const roll = rng.nextInt(5);
    if (roll < 4) {
      const nextX = enemy.x + DIRECTIONS[roll][0];
      const nextY = enemy.y + DIRECTIONS[roll][1];
      if (canEnemyStep(game, level, nextX, nextY)) moveEnemy(game, level, enemy, nextX, nextY);
    }
    return;
  }
  if (enemy.state === 'chase') {
    if (enemy.kind.special !== 'warden' && enemy.isHeavilyWounded()) {
      enemy.state = 'flee';
      if (heroSeesIt) game.say(t('ai.flees', { name: enemy.name }));
      return;
    }
    if (!sees) {
      enemy.lostTurns += 1;
      if (enemy.lostTurns > 5) {
        enemy.state = 'wander';
        return;
      }
    } else {
      enemy.lostTurns = 0;
    }
    if (distance(enemy.x, enemy.y, hero.x, hero.y) <= 1) return;
    const path = findPath(level, enemy.x, enemy.y,
      (x, y) => canEnemyStep(game, level, x, y),
      (x, y) => x === hero.x && y === hero.y);
    if (path !== null && path.length > 1 && path.length <= 20) moveEnemy(game, level, enemy, path[0].x, path[0].y);
    return;
  }
  // flee: the step that moves farthest away from the hero
  let bestX = enemy.x;
  let bestY = enemy.y;
  let bestDistance = distance(enemy.x, enemy.y, hero.x, hero.y);
  for (const direction of DIRECTIONS) {
    const nextX = enemy.x + direction[0];
    const nextY = enemy.y + direction[1];
    if (!canEnemyStep(game, level, nextX, nextY)) continue;
    const away = distance(nextX, nextY, hero.x, hero.y);
    if (away > bestDistance) {
      bestDistance = away;
      bestX = nextX;
      bestY = nextY;
    }
  }
  if (bestX !== enemy.x || bestY !== enemy.y) moveEnemy(game, level, enemy, bestX, bestY);
}

The differences from our program are few, but important:

enemySeesHero uses the line of sight (Bresenham from the map lesson), not the length of a path. So an enemy can see you through an open door, but not through a wall.
A sleeper wakes up with a 50% chance per turn (rng.chance(50)), and a wanderer moves in only 4 of 5 rolls of the die (rng.nextInt(5)). The die comes from the seeded generator of the game, so the game stays repeatable.
lostTurns > 5, not 3. The path is limited with path.length <= 20: an enemy that is farther away does not chase.
The boss (warden) never flees, however wounded it is.
The messages (ai.wakes, ai.notices, ai.flees) are written only if the hero sees the enemy: the game does not tell you more than you see.

The idea

In battle: utility scoring

On the map an enemy has a state. In battle there is nowhere to walk: there is a choice between several actions, and it has to be sensible. A state machine here would mean one line for every pair "situation — action". Instead every action gets a number: how useful it is right now. The enemy takes the biggest one.

The rule is short: the default is an attack worth 40. Every other possible action has its own score: healing a wounded friend 80, spitting 60. If a score is greater than the best so far, the action replaces it.

class Chooser {
  constructor(attack) {
    this.best = attack;
    this.bestScore = 40;
    this.trace = attack + " 40";
  }

  consider(score, action) {
    this.trace += ", " + action + " " + score;
    if (score > this.bestScore) {
      this.best = action;
      this.bestScore = score;
    }
  }
}

function percent(a, b) {
  return Math.floor((a * 100) / b);
}

function chooseEnemyAction(hero, heroPoisoned, allies, healWait, spitWait) {
  const chooser = new Chooser("attack " + hero.name);
  let weakest = null;
  for (const ally of allies) {
    if (percent(ally.hp, ally.maxHp) < 50 && (weakest === null || percent(ally.hp, ally.maxHp) < percent(weakest.hp, weakest.maxHp))) {
      weakest = ally;
    }
  }
  if (weakest !== null && healWait === 0) chooser.consider(80, "heal " + weakest.name);
  if (spitWait === 0 && !heroPoisoned) chooser.consider(60, "spit at " + hero.name);
  return chooser;
}

function weakestOf(enemies) {
  let weakest = null;
  for (const enemy of enemies) {
    if (weakest === null || enemy.hp < weakest.hp) weakest = enemy;
  }
  return weakest;
}

function chooseHeroAction(hero, hasPotion, enemies) {
  const chooser = new Chooser("attack " + weakestOf(enemies).name);
  if (percent(hero.hp, hero.maxHp) < 35 && hasPotion) chooser.consider(90, "potion");
  return chooser;
}

function show(chooser) {
  console.log(chooser.trace + " → " + chooser.best);
}

The program shows six decisions. Each line is: the actions considered with their scores, an arrow, and the chosen one.

const hero = { name: "Iva", hp: 30, maxHp: 40 };
const hurtHero = { name: "Iva", hp: 10, maxHp: 40 };
const woundedRat = { name: "rat", hp: 3, maxHp: 9 };
const rat = { name: "rat", hp: 9, maxHp: 9 };
const goblin = { name: "goblin", hp: 16, maxHp: 16 };
const woundedGoblin = { name: "goblin", hp: 6, maxHp: 16 };
const cultist = { name: "cultist", hp: 3, maxHp: 20 };

show(chooseEnemyAction(hero, false, [woundedRat, goblin], 0, 0));
show(chooseEnemyAction(hero, false, [woundedRat, goblin], 2, 0));
show(chooseEnemyAction(hero, true, [rat, goblin], 0, 0));
show(chooseEnemyAction(hero, false, [woundedRat, woundedGoblin], 0, 3));
show(chooseHeroAction(hero, true, [woundedRat, goblin, cultist]));
show(chooseHeroAction(hurtHero, true, [woundedRat, goblin, cultist]));

attack Iva 40, heal rat 80, spit at Iva 60 → heal rat
attack Iva 40, spit at Iva 60 → spit at Iva
attack Iva 40 → attack Iva
attack Iva 40, heal rat 80 → heal rat
attack rat 40 → attack rat
attack rat 40, potion 90 → potion

The first four are the shaman's. With a wounded rat and healing ready, it heals (80 > 60 > 40). If healing has to wait (healWait is 2), it spits (60). If the hero is already poisoned and no friend is wounded, the attack (40) remains. The fourth line: both the rat (33%) and the goblin (37%) are wounded; the lower percentage gets healed, that is the rat.

The last two lines are the hero on autopilot (in the game's simulation and in automatic battle). It hits the weakest: the one with the least life. The rat (3) and the cultist (3) are equal and the first one wins, because < does not replace on a tie. At 25% life (under 35%) and with a potion, the potion's score (90) beats 40 and the hero drinks.

class Chooser {
  constructor(attack) {
    this.best = attack;
    this.bestScore = 40;
    this.trace = attack + " 40";
  }

  consider(score, action) {
    this.trace += ", " + action + " " + score;
    if (score  this.bestScore) {
      this.best = action;
      this.bestScore = score;
    }
  }
}

The numbers 80, 60, 40 are not a law. They are tuning: if the shaman heals too often the game gets boring, and if too rarely it gets impossible. That is why the last lesson (the whole game and the balance) runs a thousand battles to adjust these numbers.

// In battle the AI scores every possible action with a number (utility) and picks
// the most useful one: it heals when low on life, uses a skill when it is ready, otherwise attacks.
function chooseEnemyAction(battle, enemy) {
  const hero = battle.hero;
  let best = new AttackAction(enemy, hero);
  let bestScore = 40;
  const consider = (score, action) => {
    if (score > bestScore) {
      best = action;
      bestScore = score;
    }
  };
  const special = enemy.kind.special;
  if (special === 'shaman') {
    let weakest = null;
    for (const ally of battle.aliveEnemies()) {
      if (percent(ally.hp, ally.maxHp()) < 50 && (weakest === null || percent(ally.hp, ally.maxHp()) < percent(weakest.hp, weakest.maxHp()))) weakest = ally;
    }
    if (weakest !== null && enemy.cooldownOf('heal') === 0) consider(80, new SpecialAction(enemy, 'heal', weakest));
    if (enemy.cooldownOf('shaman') === 0 && !hero.hasEffect('poison')) consider(60, new SpecialAction(enemy, 'spit', hero));
  } else if (special === 'firebolt' && enemy.cooldownOf('firebolt') === 0) {
    consider(65, new SpecialAction(enemy, 'firebolt', hero));
  } else if (special === 'rend' && enemy.cooldownOf('rend') === 0 && !hero.hasEffect('bleed')) {
    consider(55, new SpecialAction(enemy, 'rend', hero));
  } else if (special === 'slam' && enemy.cooldownOf('slam') === 0) {
    consider(60, new SpecialAction(enemy, 'slam', hero));
  } else if (special === 'warden') {
    if (enemy.phase === 1 && enemy.hp * 2 < enemy.maxHp()) consider(100, new SpecialAction(enemy, 'summon', hero));
    else if (enemy.cooldownOf('warden') === 0) consider(60, new SpecialAction(enemy, 'slam', hero));
  }
  return best;
}

function usableSkills(hero) {
  const result = [];
  for (const skillId of hero.skills) {
    const skill = SKILLS.get(skillId);
    if (hero.mana >= skill.mana && hero.cooldownOf(skill.id) === 0) result.push(skill);
  }
  return result;
}

function weakestEnemy(battle) {
  let weakest = null;
  for (const enemy of battle.aliveEnemies()) {
    if (weakest === null || enemy.hp < weakest.hp) weakest = enemy;
  }
  return weakest;
}

// The hero on autopilot (the simulation): the same utility scoring.
function chooseHeroAction(battle) {
  const hero = battle.hero;
  const target = weakestEnemy(battle);
  let best = new AttackAction(hero, target);
  let bestScore = 40;
  const consider = (score, action) => {
    if (score > bestScore) {
      best = action;
      bestScore = score;
    }
  };
  const lifeShare = percent(hero.hp, hero.maxHp());
  if (lifeShare < 35 && hero.inventory.count('potion_heal') > 0) consider(90, new ItemAction(hero, 'potion_heal'));
  if ((hero.hasEffect('poison') || hero.hasEffect('bleed')) && lifeShare < 50 && hero.inventory.count('antidote') > 0) {
    consider(70, new ItemAction(hero, 'antidote'));
  }
  const many = battle.aliveEnemies().length >= 2;
  for (const skill of usableSkills(hero)) {
    let score = 0;
    if (skill.kind === 'heal') score = lifeShare < 50 ? 75 : 0;
    else if (skill.kind === 'buff') score = hero.hasEffect(skill.effect) ? 0 : 50;
    else if (skill.kind === 'debuff') score = many ? 55 : 45;
    else if (skill.target === 'all') score = many ? 65 : 52;
    else score = 55;
    consider(score, new SkillAction(hero, skill, target));
  }
  return best;
}

The canon adds more: the cultist's firebolt 65, rend 55 (only if the hero is not bleeding yet), a heavy blow 60, and the boss, who below half life summons helpers with a score of 100. But the shape is the same: consider(score, action). The actions are objects from the lesson on skills and actions as commands: AttackAction, SkillAction and so on. That is why an enemy, a hero on autopilot and a simulation all choose in the same way.

Try it

Predict the output

A small map with an obstacle. The search starts at (1, 1). What does the program print?

const TINY = `
#######
#.#...#
#...#.#
#######`.trim();
const level = new Level(TINY);
printWave(level, distances(level, 1, 1));

Answer

#######
#1#567#
#234#8#
#######

#######
#0#234#
#123#5#
#######

#######
#0#456#
#123#7#
#######

Try it

Find the bug

A colleague changed the search, and now the path to the hero is longer:

const level = new Level(MAP);
const path = findPath(level, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y);
console.log("the enemy (" + ENEMY_X + ", " + ENEMY_Y + "), the hero (" + HERO_X + ", " + HERO_Y + "): in a straight line " +
  distance(ENEMY_X, ENEMY_Y, HERO_X, HERO_Y) + ", by path " + path.length);
console.log("The path to the hero (*):");
printPath(level, path, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y);

the enemy (8, 3), the hero (2, 3): in a straight line 6, by path 12
The path to the hero (*):
################
#......#.......#
#......#.......#
#*@....#g......#
#*.....#*......#
#********......#
################

The path is 12 steps instead of 10 and makes a needless detour. Which line takes cells from the wrong end?

Pick the line with the bug.

More precisely

More precisely: A*, fields and weak spots

A*. Breadth-first search looks equally in all directions, even far from the goal. A* adds a hint: for every cell it computes f = g + h, where g is the steps so far and h is an estimate of how many remain (most often the straight-line distance along the axes). It takes the cell with the smallest f, the one that looks most promising. It needs a priority queue instead of an ordinary one, and the result is the same shortest path as long as h never overestimates. On our map from the goblin to the hero, breadth-first search takes 59 cells out of the queue, A* takes 25. In an open room, from (2, 2) to (6, 2), it is 19 against 5. The numbers come from the lesson's model (A* is not in all four languages here). The canon uses breadth-first search: the levels are 50 × 20, there are no movement costs, and A* costs a priority queue and more code in four languages. If shallow water costs 2 (the map lesson), BFS is no longer correct and you move to Dijkstra; if the levels are large and open, to A*.

A field instead of a path. One search from the hero gives a number for every cell (the wave of this map). Then every enemy steps to the neighbour with the smallest number and does not search itself. With twenty enemies that is one search per turn instead of twenty. Many games with hordes do this. To flee, go the other way: toward the biggest number.

Fleeing is dumb. Our fugitive takes the step that increases the distance the most. In the scene it runs along the bottom row, but in a corner it is left with no move and just stands: there is no path that thinks ahead. Smart fleeing follows the distance field (from the hero), where the whole picture is visible at once and the corner is avoided.

A state machine grows with its transitions. Every new behaviour is a new state and transitions into it and out of it (see the exercise: guard and home are two states with several transitions). Utility scoring grows more gently: a new action is a new consider, with no transitions.

A score is a rough number. Here the scores are 40, 60, 80, written by hand. Better systems multiply several "considerations" with curves (how wounded it is, how far away, how much mana) and the scores change smoothly. The rule stays the same: the number decides, and the decision is repeatable.

Exercise

The guard who goes back

Solve the task in your editor. Start from the state machine program.

A guard at a post. Change the machine so that an enemy starts in the state guard at its place. The guard stands and does not wander. When the path to the hero is at most 6, it goes to chase. It chases along the path; if lost goes above 3, it goes to home and walks back to its post along the shortest path (a step per turn), and when it arrives it is guard again. The guard has no sleep, wander or flee. The hero does not strike: there is no hit.

The map is the same, the guard is at its post (8, 3), and the scenario is this (hero, hit, hidden; the hero is hidden from turn 4 to turn 12):

const SCRIPT = [
  [3, 5, 0, false],
  [4, 5, 0, false],
  [4, 5, 0, false],
  [4, 5, 0, true],
  [4, 5, 0, true],
  [4, 5, 0, true],
  [4, 5, 0, true],
  [4, 5, 0, true],
  [4, 5, 0, true],
  [4, 5, 0, true],
  [4, 5, 0, true],
  [4, 5, 0, true],
];

The output is:

turn 1: guard, enemy (8, 3), path 7, life 16
turn 2: guard → chase, enemy (8, 3), path 6, life 16
turn 3: chase, enemy (8, 4), path 5, life 16
turn 4: chase, enemy (8, 5), path 4, life 16
turn 5: chase, enemy (7, 5), path 3, life 16
turn 6: chase, enemy (6, 5), path 2, life 16
turn 7: chase → home, enemy (6, 5), path 2, life 16
turn 8: home, enemy (7, 5), path 3, life 16
turn 9: home, enemy (8, 5), path 4, life 16
turn 10: home, enemy (8, 4), path 5, life 16
turn 11: home → guard, enemy (8, 3), path 6, life 16
turn 12: guard, enemy (8, 3), path 6, life 16

More tasks

Calm. In the canon, after an escape from a battle the enemies go to wander with calm = 6: while calm is above 0 they do not notice the hero. Add a counter calm to the enemy, decreased every turn.
Walking around another enemy. Give findPath a list of occupied cells (the other enemies) and treat them as walls. What happens if two enemies chase the hero in a narrow corridor?
A distance field. Solve the chase without findPath: run distances from the hero and let the enemy step to the neighbour with the smallest number. How many searches per turn is that with five enemies, and how many with findPath?

Test

Check yourself

1. The same path search takes cells from the start of the list (a queue) or from its end (a stack). With a queue the path to the hero is 10 steps, with a stack it is 12. Why?A queue takes cells in the order they were discovered, so the first goal found is the nearest one; a stack follows one corridor to its end and reaches the goal by a detourA stack is slower, so its path is longerA queue knows where the goal is and walks straight to it

2. The goblin is asleep, the hero is on the other side of the wall 4 cells away in a straight line, and the path around the wall is 6. The wake-up threshold is 5. Why does the goblin not wake up?The goblin sleeps until the hero hits itWaking is measured by the length of the path, not by the straight line: 6 is above the threshold 5, and the straight line goes through a wallWalls muffle the noise, so with a wall in between the goblin never wakes up

3. The goblin is chasing and the hero slips out of its sight. On which turn without sight does the goblin stop chasing and start wandering (LOST = 3)?Immediately, on the first turn without sightOn turn 4: lost grows by 1 on every turn without sight, and the transition happens at lost > 3On turn 3: the transition happens at lost ≥ 3

4. In utility scoring the enemy has an attack (40) and two more actions scored 40 and 60. Which does it choose, and what happens if two actions have equal highest scores?It picks at random among the bestIt chooses 60; on equal scores the action considered first wins, because the replacement happens only when score > bestScoreIt chooses 60; on equal scores the last one wins, because the replacement happens when score ≥ bestScore

5. Why does the goblin compute the path again on every turn instead of remembering the old one?The hero moves and other enemies take cells; an old path may lead to an empty place or through another enemyIt is faster, because a new path costs no time at allBreadth-first search cannot return more than one step

Enemies that think

Cookies