Dijkstra aplicado: heat maps de peligro y huida por gradiente

0. Introducción

Dijkstra map (un solo cálculo de distancias desde un origen a todas las celdas) es la herramienta más subestimada de la IA en juegos. Brogue la popularizó en 2009: un mapa, muchas decisiones distintas, costo CPU casi nulo.

En este tutorial cubrimos cuatro casos clásicos:

Caso	Mapas Dijkstra	Decisión
Persigue/huye	1 (desde jugador)	gradient descent o ascent
Heat map de peligro	N (uno por threat)	suma + minimax al vecino más frío
IA con objetivos múltiples	N (uno por objetivo)	suma ponderada con pesos negativos/positivos
Escolta protectora	M (uno por enemigo)	posición intermedia entre VIP y gradiente

Lo que tienen en común: un cálculo, decisión por agente O(1). Cero pathfinding individual.

1. Dijkstra map = una herramienta, dos personalidades

El Dijkstra map de Brogue: distancia desde el jugador a cada celda. Las flechas son la decisión de cada agente. Slider persigue/huye: el mismo mapa sirve para perseguir (vecino con menor distancia) o huir (vecino con mayor distancia). Mismo cálculo, decisiones opuestas.

personalidad1

Figura 1 — El Dijkstra map desde el jugador. Las flechas muestran qué decidiría cada celda según el slider de personalidad: persigue (vecino con MENOR distancia), huye (vecino con MAYOR distancia), o indiferente. Mismo cálculo, decisiones opuestas.

1.1 La idea de Brogue

function dijkstraMap(grid, source) -> Float[][]
    // Dijkstra exhaustivo: gScore[c] = distancia óptima de source a c
    return gScore

Una vez que tienes el mapa de distancias:

function decide(agent, map, personality)
    bestNeighbor = null
    bestVal = personality > 0 ? +Infinity : -Infinity
    for each n in walkableNeighbors(agent.position)
        if personality > 0 and map[n] < bestVal: bestVal = map[n]; bestNeighbor = n
        if personality < 0 and map[n] > bestVal: bestVal = map[n]; bestNeighbor = n
    return bestNeighbor

Una línea cambia entre persigue (<) y huye (>). Y un agente con personality = 0.5 puede mezclar — usar persigue 50% del tiempo, idle 50%.

1.2 ¿Cuándo recalcular el mapa?

• Tras cada movimiento del jugador (= origen del mapa). En roguelikes con turnos, eso es 1× por turno.
• Si el mapa cambia (puerta abierta, muro destruido), recalcular el Dijkstra map afectado.
• Si tenes 10 enemigos persiguiendo al jugador, un solo cálculo sirve para los 10. No un Dijkstra por agente.

1.3 Casos canónicos

• Brogue / DCSS: mapas de “atracción” (persigue) y “miedo” (huye). Cada monstruo tiene una mezcla de personalidad que define cómo combina.
• Caves of Qud: mapas para “comida”, “agua”, “lugares seguros”. El monstruo elige según necesidades.
• Dwarf Fortress: pathfinding por categoría (agua, comida, dormir) precomputado. Los dwarves no hacen A*; leen el mapa correspondiente.

2. Heat maps de peligro — multi-source

Tres "peligros" rojos emiten cada uno su Dijkstra map. Sumados (clamp) forman un mapa de calor compuesto. El agente azul se mueve automáticamente hacia el vecino más frío. Click cerca de un peligro para arrastrarlo.

Figura 2 — Tres “peligros” rojos, cada uno emite su Dijkstra map. La suma capada es el mapa de calor compuesto. El agente azul se mueve hacia el vecino más frío. Click cerca de un peligro para reubicarlo.

2.1 Suma vs max

Dos formas de combinar mapas:

• Suma — varios peligros se acumulan. Estar entre dos enemigos es peor que estar cerca de uno solo.
• Max — solo el peligro más cercano cuenta. Buena para “amenaza dominante”.

Suma es lo que usan los heat maps reales. Max simplifica en juegos arcade.

2.2 Implementación canónica

function dangerHeat(grid, threats, radius) -> Float[][]
    heat = Array(grid.cells, fill = 0)
    for each threat in threats
        distance = dijkstra(grid, threat.position)
        for each cell c with distance[c] <= radius
            heat[c] += (radius - distance[c]) / radius * threat.intensity
    return heat

intensity te permite peligros de distinto peso (un boss = 5×, un enemigo común = 1×).

2.3 Cuándo recalcular

