Tower Defense, Snake AI y Lemmings: tres mini-casos

0. Introducción

Tres minijuegos icónicos, tres algoritmos distintos:

Juego	Problema	Algoritmo
Tower Defense	enemigos van al goal evitando torres dinámicas	Flow field hacia el goal
Snake AI	la cabeza busca la fruta evitando el cuerpo	BFS desde la cabeza
Lemmings	asignar tareas al lemming más cercano libre	FloodFill desde la tarea

Este tutorial es práctico: cada caso es un mini-proyecto resuelto. Ya viste los algoritmos por separado en tutoriales anteriores; acá los aplicas a problemas concretos de gameplay.

1. Tower Defense — flow field hacia el goal

Tower Defense con flow field: click para construir/quitar torres. El flow se recalcula instantáneo y los enemigos rojos siguen el nuevo camino sin perder paso. Esto es lo que hace Bloons TD por dentro.

Figura 1 — Click sobre el grid para construir/quitar torres. El flow field se recalcula y los enemigos siguen el nuevo camino sin perder el paso. Las flechas tenues son la dirección de cada celda.

1.1 Por qué flow field y no A* por enemigo

En TD típico tenés:

• Cientos de enemigos (a veces miles en TD masivos como Bloons B.A.T.T.L.E.S).
• Mismo destino (un solo goal o algunos pocos).
• El mapa cambia (jugador construye/destruye torres).

Flow field es el patrón perfecto:

• Una sola búsqueda (Dijkstra back desde el goal).
• Todos los enemigos lo consultan en O(1).
• Cuando construís una torre, recalculás el flow field UNA vez y todos los enemigos se actualizan automáticamente.

1.2 El loop completo

function towerDefenseLoop(grid, goal, enemies, dt):
    // 1. flow field se recalcula solo cuando cambian las torres (eventos, no por frame)
    // 2. mover enemigos
    for each enemy in enemies:
        cell = floor(enemy.pos)
        direction = flowField.direction[cell]
        enemy.pos += direction * speed * dt
        if enemy.reachedGoal:
            // dañar al jugador
        if enemy.dead:
            remove

function onPlayerBuiltTower(towerCell):
    grid.setWall(towerCell, true)
    // ¿queda al menos un path al goal? Si no, deshacer.
    if not pathExistsToGoal(grid, anySpawnCell, goal):
        grid.setWall(towerCell, false)   // rollback
        return "tower would block path"
    // recalcular flow field
    flowField = buildFlowField(grid, goal)

1.3 Detalles que vas a tener que añadir

• Validación del path: no permitir construir si bloqueás todos los caminos. BFS rápido para verificar.
• Múltiples spawns: cada spawn es independiente; el flow field es el mismo (un goal).
• Múltiples goals: si los enemigos pueden elegir, calcular un flow field por goal y elegir según condiciones.
• Path preview mientras construís: mostrar el flow field tentativo antes de confirmar.

2. Snake autopilot — BFS desde la cabeza

Snake con autopilot via BFS: cada tick, BFS desde la cabeza hasta la fruta evitando el cuerpo. Path proyectado en violeta tenue. Funciona perfecto al principio; eventualmente la cola se vuelve laberinto y la fruta queda inalcanzable.

PausaReset

score: 3

Figura 2 — Snake clásico con autopilot via BFS. En cada tick, BFS desde la cabeza hasta la fruta evitando el cuerpo. Path proyectado en violeta. Funciona perfecto al principio; eventualmente la cola hace laberinto y la fruta queda inalcanzable.

2.1 BFS por tick

function snakeTick(snake, food, gridDims):
    // body = todas las celdas del cuerpo excepto la cola (porque la cola se va a mover)
    body = snake.cells.slice(0, -1)
    path = bfs(snake.head, food, blocked = body)
    if path:
        nextCell = path[1]    // [0] es la cabeza, [1] es el siguiente paso
        moveSnakeTo(nextCell)
    else:
        // no hay camino — el snake se mata o intenta sobrevivir
        moveSnakeTo(anySafeNeighbor)

2.2 El problema clásico: snake auto-encerrado

Cuando el snake es largo, BFS encuentra el path “más corto” a la fruta — pero ese path puede dejar al snake atrapado en su propia cola después de comer. Soluciones:

