Enemigos que piensan

En resumen: Un enemigo en el mapa es una máquina de estados (duerme, deambula, persigue, huye) que persigue por el camino más corto hallado con búsqueda en anchura; en el combate elige la acción con la puntuación de utilidad más alta.

Problema

El goblin que choca contra la pared

Hasta ahora los enemigos de la mina estaban donde el mapa los había puesto. Un jugador que ve eso entiende enseguida que el juego es de cartón. Un enemigo vivo tiene que hacer tres cosas: decidir qué hacer (dormir, deambular, perseguir, huir), encontrar su camino y elegir en el combate.

La persecución más simple es: «da el paso que más te acerque al héroe». Aquí hay un goblin (g) y un héroe (@) a ambos lados de una pared con un hueco abajo:

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

En línea recta hay 6 celdas, pero la pared está en medio. La persecución simple solo compara la distancia: el goblin quiere ir a la izquierda, allí hay una pared, y se queda pegado a ella. Aquí se detiene:

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

Una línea recta no sabe nada de paredes. Hace falta un camino que las rodee, y el camino más corto en una cuadrícula se encuentra con la búsqueda en anchura. La lección la construye primero en el nivel pequeño de 16 × 7 (el hueco está abajo), luego pone encima una máquina de estados que decide cuándo se mueve el enemigo y, por último, muestra el segundo cerebro del juego: la puntuación de utilidad en el combate.

La idea

La ola: a cuántos pasos está cada celda

Imagina que lanzas una piedra al agua: desde donde cayó se extienden círculos. La búsqueda en anchura hace lo mismo sobre una cuadrícula. Empieza en el goblin: está a distancia 0. Sus vecinas están a 1. Las vecinas de las vecinas (aún no vistas) están a 2. Y así hasta que la ola cubre todo. Cada celda recibe un número: a cuántos pasos está del goblin por el suelo, no en línea recta.

Hace falta una cola: las celdas que la ola ha alcanzado pero aún no ha examinado. Del principio de la cola sale la celda más antigua (por eso la ola avanza en orden) y sus vecinas nuevas van al final. Una celda que ya tiene número no se añade por segunda vez.

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


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


def distances(level, start_x, start_y):
    # La ola: a cuántos pasos está cada celda del inicio.
    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("La ola desde el enemigo (a = 10, b = 11, ...):")
print_wave(level, dist)

Salida

La ola desde el enemigo (a = 10, b = 11, ...):
################
#dcba98#2345678#
#cba987#1234567#
#ba9876#0123456#
#a98765#1234567#
#98765432345678#
################

a es 10, b es 11 y así sucesivamente. El goblin está en 0 (junto a la pared, en el borde izquierdo de la sala derecha) y la pared es #. La ola primero llena la sala derecha, luego pasa por el hueco de abajo y solo entonces sube a la izquierda. El héroe en (2, 3) está en a, es decir, a 10 pasos del goblin, aunque en línea recta está a 6: el número es la distancia real por el suelo.

Step es un @dataclass(frozen=True) con x e y. No usamos list.pop(0): sacar del principio de una lista desplaza todos los demás elementos, así que avanzamos con un índice head.

La comprobación dist[nextY][nextX] != -1 es todo el «ya estuvo aquí»: la celda tiene un número, así que está en la cola o ha estado en ella. Sin ella la ola retrocedería y nunca terminaría.

Más precisamente, para curiosos

Las cuatro direcciones están en un orden fijo: arriba, derecha, abajo, izquierda. El orden no cambia las distancias (son iguales con cualquier orden), pero cambia cuál de los caminos igual de cortos se encuentra. En el juego el orden es fijo justo por eso: la misma entrada debe dar el mismo camino en Java, C#, Python y JavaScript; si no, la grabación de un combate y la comprobación con el recorrido grabado se desviarían.

Esta ola de distancias se llama distance field (también Dijkstra map): una búsqueda desde el héroe da un número para cada celda, y cada enemigo simplemente da un paso hacia la vecina con el número menor. Con muchos enemigos eso es mucho más barato que una búsqueda para cada uno.

