Advanced

Wave Function Collapse (WFC)

WFC is a constraint-based algorithm that generates output by collapsing possibilities one cell at a time, ensuring local consistency through constraint propagation.

How WFC Works

Inspired by quantum mechanics, WFC treats each output cell as a superposition of all possible tiles. The algorithm repeatedly selects the cell with the fewest remaining possibilities (lowest entropy), collapses it to a single tile, and propagates constraints to neighbors.

  1. Initialize

    Every cell starts in superposition — all tile types are possible. The grid begins in maximum entropy.

  2. Observe

    Find the cell with the lowest entropy (fewest remaining options). Collapse it by randomly selecting one tile (weighted by frequency).

  3. Propagate

    Remove impossible tiles from neighboring cells based on adjacency constraints. This may cascade to their neighbors.

  4. Repeat

    Continue observing and propagating until all cells are collapsed or a contradiction is found.

  5. Handle Contradictions

    If a cell has zero possibilities, backtrack or restart with a different seed.

Python - Simple WFC Implementation 
import random
from collections import defaultdict

class WFC:
    def __init__(self, width, height, tiles, rules):
        self.w, self.h = width, height
        self.tiles = tiles
        self.rules = rules  # {tile: {dir: [valid_neighbors]}}
        # Each cell starts with all tiles possible
        self.grid = [[set(tiles) for _ in range(width)]
                     for _ in range(height)]

    def lowest_entropy_cell(self):
        min_entropy = float('inf')
        candidates = []
        for y in range(self.h):
            for x in range(self.w):
                entropy = len(self.grid[y][x])
                if 1 < entropy < min_entropy:
                    min_entropy = entropy
                    candidates = [(x, y)]
                elif entropy == min_entropy:
                    candidates.append((x, y))
        return random.choice(candidates) if candidates else None

    def collapse(self, x, y):
        tile = random.choice(list(self.grid[y][x]))
        self.grid[y][x] = {tile}
        self.propagate(x, y)

    def propagate(self, x, y):
        stack = [(x, y)]
        while stack:
            cx, cy = stack.pop()
            for dx, dy, direction in self.neighbors(cx, cy):
                nx, ny = cx + dx, cy + dy
                changed = False
                for tile in list(self.grid[ny][nx]):
                    if not self.is_compatible(
                        tile, self.grid[cy][cx], direction):
                        self.grid[ny][nx].discard(tile)
                        changed = True
                if changed:
                    stack.append((nx, ny))

    def run(self):
        while (cell := self.lowest_entropy_cell()):
            self.collapse(*cell)
        return self.grid

WFC Variants

VariantInputBest For
Simple TiledTile set + adjacency rulesLevel generation, tile maps, building layouts
OverlappingExample imageTexture synthesis, pattern replication from samples
3D WFC3D tile set + rulesVoxel worlds, 3D building generation

Applications in Games

  • Tile-based levels: Generate 2D levels that respect tile connectivity rules (roads connect to roads, walls connect to walls).
  • City layouts: Generate building blocks, road networks, and neighborhoods that look coherent.
  • Texture synthesis: The overlapping model can synthesize large textures from small example images.
  • Interior decoration: Place furniture and props in rooms following spatial rules.
  • Sudoku-like puzzles: WFC is fundamentally a constraint satisfaction solver, applicable to any problem with local adjacency rules.
✅
Key takeaway: WFC generates content by collapsing possibilities through constraint propagation. It excels at creating locally consistent output from simple adjacency rules. The Simple Tiled model is great for levels, while the Overlapping model synthesizes patterns from example images.