Wave Function Collapse: tilemaps coherentes

0. Procgen con reglas, no con ruido

Perlin es ruido coherente: te da campos suaves para heightmaps. Pero cuando quieres tiles discretos con reglas claras — “agua nunca toca montaña sin playa de por medio”, “los caminos forman una red conectada”, “los castillos solo tienen torres en las esquinas” — Perlin se queda corto.

WFC ataca el problema desde el lado opuesto. Define un set de tiles + reglas de adyacencia (“este tile puede ir junto a este otro en esta dirección”) y la generación garantiza que toda salida cumple las reglas. No hay post-pass para arreglar inconsistencias; las reglas son durable.

▶ Auto⏭ Step↺ Reset↻ Nueva seedpaso 0 · seed 1 · ...

Cada celda empieza con todos los tiles posibles. WFC repite: observe (encuentra la celda con menor entropía → aro azul), collapse (colapsa a un tile pesando → flash verde), propagate (recalcula opciones de los vecinos). Si una celda queda sin opciones → contradicción y rollback (flash rojo).

Figura 1 — WFC corriendo paso a paso. Las celdas con número (X) tienen X tiles posibles aún. Aro azul: la celda elegida para colapsar. Verde: tile elegido. Rojo: contradicción (la celda quedó sin opciones) → rollback. Pulsa “Auto” o avanza con “Step”.

Lo usan Caves of Qud (mapas de mundos), Townscaper (urbanismo orgánico), Bad North (islas), Townseek y miles de jam games.

1. La metáfora cuántica

WFC toma su nombre prestado de la mecánica cuántica:

• Cada celda empieza en superposición: todos los tiles son posibles simultáneamente.
• Cada observation colapsa una celda a un tile concreto.
• Las observaciones de una celda se propagan a las vecinas, descartando opciones incompatibles.

Es la metáfora que da nombre, pero el algoritmo subyacente es constraint propagation clásico (AC-3, lo que cualquier curso de IA enseña en la unidad de SAT/CSP).

2. Setup: tiles y reglas

Click en un tile (fila superior) para seleccionarlo. La cruz central muestra qué vecinos son legales en cada dirección. La matriz a la derecha es la tabla simétrica de adyacencias del tileset completo.

Figura 2 — Set de 6 tiles. La cruz central muestra qué vecinos son legales para el tile seleccionado en cada dirección. La matriz de la derecha es la tabla simétrica completa: verde = adyacencia permitida.

2.1 Tile definition

Cada tile tiene:

• Display (color, sprite, mesh).
• Weight — qué tan probable es que se elija al colapsar (sesga la distribución hacia tiles “naturales”).
• Conexiones por borde — qué patrón visual tiene cada lado.

2.2 Reglas de adyacencia

Hay dos formas de derivar las reglas:

1. Manual — declaras tabla de qué tile va con qué (lo que hace la viz arriba).
2. From example — le pasas una imagen de ejemplo, WFC analiza qué pares aparecen juntos y deriva las reglas automáticamente. Esto es el “overlapping model” de Maxim Gumin (el creador original).

Para empezar, manual. Para producción con assets visuales finos, from-example.

3. El algoritmo: observe → collapse → propagate

function wfc(grid):
    # 1) inicializar: cada celda tiene todos los tiles posibles (superposición)
    for each cell:
        cell.options = ALL_TILES

    while True:
        # 2) observe: encontrar la celda con menor entropía (menos opciones)
        cell = findLowestEntropyCell(grid)
        if cell == null: return SUCCESS  # todas colapsadas

        # 3) collapse: pickear un tile pesando por weight
        tile = pickWeighted(cell.options, weights)
        cell.options = { tile }

        # 4) propagate: actualizar opciones de vecinos
        if not propagate(cell):
            return CONTRADICTION

3.1 Lowest entropy heuristic

¿Por qué empezar por la celda con menos opciones?

Heatmap de entropía↻ Nueva seed: 7

Verde = pocas opciones (1–2 tiles posibles). Naranja = entropía media. Rojo = muchas opciones (apenas constrained). WFC siempre colapsa primero la celda más verde — la elección es la más segura porque tiene menos chances de generar contradicción río abajo.

Figura 3 — El heatmap muestra entropía por celda. Verde = pocas opciones (próxima a colapsar). Naranja/rojo = muchas opciones. WFC siempre elige la celda más verde.

Razón: la celda con menos opciones es la más constrained — la elección que hagas allí es la menos arbitraria. Si esperas a que tenga 1 opción, no es elección sino determinación. Si la dejás para el final, su única opción podría ya ser inconsistente con las decisiones que tomaste antes — contradicción tardía.

