🧠 #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_iis 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! 🌌
Top comments (0)