La idea

El camino: de dónde vino cada celda

Los números muestran la distancia, pero el enemigo necesita los pasos. Añadimos una tabla: para cada celda recordamos de qué celda vino la ola. Cuando la ola llega a la meta, retrocedemos: la meta, de dónde vino, de dónde vino esa, y así hasta el inicio. Resulta el camino de atrás hacia delante, por eso al final lo invertimos.

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"el enemigo ({ENEMY_X}, {ENEMY_Y}), el héroe ({HERO_X}, {HERO_Y}): en línea recta {distance(ENEMY_X, ENEMY_Y, HERO_X, HERO_Y)}, por el camino {len(path)}")
dist = distances(level, ENEMY_X, ENEMY_Y)
print("La ola desde el enemigo (a = 10, b = 11, ...):")
print_wave(level, dist)
print("El camino hasta el héroe (*):")
print_path(level, path, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y)

Salida

el enemigo (8, 3), el héroe (2, 3): en línea recta 6, por el camino 10
La ola desde el enemigo (a = 10, b = 11, ...):
################
#dcba98#2345678#
#cba987#1234567#
#ba9876#0123456#
#a98765#1234567#
#98765432345678#
################
El camino hasta el héroe (*):
################
#......#.......#
#......#.......#
#.@****#g......#
#.....*#*......#
#.....***......#
################

El camino (*) baja por el hueco, sube junto a la pared a la sala izquierda y avanza a la izquierda hasta el héroe: 10 pasos frente a 6 en línea recta. La pared no molesta al algoritmo, porque la ola simplemente no entra en ella.

La búsqueda termina en cuanto saca la meta de la cola: después ya no necesita nada. Por eso la primera meta encontrada es la más cercana. Y si no hay camino (el héroe está tras una pared sin hueco), la cola se acaba y la función devuelve None.

Más precisamente, para curiosos

El primer paso del camino es solo una celda, pero el enemigo lo da y vuelve a preguntar en el turno siguiente. Así no puede quedarse pegado a un camino viejo: el héroe se ha movido, otro enemigo ha ocupado la celda, la puerta se ha cerrado.

El coste es bajo. El nivel del juego es de 50 × 20, unas 1000 celdas, y aunque se visiten todas, son unos miles de comprobaciones sencillas por enemigo y turno.

La idea

Una máquina de estados: duerme, deambula, persigue, huye

¿Cuándo usa el enemigo el camino? Depende de lo que sea ahora. Un durmiente no se mueve. Un vagabundo deambula. Un perseguidor sigue el camino. Uno que huye se aleja. Esto es una máquina de estados: un enemigo tiene un estado (una cadena: "sleep", "wander", "chase", "flee"), y en cada turno se dice «en este estado, en esta situación, qué hago y a qué estado paso».

De	A	Cuándo
sleep	chase	el camino hasta el héroe es como mucho 5
wander	chase	el enemigo «ve» al héroe: el camino es como mucho 8
chase	wander	más de 3 turnos sin verlo (lost > LOST)
chase	flee	vida × 4 < vida máxima (menos de un cuarto)

El programa usa el mismo mapa y un enemigo con 16 de vida. «Ver» está simplificado: un enemigo ve al héroe si el camino hasta él es como mucho 8. En el juego es una línea de visión de la lección del mapa (hasta 8 celdas), y aquí el camino da lo mismo sin otro algoritmo. El guion está en SCRIPT: el héroe se acerca, se esconde tras una esquina (hidden), vuelve a aparecer y por fin recibe un golpe (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):
    # El enemigo «ve» al héroe si el camino hasta él es corto (en el juego: la línea de visión de la lección del mapa).
    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
        # Deambula en el orden de las direcciones (el juego tira un dado).
        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
    # Huye: el paso que más lo aleja del héroe.
    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

Cada estado es una rama de un if que retorna al final: en un turno ocurre exactamente una cosa. Se lee de arriba abajo como la tabla. El contador lost es la memoria de la máquina: sin él, el enemigo olvidaría al héroe en cuanto se esconde por primera vez.

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"turno {index + 1}: {state}, enemigo ({enemy.x}, {enemy.y}), camino {length}, vida {enemy.life}")

