Lesson 10: Wave Function Collapse | Game Dev III: Advanced

🧩 Tiles That Must Fit

Picture a sudoku. Each empty square could hold any digit, until you write one in. Then its row, column and box lose that digit, which can leave another square with only one choice, which you write in, which removes more choices. Wave function collapse (WFC) runs exactly that loop on a tile map. The name borrows words from quantum physics, but the algorithm is plain constraint solving: no physics required.

All WFC needs is a set of tiles and a rule for each direction that says which tiles may sit next to which. The simplest rule set is a "may touch" table that applies in every direction. Here is a terrain set where the land rises from water to mountains:

Tile	Symbol	May touch	Weight
water	`~`	water, sand	1.0
sand	`.`	water, sand, grass	1.0
grass	`,`	sand, grass, forest	6.0
forest	`T`	grass, forest, mountain	4.0
mountain	`^`	forest, mountain	2.0

Water can never touch grass, so every lake grows a beach; mountains are always ringed by forest. Nobody draws those beaches: they are forced by the rules. The weights say how common each tile should be when there is a free choice.

In code, the rules become rules[tile][direction], a set of tile indices allowed in that direction. For the terrain table every direction gets the same set; later you will build direction-specific rules from tile edges.

🚫 What WFC is not

A common shortcut fills the grid left to right, top to bottom, giving each cell a random tile that fits the neighbors already placed. It looks similar and it is much simpler, but it is not WFC. It never looks ahead, so a cell can find that no tile fits its left and top neighbors together, and the shortcut then leaves a hole or breaks a rule. It also always grows in the same scan-line order, which shows in the result. WFC chooses where to decide next and pushes every decision's consequences through the whole grid before making the next one.

🌊 Every Cell Starts With Every Option

The "wave" is simply a grid of sets. At the start, every cell's set holds every tile: nothing is decided. A cell is collapsed when its set holds exactly one tile, and the grid is finished when every cell is collapsed.

everything = set(range(len(tiles)))
cells = [[set(everything) for _ in range(cols)] for _ in range(rows)]

(Each cell needs its own set(everything). Writing [everything] * cols would put the same set object in every cell, and removing an option from one cell would remove it from all of them.)

Which cell should we decide next? The one with the least uncertainty, because it is the most constrained: if we leave it for later, its few options may disappear. WFC measures uncertainty with Shannon entropy. For options with weights w summing to W:

H = ln W − (Σ w ln w) / W

def entropy(self, options):
    """Shannon entropy of the weighted choices left in one cell."""
    total = sum(self.weights[t] for t in options)
    return math.log(total) - sum(self.weights[t] * math.log(self.weights[t]) for t in options) / total

Entropy is 0 for a single option, ln 2 ≈ 0.69 for two equally weighted options, and smaller when one option dominates: {water, grass} with weights 1 and 6 is "nearly decided", because grass will win six times in seven. Counting options (len(options)) is a fine first version; entropy just ranks cells more carefully when weights differ. Ties are broken at random with the generator's own RNG, so the result doesn't depend on scan order.

👁️ Observe, Then Propagate

Each step of WFC has two halves.

Observe. Pick the lowest-entropy undecided cell and collapse it to one tile, chosen by weight:

def collapse(self, x, y):
    """Observe one cell: keep one tile, chosen by weight."""
    options = sorted(self.cells[y][x])            # sorted: same seed, same map, every run
    choice = self.rng.choices(options, weights=[self.weights[t] for t in options])[0]
    self.cells[y][x] = {choice}

Propagate. That cell's neighbors may now have options that can no longer fit. For each neighbor, the allowed set is the union of what the cell's remaining options allow in that direction. Intersect the neighbor's options with it. If anything was removed, the neighbor's own neighbors may be affected too, so push it on a stack and keep going until nothing changes:

def propagate(self, x, y):
    """Remove neighbor options that no longer fit. False on a contradiction."""
    stack = [(x, y)]
    while stack:
        cx, cy = stack.pop()
        for d, (dx, dy) in enumerate(DIRS):
            nx, ny = cx + dx, cy + dy
            if not (0 <= nx < self.cols and 0 <= ny < self.rows):
                continue
            allowed = set()
            for t in self.cells[cy][cx]:
                allowed |= self.rules[t][d]
            neighbor = self.cells[ny][nx]
            narrowed = neighbor & allowed
            if narrowed != neighbor:
                if not narrowed:
                    return False                  # no tile fits here any more
                self.cells[ny][nx] = narrowed
                stack.append((nx, ny))
    return True

