Tu juego necesita verificar si un sniper ve al jugador desde el otro lado del mapa. ¿Qué algoritmo es ideal?

Bresenham + check celda por celda. Para LOS punto-a-punto, una sola línea es lo más simple y eficiente. Es el caso clásico. Bresenham te da las celdas; verificar 'ninguna bloquea' es O(R). Shadowcasting calcula FOV completo (mucho más caro) si solo querés saber A→B.

Implementás FOV con BFS + Bresenham por celda. En radio 14, parece lento. ¿Causa?

BFS + Bresenham es O(R³): 196 celdas × 14 ops cada una = 2744 ops por FOV. Recursive shadowcasting es O(R²) ≈ 196 ops. La diferencia es notable a partir de R = 8. Para R = 14, shadowcasting es ~14× más rápido. Para gameplay con FOV recalculado por movimiento, vale la pena.

El jugador dispara desde un escondite y mata a un enemigo. El enemigo aparece quejándose porque 'lo mataron desde un lugar invisible'. ¿Qué falta?

Asimetría rota: tu FOV no es simétrico (vos lo ves pero él no te ve a vos). Para que se sienta justo, usar symmetric shadowcasting o equivalente. Es el caso clásico que symmetric shadowcasting resuelve: si vos podés ver a B, B también puede ver a vos. Caves of Qud y otros roguelikes serios usan la variante simétrica para evitar esa frustración.

El jugador vuelve a una zona que ya había explorado. ¿Cómo manejas la información en el fog of war?

Tres estados: never_seen (negro), seen_before (gris, muestra terreno persistente), visible_now (color, muestra unidades). Las unidades enemigas SÓLO se renderizan en visible_now. Es el patrón canónico. El jugador recuerda terreno (importante para navegación) pero no recuerda enemigos (que ya pueden haberse movido). Esa separación es lo que hace al fog of war creíble.

Para tirar disparos en un FPS-2D estilo top-down, ¿qué algoritmo de raycast usás?

Bresenham (o DDA) sobre el grid del nivel. Es exacto, rápido, y te da las celdas exactas que el rayo cruza para chequear paredes. Para grid-based shooting, Bresenham es la herramienta. Para físicas continuas (con paredes irregulares), un raycast con DDA + chequeo geométrico es más preciso pero más caro.

Line-of-sight: Bresenham y recursive shadowcasting

0. Introducción

Line-of-sight (LOS) y FOV (field of view) son dos preguntas distintas pero relacionadas:

LOS: ¿el agente A puede ver el punto B? (boolean entre dos puntos)
FOV: ¿qué celdas ve el agente desde su posición, dentro de un radio? (set de celdas)

Ambas se construyen sobre la misma matemática: tirar una “raya” entre dos celdas y ver si toca un muro. Lo que cambia es cómo lo optimizas.

Algoritmo	Resuelve	Complejidad	Casos típicos
Bresenham	LOS punto-a-punto, dibujo de líneas	O(R) por línea	Disparos, raycasts simples
BFS + Bresenham (FOV simple)	FOV por radio	O(R³)	FOV “fácil”, didáctico
Recursive shadowcasting	FOV por radio	O(R²)	Roguelikes (NetHack, DCSS, Cogmind)
Symmetric shadowcasting	FOV simétrico	O(R²)	Cuando A ve B ⟺ B ve A

1. Bresenham — la base

Bresenham: el algoritmo clásico para dibujar líneas en grid. Cada celda atravesada se ilumina; la línea negra es la conexión geométrica ideal entre A y B. Bresenham aproxima esa línea con celdas enteras.

Figura 1 — La línea negra es la conexión geométrica ideal entre A y B; las celdas iluminadas son las que Bresenham marca al “discretizar” la línea sobre el grid. Arrastra A y B.

1.1 El algoritmo

Bresenham (1962) dibuja líneas en una grilla con solo enteros, sin divisiones ni multiplicaciones. La idea:

function bresenham(x0, y0, x1, y1) -> List<Cell>
    out = []
    dx = abs(x1 - x0)
    dy = abs(y1 - y0)
    sx = x0 < x1 ? 1 : -1
    sy = y0 < y1 ? 1 : -1
    err = dx - dy

    x, y = x0, y0
    loop:
        out.append((x, y))
        if x == x1 and y == y1: break
        e2 = 2 * err
        if e2 > -dy:
            err -= dy
            x += sx
        if e2 < dx:
            err += dx
            y += sy

    return out

err mantiene un “acumulador” del error vertical/horizontal. Cuando supera un umbral, da un paso lateral. Resultado: una secuencia de celdas que aproxima la línea.

1.2 Aplicación a LOS

Para chequear si A ve a B:

function hasLineOfSight(grid, a, b) -> bool
    for each cell on bresenham(a, b):
        if cell != a and cell != b and grid[cell].blocksVision:
            return false
    return true

