Wave Function Collapse

Wave Function Collapse (WFC) is a constraint-based procedural content generation algorithm inspired by quantum mechanics principles, designed to create coherent tile-based structures such as game levels, terrains, and maps from simple input patterns and adjacency rules ¹⁵. Its primary purpose is to enable game developers to generate vast amounts of varied, high-quality content efficiently while maintaining local consistency and design coherence, significantly reducing the manual effort required for level design ². In modern game development, WFC matters because it bridges the gap between hand-crafted quality and procedural scalability, enabling the creation of replayable, dynamic game worlds that enhance player engagement while preserving artistic vision—a capability increasingly vital for indie developers and studios working with tools like Unity and ExcaliburJS ¹²⁵.

Overview

Wave Function Collapse emerged from the intersection of computer graphics research and game development needs in the mid-2010s. The algorithm originated from Maxim Gumin's 2016 implementation, which built upon Paul Merrell's earlier academic work on model synthesis and texture generation ⁵. The technique gained its name from the quantum mechanics concept of wave function collapse, where a quantum system transitions from multiple possible states (superposition) to a single definite state upon observation—though WFC itself is a purely classical algorithm that borrows this conceptual framework ¹⁵.

The fundamental challenge WFC addresses is the tension between procedural generation's scalability and the need for coherent, believable game environments. Traditional procedural generation methods like Perlin noise excel at creating natural-looking randomness but struggle to enforce complex design constraints, often producing nonsensical combinations like water tiles floating in mid-air or roads that abruptly terminate ¹³. Conversely, hand-crafted content ensures quality but becomes prohibitively expensive for games requiring vast or infinitely replayable worlds. WFC solves this by treating level generation as a constraint satisfaction problem, where local adjacency rules propagate throughout a grid to ensure global coherence while maintaining procedural variety ⁵.

Since its introduction, WFC has evolved from a niche algorithm into a widely adopted tool in game development. Early implementations focused on simple 2D tile-based generation, but the technique has expanded to support 3D voxel worlds, hierarchical generation systems, and hybrid approaches combining WFC with other procedural methods like L-systems and generative adversarial networks ²⁴. The algorithm has been integrated into major game engines through plugins like Tessera for Unity, and has influenced commercial titles ranging from indie roguelikes to ambitious procedural world-builders ²⁵.

Key Concepts

Superposition and Domain

In WFC, superposition refers to the state where each cell in the output grid simultaneously contains all possible tiles from the input tileset until it is "observed" or collapsed to a single definite state ⁵. The domain is the specific set of possible tiles that a given cell can become at any point during generation, which starts as the complete tileset and narrows through constraint propagation ¹.

For example, when generating a medieval town map, a cell might initially have a domain containing all 15 possible tiles: grass, cobblestone road, building corner, building wall, fountain, tree, etc. As neighboring cells collapse—say the cell to the north becomes a cobblestone road—the domain narrows to only tiles compatible with having a road to the north, eliminating options like standalone trees or building corners that don't connect to roads. This domain might reduce to just three possibilities: road continuation, road intersection, or road-adjacent building entrance.

Entropy and Cell Selection

Entropy in WFC measures the uncertainty or number of possibilities remaining for a given cell, typically calculated using Shannon entropy: H = -Σ p(tile) × log p(tile), where p(tile) represents the probability weight of each possible tile ⁵. The algorithm prioritizes collapsing cells with the lowest entropy first, as these have the fewest options and are most constrained by their neighbors ².

Consider generating a coastal landscape where the grid edges are pre-seeded with ocean tiles. Cells adjacent to the ocean will have very low entropy—perhaps only beach, cliff, or shallow water tiles are compatible with ocean neighbors. Meanwhile, cells in the grid's interior might still have high entropy with dozens of possible land tiles. The algorithm would collapse the low-entropy coastal cells first, which then constrains their inland neighbors, creating a cascading wave of decisions that propagates from the constrained edges toward the uncertain interior, ensuring the coastline forms coherently before inland details are determined.

Adjacency Rules and Constraints

Adjacency rules define which tiles can legally neighbor each other in each cardinal direction (north, south, east, west, and potentially up/down in 3D implementations) ¹³. These rules can be extracted automatically from sample input images by analyzing which tiles appear next to each other, or defined manually by designers to enforce specific aesthetic or gameplay requirements ⁵.

