BFS aplicado: rangos tácticos, influence maps y FOV

0. Introducción

Cualquier juego tactical (XCOM, Fire Emblem, Advance Wars, Into the Breach) hace tres cosas constantemente:

1. Calcular qué celdas alcanza una unidad este turno — el “rango azul”.
2. Saber qué facción domina cada zona — influence maps.
3. Mostrar al jugador qué ve cada unidad — FOV táctico.

Las tres son BFS (o Dijkstra) bounded con detalles distintos. En este tutorial las cubrimos las tres con la matemática y el código justo.

Caso	Algoritmo	Bound	Costo
Rango de movimiento	Dijkstra (BFS si costos uniformes)	gScore <= movePoints	Costos por terreno
Influence map	Dijkstra desde cada unidad	gScore <= radius	1 por celda, suma o max
FOV táctico	Shadowcasting o BFS+LOS	dist <= visionRadius	LOS bloqueado por muros

Las tres comparten una idea: expandir una frontera limitada desde un origen. La cosa cambia es qué guardas y cómo lo combinas.

1. Rango táctico — el “azul” de XCOM

El "rango azul" de XCOM, Fire Emblem o Advance Wars: BFS con costos heterogéneos desde la unidad. Bosque cuesta 2, montaña 3, muro infinito. La intensidad del azul muestra qué tan barato es llegar.

Suelo (1)Bosque (2)Montaña (3)Muro

movePoints6

Figura 1 — Selecciona un terreno, click+drag para pintar (bosque, montaña, muro). Shift+click mueve la unidad. El slider de movePoints define el alcance. Las celdas alcanzables se pintan azul, con intensidad inversa al costo de llegada.

1.1 La idea, en una línea

function tacticalRange(grid, unit, movePoints) -> Set<Cell>
    return all cells where Dijkstra(unit).gScore[cell] <= movePoints

Si los costos son uniformes (todos los terrenos cuestan 1), Dijkstra degenera en BFS y la condición es dist <= movePoints — es lo que hace Fire Emblem original. Cuando hay terrenos heterogéneos (bosque cuesta 2, montaña 3), Dijkstra es la respuesta correcta.

1.2 Las tres decisiones de diseño

1. ¿Costo de entrar o salir? Lo estándar es costo de entrar a la celda destino. Salir de bosque cuesta lo que cueste el destino, no lo que costó entrar al bosque.
2. ¿Diagonales? Fire Emblem y XCOM clásico no permiten diagonales; Into the Breach sí. Cambia tu vecindad de 4 a 8.
3. ¿Costo diagonal? Si permites diagonales y todas cuestan 1, la unidad puede zigzaguear cubriendo más distancia “real”. Si quieres que diagonal cueste √2, el algoritmo sigue siendo Dijkstra; solo cambia el costo del paso.

1.3 Reconstruir el path al hover

Cuando el jugador hace hover sobre una celda alcanzable, querés mostrar el path. Lo tienes gratis: durante el Dijkstra, guardás parent[]. Click → reconstruís el path desde la celda de hover hasta la unidad.

function pathToHover(parent, unitCell, hoverCell) -> List<Cell>
    path = [hoverCell]
    cur = hoverCell
    while cur != unitCell
        cur = parent[cur]
        path.append(cur)
    return reverse(path)

2. Influence maps — quién domina cada zona

Cada unidad emite influencia decreciente con distancia (Dijkstra bounded). En cada celda se compara la influencia total del equipo A y B; si una domina, pinta su color; si están parejas, queda disputada (gris). Arrastra las unidades.

Figura 2 — Tres unidades por equipo. Cada una emite influencia decreciente con distancia (Dijkstra bounded). En cada celda se compara la influencia total: gana el color del equipo dominante. Si están parejas, queda disputada (gris). Arrastra las unidades.

2.1 La fórmula

Por cada unidad u:

distance = Dijkstra(grid, u.position)
for each cell c with distance[c] <= radius
    influence[u.team][c] += (radius - distance[c]) / radius

Después, por celda, comparas influence[A][c] vs influence[B][c]. Cuatro casos:

• A > B por margen claro → celda controlada por A.
• B > A por margen claro → celda controlada por B.
• |A - B| < threshold → disputada.
• A = B = 0 → neutral.

2.2 Variantes y aplicaciones

