Wave Function Collapse

2 min read•1 page

Wave Function Collapse: Shannon Entropy Selection: Wave Function Collapse (WFC) synthesizes seamless procedural tile assemblies from small exemplar rules. Every cell begins in quantum-like superposition of all possible states. At each iteration, the algorithm finds the uncollapsed cell with minimum Shannon entropy and collapses it to a single state according to relative pattern frequencies.

Entropy Minimization Principle:

1. Superposition: Every grid slot holds a list of legally allowable modular tiles. 2. Shannon Entropy: $H(X) = -\sum p(x) \log p(x)$. Cells with fewer remaining possibilities have lower entropy. 3. Observation Collapse: Picking the lowest entropy cell avoids deadlocks and collapses the most constrained location first.

python

1import math
2
3def calculate_shannon_entropy(cell_possibilities, tile_weights):
4    """
5    Computes Shannon entropy for an uncollapsed cell in Wave Function Collapse.
6    H = log(sum_w) - (sum(w * log(w)) / sum_w)
7    Lowest entropy cells are prioritized for collapse to minimize backtracking.
8    """
9    total_w = sum(tile_weights[t] for t in cell_possibilities)
10    if total_w == 0 or len(cell_possibilities) <= 1:
11        return 0.0  # Already collapsed or contradictory
12        
13    sum_w_log_w = sum(tile_weights[t] * math.log(tile_weights[t]) for t in cell_possibilities)
14    return math.log(total_w) - (sum_w_log_w / total_w)

Collapse Step

3.00

3 min read•1 page

Wave Function Collapse: Constraint Propagation (AC-3): Once a cell collapses, its decision cascades outwards. Using socket-matching adjacency rules, any option in an adjacent cell that cannot legally connect is pruned. If that cell's options shrink, the pruning continues recursively, propagating the wave until all remaining superpositions satisfy local consistency.

Arc-Consistency Propagation:

1. Socket Matching: Tiles connect across boundaries only when matching edge phenotypes align. 2. Pruning Queue: A stack-based worklist propagates modifications outward across Manhattan neighbors. 3. Deadlock Detection: If any uncollapsed cell reaches zero possibilities (contradiction), the algorithm backtracks.

python

1def propagate_wfc_constraints(stack, wave, adjacency_rules):
2    """
3    Constraint propagation loop (AC-3 style arc consistency).
4    When tile possibilities are removed from cell (x, y), check all 4 neighbors.
5    Prune any neighbor tile that has zero valid connectors to the current cell.
6    """
7    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # N, S, E, W
8    
9    while stack:
10        cx, cy = stack.pop()
11        current_options = wave[cy][cx]
12        
13        for dx, dy in directions:
14            nx, ny = cx + dx, cy + dy
15            if not in_bounds(nx, ny):
16                continue
17                
18            neighbor_options = wave[ny][nx]
19            legal_tiles = set()
20            for t in current_options:
21                legal_tiles.update(adjacency_rules[t][(dx, dy)])
22                
23            # Intersect possibilities
24            pruned = neighbor_options - legal_tiles
25            if pruned:
26                wave[ny][nx] -= pruned
27                stack.append((nx, ny))  # Propagate ripple outwards

Propagation Depth

2.00