BFS, DFS y FloodFill: cómo recorrer un grafo

0. Introducción

Antes de A*, antes de Dijkstra, antes de NavMesh y flow fields, hay tres recorridos. Los tres parten de un nodo y visitan el resto del grafo. Cambia qué orden eligen y para qué los puedes usar:

• BFS (Breadth-First Search) — explora en anillos de distancia. Es la base de Dijkstra, A*, flow fields y la mitad del gameplay táctico que existe.
• DFS (Depth-First Search) — se mete hasta el fondo del primer pasillo y vuelve. Es la base de generación procedural (BSP, mazes), detección de ciclos, y backtracking.
• FloodFill — BFS con un predicado: rellena todo lo que está conectado y comparte una propiedad. Es el cubo de pintura, las zonas conectadas en Minecraft, el agua de Noita.

Si ya entiendes estos tres, los tutoriales siguientes (Dijkstra, A*, flow fields) son refinamientos. Si todavía los confundes, este es el tutorial para fijar el modelo mental.

¿Cuándo aplicar cuál?

Situación	Algoritmo	Por qué
”¿Cuál es el camino más corto en celdas (sin costos)?”	BFS	El primer camino que encuentra es óptimo en distancia uniforme.
”¿Hay camino entre A y B?”	BFS o DFS	Ambos llegan; BFS te da además distancia.
”Quiero pintar todo lo conectado del mismo color”	FloodFill	Es BFS con predicate(x, y).
”Voy a generar una mazmorra recorriendo backtrack”	DFS	El stack se llena/vacía como sale/entra de pasillos.
”Un agente se mueve entre celdas con costos diferentes”	Dijkstra (no BFS)	BFS asume costo uniforme; falla si el barro cuesta 3 y el camino 1.
”Mismo, pero con goal conocido”	A*	Dijkstra + heurística.

1. BFS — anillos de distancia

BFS visita primero los vecinos del origen (distancia 1), luego los vecinos de los vecinos (distancia 2), y así sucesivamente. La estructura que lo hace funcionar es una cola FIFO (queue): lo primero que entra es lo primero que sale.

BFS expande en anillos de distancia: la celda más cercana al origen siempre se procesa antes que la más lejana. Click para añadir/quitar muros, Shift+click para mover el origen. El gradiente azul→rojo es el orden en que se descubrieron las celdas.

PausaReset

velocidad (cells/s)60

Figura 1 — La frontera se ilumina en el orden en que BFS descubre cada celda. El gradiente azul→rojo cuenta el orden de visita; las celdas más oscuras se vieron más tarde.

1.1 El bucle, en una sola página

function bfs(grid, start)
    visited = Set()
    parent = Map()
    queue = Queue()
    queue.enqueue(start)
    visited.add(start)

    while queue not empty
        current = queue.dequeue()
        for each neighbor of current
            if neighbor walkable and not in visited
                visited.add(neighbor)
                parent[neighbor] = current
                queue.enqueue(neighbor)

Lo único que necesitas explicar:

1. visited evita ciclos. Sin él, en un grafo cíclico BFS se queda dando vueltas.
2. parent te permite reconstruir el camino al final, siguiendo los punteros desde el goal hasta el start.
3. Cola FIFO es lo que da la propiedad de anillos. Si fuera un stack (LIFO), tendrías DFS.

1.2 Encontrar el camino más corto (sin costos)

Cuando BFS llega al goal, sigue los parent[] para atrás:

function reconstructPath(parent, goal)
    path = []
    current = goal
    while current exists
        path.push(current)
        current = parent[current]
    return reverse(path)

Garantía: ese camino tiene el mínimo número de pasos posible. No el menor costo (si los pasos cuestan distinto, BFS miente — para eso está Dijkstra).

1.3 Casos prácticos en juegos

• Rangos de movimiento en tactical (XCOM, Fire Emblem): BFS desde el agente, expandir hasta movePoints. Las celdas alcanzables se pintan azul.
• Detección de zonas conectadas en Minecraft: ¿este chunk está conectado al resto del mundo? Floodfill con BFS.
• Auto-pilot de Snake: BFS desde la cabeza hasta la fruta, ignorando casillas con cuerpo.
• Distance maps para IA huidiza: BFS desde el jugador, los enemigos siguen el gradiente inverso (eso lo verás en Dijkstra aplicado cuando los costos entren en juego).

2. DFS — al fondo del primer pasillo

DFS cambia una sola línea respecto a BFS: usa stack en vez de queue. Eso convierte “explora lo cercano primero” en “explora hasta tocar pared, luego retrocede”.

