FloodFill aplicado: temblores, fuego, Match-3 y electricidad

0. Introducción

FloodFill es BFS con un predicado. Cambias el predicado y obtienes un algoritmo distinto cada vez. En este tutorial pasamos por cinco aplicaciones que aparecen en juegos reales y que solo requieren ajustar el predicate o añadir un contador.

Caso	Predicate / variante	Juegos donde aparece
Temblor sísmico	FloodFill bounded por iteraciones	Lemmings, simuladores físicos
Propagación de fuego	FloodFill probabilístico modulado por humedad	Don’t Starve, Noita, Project Zomboid
Match-3 clearing	FloodFill por mismo color + check de tamaño ≥ 3	Candy Crush, Bejeweled, Threes
Electricidad	FloodFill por conductores conectados	Factorio, SpaceChem, juegos de cables
Mancha de pintura	FloodFill probabilístico con porosidad	herramientas de arte, juegos de pintura

Las cinco se implementan en menos de 30 líneas cada una si ya tienes un BFS escrito. Lo difícil no es el algoritmo: es elegir el predicate correcto.

1. Temblor sísmico — FloodFill bounded

Onda sísmica como FloodFill bounded: cada celda guarda su tiempo de llegada (BFS desde el epicentro). En runtime, la celda vibra con amplitud que decae con la distancia.

alcance (celdas)15

Figura 1 — Click en cualquier celda y la onda se propaga limitada por el slider de alcance. Cada celda guarda su tiempo de llegada (BFS desde el epicentro). En runtime, vibra con amplitud que decae con la distancia.

1.1 La idea

Un temblor sísmico no se propaga al infinito: tiene un radio. La forma natural de modelarlo es BFS limitado por iteraciones:

function earthquake(grid, epicenter, maxRadius)
    arrival = Map.fillWith(-1)
    arrival[epicenter] = 0
    queue = Queue()
    queue.enqueue(epicenter)
    while queue not empty
        current = queue.dequeue()
        if arrival[current] >= maxRadius: continue
        for each neighbor of current
            if arrival[neighbor] < 0
                arrival[neighbor] = arrival[current] + 1
                queue.enqueue(neighbor)
    return arrival

arrival[cell] te dice cuándo la onda toca esa celda. Después, en cada frame:

for each cell with arrival >= 0
    timeSinceShake = currentTime - arrival[cell] * waveSpeed
    if 0 <= timeSinceShake < shakeDuration
        amp = sin(timeSinceShake * frequency) * (1 - arrival[cell] / maxRadius)
        renderCell(cell + randomOffset(amp))

Lo notable: el BFS corre una sola vez al disparar el temblor. La animación es trivial después.

1.2 Variantes

• Múltiples epicentros — corres BFS multi-source: encolas todos los epicentros con arrival = 0 y haces un solo barrido.
• Atenuación por terreno — usas Dijkstra en lugar de BFS y costos heterogéneos: el temblor cuesta más cruzar arena que roca, viaja menos.
• Shockwave en círculos perfectos — si no necesitas terreno, un simple dist(cell, epicenter) <= radius calcula arrival sin BFS. Pero si hay obstáculos, BFS es la única forma honesta.

2. Propagación de fuego con humedad

Cada celda tiene humedad (color verde→ámbar). El fuego solo prende vecinos con humedad baja, y con probabilidad inversa a esa humedad. Click para encender; sube el slider y mira cómo el incendio se ahoga.

PausaReset

humedad global0.35

Figura 2 — Cada celda tiene humedad propia (verde→ámbar). El fuego solo prende vecinos con humedad baja, con probabilidad inversa a esa humedad. Sube el slider de humedad global y ve el incendio ahogarse.

2.1 No es FloodFill puro: es probabilístico

El fuego no se propaga determinísticamente. Tu predicate es:

function shouldIgnite(cell, neighbors)
    burningCount = count of neighbors that are burning
    if burningCount == 0: return false
    moisture = cell.moisture     # 0..1
    igniteProbability = 0.85 * (1 - moisture) * min(burningCount, 3) / 3
    return random() < igniteProbability

Tres factores se combinan:

• Vecinos quemándose — más vecinos = más probable.
• Humedad de la celda — alta humedad reduce la probabilidad.
• Aleatoriedad — bordes irregulares.

El estado de cada celda es un pequeño FSM:

0 → 1 (igniting): si shouldIgnite(cell)
1 → 2 (burnout):  con probabilidad burnoutChance por tick
2 → 2:            quemado, no propaga más

2.2 Casos prácticos

• Don’t Starve: humedad por celda + viento direccional (sesga la probabilidad hacia un lado).
• Project Zomboid: madera quema rápido, concreto no quema; el predicate filtra por tipo de tile.
• Noita: cada material tiene flammability propia; mezclas de líquidos modifican humedad local en runtime.

3. Match-3 clearing

