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.

MAP = """
################
#......#.......#
#......#.......#
#......#.......#
#......#.......#
#..............#
################
""".strip()




DIRECTIONS = [(0, -1), (1, 0), (0, 1), (-1, 0)]




def distances(level, start_x, start_y):
    # The wave: how many steps each cell is from the start.
    dist = [[-1] * level.width for _ in range(level.height)]
    dist[start_y][start_x] = 0
    queue = [Step(start_x, start_y)]
    head = 0
    while head < len(queue):
        cell = queue[head]
        head += 1
        for dx, dy in DIRECTIONS:
            next_x = cell.x + dx
            next_y = cell.y + dy
            if not level.walkable(next_x, next_y) or dist[next_y][next_x] != -1:
                continue
            dist[next_y][next_x] = dist[cell.y][cell.x] + 1
            queue.append(Step(next_x, next_y))
    return dist
level = Level(MAP)
dist = distances(level, ENEMY_X, ENEMY_Y)
print("The wave from the enemy (a = 10, b = 11, ...):")
print_wave(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 @dataclass(frozen=True) with x and y. We do not use list.pop(0): taking from the start of a list 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.

def find_path(level, start_x, start_y, goal_x, goal_y):
    came_from = [-1] * (level.width * level.height)
    start = start_y * level.width + start_x
    came_from[start] = start
    queue = [start]
    head = 0
    while head < len(queue):
        current = queue[head]
        head += 1
        x = current % level.width
        y = current // level.width
        if current != start and x == goal_x and y == goal_y:
            path = []
            index = current
            while index != start:
                path.append(Step(index % level.width, index // level.width))
                index = came_from[index]
            path.reverse()
            return path
        for dx, dy in DIRECTIONS:
            next_x = x + dx
            next_y = y + dy
            if not level.walkable(next_x, next_y):
                continue
            next_index = next_y * level.width + next_x
            if came_from[next_index] != -1:
                continue
            came_from[next_index] = current
            queue.append(next_index)
    return None




def distance(ax, ay, bx, by):
    return abs(ax - bx) + abs(ay - by)
level = Level(MAP)
path = find_path(level, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y)
print(f"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 {len(path)}")
dist = distances(level, ENEMY_X, ENEMY_Y)
print("The wave from the enemy (a = 10, b = 11, ...):")
print_wave(level, dist)
print("The path to the hero (*):")
print_path(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 None.

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

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




def enemy_turn(level, enemy, hero_x, hero_y, turn, hidden):
    # The enemy "sees" the hero if the path to the hero is short (in the game: the line of sight from the map lesson).
    path = find_path(level, enemy.x, enemy.y, hero_x, hero_y)
    path_length = NONE if path is None else len(path)
    sees = not hidden and path_length <= SIGHT
    if enemy.state == "sleep":
        if sees and path_length <= 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).
        dx, dy = DIRECTIONS[turn % 4]
        next_x = enemy.x + dx
        next_y = enemy.y + dy
        if level.walkable(next_x, next_y) and not (next_x == hero_x and next_y == hero_y):
            enemy.x = next_x
            enemy.y = next_y
        return
    if enemy.state == "chase":
        if enemy.life * 4 < enemy.max_life:
            enemy.state = "flee"
            return
        if not sees:
            enemy.lost += 1
            if enemy.lost > LOST:
                enemy.state = "wander"
                return
        else:
            enemy.lost = 0
        if path_length <= 1:
            return
        if path_length <= FAR:
            enemy.x = path[0].x
            enemy.y = path[0].y
        return
    # Flees: the step that takes it farthest from the hero.
    best_x = enemy.x
    best_y = enemy.y
    best_distance = distance(enemy.x, enemy.y, hero_x, hero_y)
    for dx, dy in DIRECTIONS:
        next_x = enemy.x + dx
        next_y = enemy.y + dy
        if not level.walkable(next_x, next_y) or (next_x == hero_x and next_y == hero_y):
            continue
        away = distance(next_x, next_y, hero_x, hero_y)
        if away > best_distance:
            best_distance = away
            best_x = next_x
            best_y = next_y
    enemy.x = best_x
    enemy.y = best_y

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(MAP)
enemy = Enemy(ENEMY_X, ENEMY_Y, "sleep", ENEMY_LIFE)
for index, (hero_x, hero_y, hit, hidden) in enumerate(SCRIPT):
    enemy.life = max(0, enemy.life - hit)
    before = enemy.state
    enemy_turn(level, enemy, hero_x, hero_y, index + 1, hidden)
    path = find_path(level, enemy.x, enemy.y, hero_x, hero_y)
    length = NONE if path is None else len(path)
    state = before if before == enemy.state else before + " → " + enemy.state
    print(f"turn {index + 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.

def find_path(level, start_x, start_y, goal_x, goal_y):
    came_from = [-1] * (level.width * level.height)
    start = start_y * level.width + start_x
    came_from[start] = start
    queue = [start]
    head = 0
    while head < len(queue):
        current = queue[head]
        head += 1
        x = current % level.width
        y = current // level.width
        if current != start and x == goal_x and y == goal_y:
            path = []
            index = current
            while index != start:
                path.append(Step(index % level.width, index // level.width))
                index = came_from[index]
            path.reverse()
            return path
        for dx, dy in DIRECTIONS:
            next_x = x + dx
            next_y = y + dy
            if not level.walkable(next_x, next_y):
                continue
            next_index = next_y * level.width + next_x
            if came_from[next_index] != -1:
                continue
            came_from[next_index] = current
            queue.append(next_index)
    return None




def enemy_turn(level, enemy, hero_x, hero_y, turn, hidden):
    # The enemy "sees" the hero if the path to the hero is short (in the game: the line of sight from the map lesson).
    path = find_path(level, enemy.x, enemy.y, hero_x, hero_y)
    path_length = NONE if path is None else len(path)
    sees = not hidden and path_length <= SIGHT
    if enemy.state == "sleep":
        if sees and path_length <= 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).
        dx, dy = DIRECTIONS[turn % 4]
        next_x = enemy.x + dx
        next_y = enemy.y + dy
        if level.walkable(next_x, next_y) and not (next_x == hero_x and next_y == hero_y):
            enemy.x = next_x
            enemy.y = next_y
        return
    if enemy.state == "chase":
        if enemy.life * 4 < enemy.max_life:
            enemy.state = "flee"
            return
        if not sees:
            enemy.lost += 1
            if enemy.lost > LOST:
                enemy.state = "wander"
                return
        else:
            enemy.lost = 0
        if path_length <= 1:
            return
        if path_length <= FAR:
            enemy.x = path[0].x
            enemy.y = path[0].y
        return
    # Flees: the step that takes it farthest from the hero.
    best_x = enemy.x
    best_y = enemy.y
    best_distance = distance(enemy.x, enemy.y, hero_x, hero_y)
    for dx, dy in DIRECTIONS:
        next_x = enemy.x + dx
        next_y = enemy.y + dy
        if not level.walkable(next_x, next_y) or (next_x == hero_x and next_y == hero_y):
            continue
        away = distance(next_x, next_y, hero_x, hero_y)
        if away > best_distance:
            best_distance = away
            best_x = next_x
            best_y = next_y
    enemy.x = best_x
    enemy.y = best_y
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.
DIRECTIONS = [[0, -1], [1, 0], [0, 1], [-1, 0]]




# is_passable(x, y) and is_goal(x, y) are functions; returns the path without the start, or None.
def find_path(level, start_x, start_y, is_passable, is_goal):
    came_from = [-1] * (level.width * level.height)
    start_index = start_y * level.width + start_x
    came_from[start_index] = start_index
    queue = [start_index]
    head = 0
    while head < len(queue):
        current = queue[head]
        head += 1
        x = current % level.width
        y = current // level.width
        if current != start_index and is_goal(x, y):
            path = []
            index = current
            while index != start_index:
                path.append(SimpleNamespace(x=index % level.width, y=index // level.width))
                index = came_from[index]
            path.reverse()
            return path
        for direction in DIRECTIONS:
            next_x = x + direction[0]
            next_y = y + direction[1]
            if not level.in_bounds(next_x, next_y):
                continue
            next_index = next_y * level.width + next_x
            if came_from[next_index] != -1:
                continue
            if not is_passable(next_x, next_y) and not is_goal(next_x, next_y):
                continue
            came_from[next_index] = current
            queue.append(next_index)
    return None




def distance(ax, ay, bx, by):
    return abs(ax - bx) + 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.
def enemy_sees_hero(level, enemy, hero):
    if distance(enemy.x, enemy.y, hero.x, hero.y) > 8:
        return False
    return line_of_sight(level, enemy.x, enemy.y, hero.x, hero.y)




def can_enemy_step(game, level, x, y):
    if not level.is_walkable(x, y):
        return False
    if level.enemy_at(x, y) is not None or level.npc_at(x, y) is not None:
        return False
    return not (game.hero.x == x and game.hero.y == y)




def move_enemy(game, level, enemy, x, y):
    if enemy.has_effect('bleed'):
        level.add_blood(enemy.x, enemy.y)
    enemy.x = x
    enemy.y = y




def enemy_turn_on_map(game, level, enemy):
    hero = game.hero
    rng = game.rng
    sees = enemy_sees_hero(level, enemy, hero)
    hero_sees_it = level.visible[enemy.y][enemy.x]
    if enemy.calm > 0:
        enemy.calm -= 1
    if enemy.state == 'sleep':
        if sees and distance(enemy.x, enemy.y, hero.x, hero.y) <= 5 and rng.chance(50):
            enemy.state = 'chase'
            if hero_sees_it:
                game.say(t('ai.wakes', {'name': enemy.name}))
        return
    if enemy.state == 'guard':
        if sees and 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 and enemy.calm == 0:
            enemy.state = 'chase'
            enemy.lost_turns = 0
            if hero_sees_it:
                game.say(t('ai.notices', {'name': enemy.name}))
            return
        roll = rng.next_int(5)
        if roll < 4:
            next_x = enemy.x + DIRECTIONS[roll][0]
            next_y = enemy.y + DIRECTIONS[roll][1]
            if can_enemy_step(game, level, next_x, next_y):
                move_enemy(game, level, enemy, next_x, next_y)
        return
    if enemy.state == 'chase':
        if enemy.kind.special != 'warden' and enemy.is_heavily_wounded():
            enemy.state = 'flee'
            if hero_sees_it:
                game.say(t('ai.flees', {'name': enemy.name}))
            return
        if not sees:
            enemy.lost_turns += 1
            if enemy.lost_turns > 5:
                enemy.state = 'wander'
                return
        else:
            enemy.lost_turns = 0
        if distance(enemy.x, enemy.y, hero.x, hero.y) <= 1:
            return
        path = find_path(level, enemy.x, enemy.y,
                         lambda x, y: can_enemy_step(game, level, x, y),
                         lambda x, y: x == hero.x and y == hero.y)
        if path is not None and len(path) > 1 and len(path) <= 20:
            move_enemy(game, level, enemy, path[0].x, path[0].y)
        return
    # flee: the step that moves farthest away from the hero
    best_x = enemy.x
    best_y = enemy.y
    best_distance = distance(enemy.x, enemy.y, hero.x, hero.y)
    for direction in DIRECTIONS:
        next_x = enemy.x + direction[0]
        next_y = enemy.y + direction[1]
        if not can_enemy_step(game, level, next_x, next_y):
            continue
        away = distance(next_x, next_y, hero.x, hero.y)
        if away > best_distance:
            best_distance = away
            best_x = next_x
            best_y = next_y
    if best_x != enemy.x or best_y != enemy.y:
        move_enemy(game, level, enemy, best_x, best_y)

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:
    def __init__(self, attack):
        self.best = attack
        self.best_score = 40
        self.trace = attack + " 40"


    def consider(self, score, action):
        self.trace += ", " + action + " " + str(score)
        if score > self.best_score:
            self.best = action
            self.best_score = score




def percent(a, b):
    return a * 100 // b




def choose_enemy_action(hero, hero_poisoned, allies, heal_wait, spit_wait):
    chooser = Chooser("attack " + hero.name)
    weakest = None
    for ally in allies:
        if percent(ally.hp, ally.max_hp) < 50 and (weakest is None or percent(ally.hp, ally.max_hp) < percent(weakest.hp, weakest.max_hp)):
            weakest = ally
    if weakest is not None and heal_wait == 0:
        chooser.consider(80, "heal " + weakest.name)
    if spit_wait == 0 and not hero_poisoned:
        chooser.consider(60, "spit at " + hero.name)
    return chooser




def weakest_of(enemies):
    weakest = None
    for enemy in enemies:
        if weakest is None or enemy.hp < weakest.hp:
            weakest = enemy
    return weakest




def choose_hero_action(hero, has_potion, enemies):
    chooser = Chooser("attack " + weakest_of(enemies).name)
    if percent(hero.hp, hero.max_hp) < 35 and has_potion:
        chooser.consider(90, "potion")
    return chooser




def show(chooser):
    print(chooser.trace + " → " + chooser.best)

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

hero = Fighter("Iva", 30, 40)
hurt_hero = Fighter("Iva", 10, 40)
wounded_rat = Fighter("rat", 3, 9)
rat = Fighter("rat", 9, 9)
goblin = Fighter("goblin", 16, 16)
wounded_goblin = Fighter("goblin", 6, 16)
cultist = Fighter("cultist", 3, 20)


show(choose_enemy_action(hero, False, [wounded_rat, goblin], 0, 0))
show(choose_enemy_action(hero, False, [wounded_rat, goblin], 2, 0))
show(choose_enemy_action(hero, True, [rat, goblin], 0, 0))
show(choose_enemy_action(hero, False, [wounded_rat, wounded_goblin], 0, 3))
show(choose_hero_action(hero, True, [wounded_rat, goblin, cultist]))
show(choose_hero_action(hurt_hero, True, [wounded_rat, 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:
    def __init__(self, attack):
        self.best = attack
        self.best_score = 40
        self.trace = attack + " 40"

    def consider(self, score, action):
        self.trace += ", " + action + " " + str(score)
        if score  self.best_score:
            self.best = action
            self.best_score = 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.
def choose_enemy_action(battle, enemy):
    hero = battle.hero
    best = AttackAction(enemy, hero)
    best_score = 40


    def consider(score, action):
        nonlocal best, best_score
        if score > best_score:
            best = action
            best_score = score


    special = enemy.kind.special
    if special == 'shaman':
        weakest = None
        for ally in battle.alive_enemies():
            if percent(ally.hp, ally.max_hp()) < 50 and (weakest is None or percent(ally.hp, ally.max_hp()) < percent(weakest.hp, weakest.max_hp())):
                weakest = ally
        if weakest is not None and enemy.cooldown_of('heal') == 0:
            consider(80, SpecialAction(enemy, 'heal', weakest))
        if enemy.cooldown_of('shaman') == 0 and not hero.has_effect('poison'):
            consider(60, SpecialAction(enemy, 'spit', hero))
    elif special == 'firebolt' and enemy.cooldown_of('firebolt') == 0:
        consider(65, SpecialAction(enemy, 'firebolt', hero))
    elif special == 'rend' and enemy.cooldown_of('rend') == 0 and not hero.has_effect('bleed'):
        consider(55, SpecialAction(enemy, 'rend', hero))
    elif special == 'slam' and enemy.cooldown_of('slam') == 0:
        consider(60, SpecialAction(enemy, 'slam', hero))
    elif special == 'warden':
        if enemy.phase == 1 and enemy.hp * 2 < enemy.max_hp():
            consider(100, SpecialAction(enemy, 'summon', hero))
        elif enemy.cooldown_of('warden') == 0:
            consider(60, SpecialAction(enemy, 'slam', hero))
    return best




def usable_skills(hero):
    result = []
    for skill_id in hero.skills:
        skill = SKILLS[skill_id]
        if hero.mana >= skill.mana and hero.cooldown_of(skill.id) == 0:
            result.append(skill)
    return result




def weakest_enemy(battle):
    weakest = None
    for enemy in battle.alive_enemies():
        if weakest is None or enemy.hp < weakest.hp:
            weakest = enemy
    return weakest




# The hero on autopilot (the simulation): the same utility scoring.
def choose_hero_action(battle):
    hero = battle.hero
    target = weakest_enemy(battle)
    best = AttackAction(hero, target)
    best_score = 40


    def consider(score, action):
        nonlocal best, best_score
        if score > best_score:
            best = action
            best_score = score


    life_share = percent(hero.hp, hero.max_hp())
    if life_share < 35 and hero.inventory.count('potion_heal') > 0:
        consider(90, ItemAction(hero, 'potion_heal'))
    if (hero.has_effect('poison') or hero.has_effect('bleed')) and life_share < 50 and hero.inventory.count('antidote') > 0:
        consider(70, ItemAction(hero, 'antidote'))
    many = len(battle.alive_enemies()) >= 2
    for skill in usable_skills(hero):
        score = 0
        if skill.kind == 'heal':
            score = 75 if life_share < 50 else 0
        elif skill.kind == 'buff':
            score = 0 if hero.has_effect(skill.effect) else 50
        elif skill.kind == 'debuff':
            score = 55 if many else 45
        elif skill.target == 'all':
            score = 65 if many else 52
        else:
            score = 55
        consider(score, 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?

TINY = """
#######
#.#...#
#...#.#
#######
""".strip()
level = Level(TINY)
print_wave(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(MAP)
path = find_path(level, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y)
print(f"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 {len(path)}")
print("The path to the hero (*):")
print_path(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):

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:

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 ·