Wave Function Collapse
Wave Function Collapse (WFC) is a procedural generation algorithm that creates patterns by propagating constraints. Inspired by quantum mechanics, it generates coherent outputs from a set of tiles and their adjacency rules.
Core Concept
- Start with a grid where each cell can be any tile (superposition)
- Collapse one cell to a specific tile (observation)
- Propagate constraints to neighbors (wave propagation)
- Repeat until all cells are collapsed
Basic Structure
1type Tile struct {
2 ID int
3 Pattern [][]int // Visual pattern
4}
5
6type Cell struct {
7 Collapsed bool
8 Options []int // Possible tile IDs
9 Entropy float64
10}
11
12type WFC struct {
13 width, height int
14 grid [][]Cell
15 tiles []Tile
16 rules map[int]map[Direction][]int // Adjacency rules
17}
18
19type Direction int
20
21const (
22 North Direction = iota
23 East
24 South
25 West
26)
27
28func NewWFC(width, height int, tiles []Tile) *WFC {
29 wfc := &WFC{
30 width: width,
31 height: height,
32 tiles: tiles,
33 rules: make(map[int]map[Direction][]int),
34 grid: make([][]Cell, height),
35 }
36
37 // Initialize grid with all possibilities
38 for y := 0; y < height; y++ {
39 wfc.grid[y] = make([]Cell, width)
40 for x := 0; x < width; x++ {
41 options := make([]int, len(tiles))
42 for i := range tiles {
43 options[i] = i
44 }
45 wfc.grid[y][x] = Cell{
46 Collapsed: false,
47 Options: options,
48 Entropy: float64(len(tiles)),
49 }
50 }
51 }
52
53 return wfc
54}
Adjacency Rules
Define which tiles can be adjacent to each other:
1func (wfc *WFC) AddRule(tileID int, direction Direction, allowedNeighbors []int) {
2 if wfc.rules[tileID] == nil {
3 wfc.rules[tileID] = make(map[Direction][]int)
4 }
5 wfc.rules[tileID][direction] = allowedNeighbors
6}
7
8// Example: Define tile compatibility
9func SetupSimpleRules(wfc *WFC) {
10 // Tile 0: Grass
11 // Tile 1: Water
12 // Tile 2: Sand (transition)
13
14 // Grass can be next to grass or sand
15 wfc.AddRule(0, North, []int{0, 2})
16 wfc.AddRule(0, East, []int{0, 2})
17 wfc.AddRule(0, South, []int{0, 2})
18 wfc.AddRule(0, West, []int{0, 2})
19
20 // Water can be next to water or sand
21 wfc.AddRule(1, North, []int{1, 2})
22 wfc.AddRule(1, East, []int{1, 2})
23 wfc.AddRule(1, South, []int{1, 2})
24 wfc.AddRule(1, West, []int{1, 2})
25
26 // Sand can be next to anything
27 wfc.AddRule(2, North, []int{0, 1, 2})
28 wfc.AddRule(2, East, []int{0, 1, 2})
29 wfc.AddRule(2, South, []int{0, 1, 2})
30 wfc.AddRule(2, West, []int{0, 1, 2})
31}
Core Algorithm
1. Find Lowest Entropy Cell
1func (wfc *WFC) FindLowestEntropyCell() (int, int, bool) {
2 minEntropy := math.MaxFloat64
3 var minX, minY int
4 found := false
5
6 for y := 0; y < wfc.height; y++ {
7 for x := 0; x < wfc.width; x++ {
8 cell := &wfc.grid[y][x]
9
10 if !cell.Collapsed && cell.Entropy < minEntropy && len(cell.Options) > 0 {
11 // Add small random noise to break ties
12 entropy := cell.Entropy + rand.Float64()*0.1
13 if entropy < minEntropy {
14 minEntropy = entropy
15 minX, minY = x, y
16 found = true
17 }
18 }
19 }
20 }
21
22 return minX, minY, found
23}
2. Collapse Cell
1func (wfc *WFC) CollapseCell(x, y int) bool {
2 cell := &wfc.grid[y][x]
3
4 if len(cell.Options) == 0 {
5 return false // Contradiction!
6 }
7
8 // Choose random option (can be weighted)
9 chosenTile := cell.Options[rand.Intn(len(cell.Options))]
10
11 cell.Options = []int{chosenTile}
12 cell.Collapsed = true
13 cell.Entropy = 0
14
15 return true
16}
3. Propagate Constraints
1func (wfc *WFC) Propagate(startX, startY int) bool {
2 stack := []struct{ x, y int }{{startX, startY}}
3
4 for len(stack) > 0 {
5 // Pop from stack
6 curr := stack[len(stack)-1]
7 stack = stack[:len(stack)-1]
8
9 x, y := curr.x, curr.y
10 cell := &wfc.grid[y][x]
11
12 // Check all four neighbors
13 neighbors := []struct {
14 x, y int
15 dir Direction
16 }{
17 {x, y - 1, North},
18 {x + 1, y, East},
19 {x, y + 1, South},
20 {x - 1, y, West},
21 }
22
23 for _, n := range neighbors {
24 if n.x < 0 || n.x >= wfc.width || n.y < 0 || n.y >= wfc.height {
25 continue
26 }
27
28 neighbor := &wfc.grid[n.y][n.x]
29 if neighbor.Collapsed {
30 continue
31 }
32
33 // Constrain neighbor based on current cell's options
34 if wfc.ConstrainCell(n.x, n.y, x, y, n.dir) {
35 // If neighbor changed, add to stack
36 stack = append(stack, struct{ x, y int }{n.x, n.y})
37 }
38 }
39 }
40
41 return true
42}
43
44func (wfc *WFC) ConstrainCell(x, y, sourceX, sourceY int, direction Direction) bool {
45 cell := &wfc.grid[y][x]
46 sourceCell := &wfc.grid[sourceY][sourceX]
47
48 // Get opposite direction
49 oppositeDir := wfc.OppositeDirection(direction)
50
51 // Collect all valid options
52 validOptions := make(map[int]bool)
53 for _, sourceTileID := range sourceCell.Options {
54 if allowedNeighbors, exists := wfc.rules[sourceTileID][direction]; exists {
55 for _, neighborID := range allowedNeighbors {
56 validOptions[neighborID] = true
57 }
58 }
59 }
60
61 // Filter cell's options
62 newOptions := []int{}
63 for _, option := range cell.Options {
64 if validOptions[option] {
65 newOptions = append(newOptions, option)
66 }
67 }
68
69 // Check if options changed
70 if len(newOptions) != len(cell.Options) {
71 cell.Options = newOptions
72 cell.Entropy = float64(len(newOptions))
73
74 if len(newOptions) == 0 {
75 return false // Contradiction!
76 }
77
78 return true // Changed
79 }
80
81 return false // No change
82}
83
84func (wfc *WFC) OppositeDirection(dir Direction) Direction {
85 switch dir {
86 case North:
87 return South
88 case South:
89 return North
90 case East:
91 return West
92 case West:
93 return East
94 }
95 return North
96}
4. Main Generation Loop
1func (wfc *WFC) Generate() bool {
2 for {
3 // Find cell with lowest entropy
4 x, y, found := wfc.FindLowestEntropyCell()
5 if !found {
6 // All cells collapsed!
7 return true
8 }
9
10 // Collapse the cell
11 if !wfc.CollapseCell(x, y) {
12 return false // Contradiction
13 }
14
15 // Propagate constraints
16 if !wfc.Propagate(x, y) {
17 return false // Contradiction
18 }
19 }
20}
21
22// Generate with retry on failure
23func (wfc *WFC) GenerateWithRetry(maxAttempts int) bool {
24 for attempt := 0; attempt < maxAttempts; attempt++ {
25 // Reset grid
26 wfc.Reset()
27
28 if wfc.Generate() {
29 return true
30 }
31 }
32 return false
33}
34
35func (wfc *WFC) Reset() {
36 for y := 0; y < wfc.height; y++ {
37 for x := 0; x < wfc.width; x++ {
38 options := make([]int, len(wfc.tiles))
39 for i := range wfc.tiles {
40 options[i] = i
41 }
42 wfc.grid[y][x] = Cell{
43 Collapsed: false,
44 Options: options,
45 Entropy: float64(len(wfc.tiles)),
46 }
47 }
48 }
49}
Advanced Features
Weighted Tile Selection
1type WeightedTile struct {
2 Tile
3 Weight float64
4}
5
6func (wfc *WFC) CollapseCellWeighted(x, y int, weights map[int]float64) bool {
7 cell := &wfc.grid[y][x]
8
9 if len(cell.Options) == 0 {
10 return false
11 }
12
13 // Calculate total weight
14 totalWeight := 0.0
15 for _, tileID := range cell.Options {
16 totalWeight += weights[tileID]
17 }
18
19 // Choose weighted random
20 r := rand.Float64() * totalWeight
21 cumulative := 0.0
22
23 for _, tileID := range cell.Options {
24 cumulative += weights[tileID]
25 if r <= cumulative {
26 cell.Options = []int{tileID}
27 cell.Collapsed = true
28 cell.Entropy = 0
29 return true
30 }
31 }
32
33 return false
34}
Seeded Generation
1func (wfc *WFC) SetSeed(x, y, tileID int) {
2 cell := &wfc.grid[y][x]
3 cell.Options = []int{tileID}
4 cell.Collapsed = true
5 cell.Entropy = 0
6 wfc.Propagate(x, y)
7}
8
9// Example: Force water in center
10func GenerateWithLake(wfc *WFC) {
11 centerX := wfc.width / 2
12 centerY := wfc.height / 2
13
14 // Seed a 3x3 lake
15 for dy := -1; dy <= 1; dy++ {
16 for dx := -1; dx <= 1; dx++ {
17 wfc.SetSeed(centerX+dx, centerY+dy, 1) // 1 = water tile
18 }
19 }
20
21 wfc.Generate()
22}
Backtracking on Contradiction
1type State struct {
2 grid [][]Cell
3}
4
5func (wfc *WFC) SaveState() *State {
6 state := &State{
7 grid: make([][]Cell, wfc.height),
8 }
9
10 for y := 0; y < wfc.height; y++ {
11 state.grid[y] = make([]Cell, wfc.width)
12 for x := 0; x < wfc.width; x++ {
13 // Deep copy options
14 options := make([]int, len(wfc.grid[y][x].Options))
15 copy(options, wfc.grid[y][x].Options)
16
17 state.grid[y][x] = Cell{
18 Collapsed: wfc.grid[y][x].Collapsed,
19 Options: options,
20 Entropy: wfc.grid[y][x].Entropy,
21 }
22 }
23 }
24
25 return state
26}
27
28func (wfc *WFC) RestoreState(state *State) {
29 for y := 0; y < wfc.height; y++ {
30 for x := 0; x < wfc.width; x++ {
31 options := make([]int, len(state.grid[y][x].Options))
32 copy(options, state.grid[y][x].Options)
33
34 wfc.grid[y][x] = Cell{
35 Collapsed: state.grid[y][x].Collapsed,
36 Options: options,
37 Entropy: state.grid[y][x].Entropy,
38 }
39 }
40 }
41}
42
43func (wfc *WFC) GenerateWithBacktracking() bool {
44 stack := []*State{}
45
46 for {
47 x, y, found := wfc.FindLowestEntropyCell()
48 if !found {
49 return true // Success!
50 }
51
52 // Save state before collapse
53 stack = append(stack, wfc.SaveState())
54
55 if !wfc.CollapseCell(x, y) || !wfc.Propagate(x, y) {
56 // Contradiction! Backtrack
57 if len(stack) == 0 {
58 return false // No solution
59 }
60
61 // Restore previous state
62 wfc.RestoreState(stack[len(stack)-1])
63 stack = stack[:len(stack)-1]
64
65 // Remove the option that caused contradiction
66 cell := &wfc.grid[y][x]
67 if len(cell.Options) > 1 {
68 cell.Options = cell.Options[1:]
69 cell.Entropy = float64(len(cell.Options))
70 }
71 }
72 }
73}
Practical Example: Tilemap Generation
1func GenerateTilemap() {
2 // Define tiles
3 tiles := []Tile{
4 {ID: 0, Pattern: [][]int{{0, 0}, {0, 0}}}, // Grass
5 {ID: 1, Pattern: [][]int{{1, 1}, {1, 1}}}, // Water
6 {ID: 2, Pattern: [][]int{{2, 2}, {2, 2}}}, // Sand
7 {ID: 3, Pattern: [][]int{{3, 3}, {3, 3}}}, // Forest
8 }
9
10 // Create WFC
11 wfc := NewWFC(20, 20, tiles)
12
13 // Setup rules
14 SetupSimpleRules(wfc)
15
16 // Add weighted preferences
17 weights := map[int]float64{
18 0: 10.0, // Grass is common
19 1: 3.0, // Water is less common
20 2: 5.0, // Sand is medium
21 3: 7.0, // Forest is fairly common
22 }
23
24 // Generate
25 if wfc.GenerateWithRetry(10) {
26 // Export to image or game map
27 ExportToImage(wfc)
28 }
29}
30
31func ExportToImage(wfc *WFC) {
32 // Create image
33 img := image.NewRGBA(image.Rect(0, 0, wfc.width*16, wfc.height*16))
34
35 colors := map[int]color.RGBA{
36 0: {34, 139, 34, 255}, // Grass green
37 1: {30, 144, 255, 255}, // Water blue
38 2: {238, 214, 175, 255}, // Sand beige
39 3: {0, 100, 0, 255}, // Forest dark green
40 }
41
42 for y := 0; y < wfc.height; y++ {
43 for x := 0; x < wfc.width; x++ {
44 tileID := wfc.grid[y][x].Options[0]
45 c := colors[tileID]
46
47 // Fill 16x16 block
48 for dy := 0; dy < 16; dy++ {
49 for dx := 0; dx < 16; dx++ {
50 img.Set(x*16+dx, y*16+dy, c)
51 }
52 }
53 }
54 }
55
56 // Save image
57 f, _ := os.Create("tilemap.png")
58 defer f.Close()
59 png.Encode(f, img)
60}
Applications
- Procedural Level Generation: Dungeons, overworld maps
- Texture Synthesis: Generate seamless textures
- Terrain Generation: Biome placement, feature distribution
- Puzzle Generation: Sudoku, crosswords
- Art Generation: Pixel art, patterns
Complexity
Time: $O(n^2 \times t \times r)$ where:
- $n$ = grid size
- $t$ = number of tile types
- $r$ = number of rules
Space: $O(n^2 \times t)$
When to Use WFC
✅ Use when:
- Need coherent pattern generation
- Have well-defined tile adjacency rules
- Want deterministic results (with seed)
- Need local constraint satisfaction
❌ Don't use when:
- Need global structure (use grammar-based generation)
- Rules are too complex (may not converge)
- Need real-time generation (can be slow)
- Want more randomness (use noise-based generation)
Related Snippets
- Binary Search
Binary search is an efficient algorithm for finding a target value in a sorted … - Binary Tree
A binary tree is a tree data structure where each node has at most two children, … - General Tree
A tree is a hierarchical data structure consisting of nodes connected by edges, … - Heap Data Structure
A heap is a specialized tree-based data structure that satisfies the heap … - Heap Sort
Heap sort is a comparison-based sorting algorithm that uses a binary heap data … - Linked List Operations
Optimal techniques for common linked list operations using pointer manipulation, … - LRU and LFU Cache
Cache replacement policies determine which items to evict when the cache is … - Merge Sort
Merge sort is a stable, comparison-based sorting algorithm that uses the … - Quadtree
A Quadtree is a tree data structure where each internal node has exactly four … - Quick Sort
Quick sort is an efficient, in-place, comparison-based sorting algorithm that … - String Similarity Algorithms
Algorithms for measuring similarity between strings, used in spell checking, DNA … - Terrain & Heightmap Generation
Procedural terrain generation creates realistic landscapes using mathematical … - Trie (Prefix Tree)
A Trie (pronounced "try") is a tree-like data structure used to store …