Click sobre una ficha. FloodFill busca el grupo conectado del mismo color. Si son ≥3, se borran y caen las fichas de arriba (Candy Crush, Threes, Bejeweled). Si son menos, no pasa nada.

Score: 0

Figura 3 — Click sobre una ficha. FloodFill busca el grupo conectado del mismo color. Si son ≥3, se borran y caen las fichas de arriba. La gravedad rellena con fichas nuevas en el tope.

3.1 El predicate

function findGroup(grid, x, y) -> List<Cell>
    target = grid[x, y]
    return floodFill(grid, (x, y), predicate = (n) -> grid[n] == target)

Tres líneas. El truco es la condición de filtrado al final:

group = findGroup(grid, clickX, clickY)
if group.length >= 3
    for cell in group:
        grid[cell] = empty
    applyGravity(grid)     # las fichas de arriba caen
    refillTop(grid)         # nuevas fichas en celdas vacías

3.2 Variantes que aparecen en producción

• Match-3 con direcciones: solo cuentan grupos en línea recta (3 horizontal, 3 vertical, 3 diagonal). El predicate sigue siendo “mismo color”; pero al evaluar el grupo, descartas si no hay alineación.
• Combos en cascada: tras clear + gravity, vuelves a buscar grupos automáticamente. Si encuentras, repites. Esa cascada produce los “mega combos”.
• Power-ups: borrar 4 alineadas crea una bomba; borrar 5 crea un rayo. Detectarlo es analizar la forma del grupo después del FloodFill.

4. Electricidad encadenada

La fuente amarilla emite electricidad. FloodFill recorre solo celdas conductoras conectadas (4-conexo). Diseña la red dibujando conductores y ve la chispa propagarse en cadena.

Figura 4 — La fuente amarilla emite electricidad. Click + drag para añadir o quitar conductores. FloodFill recorre solo las celdas conductoras conectadas — exactamente como un circuito eléctrico.

4.1 FloodFill por componente conexa

El predicate es cell.isConductor. Lo que ves es una componente conexa del grafo de conductores que contiene la fuente:

function powerNetwork(grid, source) -> Set<Cell>
    return floodFill(grid, source, predicate = (n) -> n.isConductor)

Una vez que tienes el set de celdas energizadas, las animas en cascada con arrival[cell] (el orden BFS) — exactamente como el temblor de §1.

4.2 Aplicaciones

• Factorio — cada generador tiene una red de cables. Cortar un cable cambia qué máquinas reciben energía. Recálculo via FloodFill cuando el grafo cambia.
• Cables y switches — un switch que se rompe corta toda la rama: la componente conexa desde la fuente cambia.
• Cadena de bombas (Bomberman extreme): una bomba detona, FloodFill por bombas adyacentes en rango → todas detonan simultáneamente.

5. Mancha de pintura — porosidad

FloodFill probabilístico: cada vecino se pinta con probabilidad porosidad. Bordes irregulares emergen naturalmente. Click para soltar una gota; sube/baja la porosidad para manchas más cerradas o más etéreas.

porosidad0.78↺ Limpiar

Figura 5 — FloodFill probabilístico con un solo parámetro: porosidad. Cada vecino se pinta con esa probabilidad. Bordes irregulares emergen naturalmente, como pintura sobre material orgánico.

5.1 El cambio mínimo respecto a FloodFill

function paintStain(grid, origin, porosity)
    painted = Set()
    queue = Queue()
    painted.add(origin)
    queue.enqueue(origin)
    while queue not empty
        cur = queue.dequeue()
        for each neighbor of cur
            if neighbor not in painted and random() < porosity
                painted.add(neighbor)
                queue.enqueue(neighbor)
    return painted

Una sola línea cambia respecto a FloodFill clásico: random() < porosity. Eso convierte una expansión limpia en una mancha orgánica.

5.2 Cuándo lo necesitas

• Manchas de óxido, moho que crece, plagas que se extienden.
• Manchas de sangre o pintura splat en shooters.
• Niebla local que se propaga con dirección.

6. Pseudocódigo común — el patrón compartido

Todos los casos comparten esqueleto:

function appliedFloodFill(grid, origin, predicate, decorate)
    visited = Set()
    queue = Queue()
    visited.add(origin)
    queue.enqueue(origin)
    decorate(origin, distance = 0)
    while queue not empty
        cur = queue.dequeue()
        for each neighbor of cur
            if predicate(cur, neighbor) and neighbor not in visited
                visited.add(neighbor)
                decorate(neighbor, distance = cur.distance + 1)
                queue.enqueue(neighbor)
    return visited

Los cinco efectos solo cambian dos cosas:

• predicate(cur, neighbor) — qué cuenta como “vecino válido”.
• decorate(cell, distance) — qué información extra guardas (tiempo de llegada, color, energía).

Si tienes esa abstracción en una función, los cinco efectos te toman 15-20 líneas cada uno.

7. Implementación en Unity / C#