In a dungeon generation scenario, adjacency rules might specify that a "door-north" tile (a wall segment with a door on its north edge) can only have "corridor" or "room-floor" tiles to its north, while its south, east, and west sides must connect to "wall" tiles. A "corner-northeast" wall tile would require walls to its north and east, but floor tiles to its south and west. These rules prevent impossible configurations like doors opening into solid walls or corridors that dead-end into room corners, ensuring every generated dungeon is architecturally sound and navigable.

Propagation and Support

Propagation is the process by which collapsing one cell to a definite tile triggers updates to neighboring cells' domains, removing incompatible options and potentially triggering further propagation in a cascading effect ⁴⁵. Support refers to the count of compatible neighbor configurations for a given tile-direction pair—when support drops to zero, that tile becomes impossible and must be removed from the domain ⁵.

Imagine generating a river system where a cell collapses to a "river-flowing-south" tile. The propagation phase examines all four neighbors: the northern neighbor's domain is updated to include only tiles with south-facing river outlets (like "river-flowing-south" or "river-bend-southwest"), while the southern neighbor must have north-facing river inlets. The eastern and western neighbors must have tiles compatible with a river's bank (like "grass-river-east" or "forest-river-west"). If the southern neighbor previously had only "mountain" tiles in its domain—none of which accept river inlets—its support drops to zero, creating a contradiction that forces the algorithm to backtrack and try a different tile for the original cell.

Overlapping Model vs. Simple Tiled Model

WFC supports two primary operational modes: the simple tiled model, which uses explicit edge-matching rules between discrete tiles, and the overlapping model, which extracts patterns from sample images using sliding N×N windows (typically 2×2 or 3×3) to capture more organic, texture-like coherence ²⁵. The overlapping model treats each unique N×N pattern as a "tile" and derives adjacency rules from how these patterns overlap in the source image ⁵.

For a forest generation task, the simple tiled model might use 8 distinct tiles (grass, tree-center, tree-top, tree-bottom, etc.) with manually defined rules about which edges connect. The overlapping model instead takes a hand-painted 20×20 pixel forest sample and extracts all unique 3×3 pixel patterns—perhaps 45 different patterns capturing various combinations of grass, tree trunks, foliage, and shadows. When generating a new forest, it ensures every 3×3 region matches one of these extracted patterns, producing output that statistically resembles the input sample's texture and structure without directly copying it, creating natural-looking variation in tree density, clearings, and undergrowth distribution.

Backtracking and Contradiction Resolution

Backtracking occurs when the algorithm reaches a contradiction—a cell whose domain becomes empty because no tiles satisfy all neighboring constraints ⁴⁵. At this point, the algorithm must undo previous decisions and try alternative tile choices, either through full restart (regenerating from scratch) or partial backtracking (reverting to a saved state before the contradiction) ⁵.

In a city block generation scenario, suppose the algorithm has collapsed 80% of a 32×32 grid, creating a network of roads and building plots. A cell in the city center reaches a state where it must simultaneously connect to roads on three sides and accommodate a large building footprint—but no tile in the tileset satisfies both requirements. The algorithm detects this zero-domain contradiction and backtracks to the most recent decision point that contributed to this impossible state, perhaps 15 cells earlier where a road intersection was placed. It then selects a different tile for that intersection (maybe a T-junction instead of a four-way cross), and propagation resumes from that point, potentially avoiding the contradiction by creating a different road layout that leaves room for the building.

Applications in Game Development

Roguelike Dungeon Generation

WFC excels at generating coherent dungeon layouts for roguelike games where each playthrough requires a unique but navigable level structure ². By defining tiles for corridors, rooms, doors, treasure chambers, and trap rooms with appropriate adjacency rules, developers can ensure generated dungeons are always solvable while maintaining variety. For instance, the game Caves of Qud employs WFC-inspired techniques for biome generation, ensuring that underground cave systems transition logically between different geological zones ². A practical implementation might use a 50×50 grid with 25 tile types including various room sizes, corridor orientations, and special chambers, with rules ensuring every room connects to the corridor network and dead-ends are intentional (treasure rooms) rather than accidental.