DFS empuja al stack y va al fondo del primer callejón disponible. La línea roja es el camino actual desde el origen — fíjate cómo serpentea, no expande en anillos. Click para muros, Shift+click para mover el origen.

PausaReset

velocidad (cells/s)80

Figura 2 — La línea roja es el camino actual desde el origen, siguiendo el stack. Fíjate cómo serpentea por callejones enteros antes de retroceder. No expande en círculos: sigue el primer hilo hasta que se acaba.

2.1 El mismo bucle, otra estructura

function dfs(grid, start)
    visited = Set()
    stack = Stack()
    stack.push(start)
    visited.add(start)

    while stack not empty
        current = stack.pop()
        for each neighbor of current
            if neighbor walkable and not in visited
                visited.add(neighbor)
                parent[neighbor] = current
                stack.push(neighbor)

Recursivo es la otra forma habitual:

function dfs(node, visited)
    if node in visited: return
    visited.add(node)
    for each neighbor of node
        dfs(neighbor, visited)

Mismo algoritmo. La recursión usa el call stack del lenguaje en lugar de un stack explícito. La versión iterativa con stack explícito es mejor para grafos grandes (no te explota la pila de llamadas en una mazmorra de 10000 nodos).

2.2 Lo que DFS NO te da

• NO te da el camino más corto. Lo primero que encuentras puede ser tres veces más largo que el óptimo.
• NO es bueno para “expandir hasta cierto rango”. El stack te dispara lejos antes de cubrir lo cercano.

Lo que sí te da y BFS no:

• Backtracking natural para generación procedural. Mazes tipo Recursive Backtracker son DFS donde, al toparte con un callejón, retrocedes hasta encontrar un fork sin explorar.
• Detección de ciclos en grafos dirigidos.
• Topological sort (orden de dependencias).
• Componentes conexas y strongly connected components (Tarjan, Kosaraju — ambos son DFS sofisticado).

3. FloodFill — BFS con un predicado

FloodFill es BFS donde el “vecino válido” no es solo walkable, sino una propiedad que pasas como parámetro:

El "cubo de pintura" de Photoshop. Click en cualquier región y FloodFill expande celda por celda hasta llegar a una frontera de color distinto. Es BFS con un predicado de color como condición de avance.

PausaReset

velocidad (cells/s)120

Figura 3 — Click en cualquier región. El flood se expande celda por celda mientras todas las celdas vecinas comparten el color de la celda inicial. Cuando toca un color distinto, ahí termina la frontera.

3.1 El cambio mínimo respecto a BFS

function floodFill(grid, start, predicate)
    queue = Queue()
    visited = Set()
    queue.enqueue(start)
    visited.add(start)

    while queue not empty
        current = queue.dequeue()
        for each neighbor of current
            if predicate(neighbor) and neighbor not in visited
                visited.add(neighbor)
                queue.enqueue(neighbor)

predicate decide si la celda forma parte de la región. Es una abstracción mínima pero abre muchísimos casos de uso.

3.2 Variantes y aplicaciones

• Bucket fill de Photoshop: predicate = sameColorWithinTolerance(neighbor, originalColor, tolerance).
• Match-3 clearing: el predicate es “mismo color que el grupo que hizo match”; al detectar 3+ se ejecuta floodfill para encontrar el grupo entero.
• Connected components: ejecutas floodfill desde cada celda no visitada y cada llamada genera una región nueva. Útil para clasificar zonas de un mapa procedural.
• Limit por iteraciones: si quieres simular un “temblor que se propaga N celdas y se detiene”, agregas un contador de pasos al floodfill. Eso lo verás en FloodFill aplicado.

4. BFS vs DFS — lado a lado

Cambiar una sola línea (queue → stack) cambia drásticamente la forma del recorrido. Lado a lado, sobre el mismo mapa y origen:

Mismo origen, mismos muros: lo único que cambia es queue vs stack. BFS mancha en anillos; DFS dispara hacia adelante hasta tocar pared. Si llegan al mismo destino visitan el mismo número de celdas, pero el orden y la "forma" de la mancha es completamente distinto.

PausaReset

velocidad (cells/s)80

Figura 4 — BFS arriba (cola), DFS abajo (stack). Mismas paredes, mismo origen. BFS pinta anillos, DFS dispara serpentinas.

Si llegan a cubrir todo el grafo, el número total de celdas visitadas es idéntico — la diferencia está en el orden. Y el orden es lo que hace que cada uno sirva para cosas distintas.

5. Implementación en Unity / C#