• Modo seguro: tras encontrar el path BFS, verificar con un BFS adicional que después de comer la fruta, todavía hay path desde la nueva cabeza hasta la cola. Si no, descartar este path.
• Hamiltonian cycle: precomputar un ciclo que pasa por todas las celdas y seguirlo siempre. El snake nunca se atrapa pero se vuelve aburrido y lento.
• Híbrido: seguir hamiltonian la mayoría del tiempo, pero si BFS encuentra un atajo seguro, tomarlo.

function safeBfsPath(snake, food):
    path = bfs(snake.head, food, snake.body)
    if not path: return null
    // simular: ¿después de comer, hay path de la nueva cabeza a la cola?
    simulatedSnake = simulate(snake, path)
    if bfs(simulatedSnake.head, simulatedSnake.tail, simulatedSnake.body):
        return path
    return null

2.3 Casos donde aplica el patrón

• Snake / Slither.io: autopilot puro como ejemplo.
• Tron / Light Cycles: cada agente busca el path más largo evitando estelas (variante adversarial).
• Pacman ghosts: cada fantasma tiene su propia BFS modificada (Blinky persigue, Pinky predice, Inky combina, Clyde tiene comportamiento errático).

3. Lemmings — asignación al más cercano disponible

Click sobre el canvas para crear una tarea. El sistema asigna la tarea al lemming libre más cercano (con un FloodFill mental). Verde = busy/asignado, violeta = libre. Es una versión simplificada del sistema de Lemmings clásico.

Figura 3 — Click para crear una tarea. El sistema busca el lemming libre más cercano y le asigna la tarea (línea verde). Verde = ocupado, violeta = libre.

3.1 El patrón “más cercano libre”

function assignJob(lemmings, job):
    best = null
    bestDist = Infinity
    for each lemming in lemmings:
        if lemming.busy: continue
        d = distance(lemming.pos, job.pos)
        if d < bestDist:
            bestDist = d
            best = lemming
    if best:
        best.busy = true
        best.target = job.pos
        job.assignedTo = best.id

3.2 Por qué FloodFill puede ser mejor que distancia euclidiana

Si el mapa tiene paredes, la “distancia más corta” entre el lemming y la tarea no es la línea recta — es la distancia caminable. Para casos exactos:

function assignJobBfs(grid, lemmings, job):
    // BFS desde el job hacia afuera
    distances = bfs(grid, job.pos)
    // encontrar el lemming libre con menor distance[lemming.pos]
    best = lemmings.filter(l => !l.busy)
                   .min_by(l => distances[l.pos])
    return best

Eso es un BFS por tarea, no por lemming. Si tenés 100 lemmings y 1 tarea, es mucho más eficiente que 100 BFS individuales.

3.3 Variantes de asignación

• Hungarian algorithm: si tenés N tareas y N lemmings, querés asignación óptima global (no greedy). Hungarian resuelve eso en O(N³). Para juegos, el greedy “más cercano primero” suele ser suficiente.
• Capability matching: distintos lemmings tienen distintas habilidades. La asignación es greedy filtrando por habilidad antes que por distancia.
• Reservation system: cada tarea reserva al lemming. Si un job más urgente aparece, puede “robar” un lemming si la prioridad lo permite.

4. Pseudocódigo unificado — los tres casos

// Caso 1: Tower Defense
function buildTowerDefense(grid, goal):
    flowField = buildFlowField(grid, goal)
    return flowField

function tickEnemies(enemies, flowField, dt):
    for e in enemies:
        e.move(flowField.direction[floor(e.pos)] * dt)

// Caso 2: Snake autopilot
function snakeAutopilot(snake, food):
    return bfs(snake.head, food, blocked = snake.body)

// Caso 3: Lemmings job assignment
function assignJob(grid, lemmings, job):
    distances = bfs(grid, job.pos)
    return lemmings
        .filter(l => !l.busy)
        .min_by(l => distances[floor(l.pos)])

5. Implementación en Unity / C#

using System.Collections.Generic;
using UnityEngine;

// Tower defense con flow field
public class TowerDefenseManager : MonoBehaviour {
    public Vector2Int goal;
    public bool[,] walkable;
    FlowField flowField;
    List<Enemy> enemies = new();