Salida

turno 1: sleep, enemigo (8, 3), camino 7, vida 16
turno 2: sleep, enemigo (8, 3), camino 6, vida 16
turno 3: sleep → chase, enemigo (8, 3), camino 5, vida 16
turno 4: chase, enemigo (8, 4), camino 4, vida 16
turno 5: chase, enemigo (8, 5), camino 3, vida 16
turno 6: chase, enemigo (7, 5), camino 2, vida 16
turno 7: chase, enemigo (6, 5), camino 1, vida 16
turno 8: chase → wander, enemigo (6, 5), camino 1, vida 16
turno 9: wander, enemigo (7, 5), camino 2, vida 16
turno 10: wander → chase, enemigo (7, 5), camino 2, vida 16
turno 11: chase, enemigo (6, 5), camino 1, vida 16
turno 12: chase → flee, enemigo (6, 5), camino 1, vida 3
turno 13: flee, enemigo (7, 5), camino 2, vida 3
turno 14: flee, enemigo (8, 5), camino 3, vida 3
turno 15: flee, enemigo (9, 5), camino 4, vida 3

Turno 3: el camino pasa a 5 y sleep → chase. Turnos 4–7: el goblin avanza por el camino. En el turno 8 lost supera 3 y pasa a wander; en el turno 9 da un paso como vagabundo y en el turno 10 vuelve a ver al héroe. En el turno 12 el héroe lo golpea y le quita 13 de sus 16 de vida: 3 × 4 = 12 < 16 y chase → flee. Huir no usa el camino: de las cuatro vecinas toma la que más lo aleja (away > bestDistance).

Más precisamente, para curiosos

¿Por qué cadenas y no un enum? El canon usa cadenas porque los estados se escriben en la partida guardada y se leen de un archivo. Así, un nuevo tipo de enemigo con un estado nuevo no necesita un tipo nuevo. El precio es que un error en el nombre ("chaes") no se detecta al compilar.

Una máquina de estados es la forma más simple de describir un comportamiento, pero crece: diez estados con cinco transiciones cada uno son cincuenta líneas difíciles de leer. Entonces se pasa a un behavior tree o a la puntuación de utilidad, como la del combate más abajo.

Míralo

La persecución en acción

Aquí está lo mismo turno a turno. El goblin duerme al otro lado de la pared. El héroe se acerca; el camino pasa a 5 y el goblin despierta. Entonces se ve la búsqueda: una ola parte del goblin y rodea la pared por el hueco hasta llegar al héroe. Después el goblin avanza, pierde al héroe, lo vuelve a notar y por fin huye.

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):
    # El enemigo «ve» al héroe si el camino hasta él es corto (en el juego: la línea de visión de la lección del mapa).
    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
        # Deambula en el orden de las direcciones (el juego tira un dado).
        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
    # Huye: el paso que más lo aleja del héroe.
    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

Paso a paso, en palabras

1. El goblin duerme en (8, 3). El héroe está al otro lado de la pared. En el turno 2 el camino hasta el héroe es 6, y para despertar hace falta como máximo 5: el goblin sigue durmiendo, aunque en línea recta el héroe está a solo 4 celdas.
2. Turno 3: el héroe está en (6, 4). En línea recta, a través de la pared, son 3 celdas, pero el camino es 5 ≤ 5: sleep → chase.
3. Búsqueda en anchura desde el goblin: una cola de la que sale primero la celda más antigua. La ola se extiende por el suelo celda a celda y rodea la pared por el hueco. Salen de la cola 27 de 66 celdas hasta llegar al héroe.
4. El héroe está encontrado. Desde el héroe se retrocede por cameFrom, celda a celda hasta el goblin, y se invierte el camino: 5 pasos. El goblin dará el primero.
5. En cada turno el goblin pregunta de nuevo y da solo el primer paso del camino: 4, 3, 2, 1 hasta el héroe. Si el héroe se mueve, el camino es otro.
6. El héroe se oculta tras una esquina (la bola pálida). El goblin aún avanza hacia él, pero cuenta: tras 3 turnos sin verlo (lost > 3) en el turno 8 chase → wander.
7. Turno 9: el goblin deambula. La dirección sale del número de turno (el juego tira un dado), así que para el héroe el paso parece aleatorio, no dirigido.
8. Turno 10: el héroe aparece de nuevo, el camino es 2 ≤ 8: wander → chase. El goblin vuelve a perseguirlo y llega hasta el héroe.
9. Turno 12: el golpe del héroe deja al goblin con 3 de 16 de vida. La prueba es vida × 4 < vida máxima: 12 < 16, así que chase → flee.
10. Huir no necesita camino ni búsqueda: de los cuatro vecinos toma el que más lo aleja del héroe (2, 3, 4 celdas).