Propagation only ever removes options, and each cell has a finite number, so the stack always empties. It is the step that makes WFC look ahead: after a lake tile is placed, the cells two steps away already know they can't be forest.

Press Step a few times and watch the numbers around the red outline drop. Predict before each press: which cell will be chosen next? (Hint: cells next to water drop to 2 options, and {water, sand} has low entropy.)

✅ Growth Mindset: Propagation Bugs Hide Well

If your grid finishes but some neighbors break the rules, or the program never finishes, the bug is almost always in propagate, and it is hard to spot by reading. That's normal. Shrink the problem: run a 3 × 1 grid, set two cells by hand, call propagate once and print every cell's set. Small, printable cases turn "it's broken somewhere" into "this line removed the wrong tile". The lab's tests work exactly this way.

🗺️ A Complete Terrain Generator

Put the pieces together in a WFC class: pick_cell finds the lowest entropy, step observes and propagates once, and run steps until nothing is undecided. This program is complete and prints its map as text:

import math
import random

DIRS = [(0, -1), (1, 0), (0, 1), (-1, 0)]       # N, E, S, W

# Terrain tiles: name, map symbol, weight (bigger = more common)
TERRAIN = [("water", "~", 1.0), ("sand", ".", 1.0), ("grass", ",", 6.0),
           ("forest", "T", 4.0), ("mountain", "^", 2.0)]
MAY_TOUCH = {0: {0, 1}, 1: {0, 1, 2}, 2: {1, 2, 3}, 3: {2, 3, 4}, 4: {3, 4}}

# For terrain, the rule is the same in every direction: rules[tile][direction]
RULES = [[MAY_TOUCH[t] for _ in DIRS] for t in range(len(TERRAIN))]


class Tile:                                        # the WFC class only reads .weight
    def __init__(self, weight):
        self.weight = weight


class WFC:
    def __init__(self, cols, rows, tiles, rules, seed):
        self.cols, self.rows = cols, rows
        self.weights = [t.weight for t in tiles]
        self.rules = rules
        self.rng = random.Random(seed)
        self.attempts = 0
        self.reset()

    def reset(self):
        everything = set(range(len(self.weights)))
        self.cells = [[set(everything) for _ in range(self.cols)] for _ in range(self.rows)]
        self.attempts += 1

    def entropy(self, options):
        """Shannon entropy of the weighted choices left in one cell."""
        total = sum(self.weights[t] for t in options)
        return math.log(total) - sum(self.weights[t] * math.log(self.weights[t]) for t in options) / total

    def pick_cell(self):
        """The undecided cell with the lowest entropy (random among ties), or None when all are decided."""
        best, best_h = [], float("inf")
        for y in range(self.rows):
            for x in range(self.cols):
                options = self.cells[y][x]
                if len(options) > 1:
                    h = self.entropy(options)
                    if h < best_h - 1e-9:
                        best, best_h = [(x, y)], h
                    elif abs(h - best_h) <= 1e-9:
                        best.append((x, y))
        return self.rng.choice(best) if best else None

    def collapse(self, x, y):
        """Observe one cell: keep one tile, chosen by weight."""
        options = sorted(self.cells[y][x])            # sorted: same seed, same map, every run
        choice = self.rng.choices(options, weights=[self.weights[t] for t in options])[0]
        self.cells[y][x] = {choice}

    def propagate(self, x, y):
        """Remove neighbor options that no longer fit. False on a contradiction."""
        stack = [(x, y)]
        while stack:
            cx, cy = stack.pop()
            for d, (dx, dy) in enumerate(DIRS):
                nx, ny = cx + dx, cy + dy
                if not (0 <= nx < self.cols and 0 <= ny < self.rows):
                    continue
                allowed = set()
                for t in self.cells[cy][cx]:
                    allowed |= self.rules[t][d]
                neighbor = self.cells[ny][nx]
                narrowed = neighbor & allowed
                if narrowed != neighbor:
                    if not narrowed:
                        return False                  # no tile fits here any more
                    self.cells[ny][nx] = narrowed
                    stack.append((nx, ny))
        return True

    def step(self):
        """One observe + propagate. Returns 'done', 'working' or 'restarted'."""
        cell = self.pick_cell()
        if cell is None:
            return "done"
        self.collapse(*cell)
        if not self.propagate(*cell):
            self.reset()                              # contradiction: start over
            return "restarted"
        return "working"

    def run(self, max_attempts=100):
        while self.attempts <= max_attempts:
            if self.step() == "done":
                return True
        return False

    def result(self):
        return [[next(iter(c)) if len(c) == 1 else None for c in row] for row in self.cells]


