Constraint-Solved Dungeon Decoration: Wave Function Collapse with Socket Matching, Weights, and Backtracking

The Context: "Five Tilesets, One Boring Dungeon"

FRAGMENT: PROTOCOL generates its floors with BSP partitioning, which reliably produces connected, navigable rooms. It also reliably produces rooms that look like a spreadsheet. Empty grey rectangles with a corridor connecting them. Playable, but indistinguishable from one seed to the next.

The procedural map generator had been handing off a blank tile grid to the room renderer, and I was hoping for "interesting". I got five tile-based themes — archive, market, dreamscape, graveyard, core — each with its own tileset JSON, and absolutely no mechanism to place them.

The solution was not "add random decoration". Random decoration on a BSP grid produces noise that fights the architecture. What was needed was a generator that respects what fits what, which is precisely the problem Wave Function Collapse solves.

The Problem Statement

Decorate a BSP-generated room grid with themed tiles that are coherent, connected, and reachable — without hand-authoring layouts:

Constraint Satisfaction: Adjacent tiles must match on all four edges. No floor abutting wall-floor-seam nonsense.
Structural Guarantees: Rooms must remain traversable; decoration cannot wall off the exit.
Thematic Coherence: Hazards and doors should appear in plausible neighbourhoods, not uniformly at random.
Determinism: A given seed and act must always produce the same decoration.
Performance: Collapse a 64x64 grid in under 16ms on a mid-range laptop, because it runs mid-level-load.

Visual Architecture

The Core Logic / Process

1. Socket Encoding

Every tile declares what each of its four edges must connect to. A floor tile's edges all say "floor". A wall tile's edges say "wall". A corner piece says N: "wall", E: "floor", S: "floor", W: "wall".

interface TilesetTile {
  id: string;
  type: "FLOOR" | "WALL" | "DOOR" | "HAZARD";
  weight: number;
  sockets: { N: string; S: string; E: string; W: string };
}

This is the entire expressive power of the system, and it is worth resisting the urge to add richer constraint languages. Four strings per tile is enough to produce convincing architecture, and every extra constraint type is another way for the solver to deadlock.

2. The Possibility Set

The core data structure is a grid where each cell holds the set of tiles still possible at that position. Initially every cell holds every tile. Collapse narrows a cell to exactly one; propagation then narrows its neighbours.

const possible: TilesetTile[][][] = grid.map((row) =>
  row.map(() => [...tileset.tiles]),
);

function propagate(grid, startR, startC) {
  const queue = [[startR, startC]];
  while (queue.length) {
    const [r, c] = queue.pop()!;
    for (const [dr, dc] of [
      [0, 1],
      [0, -1],
      [1, 0],
      [-1, 0],
    ]) {
      const nr = r + dr,
        nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= h || nc >= w) continue;

      const filtered = possible[nr][nc].filter((tile) =>
        matchesSockets(possible[r][c], tile, dr, dc),
      );
      // Empty set == contradiction
      if (filtered.length !== possible[nr][nc].length) {
        possible[nr][nc] = filtered;
        queue.push([nr, nc]);
      }
    }
  }
}

The queue.pop() (LIFO) rather than shift() (FIFO) is deliberate and load-bearing. Propagation is a fixpoint computation, and depth-first ordering reaches contradiction faster in practice, which means fewer wasted collapses before backtracking.

3. Weighted Collapse and the Minimum-Entropy Heuristic

Which cell to collapse? Collapsing an arbitrary cell produces results that technically satisfy constraints but cluster all the interesting tiles into one corner. The minimum-entropy heuristic — always collapse the cell with the fewest remaining candidates — is what makes output look designed:

function observe(): [number, number] | null {
  let best = null,
    bestEntropy = Infinity;
  for (let r = 0; r < h; r++) {
    for (let c = 0; c < w; c++) {
      const n = possible[r][c].length;
      if (n > 1) {
        // Shannon entropy, not raw count, so weights are respected
        const entropy = weightedEntropy(possible[r][c]);
        if (entropy < bestEntropy) {
          bestEntropy = entropy;
          best = [r, c];
        }
      }
    }
  }
  return best;
}

Collapsing uses the tile's weight field as the sampling distribution, which is how the generator expresses intent: high wall weight produces tight corridors, high hazard weight produces dangerous floors. Same algorithm, different character, purely from data.

4. Contradiction and Backtracking

The failure mode of constraint propagation is a cell whose possibility set becomes empty. Two approaches exist, and the choice matters more than it looks:

Restart: abandon the grid, reseed, begin again. Simple, but with poor tilesets you can restart dozens of times.
Backtracking: retain the previous cell's prior candidate set, discard the bad choice, re-pick a different tile.

Backtracking requires remembering, per observed cell, which candidates were tried. With a seeded PRNG this is fully deterministic — the same backtrack sequence replays identically.

const prior = new Map<string, TilesetTile[]>();
// before collapsing:
prior.set(key(r, c), [...possible[r][c]]);
// on contradiction:
possible[r][c] = prior.get(key(r, c))!.filter((t) => t.id !== failedTileId);

The essential bug to avoid: restoring the prior set without removing the failed candidate. Doing so puts you back in the identical contradiction, and you spin until the run appears to hang. This cost me an afternoon and a very humbling stack trace.

5. Keeping Rooms Traversable

WFC guarantees socket coherence, not navigability. A grid of perfectly matching walls is a valid solution and an unplayable room.

The safeguard is structural rather than clever: treat the BSP output as immutable. Cells the BSP marked as traversable floor are constrained to only accept FLOOR and HAZARD tiles at initialization, before propagation begins. Walls can never be placed where the BSP intended floor, so connectivity survives by construction.

Seeding this from a constraint is the lesson. Trying to detect and repair unplayable rooms after collapse means writing a solver for a problem you created by not constraining the input.

The "Baigan" Take (Expert Insights)

Most tutorials present Wave Function Collapse as a neat little generative algorithm and then quietly assume the tileset is well-formed. Real tilesets are not.

baigan ka WFC is the belief that "if the sockets match, the level is good." Sockets matching is a local property. A room can be locally perfect, globally repetitive — the same three tile variants repeating in a visible pattern that players notice immediately and that no screenshot of the algorithm will reveal.

Three things that only surfaced in a shipped game:

Repeat detection is the real problem, not connectivity. After collapsing, I run a cheap scan for any 3x3 region that appears more than twice. If it does, I re-collapse that region with its prior candidates excluded. This single pass did more for perceived variety than any amount of weight tuning.
Pure random walks produce "nonsense" architecture that satisfies constraints perfectly. The generator kept producing long decorative chains of hazard tiles in dead-end pockets. The fix was not in the algorithm — it was adding "HAZARD" as a required socket compatibility with "FLOOR" only, so hazards can never chain. Constraints encode intent; weights encode frequency. Use both.
Backtracking without recording why fails in ways that are extremely hard to debug. I logged "contradiction at (12,7)" and learned nothing. Logging the cell, its prior candidate count, and which specific candidate collapsed to empty took thirty seconds to diagnose and would have saved the whole afternoon.

The deeper point: WFC is genuinely elegant for static generation. But a roguelite generates a level, then fills it with enemies, loot, and progression hooks. The decoration must not fight those systems. Every constraint I did not think about at decoration time became a bug report about "the room feels wrong" months later.

Configuration