El código junto a la escena es findPath y enemyTurn del programa. En cada paso se iluminan las líneas que trabajan en ese momento.

La idea

En el juego

Lo que construimos es lo mismo que en el canon, solo que más pequeño. Aquí está la búsqueda en anchura real. Recibe dos funciones en lugar de una meta ya hecha y un mapa de lo transitable ya hecho: isPassable dice dónde puede pisar un enemigo (no a través de otros enemigos ni del héroe), e isGoal dice cuál es la celda meta:

# Búsqueda en anchura: una cola de casillas, cada una recuerda de dónde vino. El primer objetivo encontrado es
# el más cercano. Las direcciones van en un orden fijo (arriba, derecha, abajo, izquierda), así que el camino es el mismo
# en todos los lenguajes.
DIRECTIONS = [[0, -1], [1, 0], [0, 1], [-1, 0]]


# is_passable(x, y) e is_goal(x, y) son funciones; devuelve el camino sin el inicio, o 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)

Y aquí está la máquina de estados en el mapa. Además de nuestros estados hay guard (un guardián en su puesto), calm (cuando el héroe huye de un combate, los enemigos deambulan y no lo notan durante 6 turnos) y un dado para despertar:

# La IA del mapa es una máquina de estados: duerme → deambula → persigue → huye con poca vida.
# El Guardián se queda en su puesto (guard) hasta que ve al héroe.
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: el paso que más aleja del héroe
    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)

Las diferencias con nuestro programa son pocas, pero importantes:

• enemySeesHero usa la línea de visión (Bresenham de la lección del mapa), no la longitud de un camino. Así, un enemigo puede verte por una puerta abierta, pero no a través de una pared.
• Un durmiente despierta con un 50 % de probabilidad por turno (rng.chance(50)), y un vagabundo se mueve solo en 4 de 5 tiradas del dado (rng.nextInt(5)). El dado viene del generador con semilla del juego, así que el juego sigue siendo repetible.
• lostTurns > 5, no 3. El camino se limita con path.length <= 20: un enemigo más lejano no persigue.
• El jefe (warden) nunca huye, por muy herido que esté.
• Los mensajes (ai.wakes, ai.notices, ai.flees) solo se escriben si el héroe ve al enemigo: el juego no revela más de lo que ves.

La idea

En el combate: puntuación de utilidad

En el mapa un enemigo tiene un estado. En el combate no hay adónde ir: hay una elección entre varias acciones, y tiene que ser sensata. Una máquina de estados aquí significaría una línea por cada par «situación — acción». En lugar de eso, cada acción recibe un número: cuán útil es ahora. El enemigo toma el mayor.

La regla es corta: lo predeterminado es un ataque con 40. Cada otra acción posible tiene su propia puntuación: curar a un amigo herido 80, escupir 60. Si una puntuación es mayor que la mejor hasta ahora, la acción la reemplaza.

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("ataque a " + 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, "cura a " + weakest.name)
    if spit_wait == 0 and not hero_poisoned:
        chooser.consider(60, "escupe a " + 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("ataque a " + weakest_of(enemies).name)
    if percent(hero.hp, hero.max_hp) < 35 and has_potion:
        chooser.consider(90, "poción")
    return chooser


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

El programa muestra seis decisiones. Cada línea es: las acciones consideradas con sus puntuaciones, una flecha y la elegida.

hero = Fighter("Iva", 30, 40)
hurt_hero = Fighter("Iva", 10, 40)
wounded_rat = Fighter("rata", 3, 9)
rat = Fighter("rata", 9, 9)
goblin = Fighter("goblin", 16, 16)
wounded_goblin = Fighter("goblin", 6, 16)
cultist = Fighter("cultista", 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]))

