Ir al contenido
wannacode

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.

const string MAP = """
    ################
    #......#.......#
    #......#.......#
    #......#.......#
    #......#.......#
    #..............#
    ################
    """;


// La ola: a cuántos pasos está cada celda del inicio.
static int[][] Distances(Level level, int startX, int startY)
{
    var dist = new int[level.Height][];
    for (int y = 0; y < level.Height; y++)
    {
        dist[y] = new int[level.Width];
        Array.Fill(dist[y], -1);
    }
    dist[startY][startX] = 0;
    var queue = new List<Step> { new Step(startX, startY) };
    int head = 0;
    while (head < queue.Count)
    {
        Step cell = queue[head];
        head++;
        foreach (int[] direction in Level.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;
}
var level = new Level(MAP);
int[][] dist = Distances(level, ENEMY_X, ENEMY_Y);
Console.WriteLine("La ola desde el enemigo (a = 10, b = 11, ...):");
PrintWave(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 record. El arreglo con las cuatro direcciones está en Level: las funciones de debajo del programa son locales y no ven las variables de Main, mientras que un campo de una clase se ve desde todas partes.

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.

static List<Step>? FindPath(Level level, int startX, int startY, int goalX, int goalY)
{
    var cameFrom = new int[level.Width * level.Height];
    Array.Fill(cameFrom, -1);
    int start = startY * level.Width + startX;
    cameFrom[start] = start;
    var queue = new List<int> { start };
    int head = 0;
    while (head < queue.Count)
    {
        int current = queue[head];
        head++;
        int x = current % level.Width;
        int y = current / level.Width;
        if (current != start && x == goalX && y == goalY)
        {
            var path = new List<Step>();
            int index = current;
            while (index != start)
            {
                path.Add(new Step(index % level.Width, index / level.Width));
                index = cameFrom[index];
            }
            path.Reverse();
            return path;
        }
        foreach (int[] direction in Level.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);
}
var level = new Level(MAP);
List<Step> path = FindPath(level, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y)!;
Console.WriteLine($"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 {path.Count}");
int[][] dist = Distances(level, ENEMY_X, ENEMY_Y);
Console.WriteLine("La ola desde el enemigo (a = 10, b = 11, ...):");
PrintWave(level, dist);
Console.WriteLine("El camino hasta el héroe (*):");
PrintPath(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 null.

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

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


// 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).
static void EnemyTurn(Level level, Enemy enemy, int heroX, int heroY, int turn, bool hidden)
{
    List<Step>? path = FindPath(level, enemy.X, enemy.Y, heroX, heroY);
    int pathLength = path == null ? NONE : path.Count;
    bool sees = !hidden && pathLength <= SIGHT;
    if (enemy.State == "sleep")
    {
        if (sees && pathLength <= WAKE) enemy.State = "chase";
        return;
    }
    if (enemy.State == "wander")
    {
        if (sees)
        {
            enemy.State = "chase";
            enemy.Lost = 0;
            return;
        }
        // Deambula en el orden de las direcciones (el juego tira un dado).
        int[] direction = Level.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 == "chase")
    {
        if (enemy.Life * 4 < enemy.MaxLife)
        {
            enemy.State = "flee";
            return;
        }
        if (!sees)
        {
            enemy.Lost++;
            if (enemy.Lost > LOST)
            {
                enemy.State = "wander";
                return;
            }
        }
        else
        {
            enemy.Lost = 0;
        }
        if (pathLength <= 1) return;
        if (pathLength <= FAR)
        {
            enemy.X = path![0].X;
            enemy.Y = path[0].Y;
        }
        return;
    }
    // Huye: el paso que más lo aleja del héroe.
    int bestX = enemy.X;
    int bestY = enemy.Y;
    int bestDistance = Distance(enemy.X, enemy.Y, heroX, heroY);
    foreach (int[] direction in Level.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;
}

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.

var level = new Level(MAP);
var 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.Count;
    string state = before == enemy.State ? before : before + " → " + enemy.State;
    Console.WriteLine($"turno {i + 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.

static List<Step>? FindPath(Level level, int startX, int startY, int goalX, int goalY)
{
    var cameFrom = new int[level.Width * level.Height];
    Array.Fill(cameFrom, -1);
    int start = startY * level.Width + startX;
    cameFrom[start] = start;
    var queue = new List<int> { start };
    int head = 0;
    while (head < queue.Count)
    {
        int current = queue[head];
        head++;
        int x = current % level.Width;
        int y = current / level.Width;
        if (current != start && x == goalX && y == goalY)
        {
            var path = new List<Step>();
            int index = current;
            while (index != start)
            {
                path.Add(new Step(index % level.Width, index / level.Width));
                index = cameFrom[index];
            }
            path.Reverse();
            return path;
        }
        foreach (int[] direction in Level.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;
}


// 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).
static void EnemyTurn(Level level, Enemy enemy, int heroX, int heroY, int turn, bool hidden)
{
    List<Step>? path = FindPath(level, enemy.X, enemy.Y, heroX, heroY);
    int pathLength = path == null ? NONE : path.Count;
    bool sees = !hidden && pathLength <= SIGHT;
    if (enemy.State == "sleep")
    {
        if (sees && pathLength <= WAKE) enemy.State = "chase";
        return;
    }
    if (enemy.State == "wander")
    {
        if (sees)
        {
            enemy.State = "chase";
            enemy.Lost = 0;
            return;
        }
        // Deambula en el orden de las direcciones (el juego tira un dado).
        int[] direction = Level.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 == "chase")
    {
        if (enemy.Life * 4 < enemy.MaxLife)
        {
            enemy.State = "flee";
            return;
        }
        if (!sees)
        {
            enemy.Lost++;
            if (enemy.Lost > LOST)
            {
                enemy.State = "wander";
                return;
            }
        }
        else
        {
            enemy.Lost = 0;
        }
        if (pathLength <= 1) return;
        if (pathLength <= FAR)
        {
            enemy.X = path![0].X;
            enemy.Y = path[0].Y;
        }
        return;
    }
    // Huye: el paso que más lo aleja del héroe.
    int bestX = enemy.X;
    int bestY = enemy.Y;
    int bestDistance = Distance(enemy.X, enemy.Y, heroX, heroY);
    foreach (int[] direction in Level.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;
}
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.
class Point
{
    public int X;
    public int Y;
}


static partial class Arcanum
{
    public static readonly int[][] DIRECTIONS = { new[] { 0, -1 }, new[] { 1, 0 }, new[] { 0, 1 }, new[] { -1, 0 } };


    // isPassable(x, y) e isGoal(x, y) son funciones; devuelve el camino sin el inicio, o null.
    public static List<Point>? FindPath(Level level, int startX, int startY, Func<int, int, bool> isPassable, Func<int, int, bool> isGoal)
    {
        int[] cameFrom = new int[level.Width * level.Height];
        Array.Fill(cameFrom, -1);
        int startIndex = startY * level.Width + startX;
        cameFrom[startIndex] = startIndex;
        List<int> queue = new List<int> { startIndex };
        int head = 0;
        while (head < queue.Count)
        {
            int current = queue[head];
            head++;
            int x = current % level.Width;
            int y = current / level.Width;
            if (current != startIndex && isGoal(x, y))
            {
                List<Point> path = new List<Point>();
                int index = current;
                while (index != startIndex)
                {
                    path.Add(new Point { X = index % level.Width, Y = index / level.Width });
                    index = cameFrom[index];
                }
                path.Reverse();
                return path;
            }
            foreach (int[] direction in 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(nextX, nextY) && !isGoal(nextX, nextY)) continue;
                cameFrom[nextIndex] = current;
                queue.Add(nextIndex);
            }
        }
        return null;
    }


    public static int Distance(int ax, int ay, int bx, int by)
    {
        return Math.Abs(ax - bx) + Math.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.
static partial class Arcanum
{
    public static bool 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);
    }


    public static bool 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);
    }


    public 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;
    }


    public static void EnemyTurnOnMap(Game game, Level level, Enemy enemy)
    {
        Hero hero = game.Hero;
        Random rng = game.Rng;
        bool sees = EnemySeesHero(level, enemy, hero);
        bool heroSeesIt = level.Visible[enemy.Y][enemy.X];
        if (enemy.Calm > 0) enemy.Calm -= 1;
        if (enemy.State == "sleep")
        {
            if (sees && Distance(enemy.X, enemy.Y, hero.X, hero.Y) <= 5 && rng.Chance(50))
            {
                enemy.State = "chase";
                if (heroSeesIt) game.Say(T("ai.wakes", ("name", enemy.Name)));
            }
            return;
        }
        if (enemy.State == "guard")
        {
            if (sees && Distance(enemy.X, enemy.Y, hero.X, hero.Y) <= 6)
            {
                enemy.State = "chase";
                game.Say(T("ai.guard", ("name", enemy.Name)));
            }
            return;
        }
        if (enemy.State == "wander")
        {
            if (sees && enemy.Calm == 0)
            {
                enemy.State = "chase";
                enemy.LostTurns = 0;
                if (heroSeesIt) game.Say(T("ai.notices", ("name", enemy.Name)));
                return;
            }
            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 == "chase")
        {
            if (enemy.Kind.Special != "warden" && enemy.IsHeavilyWounded())
            {
                enemy.State = "flee";
                if (heroSeesIt) game.Say(T("ai.flees", ("name", enemy.Name)));
                return;
            }
            if (!sees)
            {
                enemy.LostTurns += 1;
                if (enemy.LostTurns > 5)
                {
                    enemy.State = "wander";
                    return;
                }
            }
            else
            {
                enemy.LostTurns = 0;
            }
            if (Distance(enemy.X, enemy.Y, hero.X, hero.Y) <= 1) return;
            List<Point>? 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.Count > 1 && path.Count <= 20) MoveEnemy(game, level, enemy, path[0].X, path[0].Y);
            return;
        }
        // flee: el paso que más aleja del héroe
        int bestX = enemy.X;
        int bestY = enemy.Y;
        int bestDistance = Distance(enemy.X, enemy.Y, hero.X, hero.Y);
        foreach (int[] direction in 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);
    }
}

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
{
    public string Best;
    public int BestScore = 40;
    public string Trace;


    public Chooser(string attack)
    {
        Best = attack;
        Trace = attack + " 40";
    }


    public 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, bool heroPoisoned, List<Fighter> allies, int healWait, int spitWait)
{
    var chooser = new Chooser("ataque a " + hero.Name);
    Fighter? weakest = null;
    foreach (Fighter ally in 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, "cura a " + weakest.Name);
    if (spitWait == 0 && !heroPoisoned) chooser.Consider(60, "escupe a " + hero.Name);
    return chooser;
}


static Fighter WeakestOf(List<Fighter> enemies)
{
    Fighter? weakest = null;
    foreach (Fighter enemy in enemies)
    {
        if (weakest == null || enemy.Hp < weakest.Hp) weakest = enemy;
    }
    return weakest!;
}


static Chooser ChooseHeroAction(Fighter hero, bool hasPotion, List<Fighter> enemies)
{
    var chooser = new Chooser("ataque a " + WeakestOf(enemies).Name);
    if (Percent(hero.Hp, hero.MaxHp) < 35 && hasPotion) chooser.Consider(90, "poción");
    return chooser;
}


static void Show(Chooser chooser)
{
    Console.WriteLine(chooser.Trace + " → " + chooser.Best);
}

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

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


Show(ChooseEnemyAction(hero, false, [woundedRat, goblin], 0, 0));
Show(ChooseEnemyAction(hero, false, [woundedRat, goblin], 2, 0));
Show(ChooseEnemyAction(hero, true, [rat, goblin], 0, 0));
Show(ChooseEnemyAction(hero, false, [woundedRat, woundedGoblin], 0, 3));
Show(ChooseHeroAction(hero, true, [woundedRat, goblin, cultist]));
Show(ChooseHeroAction(hurtHero, true, [woundedRat, goblin, cultist]));
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
{
    public string Best;
    public int BestScore = 40;
    public string Trace;

    public Chooser(string attack)
    {
        Best = attack;
        Trace = attack + " 40";
    }

    public void Consider(int score, string action)
    {
        Trace += ", " + action + " " + score;
        if (score  BestScore)
        {
            Best = action;
            BestScore = score;
        }
    }
}

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.
static partial class Arcanum
{
    public static IBattleAction ChooseEnemyAction(Battle battle, Enemy enemy)
    {
        Hero hero = battle.Hero;
        IBattleAction best = new AttackAction(enemy, hero);
        int bestScore = 40;
        Action<int, IBattleAction> consider = (score, action) =>
        {
            if (score > bestScore)
            {
                best = action;
                bestScore = score;
            }
        };
        string special = enemy.Kind.Special;
        if (special == "shaman")
        {
            Enemy? weakest = null;
            foreach (Enemy ally in battle.AliveEnemies())
            {
                if (Percent(ally.Hp, ally.MaxHp()) < 50 && (weakest == null || Percent(ally.Hp, ally.MaxHp()) < Percent(weakest.Hp, weakest.MaxHp()))) weakest = ally;
            }
            if (weakest != null && enemy.CooldownOf("heal") == 0) consider(80, new SpecialAction(enemy, "heal", weakest));
            if (enemy.CooldownOf("shaman") == 0 && !hero.HasEffect("poison")) consider(60, new SpecialAction(enemy, "spit", hero));
        }
        else if (special == "firebolt" && enemy.CooldownOf("firebolt") == 0)
        {
            consider(65, new SpecialAction(enemy, "firebolt", hero));
        }
        else if (special == "rend" && enemy.CooldownOf("rend") == 0 && !hero.HasEffect("bleed"))
        {
            consider(55, new SpecialAction(enemy, "rend", hero));
        }
        else if (special == "slam" && enemy.CooldownOf("slam") == 0)
        {
            consider(60, new SpecialAction(enemy, "slam", hero));
        }
        else if (special == "warden")
        {
            if (enemy.Phase == 1 && enemy.Hp * 2 < enemy.MaxHp()) consider(100, new SpecialAction(enemy, "summon", hero));
            else if (enemy.CooldownOf("warden") == 0) consider(60, new SpecialAction(enemy, "slam", hero));
        }
        return best;
    }


    public static List<Skill> UsableSkills(Hero hero)
    {
        List<Skill> result = new List<Skill>();
        foreach (string skillId in hero.Skills)
        {
            Skill skill = SKILLS.Get(skillId);
            if (hero.Mana >= skill.Mana && hero.CooldownOf(skill.Id) == 0) result.Add(skill);
        }
        return result;
    }


    public static Enemy? WeakestEnemy(Battle battle)
    {
        Enemy? weakest = null;
        foreach (Enemy enemy in battle.AliveEnemies())
        {
            if (weakest == null || enemy.Hp < weakest.Hp) weakest = enemy;
        }
        return weakest;
    }


    // El héroe en piloto automático (la simulación): la misma puntuación de utilidad.
    public static IBattleAction ChooseHeroAction(Battle battle)
    {
        Hero hero = battle.Hero;
        Enemy? target = WeakestEnemy(battle);
        IBattleAction best = new AttackAction(hero, target);
        int bestScore = 40;
        Action<int, IBattleAction> consider = (score, action) =>
        {
            if (score > bestScore)
            {
                best = action;
                bestScore = score;
            }
        };
        int lifeShare = Percent(hero.Hp, hero.MaxHp());
        if (lifeShare < 35 && hero.Inventory.Count("potion_heal") > 0) consider(90, new ItemAction(hero, "potion_heal"));
        if ((hero.HasEffect("poison") || hero.HasEffect("bleed")) && lifeShare < 50 && hero.Inventory.Count("antidote") > 0)
        {
            consider(70, new ItemAction(hero, "antidote"));
        }
        bool many = battle.AliveEnemies().Count >= 2;
        foreach (Skill skill in UsableSkills(hero))
        {
            int score = 0;
            if (skill.Kind == "heal") score = lifeShare < 50 ? 75 : 0;
            else if (skill.Kind == "buff") score = hero.HasEffect(skill.Effect) ? 0 : 50;
            else if (skill.Kind == "debuff") score = many ? 55 : 45;
            else if (skill.Target == "all") score = many ? 65 : 52;
            else score = 55;
            consider(score, new SkillAction(hero, skill, target));
        }
        return best;
    }
}

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?

const string TINY = """
    #######
    #.#...#
    #...#.#
    #######
    """;
var level = new Level(TINY);
PrintWave(level, Distances(level, 1, 1));
Respuesta

Pruébalo

Encuentra el error

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

var level = new Level(MAP);
List<Step> path = FindPath(level, ENEMY_X, ENEMY_Y, HERO_X, HERO_Y)!;
Console.WriteLine($"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 {path.Count}");
Console.WriteLine("El camino hasta el héroe (*):");
PrintPath(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.

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

Turn[] script =
[
    new(3, 5, 0, false),
    new(4, 5, 0, false),
    new(4, 5, 0, false),
    new(4, 5, 0, true),
    new(4, 5, 0, true),
    new(4, 5, 0, true),
    new(4, 5, 0, true),
    new(4, 5, 0, true),
    new(4, 5, 0, true),
    new(4, 5, 0, true),
    new(4, 5, 0, true),
    new(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é?
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?
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)?
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?
5. ¿Por qué el goblin calcula el camino de nuevo en cada turno en lugar de recordar el viejo?

Creado por Ivo Gergov como parte de la campaña de Evo Tech por una educación accesible en programación ·