Posted on Jul 12

🧠 #186 — Wave Function Collapse: Overlapping Model Explained with Code & Formulas

“A constraint-solving algorithm meets procedural generation — and it’s surprisingly beautiful.”

Wave Function Collapse (WFC) is one of the coolest algorithms for procedural generation. Inspired by quantum mechanics, it’s been used to generate textures, maps, dungeons, cities, and even music — all while maintaining global coherence.

In this article, we’ll go deep into the Overlapping Model — the most popular and elegant variant of WFC. We’ll explain the formulas, the core logic, and include complete Python code to get you started!

🌊 What is Wave Function Collapse?

At its core, WFC is:

A constraint-solving algorithm
A tile-based procedural generation system
That tries to fill a grid with tiles without violating neighbor rules

Inspired by Quantum Mechanics:

Each cell begins in a superposition of all valid tiles (states). As constraints are applied and the system collapses, each cell reduces to a single state.

🔍 The Overlapping Model

In this variant:

You extract n×n patterns (tiles) from an input image.
The output grid is filled such that every tile overlaps correctly with its neighbors.
The algorithm uses the frequency of each tile in the input to weight the probabilities.

📐 Core Concepts and Formulas

1. Entropy

Entropy is the measure of uncertainty in a cell:

H = log(\sum w_i) - \frac{\sum w_i \cdot log(w_i)}{\sum w_i}

Where:

w_i is the weight (frequency) of the i-th pattern

We always collapse the cell with the lowest non-zero entropy first.

2. Wave Function

Each grid cell maintains a list of possible tiles (pattern indices). This is called the wave:

wave[x][y] = [True, False, True, True, ...]

A True at index i means pattern i is still a possibility for that cell.

3. Propagation

After collapsing one cell to a specific pattern, we propagate constraints:

For each direction (N, S, E, W), we eliminate incompatible patterns in neighbors.

This continues until no more eliminations are possible.

🧪 Python Code: Minimal Working WFC (Overlapping Model)

import numpy as np from PIL import Image from collections import defaultdict from random import choice N = 3 # pattern size output_width = 20 output_height = 20 def get_patterns(img, N): patterns = defaultdict(int) w, h = img.shape for y in range(h - N + 1): for x in range(w - N + 1): patch = tuple(img[y:y+N, x:x+N].flatten()) patterns[patch] += 1 return list(patterns.items()) def pattern_match(a, b, direction): N = int(len(a)**0.5) a = np.array(a).reshape(N, N) b = np.array(b).reshape(N, N) if direction == 'right': return np.array_equal(a[:, 1:], b[:, :-1]) if direction == 'down': return np.array_equal(a[1:, :], b[:-1, :]) return False def get_compatibility(patterns): compat = {i: {'right': set(), 'down': set()} for i in range(len(patterns))} for i, (a, _) in enumerate(patterns): for j, (b, _) in enumerate(patterns): if pattern_match(a, b, 'right'): compat[i]['right'].add(j) if pattern_match(a, b, 'down'): compat[i]['down'].add(j) return compat def collapse(wave, entropies): # Pick the cell with the lowest entropy  xs, ys = np.where(entropies == np.min(entropies[entropies > 0])) x, y = choice(list(zip(xs, ys))) options = [i for i, valid in enumerate(wave[x][y]) if valid] chosen = choice(options) wave[x][y] = [i == chosen for i in range(len(wave[x][y]))] return x, y def propagate(wave, compat, x, y, W, H): changed = [(x, y)] while changed: cx, cy = changed.pop() for dx, dy, dir in [(-1, 0, 'right'), (1, 0, 'right'), (0, -1, 'down'), (0, 1, 'down')]: nx, ny = cx + dx, cy + dy if 0 <= nx < W and 0 <= ny < H: for p in range(len(wave[nx][ny])): if wave[nx][ny][p]: valid = False for q in range(len(wave[cx][cy])): if wave[cx][cy][q] and p in compat[q][dir]: valid = True break if not valid: wave[nx][ny][p] = False changed.append((nx, ny)) def run_wfc(patterns, compat, W, H): wave = [[[True]*len(patterns) for _ in range(H)] for _ in range(W)] entropies = np.full((W, H), len(patterns), dtype=float) for _ in range(W * H): x, y = collapse(wave, entropies) propagate(wave, compat, x, y, W, H) # Update entropy  for i in range(W): for j in range(H): possibilities = [p for p in wave[i][j] if p] if possibilities: entropies[i][j] = len(possibilities) else: entropies[i][j] = 0 return wave def visualize(wave, patterns, N, W, H): tile_size = N output = np.zeros((H + N - 1, W + N - 1), dtype=np.uint8) for x in range(W): for y in range(H): idx = wave[x][y].index(True) pattern = np.array(patterns[idx][0]).reshape(N, N) output[y:y+N, x:x+N] = pattern return output # Example: Use a grayscale image input_img = Image.open("input.png").convert("L") img_array = np.array(input_img) patterns = get_patterns(img_array, N) compat = get_compatibility(patterns) wave = run_wfc(patterns, compat, output_width, output_height) result = visualize(wave, patterns, N, output_width, output_height) Image.fromarray(result).save("output.png")

🧠 Real-World Applications

Bad North (game) — Island generation
Caves of Qud — Puzzle world generation
Minecraft mods — City generation
AI music — Sequence generation

🔮 Why It’s Still Relevant

Despite being published in 2016, WFC remains one of the most clever procedural generation tools. Its ability to retain local patterns while building large-scale outputs makes it extremely useful in design, games, and AI art tools.

🧵 Bonus: Pattern Frequency Formula

Let f(p) be the count of pattern p in the input.

The weight of each pattern is:

w_p = \frac{f(p)}{\sum_{q} f(q)}

These weights are used to determine the likelihood of collapsing into that pattern.

🎯 Final Thoughts

Wave Function Collapse is not just a fancy name — it’s a blend of quantum-like logic and classic constraint solving, producing mesmerizing, rule-abiding content.

Want to build infinite Zelda maps, sci-fi textures, or even tile-based emojis?

WFC’s overlapping model is your new best friend.

📚 Resources

Happy collapsing! 🌌

DEV Community

🧠 #186 — Wave Function Collapse: Overlapping Model Explained with Code & Formulas