Introduction

Wave Function Collapse, usually shortened to WFC, is easy to describe and surprisingly easy to break in code. The algorithm is not just "pick a tile randomly." It is a constraint-satisfaction system where every local choice must be propagated through neighboring cells until the grid becomes consistent again.

Model the Grid as Domains

Each cell starts with a domain: the set of tiles that are still allowed there. The algorithm repeatedly:

1. chooses one unresolved cell
2. collapses it to a single tile
3. propagates that decision to neighbors

The most important data structure is not the final grid. It is the current domain of each cell.

A tiny Python representation might look like this:

1all_tiles = {"grass", "water", "sand"}
2domains = [
3    [set(all_tiles) for _ in range(4)]
4    for _ in range(4)
5]

If you lose track of domain updates, the implementation becomes incorrect long before it becomes slow.

Propagation Is Where Most Bugs Live

The usual failure mode is incomplete propagation. After one cell changes, you must reconsider affected neighbors, and then neighbors of those neighbors, until nothing else changes.

1from collections import deque
2
3
4def propagate(domains, rules, start_cell):
5    height = len(domains)
6    width = len(domains[0])
7    queue = deque([start_cell])
8
9    directions = [
10        (-1, 0, "up"),
11        (1, 0, "down"),
12        (0, -1, "left"),
13        (0, 1, "right"),
14    ]
15
16    while queue:
17        y, x = queue.popleft()
18        current = domains[y][x]
19
20        for dy, dx, direction in directions:
21            ny, nx = y + dy, x + dx
22            if not (0 <= ny < height and 0 <= nx < width):
23                continue
24
25            allowed = set()
26            for tile in current:
27                allowed |= rules[tile][direction]
28
29            before = domains[ny][nx]
30            after = before & allowed
31
32            if not after:
33                raise ValueError("Contradiction detected")
34
35            if after != before:
36                domains[ny][nx] = after
37                queue.append((ny, nx))

This loop is the heart of WFC. If propagation stops too early, the grid may appear valid temporarily and then fail much later for confusing reasons.

Choosing the Next Cell

Most WFC implementations pick the cell with the lowest entropy, meaning the smallest remaining domain greater than one. That is a good heuristic because it resolves the most constrained cells first.

1def choose_cell(domains):
2    best = None
3
4    for y, row in enumerate(domains):
5        for x, options in enumerate(row):
6            count = len(options)
7            if count > 1 and (best is None or count < best[0]):
8                best = (count, y, x)
9
10    if best is None:
11        return None
12
13    return best[1], best[2]

The exact entropy formula can include tile weights, but that is secondary. A correct propagation engine with a simple heuristic is better than a fancy entropy formula on top of broken domain updates.

Contradictions Need a Strategy

Sooner or later, some collapse sequence produces an empty domain for a cell. That means the current branch is invalid.

You need one of these strategies:

• restart from scratch
• backtrack to an earlier choice
• relax tile constraints

Many Python implementations start with random restarts because they are much easier than full backtracking. That is a reasonable first version, but it can become expensive on larger grids or stricter tile sets.

Python Performance Problems

WFC performs many tiny set operations and neighbor checks, so Python overhead appears quickly. The first useful optimizations are usually:

• store tile IDs as small integers instead of strings
• precompute adjacency lookups
• use a queue instead of rescanning the full grid
• consider bitmasks for domains if the tile set is modest

For a learning implementation, plain Python sets are fine. For large procedural maps, compact representations pay off fast.

Keep the Rules Verifiable

A subtle source of bugs is bad adjacency data rather than bad algorithm code. If tile A allows tile B on the right, make sure tile B also allows tile A on the left when the design expects symmetry.

Before you generate a full map, test the rule table separately with tiny grids and assertions. It is far easier to debug one inconsistent rule than a full generator that sometimes collapses and sometimes implodes.

Common Pitfalls

• Treating propagation as a one-step neighbor update instead of a repeated fixed-point process.
• Spending too much effort on entropy math before domain propagation is correct.
• Ignoring contradictions instead of restarting or backtracking.
• Using slow rule lookups that turn every neighbor check into a bottleneck.
• Debugging the generator without first validating the tile adjacency rules.

Summary

• WFC is primarily a constraint-propagation algorithm.
• The key state is each cell's current domain of possible tiles.
• Correct propagation matters more than sophisticated entropy formulas.
• Contradictions are normal and require restart or backtracking logic.
• In Python, data representation and rule lookup speed determine how far the implementation scales.