wfc = WFC(48, 16, [Tile(w) for _, _, w in TERRAIN], RULES, seed=3)
wfc.run()
for row in wfc.result():
    print("".join(TERRAIN[t][1] for t in row))
print(f"finished after {wfc.attempts} attempt(s)")

Every lake has a beach and every mountain sits in forest, yet nobody placed them. Now experiment with the weights. Raise water to 4.0 and try seeds 0 to 9: on five of those ten seeds, water covers more than 70% of the map (at weight 1.0 it never covered more than 14%). The reason is the lowest-entropy rule. A cell next to water has only {water, sand} left, which is very low entropy, so it is chosen next, and it becomes water often enough that the lake keeps growing outward. WFC decides the most constrained cells first, so it grows regions outward from what is already placed. Weights are your main tool for steering that growth.

💡 Why this matters

WFC separates what is allowed (the rules) from how you choose (entropy, weights and the seed). Artists can add a tile and its edges without touching the solver, and designers can tune weights without breaking a single rule. The same solver runs terrain, dungeon rooms, city blocks or pipe puzzles.

💥 Contradictions, Restarts and Reproducibility

Propagation keeps neighboring pairs consistent, but it does not see every combination of constraints ahead of time. Sometimes a later observation leaves a cell with no options: a contradiction. Our propagate reports it by returning False, and step responds by resetting the grid and starting over:

def step(self):
    """One observe + propagate. Returns 'done', 'working' or 'restarted'."""
    cell = self.pick_cell()
    if cell is None:
        return "done"
    self.collapse(*cell)
    if not self.propagate(*cell):
        self.reset()                              # contradiction: start over
        return "restarted"
    return "working"

The RNG is not reseeded on a restart, so the next attempt makes different choices, and the whole run is still reproducible from the original seed. How often restarts happen depends entirely on the tile set. The terrain set (seeds 0 to 39) and the lab's full road set (seeds 0 to 39) never needed a restart. Remove the four bend tiles and the cross from the road set, though, and 9 of 40 seeds on a 24 × 16 grid needed at least one restart. Restarting is the simplest recovery. The alternative is backtracking: save the grid before each observation and undo the last choice on a contradiction. It wastes less work on large grids but costs memory and code.

🔁 A reproducibility trap: set order

rng.choices(options, ...) depends on the order of options. A set of strings is iterated in an order that depends on string hashes, and Python randomizes string hashing in every new process (unless PYTHONHASHSEED is set). If your tiles were named strings in a set, the same seed could give a different map every time you launch the game. Our cells hold integer indices, and collapse sorts them anyway, so the order is fixed by design rather than by luck.

✅ Growth Mindset: A Restart Is Not a Failure

The first time your generator prints "attempt 3", it can feel like something broke. It didn't: contradictions are part of how WFC works, and a restart is the algorithm doing its job. What deserves your attention is a tile set that restarts on most seeds. That is feedback about the tiles (a missing transition tile, rules that are too strict), not about you.

🔌 Rules From Tile Edges

A "may touch" table ignores direction, which is fine for terrain but useless for roads: a straight north–south road may have another north–south road above it, but not to its right with its road ends pointing into grass. For tiles like that, describe each tile by its four edge sockets in the order north, east, south, west: 1 means a road leaves through that edge, 0 means grass.

