Skip to content
wannacode

Enemies that think

In short: An enemy on the map is a state machine (asleep, wandering, chasing, fleeing) that chases along the shortest path found by breadth-first search; in battle it picks the action with the highest utility score.

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.

static final String MAP = """
    ################
    #......#.......#
    #......#.......#
    #......#.......#
    #......#.......#
    #..............#
    ################""";


static final int[][] DIRECTIONS = { { 0, -1 }, { 1, 0 }, { 0, 1 }, { -1, 0 } };


// The wave: how many steps each cell is from the start.
static int[][] distances(Level level, int startX, int startY) {
    int[][] dist = new int[level.height][level.width];
    for (int[] row : dist) Arrays.fill(row, -1);
    dist[startY][startX] = 0;
    List<Step> queue = new ArrayList<>(List.of(new Step(startX, startY)));
    int head = 0;
    while (head < queue.size()) {
        Step cell = queue.get(head);
        head++;
        for (int[] direction : DIRECTIONS) {
            int nextX = cell.x() + direction[0];
            int nextY = cell.y() + direction[1];
            if (!level.walkable(nextX, nextY) || dist[nextY][nextX] != -1) continue;
            dist[nextY][nextX] = dist[cell.y()][cell.x()] + 1;
            queue.add(new Step(nextX, nextY));
        }
    }
    return dist;
}
Level level = new Level(MAP);
int[][] dist = distances(level, ENEMY_X, ENEMY_Y);
System.out.println("The wave from the enemy (a = 10, b = 11, ...):");
printWave(level, dist);
Output
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.

Step is a record with x and y. The queue is a List<Step>, and the index head points to the next cell to take: nothing is removed from the list, so nothing has to shift.

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.

static List<Step> findPath(Level level, int startX, int startY, int goalX, int goalY) {
    int[] cameFrom = new int[level.width * level.height];
    Arrays.fill(cameFrom, -1);
    int start = startY * level.width + startX;
    cameFrom[start] = start;
    List<Integer> queue = new ArrayList<>(List.of(start));
    int head = 0;
    while (head < queue.size()) {
        int current = queue.get(head);
        head++;
        int x = current % level.width;
        int y = current / level.width;
        if (current != start && x == goalX && y == goalY) {
            List<Step> path = new ArrayList<>();
            int index = current;
            while (index != start) {
                path.add(new Step(index % level.width, index / level.width));
                index = cameFrom[index];
            }
            Collections.reverse(path);
            return path;
        }
        for (int[] direction : DIRECTIONS) {
            int nextX = x + direction[0];
            int nextY = y + direction[1];
            if (!level.walkable(nextX, nextY)) continue;
            int next = nextY * level.width + nextX;
            if (cameFrom[next] != -1) continue;
            cameFrom[next] = current;
            queue.add(next);
        }
    }
    return null;
}


static int distance(int ax, int ay, int bx, int by) {
    return Math.abs(ax - bx) + Math.abs(ay - by);
}
Level level = new Level(MAP);
List<Step> path = findPath(level, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y);
System.out.println("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.size());
int[][] dist = distances(level, ENEMY_X, ENEMY_Y);
System.out.println("The wave from the enemy (a = 10, b = 11, ...):");
printWave(level, dist);
System.out.println("The path to the hero (*):");
printPath(level, path, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y);
Output
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).