Salida

ataque a Iva 40, cura a rata 80, escupe a Iva 60 → cura a rata
ataque a Iva 40, escupe a Iva 60 → escupe a Iva
ataque a Iva 40 → ataque a Iva
ataque a Iva 40, cura a rata 80 → cura a rata
ataque a rata 40 → ataque a rata
ataque a rata 40, poción 90 → poción

Las primeras cuatro son del chamán. Con una rata herida y la cura lista, cura (80 > 60 > 40). Si la cura tiene que esperar (healWait es 2), escupe (60). Si el héroe ya está envenenado y ningún amigo está herido, queda el ataque (40). En la cuarta línea están heridos tanto la rata (33 %) como el goblin (37 %); se cura el porcentaje menor, es decir, la rata.

Las dos últimas líneas son del héroe en piloto automático (en la simulación del juego y en el combate automático). Golpea al más débil: el que tiene menos vida. La rata (3) y el cultista (3) están empatados y gana el primero, porque < no reemplaza en un empate. Con un 25 % de vida (menos del 35 %) y con una poción, la puntuación de la poción (90) supera 40 y el héroe bebe.

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

Comprobar

Los números 80, 60, 40 no son una ley. Son un ajuste: si el chamán cura demasiado a menudo, el juego se vuelve aburrido, y si lo hace muy poco, imposible. Por eso la última lección (el juego entero y el equilibrio) ejecuta mil combates para afinar estos números.

# En combate la IA puntúa cada acción posible con un número (utilidad) y elige
# la más útil: se cura con poca vida, usa una habilidad cuando está lista y, si no, ataca.
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


# El héroe en piloto automático (la simulación): la misma puntuación de utilidad.
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

El canon añade más: la flecha de fuego del cultista 65, desgarrar 55 (solo si el héroe aún no sangra), un golpe pesado 60 y el jefe, que con menos de la mitad de vida invoca ayudantes con una puntuación de 100. Pero la forma es la misma: consider(puntuación, acción). Las acciones son objetos de la lección sobre habilidades y acciones como comandos: AttackAction, SkillAction y así sucesivamente. Por eso un enemigo, un héroe en piloto automático y una simulación eligen de la misma manera.

Pruébalo

Predice la salida

Un mapa pequeño con un obstáculo. La búsqueda empieza en (1, 1). ¿Qué imprime el programa?

TINY = """
#######
#.#...#
#...#.#
#######
""".strip()
level = Level(TINY)
print_wave(level, distances(level, 1, 1))

Respuesta

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

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

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

Comprobar

Pruébalo

Encuentra el error

Un colega cambió la búsqueda y ahora el camino hasta el héroe es más largo:

level = Level(MAP)
path = find_path(level, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y)
print(f"el enemigo ({ENEMY_X}, {ENEMY_Y}), el héroe ({HERO_X}, {HERO_Y}): en línea recta {distance(ENEMY_X, ENEMY_Y, HERO_X, HERO_Y)}, por el camino {len(path)}")
print("El camino hasta el héroe (*):")
print_path(level, path, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y)

Salida

el enemigo (8, 3), el héroe (2, 3): en línea recta 6, por el camino 12
El camino hasta el héroe (*):
################
#......#.......#
#......#.......#
#*@....#g......#
#*.....#*......#
#********......#
################

El camino es de 12 pasos en lugar de 10 y da un rodeo innecesario. ¿Qué línea toma las celdas del extremo equivocado?

Elige la línea con el error.