DIRS = [(0, -1), (1, 0), (0, 1), (-1, 0)]       # N, E, S, W (index = socket index)
OPPOSITE = [2, 3, 0, 1]                          # N<->S, E<->W


def build_rules(tiles):
    """rules[a][d] = set of tile indices allowed next to tile a in direction d."""
    rules = []
    for a in tiles:
        per_dir = []
        for d in range(4):
            per_dir.append({i for i, b in enumerate(tiles) if a.sockets[d] == b.sockets[OPPOSITE[d]]})
        rules.append(per_dir)
    return rules

Two tiles fit side by side when the edges that touch carry the same socket: tile a's east socket must equal tile b's west socket. You never write a rule by hand; you describe each tile once, and the rules follow. Adding a new tile is one line. The solver from the terrain generator doesn't change at all. That is the project for this lesson.

🌿 Side quest: L-systems for plants

WFC fills grids. For branching shapes such as trees, vines, rivers and lightning, a different rule-based tool is popular: the L-system. It rewrites every symbol of a string at once, generation after generation:

def expand(axiom, rules, generations):
    """Rewrite every symbol at once, generation after generation."""
    text = axiom
    for _ in range(generations):
        text = "".join(rules.get(symbol, symbol) for symbol in text)
    return text


PLANT = {"X": "F+[[X]-X]-F[-FX]+X", "F": "FF"}      # a classic branching plant
for n in range(4):
    result = expand("X", PLANT, n)
    print(n, len(result), result[:60])

To draw it, read the string as turtle commands: F = draw forward, +/- = turn, [ = remember the position and heading, ] = go back to it. Symbols such as X draw nothing; they only steer the growth.

def draw_lsystem(surface, text, start, heading=-90, step=4, turn=25):
    pos, angle, saved = pygame.Vector2(start), heading, []
    for symbol in text:
        if symbol == "F":
            end = pos + pygame.Vector2(step, 0).rotate(angle)
            pygame.draw.line(surface, (90, 160, 80), pos, end, 1)
            pos = end
        elif symbol == "+":
            angle += turn
        elif symbol == "-":
            angle -= turn
        elif symbol == "[":
            saved.append((pygame.Vector2(pos), angle))
        elif symbol == "]":
            pos, angle = saved.pop()

Five generations of the plant rule give a convincing fern. Because the length grows by about four times per generation here, draw it once to a Surface at load time, just like the dungeon map in Dungeons & Caves.

🏋️ Practice Exercise: WFC Road Builder

Objective: finish a wave function collapse solver that fills a grid with road tiles, animates the collapse a few cells per frame, and never leaves a road that ends at a grass edge.

Time: about 35 minutes. Starter file: wfc_roads_starter.py (your instructor has it). The tiles, drawing and keys already work; right now every tile is allowed everywhere, so roads end in mid-air. Its numbered comments match the steps below.

Run the starter and look closely: many roads run into grass. (≈ 2 min)
Write build_rules from the sockets, using OPPOSITE. Run it: most roads now connect, but not all, because nothing propagates yet. (≈ 7 min)
Replace the option count in entropy with the Shannon formula. (≈ 4 min)
Make collapse choose by weight with self.rng.choices. Grass should now dominate. (≈ 4 min)
Write propagate with a stack. Every road should now connect. (≈ 12 min)
In step, reset and return "restarted" when propagate returns False. Test it by deleting the four bend tiles and the cross from TILES and pressing R until the attempt counter goes above 1. (≈ 6 min)

You are done when:

every road on screen connects to another road at every edge it touches;
SPACE finishes the grid instantly and R shows a new network for the next seed;
with the bends and the cross removed, some seeds show an attempt count above 1 and still finish;
closing the window prints every edge matches: True.

💡 Hint

In build_rules, direction index d is also the socket index: 0 north, 1 east, 2 south, 3 west. Tile b is allowed in direction d of tile a when a.sockets[d] == b.sockets[OPPOSITE[d]]. In propagate, only push a neighbor when its set actually got smaller; pushing unchanged cells makes the loop run forever.

✅ Example Solution

The lab file your instructor hands out also contains a few lines marked lab runtime and and frame_budget() in the loop condition. They let the checker run the program for a fixed number of frames; they do nothing when you run it yourself.