using System.Collections.Generic;
using UnityEngine;

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

    public static List<Vector2Int> Bfs(bool[,] walkable, Vector2Int start, Vector2Int goal) {
        int W = walkable.GetLength(0), H = walkable.GetLength(1);
        var parent = new Dictionary<Vector2Int, Vector2Int>();
        var visited = new HashSet<Vector2Int> { start };
        var queue = new Queue<Vector2Int>();
        queue.Enqueue(start);

        while (queue.Count > 0) {
            var cur = queue.Dequeue();
            if (cur == goal) return Reconstruct(parent, goal);
            foreach (var d in Dirs4) {
                var n = cur + d;
                if (n.x < 0 || n.y < 0 || n.x >= W || n.y >= H) continue;
                if (!walkable[n.x, n.y] || visited.Contains(n)) continue;
                visited.Add(n);
                parent[n] = cur;
                queue.Enqueue(n);
            }
        }
        return null;
    }

    public static int FloodFillCount(int[,] regions, Vector2Int start) {
        int W = regions.GetLength(0), H = regions.GetLength(1);
        int targetColor = regions[start.x, start.y];
        var visited = new HashSet<Vector2Int> { start };
        var queue = new Queue<Vector2Int>();
        queue.Enqueue(start);
        int count = 0;
        while (queue.Count > 0) {
            var cur = queue.Dequeue();
            count++;
            foreach (var d in Dirs4) {
                var n = cur + d;
                if (n.x < 0 || n.y < 0 || n.x >= W || n.y >= H) continue;
                if (regions[n.x, n.y] != targetColor || visited.Contains(n)) continue;
                visited.Add(n);
                queue.Enqueue(n);
            }
        }
        return count;
    }

    static List<Vector2Int> Reconstruct(Dictionary<Vector2Int, Vector2Int> parent, Vector2Int goal) {
        var path = new List<Vector2Int> { goal };
        while (parent.TryGetValue(goal, out var prev)) {
            path.Add(prev);
            goal = prev;
        }
        path.Reverse();
        return path;
    }
}

6. En otros engines

• Godot: AStarGrid2D trae BFS y A* para grids; para FloodFill, escribes el bucle manual con Vector2i — es media página.
• Unreal: FNavigationSystem te da pathfinding sobre navmesh, pero para gameplay con grids (tactical, puzzle) lo más práctico es escribirlo a mano sobre TArray<TArray<bool>>.
• JavaScript / TypeScript: la lib del sitio (~/lib/viz/sim/pathfinding) es exactamente esto, con generadores para que las visualizaciones puedan animarlo paso a paso.

7. Quiz

Pon a prueba lo que entendiste

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

1. Tienes un grid sin costos heterogéneos y necesitas el camino más corto en número de pasos. ¿Qué algoritmo usas?

   • ABFS. La primera vez que toca el goal, el camino reconstruido por parent[] es óptimo en distancia uniforme.
   • BDFS. Suele encontrar caminos rápido.
   • CDijkstra. Es el algoritmo estándar para shortest path.

2. ¿Qué cambia conceptualmente entre BFS y DFS?

   • ALa estructura: BFS usa queue (FIFO), DFS usa stack (LIFO). Eso convierte 'lo cercano primero' en 'al fondo primero'.
   • BDFS es siempre recursivo, BFS es siempre iterativo.
   • CBFS no usa memoria adicional, DFS sí.

3. FloodFill encuentra todas las celdas conectadas que cumplen una propiedad. ¿Cómo se relaciona con BFS?

   • AEs BFS con un predicado: en vez de 'walkable', usa una función arbitraria que decide si la celda forma parte de la región.
   • BEs un algoritmo distinto de BFS, basado en recursión.
   • CEs solo aplicable a imágenes.

4. Para generar una mazmorra estilo roguelike con 'recursive backtracker', ¿BFS o DFS?

   • ADFS. El stack se llena cuando metes el cabezal en un pasillo nuevo y se vacía cuando ese pasillo se acaba — ideal para backtracking.
   • BBFS. Genera resultados más balanceados.
   • CFloodFill. Llena la mazmorra desde múltiples puntos.

5. Tienes un grid 100x100 y la simulación de fuego tiene que propagarse, pero a una velocidad finita: el fuego no salta más de 5 celdas por segundo. ¿Cómo lo modelas?

   • AFloodFill con un contador de pasos: cada paso del flood representa una unidad de tiempo. Procesas N celdas por frame y dejas el resto en la cola hasta el próximo frame.
   • BBFS completo cada frame.
   • CDFS hasta el fondo y luego replicas el resultado por celda.

8. Siguientes pasos