Es una heurística codiciosa que minimiza la chance de backtrack.

3.2 Propagación: AC-3

Cuando colapsas una celda, sus opciones cambian. Eso afecta a sus vecinos: tiles que ya no son compatibles deben removerse. Y eso puede afectar a los vecinos de los vecinos. Y así.

function propagate(startCell):
    stack = [startCell]
    while stack not empty:
        cell = stack.pop()
        for each neighbor (n, dir) of cell:
            possibleAtN = union of allowed[t][dir] for t in cell.options
            removed = n.options ∩ ¬possibleAtN
            if removed not empty:
                n.options -= removed
                if n.options empty: return false  # contradicción
                stack.push(n)
    return true

allowed[t][dir] es un bitset: bits puestos a 1 para los tiles que pueden ir como vecino de t en la dirección dir. Hacer la unión, intersección y check de vacío con bitsets es ridículamente rápido — mil tiles caben en ~32 enteros.

3.3 Bitsets son la clave de performance

Para N tiles:

• cell.options = bitset de N bits.
• allowed[t][dir] = bitset de N bits.
• Unión = OR. Intersección = AND. Vacío = todos los words son 0.

Sin bitsets, WFC sería 10–50× más lento. Con bitsets, generas un mapa de 50×50 con 100 tiles en milisegundos.

4. Contradicciones y backtrack

A veces las reglas son tan estrictas (o el grid tan pequeño) que llegas a un punto sin solución: una celda queda con cero opciones. ¿Qué haces?

Opción A: empezar de nuevo con otra seed. Funciona para casos simples; impractical para tilesets grandes.

Opción B: backtrack. Mantienes un stack de snapshots; cada vez que colapsas una celda, guardas el estado anterior. Si propagate detecta contradicción, restauras el snapshot y excluyes la elección que falló. Si todas las elecciones fallan, retrocede al snapshot anterior.

function wfcWithBacktrack(grid):
    snapshots = []
    while True:
        cell = findLowestEntropyCell(grid)
        if cell == null: return SUCCESS

        tile = pickWeighted(cell.options - bannedAt(cell), weights)
        if tile == null:
            # no quedan opciones aquí; rollback
            if snapshots.empty: return GLOBAL_FAILURE
            restore(snapshots.pop())
            continue

        snapshots.push(snapshot(grid, cell, tile))
        cell.options = { tile }
        if not propagate(cell):
            restore(snapshots.pop())
            ban(cell, tile)

El backtrack es lo que hace WFC robusto. Sin él, generaciones de mapas grandes fallan ~10% del tiempo. Con él, fallan ~0%.

5. Variabilidad de salida

↻ Regenerar los 4

Mismo tileset, mismas reglas, distinta seed. WFC es determinístico dada una seed: regeneras y obtienes idéntico output. La variación viene de la seed; las reglas garantizan que cualquier output sea coherente (no hay agua tocando montaña sin transiciones).

Figura 4 — Mismas reglas, mismo tileset, 4 seeds distintas. Outputs visualmente diversos pero todos coherentes. WFC es determinístico dada una seed.

Pulsa “Regenerar los 4” varias veces. Notarás:

• Los outputs son diversos: la misma estructura nunca aparece dos veces seguidas.
• Pero todos respetan las reglas: nunca verás una celda de agua junto a una de montaña sin transición.

Esa combinación — diversidad + coherencia — es lo que hace a WFC mejor que el “spam de Perlin + lookup table”.

6. Cuándo usar WFC

6.1 Buen fit

• Tilemaps con conectividad fuerte (caminos, ríos, paredes).
• Patrones repetitivos con variación (ciudades, mosaicos).
• Mundos con reglas explícitas (“siempre hay un boss en el tile rojo”).
• Generación offline (compilar mundos en build time).

6.2 Mal fit

• Mundos enormes en tiempo real — WFC es slow para 1000×1000 sin tricks (chunking, hierarchical).
• Heightmaps continuos — usá Perlin.
• Sin reglas claras — si no tienes idea de qué adyacencias son legales, WFC no es para ti.

6.3 Trade-offs vs Perlin

Aspecto	Perlin	WFC
Continuidad	✓	Discreto
Reglas explícitas	✗	✓
Velocidad	Muy rápido	Más lento
Determinístico	Por seed	Por seed
Estructura emergente	Limitada	Cualquier patrón expresable como reglas

7. Implementación en Unity / C#

