Constraint Systems
Wave Function Collapse with entropy visualization
System Overview
Wave Function Collapse (WFC) generates patterns by collapsing possibilities based on constraints. Starting with all possibilities, it repeatedly picks the cell with lowest entropy (fewest options), collapses it to a single value, and propagates constraints to neighbors.
The entropy heatmap visualizes uncertainty: bright red = many possibilities, dark blue = few possibilities, black = collapsed. This makes the algorithm's decision-making process visible.
Why Games Use This
- Procedural Generation: Create coherent patterns from examples
- Tile-based Worlds: Generate dungeons, cities, landscapes
- Constraint Satisfaction: Ensure local consistency
- Example-based: Learn patterns from sample images
- Backtracking: Handle contradictions gracefully
Key Parameters
- Collapse Speed: How fast the algorithm progresses
- Constraints: Rules defining valid adjacencies
- Entropy: Number of remaining possibilities per cell
- Propagation: How constraints spread to neighbors
Failure Modes
- Contradictions: No valid tile for a cell (requires backtracking)
- Insufficient constraints: Too many possibilities, slow convergence
- Over-constrained: No valid solutions exist
- Poor tile set: Tiles don't connect properly
- Performance: Large grids with many tile types are expensive
Scaling Behavior
WFC is O(n²) in worst case, but typically much better due to constraint propagation. Each collapse can trigger cascading propagations. For large grids, use chunking or hierarchical WFC.
Memory scales with grid size and tile count. Each cell stores a list of possible tiles.
Related Algorithms
- Model Synthesis: Similar constraint-based generation
- Markov Chains: Probabilistic tile placement
- Graph Grammars: Rule-based pattern generation
- Backtracking Search: Handle contradictions
Free Tools & Libraries
- mxgmn/WaveFunctionCollapse: Original implementation
- Oskar Stålberg: Interactive WFC demos
System-Thinking Prompts
- What happens when constraints conflict? How does backtracking work?
- Where does WFC break? Contradictions, infinite loops?
- How could players exploit deterministic WFC? Predict patterns?
- Which parameter dominates? Constraint strength or entropy selection?
- What's the optimal entropy selection? Random vs lowest?
- How do tile sets affect generation? Too few vs too many tiles?
- Can we guarantee valid solutions? Or is backtracking always needed?