Excluir A y B de la verificación es importante: una unidad puede estar “dentro” de un muro temporalmente (cubierta) y no querés que se desconecte de sí misma.

1.3 Variantes

Supercover Bresenham — incluye todas las celdas que la línea cruza, no solo el camino “thin” típico. Es más estricto: si la línea roza una esquina, esa celda cuenta. Para LOS conservador (no querés que el rayo “salte” entre obstáculos diagonales).
DDA (Digital Differential Analyzer) — usa floats, más simple pero menos preciso. Para casos no críticos.

2. Recursive Shadowcasting — el FOV de los roguelikes

Recursive shadowcasting: barre 8 octantes desde el origen. Al tocar un muro, propaga "sombras" angulares que ocluyen las celdas detrás. Es el FOV estándar en roguelikes (NetHack, DCSS, Caves of Qud).

radio8

Figura 2 — El algoritmo barre 8 octantes desde el origen, propagando “sombras” angulares cuando un muro corta la línea de visión. Las celdas detrás de un muro quedan ocluidas. Es lo que NetHack, DCSS y Caves of Qud usan.

2.1 La intuición

Mirá el origen como un sol y las celdas walkable como aire. Cuando un muro entra en el campo de visión, proyecta una sombra detrás de sí — una cuña angular donde la luz no llega. Recursive shadowcasting hace exactamente eso:

Divide el plano en 8 octantes (norte, noreste, este, sureste, sur, suroeste, oeste, noroeste).
Por cada octante, recorre celda por celda hacia afuera.
Mantiene un rango angular [startSlope, endSlope] que define qué partes del octante son “visibles”.
Cuando encuentra un muro, divide el rango en sub-rangos y recursea en cada uno. Eso es la “propagación de sombra”.

function castLight(grid, visible, ox, oy, radius, row, startSlope, endSlope, octant):
    if startSlope < endSlope: return
    nextStart = startSlope
    for i = row to radius:
        blocked = false
        for dx = -i to 0:
            lSlope = (dx - 0.5) / (dy + 0.5)
            rSlope = (dx + 0.5) / (dy - 0.5)
            if startSlope < rSlope: continue
            if endSlope > lSlope: break

            sax = ox + dx * octant.xx + dy * octant.xy
            say = oy + dx * octant.yx + dy * octant.yy
            if (dx² + dy²) <= radius²:
                visible[sax, say] = true

            if blocked:
                if grid[sax, say].blocksVision:
                    newStart = rSlope
                else:
                    blocked = false
                    startSlope = newStart
            else:
                if grid[sax, say].blocksVision and i < radius:
                    blocked = true
                    castLight(grid, visible, ox, oy, radius, i + 1, startSlope, lSlope, octant)
                    newStart = rSlope
        if blocked: break

Cada octante tiene su propia OctantTransform que mapea coordenadas locales a globales. El truco es que el algoritmo central solo trabaja con un octante (digamos norte-noreste); las simetrías cubren los otros 7.

2.2 Por qué O(R²) en vez de O(R³)

BFS + Bresenham hace R² lookups (todas las celdas en el círculo) y para cada una, un Bresenham de O(R) celdas — total O(R³). Shadowcasting toca cada celda a lo sumo una vez porque la “sombra” se propaga sin re-procesar lo ocluido. Para R = 12, eso es 1728 vs 144 ops — un orden de magnitud.

3. Comparativa visual

Mismo mapa, mismo origen, mismo radio. BFS + Bresenham chequea LOS celda por celda (O(R³)). Recursive shadowcasting propaga sombras por octante (O(R²)). Las celdas marcadas son casi idénticas; la diferencia es performance.

Figura 3 — Mismo mapa, mismo origen. Arriba: BFS + Bresenham. Abajo: recursive shadowcasting. Las celdas marcadas son casi idénticas; ambos dan resultados visualmente similares. La diferencia es cuántas operaciones hicieron para llegar.

3.1 Cuándo elegir uno u otro

BFS + Bresenham: didáctico, fácil de entender y debuggear. Apropiado para FOV one-shot o radio chico.
Shadowcasting: estándar en producción. Para FOV interactivo (recalculado cada turno o cada movimiento), la velocidad importa.
Symmetric shadowcasting: si necesitas la simetría dura (A ve B ⟺ B ve A), hay que usar la variante simétrica. Importa en gameplay donde “te tiraron desde un lugar invisible para vos pero visible para el shooter” se siente injusto.

4. FOV dinámico con memoria

Patrulla con FOV dinámico que se recalcula cada paso. Las celdas actualmente visibles brillan amarillo; las vistas antes quedan en gris (fog of war con memoria). El agente recorre 4 waypoints en loop.

Figura 4 — Un agente patrulla 4 waypoints. El FOV se recalcula en cada paso. Las celdas actualmente visibles brillan; las vistas antes quedan en gris (fog of war con memoria). Es lo que vos jugás como jugador en cualquier roguelike.