1def find_path(level, start_x, start_y, goal_x, goal_y):2 came_from = [-1] * (level.width * level.height)3 start = start_y * level.width + start_x4 came_from[start] = start5 queue = [start]6 while queue:7 current = queue.pop()8 x = current % level.width9 y = current // level.width10 if current != start and x == goal_x and y == goal_y:11 path = []12 index = current13 while index != start:14 path.append(Step(index % level.width, index // level.width))15 index = came_from[index]16 path.reverse()17 return path18 for dx, dy in DIRECTIONS:19 next_x = x + dx20 next_y = y + dy21 if not level.walkable(next_x, next_y):22 continue23 next_index = next_y * level.width + next_x24 if came_from[next_index] != -1:25 continue26 came_from[next_index] = current27 queue.append(next_index)28 return None

Comprobar

Más precisamente

Con más precisión: A*, campos y puntos débiles

A*. La búsqueda en anchura mira por igual en todas las direcciones, incluso lejos de la meta. A* añade una pista: para cada celda calcula f = g + h, donde g son los pasos hasta ahora y h es una estimación de cuántos quedan (casi siempre la distancia en línea recta a lo largo de los ejes). Toma la celda con el menor f, la que parece más prometedora. Hace falta una cola de prioridad en lugar de una común, y el resultado es el mismo camino más corto mientras h no sobrestime. En nuestro mapa, del goblin al héroe, la búsqueda en anchura saca 59 celdas de la cola y A* saca 25. En una sala abierta, de (2, 2) a (6, 2), son 19 frente a 5. Los números vienen del modelo de la lección (aquí A* no está en los cuatro lenguajes). El canon usa búsqueda en anchura: los niveles son de 50 × 20, no hay costes de movimiento, y A* cuesta una cola de prioridad y más código en cuatro lenguajes. Si el agua poco profunda cuesta 2 (la lección del mapa), la búsqueda en anchura ya no es correcta y se pasa a Dijkstra; si los niveles son grandes y abiertos, a A*.

Un campo en lugar de un camino. Una búsqueda desde el héroe da un número para cada celda (la ola de este mapa). Entonces cada enemigo da un paso hacia la vecina con el número menor y no busca por su cuenta. Con veinte enemigos es una búsqueda por turno en lugar de veinte. Muchos juegos con hordas lo hacen así. Para huir se va al revés: hacia el número mayor.

Huir es tonto. Nuestro fugitivo toma el paso que más aumenta la distancia. En la escena corre por la fila de abajo, pero en una esquina se queda sin movimiento y se queda parado: no hay un camino que piense por adelantado. Una huida inteligente sigue el campo de distancias (desde el héroe), donde todo el panorama se ve de una vez y se evita la esquina.

Una máquina de estados crece con sus transiciones. Cada comportamiento nuevo es un estado nuevo y transiciones hacia él y desde él (mira el ejercicio: guard y home son dos estados con varias transiciones). La puntuación de utilidad crece con más suavidad: una acción nueva es un consider nuevo, sin transiciones.

Una puntuación es un número tosco. Aquí las puntuaciones son 40, 60, 80, escritas a mano. Los sistemas mejores multiplican varias «consideraciones» con curvas (cuán herido está, a qué distancia, cuánto maná tiene) y las puntuaciones cambian con suavidad. La regla sigue siendo la misma: el número decide, y la decisión es repetible.

Ejercicio

El guardián que vuelve

Resuelve la tarea en tu editor. Parte del programa de la máquina de estados.

Un guardián en su puesto. Cambia la máquina para que un enemigo empiece en el estado guard en su lugar. El guardián está quieto y no deambula. Cuando el camino hasta el héroe es como mucho 6, pasa a chase. Persigue por el camino; si lost supera 3, pasa a home y vuelve a su puesto por el camino más corto (un paso por turno), y cuando llega vuelve a ser guard. El guardián no tiene sleep, wander ni flee. El héroe no golpea: no hay hit.

El mapa es el mismo, el guardián está en su puesto (8, 3) y el guion es este (héroe, hit, hidden; el héroe está oculto del turno 4 al turno 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),
]

La salida es:

Salida

turno 1: guard, enemigo (8, 3), camino 7, vida 16
turno 2: guard → chase, enemigo (8, 3), camino 6, vida 16
turno 3: chase, enemigo (8, 4), camino 5, vida 16
turno 4: chase, enemigo (8, 5), camino 4, vida 16
turno 5: chase, enemigo (7, 5), camino 3, vida 16
turno 6: chase, enemigo (6, 5), camino 2, vida 16
turno 7: chase → home, enemigo (6, 5), camino 2, vida 16
turno 8: home, enemigo (7, 5), camino 3, vida 16
turno 9: home, enemigo (8, 5), camino 4, vida 16
turno 10: home, enemigo (8, 4), camino 5, vida 16
turno 11: home → guard, enemigo (8, 3), camino 6, vida 16
turno 12: guard, enemigo (8, 3), camino 6, vida 16

Más tareas

• Calma. En el canon, tras una huida de un combate los enemigos pasan a wander con calm = 6: mientras calm sea mayor que 0, no notan al héroe. Añade al enemigo un contador calm que disminuya en cada turno.
• Rodear a otro enemigo. Dale a findPath una lista de celdas ocupadas (los demás enemigos) y trátalas como paredes. ¿Qué pasa si dos enemigos persiguen al héroe en un pasillo estrecho?
• Un campo de distancias. Resuelve la persecución sin findPath: ejecuta distances desde el héroe y que el enemigo dé un paso hacia la vecina con el número menor. ¿Cuántas búsquedas por turno son con cinco enemigos y cuántas con findPath?

Test

Ponte a prueba

1. La misma búsqueda de camino toma las celdas del principio de la lista (una cola) o del final (una pila). Con una cola el camino hasta el héroe es de 10 pasos; con una pila, de 12. ¿Por qué?

Una pila es más lenta y por eso su camino es más largoUna cola sabe dónde está la meta y va directa hacia ellaUna cola toma las celdas en el orden en que se descubrieron, así que la primera meta que se encuentra es la más cercana; una pila sigue un pasillo hasta el fondo y llega a la meta dando un rodeo

2. El goblin duerme, el héroe está al otro lado de la pared a 4 celdas en línea recta y el camino alrededor de la pared es de 6. El umbral para despertar es 5. ¿Por qué no despierta el goblin?

El goblin duerme hasta que el héroe lo golpeaLas paredes amortiguan el ruido, así que con una pared de por medio el goblin nunca despiertaDespertar se mide por la longitud del camino, no por la línea recta: 6 supera el umbral 5, y la línea recta atraviesa una pared

3. El goblin persigue y el héroe se esconde de su vista. ¿En qué turno sin verlo deja el goblin de perseguir y empieza a deambular (LOST = 3)?

En el turno 3: la transición ocurre con lost ≥ 3De inmediato, en el primer turno sin verEn el turno 4: lost crece en 1 en cada turno sin ver, y la transición ocurre con lost > 3

4. En la puntuación de utilidad el enemigo tiene un ataque (40) y dos acciones más con 40 y 60. ¿Cuál elige y qué pasa si dos acciones tienen la misma puntuación más alta?

Elige 60; con puntuaciones iguales gana la acción que se consideró primero, porque el reemplazo solo ocurre con score > bestScoreElige al azar entre las mejoresElige 60; con puntuaciones iguales gana la última, porque el reemplazo ocurre con score ≥ bestScore

5. ¿Por qué el goblin calcula el camino de nuevo en cada turno en lugar de recordar el viejo?

Es más rápido, porque un camino nuevo no cuesta tiempoEl héroe se mueve y otros enemigos ocupan celdas; un camino viejo puede llevar a un lugar vacío o atravesar a otro enemigoLa búsqueda en anchura no puede devolver más de un paso

Comprobar

Empezar la lección de nuevo

Lecciones relacionadas

• Se basa en: Excepciones · Lanzar excepciones y crear las tuyas · Listas: append, remove y sort · dataclass, match y patrones
• Ejercicios sobre el tema: Las crónicas de Arcanum