public class WFC {
    int cols, rows, tileCount;
    uint[][] wave;            // wave[cellIdx] = bitset de tiles posibles
    uint[][] adj;             // adj[t * 4 + dir] = bitset de vecinos legales
    System.Random rng;

    public bool Step() {
        int cell = FindLowestEntropyCell();
        if (cell == -1) return true; // done

        int tile = PickWeighted(cell);
        if (tile == -1) return false; // contradiction

        SetSingleTile(cell, tile);
        return Propagate(cell);
    }

    bool Propagate(int startCell) {
        var stack = new Stack<int>();
        stack.Push(startCell);
        while (stack.Count > 0) {
            int c = stack.Pop();
            int cx = c % cols, cy = c / cols;
            for (int d = 0; d < 4; d++) {
                int nx = cx + DX[d], ny = cy + DY[d];
                if (nx < 0 || ny < 0 || nx >= cols || ny >= rows) continue;
                int ni = ny * cols + nx;
                var union = new uint[wordCount];
                for (int t = 0; t < tileCount; t++) {
                    if (!HasBit(wave[c], t)) continue;
                    var a = adj[t * 4 + d];
                    for (int i = 0; i < wordCount; i++) union[i] |= a[i];
                }
                bool changed = AndInPlace(wave[ni], union);
                if (changed) {
                    if (Popcount(wave[ni]) == 0) return false;
                    stack.Push(ni);
                }
            }
        }
        return true;
    }
}

8. Variantes y extensiones

• Overlapping model: en vez de tiles atómicos, analiza patrones N×N en una imagen ejemplo. Genera nuevos patrones que respetan las co-ocurrencias del ejemplo. Es lo que se popularizó en 2017.
• Hierarchical WFC: para mundos grandes, generas primero a baja resolución, luego refinás en zonas. Mantiene coherencia global con costo manejable.
• Constrained WFC: pre-coloreas algunas celdas (puntos de spawn, salidas, props clave) y WFC genera el resto respetando esas restricciones. Útil para “mapas de quest” con elementos fijos.
• 3D WFC: 6 direcciones en vez de 4. Townscaper lo usa para edificios; Bad North para islas con relieve.

9. Errores comunes

1. Reglas demasiado estrictas — si pocos pares de tiles son compatibles, WFC casi siempre cae en contradicción. Empezá flexible (más reglas verdaderas que falsas) y ajustá.
2. Sin backtrack — para tilesets > 10 tiles, sin backtrack las generaciones fallan demasiado seguido.
3. Picking sin pesos — si todos los tiles tienen weight uniforme, el output se ve “ruidoso”. Asigná pesos altos a tiles “comunes” (grass) y bajos a especiales (oro).
4. No usar bitsets — con sets/listas de tiles, WFC es 10× más lento. Bitsets no son optimización prematura, son la representación correcta.
5. Lowest entropy con count puro — si dos celdas tienen el mismo count, ¿cuál elegís? Sin tiebreaker (jitter aleatorio o weighted Shannon), produces patrones predecibles. Agregá ruido pequeño al score.

10. Quiz

Pon a prueba lo que entendiste

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

1. WFC siempre colapsa primero la celda con MENOR entropía. ¿Por qué?

   • AEs la celda con la elección más constrained, lo que minimiza la chance de contradicción tardía.
   • BLas celdas con menos entropía se procesan más rápido.
   • CPara que el output se vea más uniforme.

2. Tu WFC genera mapas pero falla con contradicción ~30% del tiempo. ¿Primer fix?

   • AAgregar backtracking — guardar snapshots antes de cada collapse y rollback en caso de contradicción.
   • BAflojar las reglas para que más tiles sean compatibles.
   • CReducir el tamaño del grid.

3. ¿Por qué bitsets son críticos para WFC eficiente?

   • ALas operaciones core (unión, intersección, count) son AND/OR sobre uint, ridículamente rápidas.
   • BReducen memoria.
   • CPermiten serialización trivial.

4. Quieres que tu mundo tenga 80% de pasto, 15% de bosque, 5% de roca. ¿Dónde tocás eso en WFC?

   • AEn los weights del tile — pesar grass=8, forest=2, rock=0.5 sesga la distribución sin tocar reglas.
   • BEn las reglas — prohibir más adyacencias para tiles raros.
   • CPost-procesar el output reemplazando tiles raros por comunes.

11. Siguientes pasos

WFC genera mundos libres de reglas. Cuando lo que necesitás son mazmorras estructuradas con habitaciones y corredores conectados, hay un algoritmo más simple y específico: BSP dungeons, el algoritmo que sostiene a Rogue, NetHack y miles de roguelikes. Te toca el siguiente.