Terrain and World Map Creation

Game developers use WFC to generate believable terrain that respects geographical logic—beaches transition to grasslands, which give way to forests, then mountains, with rivers flowing downhill ¹². The ExcaliburJS framework demonstrates this with a Final Fantasy-inspired overworld generator that first creates base terrain (ocean, beach, grass, forest, mountains) using WFC, then runs a second WFC pass to place structures like towns and castles only on appropriate terrain types ². This layered approach ensures towns never spawn in oceans and forests don't abruptly transition to deserts, creating a 100×100 tile world map in under two seconds that feels hand-designed despite being entirely procedural.

Architectural and Settlement Layout

WFC enables the generation of believable buildings and settlements by encoding architectural rules into tile adjacency constraints ². The game Townscaper uses WFC-like principles to let players place building blocks that automatically configure themselves into coherent structures with appropriate windows, doors, rooflines, and decorative elements based on neighboring blocks ². A practical implementation for a medieval village might define 40 tiles representing building components (walls, corners, roofs, doors, windows) with rules ensuring structural integrity (walls support roofs, doors appear on ground floors, windows don't float), generating unique village layouts where each building is architecturally sound and streets form natural pathways between structures.

Texture and Pattern Synthesis

Beyond discrete tile-based generation, WFC's overlapping model serves as a powerful texture synthesis tool for creating large, non-repeating textures from small samples ⁵. Game artists can paint a small 32×32 pixel sample of brick wall, grass, or alien terrain, and WFC generates a 512×512 pixel texture that maintains the sample's visual characteristics without obvious tiling artifacts. This application extends to non-visual domains: developers have experimented with WFC for generating musical patterns (treating notes and rhythms as tiles with harmonic adjacency rules) and dialogue trees (where sentence fragments must connect grammatically and thematically) ¹⁴.

Best Practices

Start with High-Quality, Diverse Tilesets

The output quality of WFC is fundamentally limited by the input tileset's diversity and rule richness ³⁵. Best practice involves creating tilesets with 10-30 distinct tiles that capture meaningful variation while maintaining clear adjacency relationships. For example, rather than a single "grass" tile, include grass-with-flowers, grass-with-rocks, grass-near-water, and grass-shaded variants, each with slightly different adjacency rules that create natural-looking variation. When using the overlapping model, provide sample images that demonstrate the full range of desired patterns—a forest sample should include clearings, dense areas, and edge transitions, not just uniform tree coverage. Iterative refinement is essential: generate hundreds of outputs, identify undesirable patterns (like repetitive structures or impossible configurations), and adjust tiles or rules accordingly ²⁴.

Implement Entropy Visualization and Debugging Tools

Given WFC's complexity, developers should build visualization tools that display each cell's current domain size or entropy as a heatmap during generation ³⁵. This allows real-time observation of how constraints propagate and helps identify problematic rules that cause frequent contradictions. A practical implementation might color cells on a gradient from blue (high entropy, many options) to red (low entropy, few options) to black (contradiction, zero options), with the ability to pause generation and inspect individual cells' remaining tile possibilities. Additionally, logging the propagation depth—how many cascade steps each collapse triggers—helps identify overly restrictive rules that cause excessive backtracking. These debugging tools reduce development time from weeks to days when tuning complex tilesets ⁵.

Use Hierarchical and Layered Generation

Rather than generating all content in a single WFC pass, best practice involves multiple passes at different scales or for different content types ²⁴. A terrain generator might first create a low-resolution 25×25 grid establishing major biomes (ocean, plains, mountains), then upscale each cell to a 4×4 high-resolution grid using biome-specific tilesets for detail. Subsequently, a separate WFC pass places structures (buildings, trees, rocks) only on appropriate terrain types. This hierarchical approach prevents contradictions by establishing large-scale structure before details, and allows different tilesets optimized for different scales. The ExcaliburJS example demonstrates this by generating base terrain first, then running a second pass for non-colliding building placement, ensuring towns never overlap and always sit on suitable ground ².

Optimize Propagation with Efficient Data Structures

Since propagation consumes 70-80% of WFC's computation time, performance optimization focuses here ³⁵. Best practice involves using bitsets or boolean arrays to represent domains (rather than lists), enabling O(1) tile removal and compatibility checks. Maintain a priority queue (min-heap) of uncollapsed cells sorted by entropy, avoiding full grid scans each iteration. Cache support counts—the number of compatible neighbors for each tile-direction pair—and update them incrementally during propagation rather than recalculating from scratch. For large grids (100×100+), implement chunking where the grid is divided into regions generated semi-independently, or use asynchronous coroutines in engines like Unity to spread generation across multiple frames, preventing frame rate drops ²⁴. These optimizations can reduce generation time from minutes to milliseconds for typical game levels.

Implementation Considerations

Tool and Engine Integration

Developers must choose between implementing WFC from scratch or using existing libraries and plugins based on project requirements ²⁵. For Unity projects, the Tessera plugin provides a production-ready WFC implementation with visual tile editors and 3D support, ideal for teams prioritizing rapid development over algorithmic control. The DeBroglie .NET library offers more flexibility for custom C# implementations with advanced features like backtracking strategies and constraint mixing. For web-based games, ExcaliburJS includes WFC utilities optimized for JavaScript performance ². When implementing from scratch, critical tool choices include the data structure for the grid (2D arrays for simple cases, spatial hashing for sparse 3D worlds), the rule storage format (JSON for designer-friendly editing, binary for runtime performance), and the random number generator (seedable for reproducible outputs, essential for multiplayer consistency) ³⁵.

Balancing Designer Control and Procedural Freedom

Effective WFC implementation requires carefully balancing designer intent with procedural variation ¹⁵. Provide mechanisms for "seeding" specific cells with required tiles—for example, fixing the player spawn point as a safe grass area, or placing a boss room at a dungeon's far end—while letting WFC fill surrounding areas procedurally. Implement weighted tile probabilities so designers can bias generation toward preferred aesthetics (e.g., 60% grass, 30% forest, 10% rocky areas) without hard constraints. For narrative-driven games, consider hybrid approaches where WFC generates the spatial layout but designers manually place story-critical elements afterward. The key is exposing intuitive parameters (biome density sliders, structure frequency controls) rather than raw adjacency matrices, allowing non-technical designers to guide generation without understanding the underlying algorithm ²⁴.

Performance Profiling and Scalability

WFC's performance varies dramatically based on grid size, tileset complexity, and rule restrictiveness, requiring careful profiling for target platforms ³⁵. Mobile games might limit generation to 32×32 grids completed in under 100ms, while PC titles can afford 256×256 grids over several seconds during loading screens. Profile contradiction rates—if more than 10% of generation attempts fail and require restarts, rules are likely over-constrained and need relaxation (adding wildcard tiles or loosening adjacency requirements). For real-time applications like dynamic terrain modification, implement incremental WFC that regenerates only affected regions when players alter the world. Consider GPU acceleration for massive grids: parallel implementations can collapse multiple non-adjacent cells simultaneously, though synchronization overhead limits speedup to 3-5× on typical hardware ⁴⁵.

Tileset Design Workflow and Iteration

Successful WFC implementation requires an iterative tileset design workflow ²³. Begin with a minimal viable tileset (5-8 tiles) capturing core patterns, generate test outputs, and identify missing transitions or undesirable repetitions. Gradually expand the tileset to address these issues—if grass-to-forest transitions look abrupt, add intermediate "grass-with-saplings" tiles. Use the overlapping model for rapid prototyping: paint a small sample image demonstrating desired aesthetics, extract patterns automatically, generate outputs, then refine the sample based on results. Maintain a test suite of edge cases: generate 1000 outputs and automatically flag any containing invalid adjacencies or excessive repetition. Version control tilesets alongside code, as rule changes can dramatically alter output characteristics. Budget 30-50% of WFC development time for tileset iteration—the algorithm is only as good as its input data ⁵.

Common Challenges and Solutions

Challenge: Contradiction Cascades and Generation Failures

One of the most frustrating WFC challenges occurs when the algorithm frequently encounters contradictions—cells whose domains become empty because no tiles satisfy all neighboring constraints—forcing complete regeneration or extensive backtracking ⁴⁵. This typically happens with overly restrictive adjacency rules or tilesets lacking necessary transition tiles. In a city generation scenario, if the tileset includes only straight roads and 90-degree corners but no T-junctions, the algorithm will frequently reach states where a road must connect in three directions but no tile exists to satisfy this requirement, causing generation to fail 40-60% of the time and frustrating players with long loading times.

Solution:

Address contradictions through a multi-pronged approach. First, analyze failed generations to identify common contradiction patterns—if failures cluster around specific tile combinations, add missing transition tiles to the tileset ⁵. Implement "wildcard" or "fallback" tiles that can legally neighbor any other tile (like a generic "rubble" or "mixed terrain" tile) to prevent impossible states, even if they're aesthetically suboptimal. Second, relax overly strict rules by adding low-probability adjacencies: if water should rarely neighbor mountains, assign a 5% probability rather than zero, allowing occasional exceptions that prevent deadlock ³. Third, implement sophisticated backtracking: instead of full restart on contradiction, save generation state every 10-20 collapses and revert to the most recent save, trying alternative tile choices. Finally, use entropy noise (small random values added to entropy calculations) to vary cell selection order between attempts, often avoiding contradictions through different collapse sequences ²⁵.

Challenge: Repetitive and Monotonous Outputs

Even when WFC successfully generates valid outputs, results can feel repetitive or monotonous, with the same patterns recurring frequently and lacking the organic variation of hand-crafted content ²³. This occurs when tilesets are too small, adjacency rules are too uniform, or tile probabilities are poorly balanced. For example, a dungeon generator might produce technically valid layouts but every dungeon feels similar—always 3-4 rectangular rooms connected by straight corridors—because the tileset lacks variety in room shapes and the rules don't encourage interesting spatial configurations.

Solution:

Combat monotony through tileset enrichment and probability tuning ²⁵. Expand tilesets to include rare "special" tiles (unique room shapes, decorative elements, unusual terrain features) with low spawn probabilities (5-10%), ensuring they appear occasionally but don't dominate. Implement tile rotation and reflection symmetry: a single "L-shaped corridor" tile can generate eight variations through 90-degree rotations and mirroring, multiplying effective tileset size without additional art assets ³. Use position-dependent rules for non-stationary generation: edge regions might favor defensive walls while centers prefer open plazas, creating spatial variation. Introduce multiple generation seeds: run WFC with different random seeds and let players choose preferred outputs, or blend multiple WFC results (terrain from seed A, structures from seed B). Finally, combine WFC with other procedural techniques—use Perlin noise to bias tile probabilities spatially (more trees in northern regions, more desert in south), or post-process WFC output with cellular automata to add organic irregularity ¹⁴.

Challenge: Performance Bottlenecks in Large-Scale Generation

WFC's computational complexity becomes problematic for large grids or real-time applications, with propagation cascades consuming seconds or minutes for 100×100+ grids ³⁵. The algorithm's iterative nature—each collapse potentially triggering dozens of propagation steps—creates unpredictable performance spikes. A open-world game attempting to generate a 500×500 tile region might experience 10-30 second freezes, unacceptable for player experience, while VR applications requiring 90fps cannot tolerate even 100ms generation pauses.

Solution:

Optimize performance through algorithmic improvements and architectural strategies ²⁴⁵. First, implement efficient data structures: use bitsets for domains (64 tiles fit in a single 64-bit integer, enabling fast bitwise operations), maintain a min-heap priority queue for entropy-based cell selection (O(log N) vs. O(N) for linear search), and cache support counts rather than recalculating. Second, employ spatial chunking: divide large grids into 32×32 chunks generated independently, with only boundary cells requiring cross-chunk constraint propagation. This enables parallel generation across CPU cores and progressive loading (generate visible chunks first, distant chunks during gameplay). Third, use asynchronous generation: in Unity, implement WFC as coroutines that yield every 10-20 collapses, spreading work across multiple frames to maintain 60fps. Fourth, consider GPU acceleration for massive grids: shader-based implementations can collapse multiple non-adjacent cells in parallel, though synchronization overhead limits practical speedup ⁵. Finally, pre-generate and cache common patterns: if generating similar dungeons repeatedly, pre-compute a library of valid room configurations and use WFC only for high-level layout, reducing generation time by 70-80% ⁴.

Challenge: Difficulty Extracting Rules from Complex Samples

When using the overlapping model to extract adjacency rules from sample images, complex or noisy inputs can produce thousands of unique patterns with unclear relationships, leading to either over-constrained generation (frequent contradictions) or under-constrained generation (outputs that don't resemble the sample) ⁵. A developer providing a hand-painted 64×64 pixel fantasy landscape as input might find WFC extracts 800+ unique 3×3 patterns, many differing by only a single pixel due to anti-aliasing or subtle shading, resulting in outputs that capture low-level texture but miss high-level structure like "forests cluster together" or "rivers flow downhill."

Solution:

Improve rule extraction through sample preparation and parameter tuning ³⁵. First, simplify input samples: use pixel art or posterized images with limited color palettes (8-16 colors) rather than high-resolution paintings, reducing pattern count by 90% while preserving structural information. Pre-process samples to remove noise—apply median filters to eliminate single-pixel variations, or manually clean samples to ensure every pixel is intentional. Second, tune N-gram size strategically: 2×2 patterns capture only immediate adjacency (fast but limited structure), 3×3 patterns balance locality and context (recommended default), while 4×4+ patterns capture more structure but exponentially increase pattern count and contradiction risk ⁵. Third, implement pattern frequency thresholds: ignore patterns appearing only once or twice in the sample (likely noise), focusing on patterns appearing 5+ times (likely meaningful). Fourth, use hierarchical sampling: extract coarse patterns from a downscaled sample to establish large-scale structure, then fine patterns from the full-resolution sample for detail. Finally, consider hybrid approaches: manually define high-level rules (biome transitions, architectural constraints) while using overlapping extraction only for texture-level detail within each biome or structure type ²⁴.

Challenge: Integration with Gameplay Systems

WFC generates spatial layouts but doesn't inherently understand gameplay requirements like difficulty progression, resource distribution, or narrative pacing ¹². A procedurally generated dungeon might be architecturally coherent but place the exit next to the entrance, scatter powerful items randomly, or create impossible difficulty spikes by clustering enemies. This disconnect between spatial generation and gameplay logic frustrates players and requires extensive post-processing or regeneration.

Solution:

Bridge WFC and gameplay through constraint layering and post-generation analysis ²⁴. First, implement gameplay-aware tile attributes: tag tiles with metadata (difficulty level, loot tier, traversal cost) and add these as soft constraints during generation—early dungeon regions favor low-difficulty tiles, later regions favor high-difficulty, with WFC's weighted probabilities ensuring gradual progression. Second, use multi-pass generation: WFC creates the spatial layout first, then a separate pathfinding pass analyzes the result to identify the longest path from entrance to exit, placing the boss room at the path's end and distributing checkpoints at intervals. Third, implement validation and regeneration: after WFC completes, run automated tests checking for gameplay requirements (Is the exit reachable? Are resources distributed evenly? Is difficulty progression monotonic?), regenerating with a different seed if tests fail. Fourth, combine WFC with directed graph generation: use WFC to generate individual rooms or terrain chunks, but connect them using a hand-crafted or procedurally generated graph that ensures proper progression (lock-and-key puzzles, ability-gated areas). Finally, expose gameplay parameters to designers: sliders for enemy density, loot frequency, and traversal complexity that modify tile probabilities and post-generation placement, allowing tuning without understanding WFC internals ¹⁵.

References

1. OreateAI. (2024). Understanding the Wave Function Collapse Algorithm: A Journey from Quantum Mechanics to Game Design. https://www.oreateai.com/blog/understanding-the-wave-function-collapse-algorithm-a-journey-from-quantum-mechanics-to-game-design/3a86eff845bced13411588c34ae3cc3d
2. ExcaliburJS. (2024). Wave Function Collapse. https://excaliburjs.com/blog/Wave%20Function%20Collapse/
3. Kavin Bharathi. (2024). The Fascinating Wave Function Collapse Algorithm. https://dev.to/kavinbharathi/the-fascinating-wave-function-collapse-algorithm-4nc3
4. YouTube. (2024). Wave Function Collapse Tutorial. https://www.youtube.com/watch?v=57MaTTVH_XI
5. Boris the Brave. (2020). Wave Function Collapse Explained. https://www.boristhebrave.com/2020/04/13/wave-function-collapse-explained/