• Si los threats no se mueven (torres fijas), una sola vez al cargar el nivel.
• Si se mueven (enemigos), cada N ticks. Cada turno es ideal en turn-based; cada 200ms es razonable en real-time.
• Para optimizar: solo recalculá los Dijkstra maps de threats que se movieron desde el último frame. Los demás siguen válidos.

3. IA con objetivos múltiples

Tres Dijkstra maps combinados con pesos: peligro (rojo), comida (verde), salida (violeta). El agente puede combinar metas. Sliders ajustan el peso de cada uno (negativo = huir, positivo = atraer). Es el patrón de Brogue para IA con personalidades.

peso peligro (negativo huye)-1.00peso comida0.60peso salida0.40

Figura 3 — Tres Dijkstra maps superpuestos: peligro, comida, salida. Los sliders ajustan el peso de cada uno (negativo = huir, positivo = atraer). El campo combinado emerge como una superficie verde-roja: verde es deseable, rojo es peligro.

3.1 La fórmula

combined[c] = weightPlayer * (1 - normalize(distance_player[c]))
            + weightFood   * (1 - normalize(distance_food[c]))
            + weightExit   * (1 - normalize(distance_exit[c]))

normalize mapea distancia a [0, 1] (típicamente min(1, dist / maxRange)). El (1 - x) invierte: cuanto más cerca, más cuenta.

Pesos negativos = repulsión, positivos = atracción. La IA elige el vecino con combined[c] máximo.

3.2 Los pesos son tu personalidad

Un solo motor + recetas de pesos = personalidades distintas:

warrior: weightPlayer = +2, weightFood = 0, weightExit = 0    # busca pelea
coward:  weightPlayer = -3, weightFood = 0, weightExit = +1    # huye y busca salida
zombie:  weightPlayer = +1, weightFood = +1.5, weightExit = 0  # come lo que hay
hero:    weightPlayer = +1, weightFood = 0, weightExit = +0.5  # busca pelea pero recuerda salida

Cada arquetipo es 3-4 números. Cero scripting. Total escalable.

4. Escolta protectora — caso compuesto

Caso de escolta. El VIP (V) deambula sin pensar. Los enemigos (rojo) emiten un Dijkstra map de "amenaza". El escolta (E, azul) lee el gradiente y se interpone entre el VIP y la amenaza más cercana. Sin scripted positions, sin path manual.

Figura 4 — El VIP (amarillo) deambula sin pensar. Los enemigos rojos emiten un Dijkstra map de “amenaza”. El escolta (azul) se posiciona automáticamente entre el VIP y la amenaza más cercana. Sin scripted positions.

4.1 La lógica del escolta

function escortPosition(vip, escort, threatMap, threats):
    // encontrar el threat más cercano al VIP
    nearestThreat = argmin(distance(vip.position, t) for t in threats)
    // dirección del VIP al threat
    direction = normalize(nearestThreat.position - vip.position)
    // posición ideal del escolta: 1.5 unidades en esa dirección desde el VIP
    return vip.position + direction * 1.5

El escolta no necesita Dijkstra para sí mismo; lee el mapa de amenazas para saber dónde está el peligro. Su posición ideal es geométrica.

4.2 Variantes

• Escolta múltiple: 3 escoltas, cada uno cubre una dirección distinta (dividir el círculo del VIP en 120°).
• Escolta con LOS: el escolta debe tener LOS hacia el VIP (no perderlo). Restricción adicional.
• Escolta agresivo: en vez de posicionarse, el escolta intercepta — predict + Dijkstra del enemigo + cortar el path.

5. Los principios compartidos

Los cuatro casos del tutorial siguen el mismo patrón:

1. Calcular Dijkstra map(s) desde origen(es) relevante(s)        // O(N log N) por map
2. Combinar con suma/max/pesos                                    // O(N)
3. Cada agente decide leyendo el mapa combinado                   // O(1) por agente

Beneficios:

• Centenares de agentes pagan por uno: el Dijkstra es la única operación cara.
• Cambiar personalidad = cambiar pesos. Sin tocar código.
• Visual debug trivial: el mapa se renderiza como heatmap, ves al instante por qué un agente decidió X.

Costos:

• Recálculo cuando cambian sources (peligros se mueven).
• Memoria: un float por celda por fuente. En mapas chicos no se nota; en mapas 1000×1000 con 50 sources, son 200 MB.

6. Implementación en Unity / C#

using System.Collections.Generic;
using UnityEngine;

public static class DijkstraMap {
    static readonly Vector2Int[] Dirs4 = {
        new(1, 0), new(-1, 0), new(0, 1), new(0, -1),
    };