4.1 Tres estados por celda

estado de cada celda:
  - never_seen  → niebla total (negro)
  - seen_before → terreno conocido pero no visible ahora (gris)
  - visible_now → vista actualmente (color completo, unidades)

Implementación:

class FogOfWar
    seen: Set<Cell>      // todo lo visto alguna vez
    visible: Set<Cell>   // visible este turno

    function updateFov(unit, radius):
        visible = computeFov(grid, unit.position, radius)
        seen = seen ∪ visible    // memoria persistente

4.2 Detalles que importan

Reset de unidades enemigas en seen pero no visible: si vuelvo a una zona, no quiero ver “el enemigo que estaba ahí hace 30 turnos” — ya no está. Solo terreno persiste.
Reset on dungeon change: en roguelikes con niveles, la memoria es por nivel. Bajar al siguiente piso = niebla total.
Diff visualization: muchos juegos animan el “amarillo apareciendo” cuando una celda nueva se ve por primera vez. Es atención al detalle pero suma sensación.

5. Pseudocódigo — Bresenham + Shadowcasting

// Bresenham: línea entre dos celdas
function bresenhamCells(x0, y0, x1, y1) -> List<Cell>
    cells = []
    x, y = x0, y0
    dx = abs(x1 - x0)
    dy = abs(y1 - y0)
    sx = x0 < x1 ? 1 : -1
    sy = y0 < y1 ? 1 : -1
    err = dx - dy
    while true:
        cells.append((x, y))
        if x == x1 and y == y1: break
        e2 = 2 * err
        if e2 > -dy: err -= dy; x += sx
        if e2 < dx: err += dx; y += sy
    return cells

// LOS check trivial
function hasLineOfSight(grid, a, b) -> bool
    for cell in bresenhamCells(a, b):
        if cell != a and cell != b and grid[cell].blocksVision:
            return false
    return true

// FOV simple (BFS + LOS por celda)
function computeSimpleFov(grid, origin, radius) -> Set<Cell>
    visible = Set()
    for each cell c with chebyshevDist(c, origin) <= radius:
        if hasLineOfSight(grid, origin, c):
            visible.add(c)
    return visible

// FOV con shadowcasting: ver ShadowcastingViz arriba para implementación completa.

6. Implementación en Unity / C#

using UnityEngine;
using System.Collections.Generic;

public static class Los {
    public static List<Vector2Int> BresenhamCells(Vector2Int a, Vector2Int b) {
        var cells = new List<Vector2Int>();
        int x = a.x, y = a.y;
        int dx = Mathf.Abs(b.x - x), dy = Mathf.Abs(b.y - y);
        int sx = x < b.x ? 1 : -1, sy = y < b.y ? 1 : -1;
        int err = dx - dy;
        while (true) {
            cells.Add(new Vector2Int(x, y));
            if (x == b.x && y == b.y) break;
            int e2 = 2 * err;
            if (e2 > -dy) { err -= dy; x += sx; }
            if (e2 < dx) { err += dx; y += sy; }
        }
        return cells;
    }

    public static bool HasLos(bool[,] blocks, Vector2Int a, Vector2Int b) {
        var cells = BresenhamCells(a, b);
        for (int i = 1; i < cells.Count - 1; i++) {
            if (blocks[cells[i].x, cells[i].y]) return false;
        }
        return true;
    }

    // Recursive shadowcasting (8 octantes). Implementación completa en el asset.
    public static bool[,] ComputeFov(bool[,] blocks, Vector2Int origin, int radius) {
        int W = blocks.GetLength(0), H = blocks.GetLength(1);
        var visible = new bool[W, H];
        visible[origin.x, origin.y] = true;
        // ... 8 llamadas a CastLight() con sus OctantTransforms.
        return visible;
    }
}

7. En otros engines

Godot: Light2D con occluders y LightOccluder2D para FOV continuo. Para FOV por celdas (gameplay tactical), implementar custom.
Unreal: UAISense_Sight componente para perception system. Trae cone-based FOV para AI; para gameplay grid-based, custom.
JavaScript / TypeScript: la lib del sitio (~/lib/viz/sim/los) trae bresenhamCells, hasLos, computeFov (recursive shadowcasting) y computeSimpleFov.

8. Quiz

Pon a prueba lo que entendiste

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

Tu juego necesita verificar si un sniper ve al jugador desde el otro lado del mapa. ¿Qué algoritmo es ideal?
Implementás FOV con BFS + Bresenham por celda. En radio 14, parece lento. ¿Causa?
El jugador dispara desde un escondite y mata a un enemigo. El enemigo aparece quejándose porque 'lo mataron desde un lugar invisible'. ¿Qué falta?
El jugador vuelve a una zona que ya había explorado. ¿Cómo manejas la información en el fog of war?
Para tirar disparos en un FPS-2D estilo top-down, ¿qué algoritmo de raycast usás?