• Suma vs max: si quieres que muchas unidades amplifiquen el control, suma. Si quieres que una unidad sea suficiente para tomar la celda, max. RTS típicamente usan suma con cap.
• Decay temporal: la influencia decae con el tiempo. Una unidad que estuvo en una zona y se fue deja “memoria” de control que se desvanece.
• Influence multi-capa: capa “amenaza” (suma de daño potencial), capa “defensa” (suma de healing potencial). Combinar capas para decisiones tácticas.

3. FOV táctico — qué ve cada unidad

FOV táctico por casillas: BFS bounded por radio + line-of-sight con shadowcasting. La unidad ve solo las celdas dentro del radio que no están ocluidas. Es lo que XCOM, Into the Breach o Advance Wars dibujan.

radio de visión8

Figura 3 — La unidad ve solo las celdas dentro de su radio de visión que no estén ocluidas por muros. El algoritmo es recursive shadowcasting: barre 8 octantes desde la unidad y propaga “sombras” cuando un muro corta la línea de visión.

3.1 Tres opciones de FOV

Algoritmo	Coste	Calidad
BFS + Bresenham por celda	O(R² × R)	Simple, pero asimétrico (A puede ver a B pero B no a A).
Recursive shadowcasting	O(R²)	Estándar en roguelikes. Asimétrico también. Rápido.
Symmetric Shadowcasting	O(R²)	Simétrico (si A ve a B, B ve a A). Más complejo.

Para tactical, recursive shadowcasting es el sweet spot. Lo verás explicado en detalle en Line-of-sight con su propia visualización.

3.2 BFS + LOS — la versión “fácil”

function tacticalFov(grid, unit, radius) -> Set<Cell>
    visible = Set()
    for each cell c with Manhattan(c, unit) <= radius
        if hasLineOfSight(unit, c, grid)
            visible.add(c)
    return visible

function hasLineOfSight(a, b, grid)
    for each cell on Bresenham(a, b)
        if grid[cell].blocksVision: return false
    return true

Funciona para FOV sencillo. Pierde performance en mapas grandes (R² LOS checks, cada uno O(R)). Recursive shadowcasting es un upgrade gratis.

3.3 Memoria del fog of war

XCOM y Fire Emblem recuerdan lo que viste alguna vez (mostrado en gris/sepia), pero solo lo que está actualmente visible se renderiza con detalle (unidades, animación). Implementación:

seen: Set      // todo lo visto alguna vez
visible: Set   // visible este turno

cada turno:
    visible = computeFov(unit, radius)
    seen = seen ∪ visible

renderizar:
    cell ∈ visible    → full detail
    cell ∈ seen       → fade gris (terreno conocido, sin unidades)
    cell ∉ seen       → niebla total

4. Caso completo — Advance Wars

Cuatro tipos de unidad con costos por terreno distintos. Movimiento + ataque combinados: el azul es alcanzable en este turno; el rojo es atacable después de moverse. Helicóptero ignora el terreno; tanque y artillería no pueden cruzar montaña.

InfanteríaTanqueHelicópteroArtillería

Figura 4 — Cuatro tipos de unidad con costos por terreno distintos. Movimiento + ataque combinados: el azul es alcanzable en este turno; el rojo claro es atacable después de moverse. Helicóptero ignora el terreno; tanque y artillería no pueden cruzar montaña.

4.1 La combinación move + attack

El jugador necesita ver dónde puede mover y a quién puede atacar después de moverse. Implementación:

moveZone = tacticalRange(grid, unit, unit.movePoints)
attackZone = Set()
for each cell c in moveZone
    for each cell t with ManhattanDist(c, t) <= unit.attackRange
        if t not in moveZone
            attackZone.add(t)

El jugador ve los dos overlays simultáneos. El rojo muestra rangos de ataque que requieren moverse a una celda específica primero; el azul son las celdas a las que puede ir.

4.2 Tipos de unidad como tabla de costos

unitTypes = {
    Infantry:  { move: 5, attack: 1, costs: { plain: 1, forest: 2, mountain: 3 } },
    Tank:      { move: 7, attack: 1, costs: { plain: 1, forest: 3, mountain: ∞ } },
    Heli:      { move: 9, attack: 1, costs: { plain: 1, forest: 1, mountain: 1 } },
    Artillery: { move: 5, attack: 3, costs: { plain: 1, forest: 4, mountain: ∞ } },
}