    public void OnTowerBuilt(Vector2Int cell) {
        if (!walkable[cell.x, cell.y]) return;
        walkable[cell.x, cell.y] = false;
        if (!PathExists(walkable, anySpawn, goal)) {
            walkable[cell.x, cell.y] = true;     // rollback
            return;
        }
        flowField = FlowField.Build(walkable, /*cost*/ uniformCost, goal);
    }

    void Update() {
        foreach (var e in enemies) {
            var cell = new Vector2Int((int)e.pos.x, (int)e.pos.y);
            var dir = flowField.SampleDirection(e.pos);
            e.pos += dir * e.speed * Time.deltaTime;
        }
    }
}

// Snake autopilot
public static class SnakeAi {
    public static List<Vector2Int> BfsPath(Vector2Int head, Vector2Int food, HashSet<Vector2Int> body, int W, int H) {
        var visited = new Dictionary<Vector2Int, Vector2Int>();
        visited[head] = new Vector2Int(-1, -1);
        var q = new Queue<Vector2Int>();
        q.Enqueue(head);
        var dirs = new[] { Vector2Int.right, Vector2Int.left, Vector2Int.up, Vector2Int.down };
        while (q.Count > 0) {
            var cur = q.Dequeue();
            if (cur == food) {
                var path = new List<Vector2Int>();
                while (cur.x >= 0) { path.Add(cur); cur = visited[cur]; }
                path.Reverse();
                return path;
            }
            foreach (var d in dirs) {
                var n = cur + d;
                if (n.x < 0 || n.y < 0 || n.x >= W || n.y >= H) continue;
                if (body.Contains(n) || visited.ContainsKey(n)) continue;
                visited[n] = cur;
                q.Enqueue(n);
            }
        }
        return null;
    }
}

6. En otros engines

• Godot: el patrón se traduce limpio. Para TD, TileMap + custom flow field. Para Snake, BFS sobre grid manual. Para Lemmings, lista de unidades + BFS por job.
• Unreal: AAIController puede manejar la lógica por agente. Para TD masivo, ECS-style con flow field global y agentes ligeros.
• JavaScript / TypeScript: la lib del sitio expone buildFlowField y bfs listos para los tres casos.

7. Quiz

Pon a prueba lo que entendiste

Responde una por una. La explicación aparece al elegir, correcta o no.

1. Tu Tower Defense tiene 200 enemigos en pantalla simultáneos. ¿Por qué flow field gana sobre A* por enemigo?

   • AEl flow field es O(N log N) una vez por evento de cambio (torre construida); A* sería O(N) por enemigo por frame, prohibitivo a 200 agentes.
   • BA* no encuentra paths cuando hay torres.
   • CFlow field encuentra paths más cortos.

2. Tu Snake autopilot funciona perfecto al principio pero al crecer se atrapa en su propia cola. ¿Solución?

   • AModo 'safe BFS': después de encontrar el path a la fruta, simular que comió y verificar con otro BFS que la nueva cabeza puede alcanzar la cola. Si no, descartar el path.
   • BAumentar el radio de búsqueda de BFS.
   • CUsar Dijkstra en lugar de BFS.

3. 100 lemmings caminando, una tarea aparece. ¿Cómo encontrás al lemming libre más cercano de forma eficiente?

   • AUn BFS desde la TAREA (no desde cada lemming). Como hay UN job y N lemmings, un BFS sirve para todos. Encontrás al lemming libre con menor distance.
   • BUn BFS desde cada lemming.
   • CDistancia euclidiana es suficiente.

4. Construyes una torre en TD que justo bloquea el último camino. ¿Qué hace el sistema?

   • AAntes de confirmar la construcción, verificar con BFS que sigue habiendo path desde spawn a goal. Si no, rollback (no construir) y mostrar feedback al jugador.
   • BConstruir y dejar que los enemigos se queden quietos.
   • CCambiar el algoritmo a A* para que encuentre paths imposibles.

5. Un job en Lemmings está asignado a un lemming, pero un job más urgente aparece. ¿Cómo lo manejas?

   • ASistema de prioridades: cada job tiene priority. Antes de empezar el work del job actual, comparar con cualquier job libre de mayor priority; si la hay, reasignar.
   • BEsperar a que termine el job actual y después tomar el urgente.
   • CAsignar el job urgente al lemming más cercano sin importar si está ocupado.

8. Siguientes pasos