"""WFC Road Builder: Advanced Lesson 10 practice exercise (solution).

Wave function collapse fills a grid with road tiles whose edges always
match. Watch it work a few cells per frame: gray cells are still
undecided (darker = fewer options left). SPACE finishes instantly,
R starts again with the next seed.
"""
import math
import random
from dataclasses import dataclass

import pygame


COLS, ROWS = 24, 16
CELL = 36
HUD_H = 30
STEPS_PER_FRAME = 3
DIRS = [(0, -1), (1, 0), (0, 1), (-1, 0)]       # N, E, S, W (index = socket index)
OPPOSITE = [2, 3, 0, 1]                          # N<->S, E<->W
GRASS = (70, 120, 70)
ROAD = (205, 200, 185)
TEXT_COLOR = (235, 235, 235)


@dataclass(frozen=True)
class Tile:
    name: str
    sockets: tuple          # (N, E, S, W): 1 = a road leaves through that edge
    weight: float


TILES = [
    Tile("grass", (0, 0, 0, 0), 8.0),
    Tile("road NS", (1, 0, 1, 0), 2.0),
    Tile("road EW", (0, 1, 0, 1), 2.0),
    Tile("bend NE", (1, 1, 0, 0), 1.0),
    Tile("bend ES", (0, 1, 1, 0), 1.0),
    Tile("bend SW", (0, 0, 1, 1), 1.0),
    Tile("bend WN", (1, 0, 0, 1), 1.0),
    Tile("tee NES", (1, 1, 1, 0), 0.5),
    Tile("tee ESW", (0, 1, 1, 1), 0.5),
    Tile("tee SWN", (1, 0, 1, 1), 0.5),
    Tile("tee WNE", (1, 1, 0, 1), 0.5),
    Tile("cross", (1, 1, 1, 1), 0.3),
]   # delete the 4 bends AND the cross: some seeds then hit a contradiction and restart


def build_rules(tiles):
    """rules[a][d] = set of tile indices allowed next to tile a in direction d."""
    rules = []
    for a in tiles:
        per_dir = []
        for d in range(4):
            per_dir.append({i for i, b in enumerate(tiles) if a.sockets[d] == b.sockets[OPPOSITE[d]]})
        rules.append(per_dir)
    return rules


class WFC:
    def __init__(self, cols, rows, tiles, rules, seed):
        self.cols, self.rows = cols, rows
        self.weights = [t.weight for t in tiles]
        self.rules = rules
        self.rng = random.Random(seed)
        self.attempts = 0
        self.reset()

    def reset(self):
        everything = set(range(len(self.weights)))
        self.cells = [[set(everything) for _ in range(self.cols)] for _ in range(self.rows)]
        self.attempts += 1

    def entropy(self, options):
        """Shannon entropy of the weighted choices left in one cell."""
        total = sum(self.weights[t] for t in options)
        return math.log(total) - sum(self.weights[t] * math.log(self.weights[t]) for t in options) / total

    def pick_cell(self):
        """The undecided cell with the lowest entropy (random among ties), or None when all are decided."""
        best, best_h = [], float("inf")
        for y in range(self.rows):
            for x in range(self.cols):
                options = self.cells[y][x]
                if len(options) > 1:
                    h = self.entropy(options)
                    if h < best_h - 1e-9:
                        best, best_h = [(x, y)], h
                    elif abs(h - best_h) <= 1e-9:
                        best.append((x, y))
        return self.rng.choice(best) if best else None

    def collapse(self, x, y):
        """Observe one cell: keep one tile, chosen by weight."""
        options = sorted(self.cells[y][x])            # sorted: same seed, same map, every run
        choice = self.rng.choices(options, weights=[self.weights[t] for t in options])[0]
        self.cells[y][x] = {choice}

    def propagate(self, x, y):
        """Remove neighbor options that no longer fit. False on a contradiction."""
        stack = [(x, y)]
        while stack:
            cx, cy = stack.pop()
            for d, (dx, dy) in enumerate(DIRS):
                nx, ny = cx + dx, cy + dy
                if not (0 <= nx < self.cols and 0 <= ny < self.rows):
                    continue
                allowed = set()
                for t in self.cells[cy][cx]:
                    allowed |= self.rules[t][d]
                neighbor = self.cells[ny][nx]
                narrowed = neighbor & allowed
                if narrowed != neighbor:
                    if not narrowed:
                        return False                  # no tile fits here any more
                    self.cells[ny][nx] = narrowed
                    stack.append((nx, ny))
        return True

    def step(self):
        """One observe + propagate. Returns 'done', 'working' or 'restarted'."""
        cell = self.pick_cell()
        if cell is None:
            return "done"
        self.collapse(*cell)
        if not self.propagate(*cell):
            self.reset()                              # contradiction: start over
            return "restarted"
        return "working"

    def run(self, max_attempts=100):
        while self.attempts <= max_attempts:
            if self.step() == "done":
                return True
        return False

    def result(self):
        return [[next(iter(c)) if len(c) == 1 else None for c in row] for row in self.cells]