Antes de cada Dijkstra para una unidad, rebuild el grid con sus costos. La unidad ve un mapa “personalizado” donde montaña es muro para tanques pero llano para helicópteros.

5. Implementación en Unity / C#

using System.Collections.Generic;
using UnityEngine;

public class TacticalGrid {
    public int Cols, Rows;
    public bool[] Walkable;
    public float[] Cost;
    public int Idx(int x, int y) => y * Cols + x;
}

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

    public static HashSet<Vector2Int> Range(TacticalGrid g, Vector2Int unit, float movePoints) {
        int N = g.Cols * g.Rows;
        var dist = new float[N];
        for (int i = 0; i < N; i++) dist[i] = float.PositiveInfinity;
        dist[g.Idx(unit.x, unit.y)] = 0;

        var pq = new PriorityQueue<int, float>();
        pq.Enqueue(g.Idx(unit.x, unit.y), 0);

        while (pq.Count > 0) {
            int cur = pq.Dequeue();
            int cx = cur % g.Cols, cy = cur / g.Cols;
            foreach (var d in Dirs4) {
                int nx = cx + d.x, ny = cy + d.y;
                if (nx < 0 || ny < 0 || nx >= g.Cols || ny >= g.Rows) continue;
                int ni = g.Idx(nx, ny);
                if (!g.Walkable[ni]) continue;
                float tentative = dist[cur] + g.Cost[ni];
                if (tentative > movePoints) continue;
                if (tentative < dist[ni]) {
                    dist[ni] = tentative;
                    pq.Enqueue(ni, tentative);
                }
            }
        }

        var result = new HashSet<Vector2Int>();
        for (int y = 0; y < g.Rows; y++)
            for (int x = 0; x < g.Cols; x++)
                if (dist[g.Idx(x, y)] <= movePoints) result.Add(new Vector2Int(x, y));
        return result;
    }
}

6. En otros engines

• Godot: TileMap + un BFS propio. Las celdas con costo INF son obstáculos efectivos.
• Unreal: FNavigationSystem no calcula rangos por celda; lo escribes a mano sobre tu propio grid de gameplay (separado del navmesh de movimiento físico).
• JavaScript / TypeScript: la lib del sitio expone dijkstra y computeFov directamente.

7. Quiz

Pon a prueba lo que entendiste

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

1. Tu juego tactical permite movimientos diagonales con costo 1.5. ¿Qué algoritmo usas para el rango azul?

   • ADijkstra con vecindad 8-conexa y costo de paso 1 ortogonal, 1.5 diagonal. Filtras por gScore <= movePoints.
   • BBFS, ignorando el costo 1.5 (aproximar todo a 1).
   • CA* con goal = unit.position.

2. Un influence map muestra que cierta zona está 'disputada' cuando ambos equipos tienen casi la misma influencia. ¿Cómo lo defines numéricamente?

   • A|influenceA - influenceB| < threshold. Si están parejas dentro de cierto margen, la celda se marca como disputada.
   • BCuando ambas son cero.
   • CCuando alguna unidad de cada equipo está en la celda exacta.

3. Tu unidad de tactical tiene costos distintos según tipo de unidad (helicóptero ignora montañas, tanque no). ¿Cómo lo modelas?

   • AUna tabla 'tipo de unidad → costos por tile-type'. Antes de calcular el rango, rebuilds el grid con los costos del tipo de unidad activo. Luego Dijkstra normal.
   • BUn grid distinto por tipo de unidad, pre-computado.
   • CUn solo grid con costos promedio.

4. Para el FOV táctico (qué ve cada unidad), ¿qué te da recursive shadowcasting que BFS+Bresenham no?

   • APerformance: O(R²) en vez de O(R³). Para FOV interactivo (calculado cada turno), shadowcasting es ~100× más rápido en mapas grandes.
   • BMejor calidad visual.
   • CSoporte para diagonales.

5. Después de calcular el rango azul (movimiento), querés calcular las celdas atacables. ¿Cómo lo haces?

   • APara cada celda alcanzable, marcas las celdas a distancia ≤ attackRange. Eso te da el 'overlay rojo' que combina movimiento + ataque.
   • BHacés un Dijkstra distinto con costos de ataque.
   • CSumas movePoints + attackRange como rango total.

8. Siguientes pasos