🌿 CuriousWinds

Wave Function Collapse & 3D Procedural Constraints

Constraint satisfaction solvers, Shannon entropy heuristics, and contradiction backtracking in modular 3D worlds.

Executive Summary & Key Takeaways
Foundational Synthesis for Practitioners & Research Systems

Wave Function Collapse (WFC) reframes 3D procedural generation as entropy-driven constraint satisfaction, not brute-force sampling. Misconceptions conflate randomness with systematic pruning of invalid voxel configurations via empirical probability weights.

01 Entropy-Driven Collapse

Voxels collapse via Shannon entropy minimization, selecting lowest-uncertainty cells to reduce branching factor exponentially.

02 Six-Directional AC-3

Collapsing a voxel enforces bidirectional constraint propagation across ±X, ±Y, ±Z axes using arc consistency rules.

03 Adjacency Socket Errors

Face-matching violations (e.g., mismatched +X/-X sockets) halt propagation, risking combinatorial deadlocks.

04 MRV Entropy Threshold

Prioritize collapsing cells with non-zero entropy and highest remaining values to avoid invalid configurations.

In This Article
Curated Inquiry • Computing Systems & Machine Cognition

01. Voxel Superposition and Shannon Entropy Minimization

The algorithm models an empty 3D grid as a quantum-like system where every voxel cell $c$ contains a superposition of all candidate module prototypes:

SHANNON HEURISTIC METRIC
Minimum Entropy Heuristic
Cell Shannon Entropy with Frequency Weights (H(c))
H(c) = ln ( ∑ K k=1 wk ) − ∑k=1K wk ln wk ∑k=1K wk
wk: Frequency weight / prior probability of prototype tile k
K: Number of valid remaining candidate tiles in cell superposition D(c)
Selection Rule: Always collapse cell with minimal H(c) > 0 to avoid backtrack branching

Cells with $|D(c)| = 1$ have zero entropy and are already collapsed. Cells with the lowest non-zero entropy represent locations where surrounding constraints have reduced the space of possibilities to the narrowest margin. Selecting the cell $c^* = \operatorname{argmin}_{c} H(c)$ dramatically reduces the branching factor of the search space, preventing combinatorial search explosion.


02. Wave Function Collapse 3D: Six-Way Constraint Propagation

Once a cell $c^*$ collapses to a single prototype $t$, its decision restricts the set of admissible modules in all six contiguous spatial directions:

Δ = { +x, −x, +y, −y, +z, −z }

In rigorous wave function collapse 3d architectures, compatibility rules are encoded as directional binary relations. If prototype $t$ is placed at $(x, y, z)$, its neighbor at $(x+1, y, z)$ must possess a $-x$ face compatible with the $+x$ face of $t$:

D(cneighbor) ← D(cneighbor) ∩ Allowed(t, +x)
3D CONSTRAINT TOPOLOGY
3D Voxel Socket Adjacency Matrix
6-Directional Interface Rules
Spatial Axis / Direction Voxel Face Classification Symmetry & Inversion Match
+X / −X (Lateral East-West) Horizontal Structural Beam / Wall Socket Socket_A == Socket_A* (Mirrored Complement)
+Y / −Y (Longitudinal North-South) Lateral Facade Aperture / Fenestration Socket_B == Socket_B* (Symmetric Continuity)
+Z / −Z (Vertical Column Core) Load-Bearing Pillar & Slab Substrate Floor_Top == Base_Bottom (Rigid Gravity Alignment)

