SpecializedSource checked

Wave Function Collapse

Generates layouts by repeatedly choosing low-uncertainty cells and propagating constraints.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Procedural Generation
Difficulty: Advanced
Family: Constraint-Based Generation
Tier: Specialized
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 0
Relationships: 6
Code example: Not ready
Visualization: Ready

Overview

Wave Function Collapse keeps possible tiles for each cell, chooses a cell to resolve, and removes incompatible options from neighbors.

Core Concepts

tile constraintsentropy choiceconstraint propagationcontradiction handlinggenerated structurerandom samplingconstraint-based generationseeded variation

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(c log c)

Average

O(c r)

Worst

O(c r^2)

Space

O(c r)

When to Use

Use Wave Function Collapse when you need to maintain possible states for each cell.
Use it for tilemap generation with inputs like tile set.
Use it when repeatable content can be produced from compact rules, parameters, and seeds.
Use it when the Constraint-Based Generation tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when repeatability is required but seeds and random sources are not controlled.
Avoid it when authored control matters more than variation or replayability.
Avoid it when O(c r^2) worst-case behavior is too costly for the expected input size.
Avoid it when the required output is not generated grid.

What It Does

Maintains possible states for each cell
Propagates adjacency constraints

Use Cases

Tilemap generation
Texture synthesis
Constrained level layouts

Inputs

Tile set
Adjacency rules
Output grid size

Outputs

Generated grid
Contradiction result if constraints fail

Pseudocode

1.Start with every cell allowing every tile
2.Choose a cell with low uncertainty
3.Randomly select one valid tile for that cell
4.Remove incompatible options from neighboring cells
5.Repeat until the grid is complete or a contradiction occurs

Canonical Example

Input: seed = 42, size = 8x8
Output: generated map, pattern, or noise field
Explanation: Wave Function Collapse: The algorithm expands a small set of rules and random choices into structured content.

Implementation Notes

Keep the input contract explicit: Tile set; Adjacency rules; Output grid size.
Use this step as the implementation spine: Start with every cell allowing every tile.
Then preserve the next state change: Choose a cell with low uncertainty.
Thread a seedable random source through the implementation for repeatable tests.
Expose seed and parameters so results can be reproduced and tuned.

Common Pitfalls

When constraints lead to a contradiction, implementations usually restart or backtrack.
Letting random choices create disconnected, invalid, or impossible-to-use output.
Returning generated grid without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

2D Grid Wavefront & Trajectory

Show grid cells losing possibilities until a complete pattern appears.

Step 1 of 5: Start with every cell allowing every tile

constraint-grid

Notes

Wave Function Collapse operates in O(c r) time and O(c r) space within the Constraint-Based Generation family. Often compared with Perlin Noise and Simplex Noise.