def rules_ok(grid, tiles):
    """Check every pair of neighbors in a finished grid really matches."""
    for y, row in enumerate(grid):
        for x, t in enumerate(row):
            if t is None:
                return False
            if x + 1 < len(row) and tiles[t].sockets[1] != tiles[row[x + 1]].sockets[3]:
                return False
            if y + 1 < len(grid) and tiles[t].sockets[2] != tiles[grid[y + 1][x]].sockets[0]:
                return False
    return True


def make_tile_images(tiles):
    """Draw each tile once: grass plus a road arm for every open socket."""
    images = []
    half, w = CELL // 2, CELL // 3
    for tile in tiles:
        surf = pygame.Surface((CELL, CELL))
        surf.fill(GRASS)
        arms = [(half - w // 2, 0, w, half), (half, half - w // 2, half, w),
                (half - w // 2, half, w, half), (0, half - w // 2, half, w)]
        for open_edge, rect in zip(tile.sockets, arms):
            if open_edge:
                surf.fill(ROAD, rect)
        if any(tile.sockets):
            surf.fill(ROAD, (half - w // 2, half - w // 2, w, w))
        images.append(surf)
    return images


def main():
    pygame.init()
    screen = pygame.display.set_mode((COLS * CELL, ROWS * CELL + HUD_H))
    pygame.display.set_caption("WFC Road Builder")
    clock = pygame.time.Clock()
    font = pygame.font.Font(None, 26)
    images = make_tile_images(TILES)
    rules = build_rules(TILES)
    total = len(TILES)
    shades = [(max(0, min(255, 40 + 180 * n // total)),) * 3 for n in range(total + 1)]

    seed = 1
    wfc = WFC(COLS, ROWS, TILES, rules, seed)
    state, finished, all_ok = "working", 0, True

    running = True
    while running:
        clock.tick(60)
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                running = False
            elif event.type == pygame.KEYDOWN and event.key == pygame.K_SPACE and state != "done":
                wfc.run()
                state = "done" if wfc.pick_cell() is None else state
                if state == "done":
                    finished += 1
                    all_ok = all_ok and rules_ok(wfc.result(), TILES)
            elif event.type == pygame.KEYDOWN and event.key == pygame.K_r:
                seed += 1
                wfc = WFC(COLS, ROWS, TILES, rules, seed)
                state = "working"

        for _ in range(STEPS_PER_FRAME):
            if state == "done":
                break
            state = wfc.step()
            if state == "done":
                finished += 1
                all_ok = all_ok and rules_ok(wfc.result(), TILES)

        screen.fill((0, 0, 0))
        for y, row in enumerate(wfc.cells):
            for x, options in enumerate(row):
                pos = (x * CELL, y * CELL + HUD_H)
                if len(options) == 1:
                    screen.blit(images[next(iter(options))], pos)
                else:
                    screen.fill(shades[len(options)], (*pos, CELL - 1, CELL - 1))
        label = f"seed {seed} | attempt {wfc.attempts} | {state}   [SPACE] finish  [R] next seed"
        screen.blit(font.render(label, True, TEXT_COLOR), (8, 7))
        pygame.display.flip()

    pygame.quit()
    print(f"Finished {finished} grid(s); every edge matches: {all_ok}")


if __name__ == "__main__":
    main()

📓 Learning Journal

Take five minutes to write in your learning journal. Jot down:

Key concepts you learned today
Techniques that clicked (and the ones that haven't, yet)
Questions or confusion to bring to the next session
Ideas to try in your own game
Progress and feelings: how did this lesson go for you?

✍️ This lesson's prompts:

Explain observation and propagation using the sudoku comparison, in your own words. Where does the comparison break down?
Design a small tile set for a game you like (a dungeon, a railway, a farm). What are its sockets, and which tile would you add to reduce contradictions?
When did a small test case (a 3 × 1 grid, a single propagate call) help you today, or when could it have?

📝 Summary

Wave function collapse treats a tile map as a constraint puzzle. Every cell starts with every tile. The solver repeatedly observes the lowest-entropy cell, choosing a tile by weight, and propagates the consequences, removing any neighbor options that no longer fit and following the changes outward. When a cell runs out of options, the grid restarts with the same RNG, so results stay reproducible. Rules can come from a simple "may touch" table or from edge sockets, and in both cases the solver itself never changes.

🎓 Key Takeaways

The wave is a grid of option sets; a cell is collapsed when one option is left.
Observe the lowest-entropy cell (random among ties), choosing by weight with the generator's own RNG.
Propagation intersects each neighbor's options with what is still allowed, and repeats for every cell that changed.
An empty option set is a contradiction; restart (or backtrack) and carry on.
Sort before choosing: set order must never decide a seeded result.
Edge sockets turn "tile a's east edge equals tile b's west edge" into direction-aware rules automatically.

🔭 Looking Ahead

Your worlds are built; next they need to push back. In SAT & Rotational Collisions you collide rotating polygons, find exactly how deep they overlap, and make them spin when they hit.

❓ Common Questions

Is this the "overlapping" WFC I have seen in videos?

No. This lesson builds the simple tiled model: you supply the tiles and their adjacency rules. The overlapping model learns its rules from a sample image by cutting it into small patterns (for example 3 × 3 pixels) and recording which patterns overlap. The solver loop, entropy, observation and propagation, is the same in both.

My maps look noisy. Is WFC just fancy noise?

WFC only guarantees that neighbors follow the rules; it has no idea of "large regions" unless your tiles and weights encode it. Bigger transition tiles, stronger weights, or seeding some cells by hand before running (a river across the map, a town square in the middle) give more structure.

How do I force a tile at a particular spot?

Before calling run, set that cell's set to just the tile you want and call propagate on it. If that returns False, your request can't be satisfied with this tile set. Don't reset in that case, or you would lose the pinned tile; fix the request or the tiles instead.

Why use a stack in propagate and not recursion?

A single observation can ripple across the whole grid. Recursion would add one Python stack frame per changed cell and can hit the recursion limit on big grids; an explicit list used as a stack has no such limit.

Can WFC run while the player is playing?

Yes, if you spread the work out. The lab runs a few step() calls per frame, which is how you would generate a chunk in the background. For endless worlds, generate chunks next to already-finished ones and pin their border cells first so the seams match.

🎯 Quick Quiz

Question 1: Which cell does our WFC solver observe next?

Question 2: What does propagate() do after a cell collapses?

Question 3: During propagation, a cell's set of options becomes empty. What does this lesson's solver do?

Question 4: With sockets in the order (N, E, S, W), when may tile b sit directly east of tile a?

Question 5: Why does collapse() sort a cell's options before calling rng.choices?

🌟 Going Further

Rivers and roads: add a second socket kind (2 = water) with straight river tiles and one bridge tile. Watch how often contradictions appear without a river bend.
Pinned cells: before running, pin a crossroads in the center of the grid and a road on every border cell of the west edge, then let WFC fill in the rest.
Backtracking: replace restart-on-contradiction with a stack of saved grids ([[set(c) for c in row] for row in cells]) and compare how many steps each approach needs on the tile set without bends or the cross.
WFC + BSP: use a BSP dungeon from Dungeons & Caves for the layout, then run WFC inside each room to decorate it with furniture tiles that must line up.
Read more: Maxim Gumin's WaveFunctionCollapse repository is the original implementation and explains both the tiled and the overlapping model.

🎯 Learning Objectives