using System;
using System.Collections.Generic;
using UnityEngine;

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

    public delegate bool Predicate(Vector2Int cur, Vector2Int neighbor);
    public delegate void Decorator(Vector2Int cell, int distance);

    public static void Run(int cols, int rows, Vector2Int origin, Predicate p, Decorator d) {
        var visited = new HashSet<Vector2Int> { origin };
        var queue = new Queue<(Vector2Int cell, int dist)>();
        queue.Enqueue((origin, 0));
        d(origin, 0);

        while (queue.Count > 0) {
            var (cur, dist) = queue.Dequeue();
            foreach (var dir in Dirs4) {
                var n = cur + dir;
                if (n.x < 0 || n.y < 0 || n.x >= cols || n.y >= rows) continue;
                if (visited.Contains(n)) continue;
                if (!p(cur, n)) continue;
                visited.Add(n);
                d(n, dist + 1);
                queue.Enqueue((n, dist + 1));
            }
        }
    }

    // Ejemplo: temblor sísmico
    public static int[,] Earthquake(int cols, int rows, Vector2Int epicenter, int maxRadius) {
        var arrival = new int[cols, rows];
        for (int x = 0; x < cols; x++) for (int y = 0; y < rows; y++) arrival[x, y] = -1;

        Run(cols, rows, epicenter,
            (cur, n) => Vector2Int.Distance(epicenter, n) <= maxRadius,
            (cell, dist) => arrival[cell.x, cell.y] = dist);

        return arrival;
    }

    // Ejemplo: fuego probabilístico (un solo step; llamar por tick)
    public static void StepFire(int[,] state, float[,] moisture) {
        int W = state.GetLength(0), H = state.GetLength(1);
        var next = (int[,])state.Clone();
        for (int y = 0; y < H; y++)
            for (int x = 0; x < W; x++) {
                if (state[x, y] == 1) {
                    if (UnityEngine.Random.value < 0.06f) next[x, y] = 2;
                    continue;
                }
                if (state[x, y] == 2) continue;
                int burning = 0;
                foreach (var d in Dirs4) {
                    int nx = x + d.x, ny = y + d.y;
                    if (nx < 0 || ny < 0 || nx >= W || ny >= H) continue;
                    if (state[nx, ny] == 1) burning++;
                }
                if (burning > 0) {
                    float prob = 0.85f * (1f - moisture[x, y]) * Mathf.Min(burning, 3) / 3f;
                    if (UnityEngine.Random.value < prob) next[x, y] = 1;
                }
            }
        Array.Copy(next, state, next.Length);
    }
}

8. En otros engines

• Godot: el patrón se traduce directo. TileMap con tipos de celda + un predicate por enum, todo sobre Vector2i.
• Unreal: TArray<TArray<int>> para grid + TQueue para BFS. Para gameplay con grids, custom es la opción.
• JavaScript / TypeScript: la lib del sitio (~/lib/viz/sim/pathfinding) trae floodFill como generador, perfecto para animar paso a paso.

9. Quiz

Pon a prueba lo que entendiste

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

1. Tu juego tiene un sistema de fuego que se propaga. Quieres que prenda más rápido en madera y casi nada en piedra. ¿Cómo lo modelas?

   • ACada celda tiene una propiedad 'flammability' (0..1). El predicate de propagación es 'random() < flammability * factor(vecinos quemándose)'.
   • BDos FloodFills separados, uno para madera y uno para piedra.
   • CHard-coded en el predicate: 'if material == wood return true'.

2. El usuario hace click sobre una ficha en Match-3. ¿Cómo decides si el grupo se borra?

   • AFloodFill desde la ficha clickeada con predicate 'mismo color'. Si el grupo encontrado tiene tamaño ≥ 3, se borra. Si no, no pasa nada (o feedback visual).
   • BComparas con cada ficha del tablero individualmente.
   • CDFS para encontrar el grupo.

3. Tienes una red de cables eléctricos donde cortar uno corta toda la rama. ¿Cuándo recalculas qué máquinas tienen energía?

   • ASolo cuando cambia la topología (alguien construye/destruye un cable). FloodFill desde la fuente: O(N) por evento, no por frame.
   • BCada frame, FloodFill desde cada fuente.
   • CNunca: dejas la red estática.

4. Quieres una mancha de óxido que crezca lentamente sobre el metal. ¿Qué variante de FloodFill usas?

   • AFloodFill probabilístico con ticks: por tick, cada celda con óxido tiene baja probabilidad de propagar a un vecino. La mancha crece orgánica con bordes irregulares.
   • BFloodFill clásico instantáneo.
   • CDFS recursivo desde el origen.

5. Para un temblor sísmico que se propaga a velocidad finita y decae con distancia, ¿qué guardas por celda?

   • AEl tiempo de llegada (frame en que la onda toca esa celda). Lo calculas una vez con BFS desde el epicentro; la animación lee ese valor cada frame.
   • BRecalcular el FloodFill cada frame.
   • CLa distancia euclidiana al epicentro.

10. Siguientes pasos