static final int SIGHT = 8;
static final int WAKE = 5;
static final int LOST = 3;
static final int FAR = 20;
static final int NONE = 99;
static final int 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).
static void enemyTurn(Level level, Enemy enemy, int heroX, int heroY, int turn, boolean hidden) {
    List<Step> path = findPath(level, enemy.x, enemy.y, heroX, heroY);
    int pathLength = path == null ? NONE : path.size();
    boolean sees = !hidden && pathLength <= SIGHT;
    if (enemy.state.equals("sleep")) {
        if (sees && pathLength <= WAKE) enemy.state = "chase";
        return;
    }
    if (enemy.state.equals("wander")) {
        if (sees) {
            enemy.state = "chase";
            enemy.lost = 0;
            return;
        }
        // Wanders in the order of the directions (the game rolls a die).
        int[] direction = DIRECTIONS[turn % 4];
        int nextX = enemy.x + direction[0];
        int nextY = enemy.y + direction[1];
        if (level.walkable(nextX, nextY) && !(nextX == heroX && nextY == heroY)) {
            enemy.x = nextX;
            enemy.y = nextY;
        }
        return;
    }
    if (enemy.state.equals("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.get(0).x();
            enemy.y = path.get(0).y();
        }
        return;
    }
    // Flees: the step that takes it farthest from the hero.
    int bestX = enemy.x;
    int bestY = enemy.y;
    int bestDistance = distance(enemy.x, enemy.y, heroX, heroY);
    for (int[] direction : DIRECTIONS) {
        int nextX = enemy.x + direction[0];
        int nextY = enemy.y + direction[1];
        if (!level.walkable(nextX, nextY) || (nextX == heroX && nextY == heroY)) continue;
        int 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.

Level level = new Level(MAP);
Enemy enemy = new Enemy(ENEMY_X, ENEMY_Y, "sleep", ENEMY_LIFE);
for (int i = 0; i < SCRIPT.length; i++) {
    Turn turn = SCRIPT[i];
    enemy.life = Math.max(0, enemy.life - turn.hit());
    String before = enemy.state;
    enemyTurn(level, enemy, turn.heroX(), turn.heroY(), i + 1, turn.hidden());
    List<Step> path = findPath(level, enemy.x, enemy.y, turn.heroX(), turn.heroY());
    int length = path == null ? NONE : path.size();
    String state = before.equals(enemy.state) ? before : before + " → " + enemy.state;
    System.out.println("turn " + (i + 1) + ": " + state + ", enemy (" + enemy.x + ", " + enemy.y + "), path " + length + ", life " + enemy.life);
}
Output
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.

static List<Step> findPath(Level level, int startX, int startY, int goalX, int goalY) {
    int[] cameFrom = new int[level.width * level.height];
    Arrays.fill(cameFrom, -1);
    int start = startY * level.width + startX;
    cameFrom[start] = start;
    List<Integer> queue = new ArrayList<>(List.of(start));
    int head = 0;
    while (head < queue.size()) {
        int current = queue.get(head);
        head++;
        int x = current % level.width;
        int y = current / level.width;
        if (current != start && x == goalX && y == goalY) {
            List<Step> path = new ArrayList<>();
            int index = current;
            while (index != start) {
                path.add(new Step(index % level.width, index / level.width));
                index = cameFrom[index];
            }
            Collections.reverse(path);
            return path;
        }
        for (int[] direction : DIRECTIONS) {
            int nextX = x + direction[0];
            int nextY = y + direction[1];
            if (!level.walkable(nextX, nextY)) continue;
            int next = nextY * level.width + nextX;
            if (cameFrom[next] != -1) continue;
            cameFrom[next] = current;
            queue.add(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).
static void enemyTurn(Level level, Enemy enemy, int heroX, int heroY, int turn, boolean hidden) {
    List<Step> path = findPath(level, enemy.x, enemy.y, heroX, heroY);
    int pathLength = path == null ? NONE : path.size();
    boolean sees = !hidden && pathLength <= SIGHT;
    if (enemy.state.equals("sleep")) {
        if (sees && pathLength <= WAKE) enemy.state = "chase";
        return;
    }
    if (enemy.state.equals("wander")) {
        if (sees) {
            enemy.state = "chase";
            enemy.lost = 0;
            return;
        }
        // Wanders in the order of the directions (the game rolls a die).
        int[] direction = DIRECTIONS[turn % 4];
        int nextX = enemy.x + direction[0];
        int nextY = enemy.y + direction[1];
        if (level.walkable(nextX, nextY) && !(nextX == heroX && nextY == heroY)) {
            enemy.x = nextX;
            enemy.y = nextY;
        }
        return;
    }
    if (enemy.state.equals("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.get(0).x();
            enemy.y = path.get(0).y();
        }
        return;
    }
    // Flees: the step that takes it farthest from the hero.
    int bestX = enemy.x;
    int bestY = enemy.y;
    int bestDistance = distance(enemy.x, enemy.y, heroX, heroY);
    for (int[] direction : DIRECTIONS) {
        int nextX = enemy.x + direction[0];
        int nextY = enemy.y + direction[1];
        if (!level.walkable(nextX, nextY) || (nextX == heroX && nextY == heroY)) continue;
        int 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
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. Turn 10: the hero shows up again, the path is 2 ≤ 8: wander → chase. The goblin chases again and reaches the hero.
  9. 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.
  10. 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.
static final int[][] DIRECTIONS = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};


// A check for a cell: isPassable(x, y) and isGoal(x, y).
interface CellTest {
    boolean test(int x, int y);
}


static class Step {
    int x;
    int y;


    Step(int x, int y) {
        this.x = x;
        this.y = y;
    }
}


// isPassable(x, y) and isGoal(x, y) are functions; returns the path without the start, or null.
static List<Step> findPath(Level level, int startX, int startY, CellTest isPassable, CellTest isGoal) {
    int[] cameFrom = new int[level.width * level.height];
    java.util.Arrays.fill(cameFrom, -1);
    int startIndex = startY * level.width + startX;
    cameFrom[startIndex] = startIndex;
    List<Integer> queue = new ArrayList<>(List.of(startIndex));
    int head = 0;
    while (head < queue.size()) {
        int current = queue.get(head);
        head++;
        int x = current % level.width;
        int y = current / level.width;
        if (current != startIndex && isGoal.test(x, y)) {
            List<Step> path = new ArrayList<>();
            int index = current;
            while (index != startIndex) {
                path.add(new Step(index % level.width, index / level.width));
                index = cameFrom[index];
            }
            java.util.Collections.reverse(path);
            return path;
        }
        for (int[] direction : DIRECTIONS) {
            int nextX = x + direction[0];
            int nextY = y + direction[1];
            if (!level.inBounds(nextX, nextY)) continue;
            int nextIndex = nextY * level.width + nextX;
            if (cameFrom[nextIndex] != -1) continue;
            if (!isPassable.test(nextX, nextY) && !isGoal.test(nextX, nextY)) continue;
            cameFrom[nextIndex] = current;
            queue.add(nextIndex);
        }
    }
    return null;
}


static int distance(int ax, int ay, int bx, int 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.
static boolean enemySeesHero(Level level, Enemy enemy, Hero 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);
}


static boolean canEnemyStep(Game game, Level level, int x, int 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);
}


static void moveEnemy(Game game, Level level, Enemy enemy, int x, int y) {
    if (enemy.hasEffect("bleed")) level.addBlood(enemy.x, enemy.y);
    enemy.x = x;
    enemy.y = y;
}


static void enemyTurnOnMap(Game game, Level level, Enemy enemy) {
    Hero hero = game.hero;
    Random rng = game.rng;
    boolean sees = enemySeesHero(level, enemy, hero);
    boolean heroSeesIt = level.visible[enemy.y][enemy.x];
    if (enemy.calm > 0) enemy.calm -= 1;
    if (enemy.state.equals("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.equals("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.equals("wander")) {
        if (sees && enemy.calm == 0) {
            enemy.state = "chase";
            enemy.lostTurns = 0;
            if (heroSeesIt) game.say(t("ai.notices", "name", enemy.name));
            return;
        }
        int roll = rng.nextInt(5);
        if (roll < 4) {
            int nextX = enemy.x + DIRECTIONS[roll][0];
            int nextY = enemy.y + DIRECTIONS[roll][1];
            if (canEnemyStep(game, level, nextX, nextY)) moveEnemy(game, level, enemy, nextX, nextY);
        }
        return;
    }
    if (enemy.state.equals("chase")) {
        if (!enemy.kind.special.equals("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;
        List<Step> 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.size() > 1 && path.size() <= 20) moveEnemy(game, level, enemy, path.get(0).x, path.get(0).y);
        return;
    }
    // flee: the step that moves farthest away from the hero
    int bestX = enemy.x;
    int bestY = enemy.y;
    int bestDistance = distance(enemy.x, enemy.y, hero.x, hero.y);
    for (int[] direction : DIRECTIONS) {
        int nextX = enemy.x + direction[0];
        int nextY = enemy.y + direction[1];
        if (!canEnemyStep(game, level, nextX, nextY)) continue;
        int 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 {
    String best;
    int bestScore = 40;
    String trace;


    Chooser(String attack) {
        best = attack;
        trace = attack + " 40";
    }


    void consider(int score, String action) {
        trace += ", " + action + " " + score;
        if (score > bestScore) {
            best = action;
            bestScore = score;
        }
    }
}


static int percent(int a, int b) {
    return a * 100 / b;
}


static Chooser chooseEnemyAction(Fighter hero, boolean heroPoisoned, List<Fighter> allies, int healWait, int spitWait) {
    Chooser chooser = new Chooser("attack " + hero.name());
    Fighter weakest = null;
    for (Fighter ally : 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;
}


static Fighter weakestOf(List<Fighter> enemies) {
    Fighter weakest = null;
    for (Fighter enemy : enemies) {
        if (weakest == null || enemy.hp() < weakest.hp()) weakest = enemy;
    }
    return weakest;
}


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


static void show(Chooser chooser) {
    System.out.println(chooser.trace + " → " + chooser.best);
}

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

Fighter hero = new Fighter("Iva", 30, 40);
Fighter hurtHero = new Fighter("Iva", 10, 40);
Fighter woundedRat = new Fighter("rat", 3, 9);
Fighter rat = new Fighter("rat", 9, 9);
Fighter goblin = new Fighter("goblin", 16, 16);
Fighter woundedGoblin = new Fighter("goblin", 6, 16);
Fighter cultist = new Fighter("cultist", 3, 20);


show(chooseEnemyAction(hero, false, List.of(woundedRat, goblin), 0, 0));
show(chooseEnemyAction(hero, false, List.of(woundedRat, goblin), 2, 0));
show(chooseEnemyAction(hero, true, List.of(rat, goblin), 0, 0));
show(chooseEnemyAction(hero, false, List.of(woundedRat, woundedGoblin), 0, 3));
show(chooseHeroAction(hero, true, List.of(woundedRat, goblin, cultist)));
show(chooseHeroAction(hurtHero, true, List.of(woundedRat, goblin, cultist)));
Output
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 {
    String best;
    int bestScore = 40;
    String trace;

    Chooser(String attack) {
        best = attack;
        trace = attack + " 40";
    }

    void consider(int score, String action) {
        trace += ", " + action + " " + score;
        if (score  bestScore) {
            best = action;
            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.


// The most useful action so far. consider(score, action) replaces it if the new one is more useful.
// (A lambda in Java cannot change local variables, so the choice lives in a small object.)
static class BestAction {
    BattleAction best;
    int bestScore;


    BestAction(BattleAction best, int bestScore) {
        this.best = best;
        this.bestScore = bestScore;
    }


    void consider(int score, BattleAction action) {
        if (score > this.bestScore) {
            this.best = action;
            this.bestScore = score;
        }
    }
}


static BattleAction chooseEnemyAction(Battle battle, Enemy enemy) {
    Hero hero = battle.hero;
    BestAction choice = new BestAction(new AttackAction(enemy, hero), 40);
    String special = enemy.kind.special;
    if (special.equals("shaman")) {
        Enemy weakest = null;
        for (Enemy ally : 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) choice.consider(80, new SpecialAction(enemy, "heal", weakest));
        if (enemy.cooldownOf("shaman") == 0 && !hero.hasEffect("poison")) choice.consider(60, new SpecialAction(enemy, "spit", hero));
    } else if (special.equals("firebolt") && enemy.cooldownOf("firebolt") == 0) {
        choice.consider(65, new SpecialAction(enemy, "firebolt", hero));
    } else if (special.equals("rend") && enemy.cooldownOf("rend") == 0 && !hero.hasEffect("bleed")) {
        choice.consider(55, new SpecialAction(enemy, "rend", hero));
    } else if (special.equals("slam") && enemy.cooldownOf("slam") == 0) {
        choice.consider(60, new SpecialAction(enemy, "slam", hero));
    } else if (special.equals("warden")) {
        if (enemy.phase == 1 && enemy.hp * 2 < enemy.maxHp()) choice.consider(100, new SpecialAction(enemy, "summon", hero));
        else if (enemy.cooldownOf("warden") == 0) choice.consider(60, new SpecialAction(enemy, "slam", hero));
    }
    return choice.best;
}


static List<Skill> usableSkills(Hero hero) {
    List<Skill> result = new ArrayList<>();
    for (String skillId : hero.skills) {
        Skill skill = SKILLS.get(skillId);
        if (hero.mana >= skill.mana && hero.cooldownOf(skill.id) == 0) result.add(skill);
    }
    return result;
}


static Enemy weakestEnemy(Battle battle) {
    Enemy weakest = null;
    for (Enemy enemy : battle.aliveEnemies()) {
        if (weakest == null || enemy.hp < weakest.hp) weakest = enemy;
    }
    return weakest;
}


// The hero on autopilot (the simulation): the same utility scoring.
static BattleAction chooseHeroAction(Battle battle) {
    Hero hero = battle.hero;
    Enemy target = weakestEnemy(battle);
    BestAction choice = new BestAction(new AttackAction(hero, target), 40);
    int lifeShare = percent(hero.hp, hero.maxHp());
    if (lifeShare < 35 && hero.inventory.count("potion_heal") > 0) choice.consider(90, new ItemAction(hero, "potion_heal"));
    if ((hero.hasEffect("poison") || hero.hasEffect("bleed")) && lifeShare < 50 && hero.inventory.count("antidote") > 0) {
        choice.consider(70, new ItemAction(hero, "antidote"));
    }
    boolean many = battle.aliveEnemies().size() >= 2;
    for (Skill skill : usableSkills(hero)) {
        int score = 0;
        if (skill.kind.equals("heal")) score = lifeShare < 50 ? 75 : 0;
        else if (skill.kind.equals("buff")) score = hero.hasEffect(skill.effect) ? 0 : 50;
        else if (skill.kind.equals("debuff")) score = many ? 55 : 45;
        else if (skill.target.equals("all")) score = many ? 65 : 52;
        else score = 55;
        choice.consider(score, new SkillAction(hero, skill, target));
    }
    return choice.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?

static final String TINY = """
    #######
    #.#...#
    #...#.#
    #######""";
Level level = new Level(TINY);
printWave(level, distances(level, 1, 1));
Answer

Try it

Find the bug

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

Level level = new Level(MAP);
List<Step> path = findPath(level, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y);
System.out.println("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.size());
System.out.println("The path to the hero (*):");
printPath(level, path, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y);
Output
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):

static final Turn[] SCRIPT = {
    new Turn(3, 5, 0, false),
    new Turn(4, 5, 0, false),
    new Turn(4, 5, 0, false),
    new Turn(4, 5, 0, true),
    new Turn(4, 5, 0, true),
    new Turn(4, 5, 0, true),
    new Turn(4, 5, 0, true),
    new Turn(4, 5, 0, true),
    new Turn(4, 5, 0, true),
    new Turn(4, 5, 0, true),
    new Turn(4, 5, 0, true),
    new Turn(4, 5, 0, true),
};

The output is:

Output
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?
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?
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)?
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?
5. Why does the goblin compute the path again on every turn instead of remembering the old one?

Made by Ivo Gergov as part of Evo Tech's campaign for accessible programming education ·