Constraint propagation is executed via the AC-3 (Arc Consistency Algorithm #3) worklist. When an invalid prototype is removed from a neighbor’s domain, that neighbor’s adjacent cells are pushed onto the propagation stack, continuing outward until no further domains can be pruned.


03. Contradiction Detection and Non-Chronological Backtracking

Because the selection heuristic is greedy, the propagator may encounter a state where a cell’s domain becomes empty:

D(cunfortunate) = ∅  (Immediate Contradiction Rollback)

An empty domain represents a logical contradiction: no prototype satisfies all surrounding spatial constraints simultaneously. In naive implementations, encountering a contradiction forces an entire grid regeneration, which scales exponentially with grid volume ($V = L \times W \times H$).

Advanced 3D WFC pipelines employ non-chronological backtracking (backjumping):

  1. Decision Trail Logging: Every collapse operation pushes the grid delta and candidate choices onto an undo stack.
  2. Conflict-Directed Graph Isolation: Identifying the minimal set of historical cell decisions that contributed to the impossible configuration.
  3. Targeted State Restoration: The system rolls back only the conflicting decisions, adds a negative constraint (nogood), and re-evaluates alternative prototypes without destroying distant valid architecture.

04. Rotational Symmetries and Socket Compression

To maximize procedural variety from a minimal set of authored 3D assets, modules undergo geometric transformations: rotations by $90^{\circ}, 180^{\circ}, 270^{\circ}$ around the vertical Z-axis, paired with reflection operators.

A prototype with asymmetric horizontal features generates four distinct rotational variants. To avoid computing an unwieldy $4M \times 4M$ adjacency matrix, sockets are parameterized by string tokens and symmetry flags:

  • Symmetric Sockets (S): Compatible with themselves under reflection (e.g., planar wall panels).
  • Asymmetric Sockets (A / A_flip): Require inverted matching tokens (e.g., left-handed pipe joints).
  • Vertical Alignment Sockets (V): Top and bottom connections that must align under rotation.

05. Infinite Chunk Generation and Boundary Preservation

Generating continuous procedural landscapes requires partitioning infinite space into discrete spatial chunks (e.g., $16 \times 16 \times 16$ voxel volumes).

wave-function-collap_tool.py
Python 3.11 · Diagnostic Framework
class VoxelGridWFC:
    def __init__(self, size_x, size_y, size_z, prototypes, weights, adjacency_rules):
        import math
        self.dims = (size_x, size_y, size_z)
        self.prototypes = prototypes
        self.weights = weights
        self.adjacency = adjacency_rules # dict: (proto, direction) -> set(allowed_neighbors)
        # Initialize full superposition
        self.grid = {}
        for x in range(size_x):
            for y in range(size_y):
                for z in range(size_z):
                    self.grid[(x, y, z)] = set(prototypes)
                    
    def compute_entropy(self, coord):
        import math
        domain = self.grid[coord]
        if len(domain) <= 1:
            return float('inf') # Already collapsed or invalid
        sum_w = sum(self.weights[t] for t in domain)
        sum_w_log_w = sum(self.weights[t] * math.log(self.weights[t]) for t in domain)
        return math.log(sum_w) - (sum_w_log_w / sum_w)
        
    def find_min_entropy_cell(self):
        min_entropy = float('inf')
        best_coord = None
        for coord in self.grid:
            h = self.compute_entropy(coord)
            if h < min_entropy:
                min_entropy = h
                best_coord = coord
        return best_coord
        
    def collapse_cell(self, coord):
        import random
        domain = list(self.grid[coord])
        weights = [self.weights[t] for t in domain]
        chosen = random.choices(domain, weights=weights, k=1)[0]
        self.grid[coord] = {chosen}
        return chosen

To eliminate seam artifacts between independently generated chunks, adjacent chunk boundary faces are locked as immutable boundary constraints prior to triggering internal wave collapse.

Wave function collapse 3d entropy minimization and constraint propagation


Wave function collapse 3d procedural generation rules architectural schematic and benchmark matrix

Technical Specifications & Parameter Matrix

ParameterRecommended SpecificationHard BoundProcedural Failure Mode
Voxel Prototype Count$40 - 120$ unique tilesMin $15$ prototypesRepetitive architecture or contradiction explosion
Propagation HorizonFull AC-3 closureClamped radius $R \ge 8$Delayed contradiction discovery causing deep backtrack
Backtrack Stack Depth$500$ state framesMax $2,000$ framesOut-of-memory crashes on dense constraint lattices
Entropy Noise JitterGaussian $\sigma = 10^{-4}$Unbiased tie-breakingAxis-aligned directional bias in world synthesis
Chunk Boundary Buffer$1$ voxel shared overlapStrict planar matchVisible gaps and misaligned sockets at chunk seams
Curated Inquiry Series • 10 Investigations

Wave Function Collapse & 3D Procedural Generation Constraints

An empirical exploration through constraint satisfaction, voxel Shannon entropy, backtracking repair, and GPU parallelized collapse shaders.

01 Wave Function Collapse Current Inquiry
9 min read
9 min read
9 min read
9 min read
9 min read
Primary Scholarly Provenance & Empirical Attribution
Gumin, M. (2016). WaveFunctionCollapse Algorithm . Open-source algorithmic specification.
Source Link
Merrell, P. (2007). Example-based Model Synthesis . ACM Transactions on Graphics (SIGGRAPH '07), 26(3), Article 105.
DOI: 10.1145/1276377.1276495
Mackworth, A. K. (1977). Consistency in networks of relations 90007-8). Artificial Intelligence, 8(1), 99–118.
DOI: 10.1016/0004-3702(77