    public static float[] Compute(bool[,] walkable, Vector2Int source) {
        int W = walkable.GetLength(0), H = walkable.GetLength(1), N = W * H;
        var dist = new float[N];
        for (int i = 0; i < N; i++) dist[i] = float.PositiveInfinity;
        dist[source.y * W + source.x] = 0;

        var pq = new PriorityQueue<int, float>();
        pq.Enqueue(source.y * W + source.x, 0);

        while (pq.Count > 0) {
            int cur = pq.Dequeue();
            int cx = cur % W, cy = cur / W;
            foreach (var d in Dirs4) {
                int nx = cx + d.x, ny = cy + d.y;
                if (nx < 0 || ny < 0 || nx >= W || ny >= H) continue;
                if (!walkable[nx, ny]) continue;
                int ni = ny * W + nx;
                float tentative = dist[cur] + 1;
                if (tentative < dist[ni]) {
                    dist[ni] = tentative;
                    pq.Enqueue(ni, tentative);
                }
            }
        }
        return dist;
    }

    public static Vector2Int FollowGradient(float[] map, int W, int H, Vector2Int agent, bool descend = true) {
        int cur = agent.y * W + agent.x;
        float bestVal = map[cur];
        Vector2Int best = agent;
        foreach (var d in Dirs4) {
            int nx = agent.x + d.x, ny = agent.y + d.y;
            if (nx < 0 || ny < 0 || nx >= W || ny >= H) continue;
            float v = map[ny * W + nx];
            bool better = descend ? v < bestVal : v > bestVal;
            if (better) { bestVal = v; best = new Vector2Int(nx, ny); }
        }
        return best;
    }

    public static float[] CombineWeighted((float[] map, float weight)[] inputs, int N) {
        var result = new float[N];
        foreach (var (map, w) in inputs) {
            for (int i = 0; i < N; i++) {
                result[i] += w * (1f - Mathf.Min(1, map[i] / 20f));
            }
        }
        return result;
    }
}

7. En otros engines

• Godot: el patrón es directo. AStarGrid2D da Dijkstra implícito (con h=0); para combinaciones multi-mapa, código custom.
• Unreal: FNavigationSystem no expone gScore directo. Para Dijkstra maps de gameplay, mejor escribirlo aparte sobre tu propio grid.
• JavaScript / TypeScript: la lib del sitio expone dijkstra como generador y buildFlowField como Dijkstra map directamente.

8. Quiz

Pon a prueba lo que entendiste

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

1. Tienes 50 enemigos persiguiendo al jugador. ¿Cuántos Dijkstra cálculas por turno?

   • AUno solo desde el jugador. Los 50 enemigos leen el mismo mapa de distancias para decidir su próximo paso.
   • B50, uno por enemigo, con goal en el jugador.
   • CNinguno: cada enemigo usa A* directo.

2. Tu juego tiene torres de daño (peligros estáticos) en varios puntos del mapa. ¿Cuándo recalculas el heat map?

   • AUna sola vez al cargar el nivel. Los Dijkstra maps de torres estáticas no cambian. Recálculo solo si el jugador construye/destruye una torre.
   • BCada frame, para mantenerlo actualizado.
   • CCada vez que un enemigo se mueve.

3. Quieres que tu IA tenga personalidades distintas: cobarde, agresivo, equilibrado. ¿Cómo lo implementas con multi-objective Dijkstra maps?

   • AUn mapa por objetivo (jugador, comida, salida). Cada arquetipo es un set de pesos: cobarde tiene weightPlayer = -3, agresivo +3, etc. Mismo motor, distintos números.
   • BTres versiones del algoritmo, una por arquetipo.
   • CUna FSM con un estado por personalidad.

4. Una unidad escolta a un VIP. ¿Cómo decide su posición usando Dijkstra maps?

   • ALee el Dijkstra map de los enemigos cerca del VIP, identifica la amenaza más cercana, y se posiciona geométricamente entre VIP y esa amenaza. No requiere Dijkstra propio.
   • BHace su propio Dijkstra cada turno hacia el VIP.
   • CHace A* a una posición scripted.

5. Combinás 4 Dijkstra maps con pesos. ¿Por qué normalizar (mapear distancia a [0,1]) antes de sumar?

   • ASin normalizar, los mapas con escala distinta dominan: si uno va 0..50 y otro 0..5, el primero se traga al segundo en la suma. Normalizar pone todos a la misma escala así los pesos importan.
   • BPara que los números sean enteros.
   • CPara evitar overflow.

9. Siguientes pasos