How to Learn Wave Function Collapse: Local Constraints, Entropy, Observation, Propagation and Procedural Generation

Wait, What?

Wave Function Collapse sounds like quantum physics, but the practical algorithm is really a constraint-propagation system for generating structured patterns.

Wave Function Collapse (WFC), popularised by Maxim Gumin’s implementation, generates outputs that obey local compatibility rules learned from or supplied by an example. It is widely associated with procedural generation for tiles, textures, maps and game spaces.

The algorithm begins with many possible states at each output location. It repeatedly chooses a low-uncertainty location, selects one allowed state, and propagates the consequences to neighbouring locations. If a location is left with no valid states, the run has reached a contradiction.

At beginner level, WFC is a lesson about “possible choices shrinking as constraints spread.” At professional level, it becomes a study of model construction, local versus global consistency, entropy heuristics, propagation data structures, contradictions, restarts, backtracking, reproducibility and the limits of example-driven procedural generation.

Quick Answer

Learn WFC in this order: tiles and adjacency rules → domains of possible states → local constraints → propagation → minimum-entropy choice → weighted observation → contradiction → restart/backtracking → overlapping model → simple tiled model → symmetry → performance → validation → professional content-generation pipelines. Do not start with the quantum metaphor. Start with constraint satisfaction.

1. The simplest mental model: every cell has a set of possibilities

Imagine a 5×5 grid. Each cell may contain one of four tiles:

grass
road-straight
road-corner
water

Initially, every cell may allow all four. But adjacency rules restrict which tiles may touch.

If one cell becomes water and roads are not allowed directly beside water, those road possibilities must be removed from neighbouring cells. Those removals may force new removals further away.

That is constraint propagation.

2. “Collapse” means choosing one state from a remaining domain

A cell begins with several allowed states. Observation selects one state and removes the others.

After that decision, propagation updates neighbours so they retain only states compatible with the chosen result.

The algorithm alternates between choosing and propagating until:

• every location has one remaining state;
• or some location has zero remaining states, creating a contradiction.

3. It is not actually simulating quantum mechanics

The original project uses quantum-inspired language such as “wave,” “superposition,” “observation” and “collapse.” Gumin’s own documentation is explicit that the coefficients are ordinary real/boolean state information, not a physical quantum simulation.

The metaphor can be memorable, but it should not replace the computational model: WFC is a constrained generative search process.

4. Two important WFC models

The original project prominently uses two families:

• Overlapping model: extract small overlapping patterns from a sample image and require generated neighbourhoods to be locally compatible with those observed patterns.
• Simple tiled model: use an explicit set of tiles plus adjacency rules defining which tile orientations may touch.

They share the same observation-and-propagation idea but differ in how the states and compatibility rules are obtained.

5. The overlapping model learns local pattern vocabulary

Choose a pattern size such as N = 3. Slide a 3×3 window across the example image and collect distinct patterns, often with frequencies.

Two patterns are compatible at a relative offset when their overlapping pixels agree.

The output grid does not simply paste the source image. It assembles locally compatible patterns so that every generated neighbourhood belongs to the learned local vocabulary.

6. Local similarity is not global meaning

This is one of the most important limits.

A system can obey every local adjacency rule and still produce a globally undesirable result: a corridor that goes nowhere, a town with no reachable centre, a level with isolated regions, or a decorative pattern that is locally valid but compositionally poor.

WFC’s local constraints do not automatically encode global semantics.

7. The simple tiled model makes rules explicit

Instead of learning overlaps from an image, define tile states and legal neighbours directly.

For example:

road-horizontal may have road-horizontal or road-corner on left/right
road-horizontal may have grass above/below
water may touch water or shore
shore may connect water to grass

Rotations and reflections can produce additional tile states. Symmetry information can reduce the amount of rule data that must be written manually.

8. Entropy chooses where to decide next

If one cell allows only two possibilities while another allows twenty, the two-choice cell is more constrained. WFC commonly chooses a location with minimum non-zero entropy.

With equal weights, domain size is a rough uncertainty measure. With weighted patterns, Shannon-style entropy takes the pattern probabilities into account.

The heuristic is similar in spirit to the “most constrained variable” idea in constraint satisfaction: decide where options are already narrow.

9. Weighted observation controls frequency, not certainty

After choosing a location, select one of its remaining states, often randomly according to learned or declared weights.

If a pattern appeared frequently in the source example, giving it a larger weight can make outputs statistically resemble the source more closely.

But weights do not guarantee a target global frequency in one generated sample. They influence selection probabilities under changing constraints.

10. Propagation is the real engine

Suppose state A is removed from cell X. A neighbouring cell Y may contain a state that was supported only because A was available at X. That state must now be removed from Y.

Those removals may invalidate states in other neighbours, so the process continues until no more consequences remain.

An efficient implementation tracks only locations or state relationships affected by recent changes rather than rescanning the whole output after every observation.

11. Conceptual pseudocode

initialize every output location with all allowed states
propagate any pre-existing constraints

while unresolved locations remain:
    cell = unresolved cell with minimum entropy
    state = weighted_random_choice(cell.allowed_states)
    cell.allowed_states = {state}

    propagate removals through neighbours

    if any cell has zero allowed states:
        return CONTRADICTION

return generated_output

This is intentionally simplified. Real implementations differ in propagation representation, entropy updates, queue management, backtracking and failure policy.

12. Contradiction is a first-class outcome

A contradiction means at least one output location has no remaining valid state. The earlier choices and constraints have become mutually incompatible.

The original WFC project notes that contradictions can occur and that the underlying feasibility problem is computationally difficult in general. A production system therefore needs an explicit policy:

• restart with a different random seed;
• backtrack to an earlier decision;
• relax selected constraints;
• repair locally;
• reject the sample and generate another.

“It usually works” is not a failure-handling policy.

13. Backtracking changes the algorithmic character

Classic lightweight WFC implementations often restart after contradiction rather than maintaining a full search tree. Adding backtracking can reduce wasted complete restarts, but requires storing enough prior state to undo decisions and propagation safely.

This creates trade-offs in memory, implementation complexity and determinism.

Be explicit about whether your implementation is restart-based, backtracking, or hybrid.

14. Boundary conditions can dominate the result

Periodic output, fixed border tiles, pre-collapsed cells and forbidden edge states all change the solution space.

A tileset that generates well on a toroidal/periodic grid may fail when hard borders are introduced. Likewise, a model that works on small maps may contradict frequently at larger scales because global conflicts have more room to emerge.

Test boundary policy as part of the model, not as a cosmetic option.

15. Seeds matter for reproducibility

Weighted observation usually uses randomness. Record the random seed for every generated artefact used in testing or production review.

Without seeds, a rare contradiction or strange pattern may be impossible to reproduce. With seeds, generation becomes debuggable.

Professional procedural generation should log at least model version, seed, dimensions, constraint settings and outcome.

16. Model quality often matters more than clever search

If the source example contains accidental local relationships, the overlapping model can learn them. If a tile rule set is incomplete, generation may fail or become repetitive. If too many adjacencies are allowed, outputs may be valid but visually incoherent.

The algorithm cannot infer design intent that the representation never encoded.

Spend serious effort on pattern extraction, tile vocabulary, symmetry, weights and constraints.

17. Global constraints require extra machinery

Suppose a level must contain exactly one entrance and one exit connected by a traversable path. Local tile compatibility alone does not guarantee this.

You may need:

• pre-placed anchors;
• post-generation graph checks;
• global constraint propagation;
• hierarchical generation;
• repair passes;
• search/backtracking aware of global goals.

Recent WFC research continues exploring hierarchical and large-scale extensions precisely because local consistency alone is not enough for many production goals.

18. How to teach WFC from beginner to professional

Use a small tile set and make the shrinking domains visible before showing source code.

• Predict: collapse one cell and ask which neighbour states become impossible.
• Run: execute a tiny deterministic model with fixed seed.
• Investigate: trace domain removals and propagation order.
• Modify: add one adjacency rule or change one tile weight.
• Make: implement a small tiled model, then add contradiction handling and reproducible testing.

This sequence reflects programming-education research supporting code reading, tracing, worked examples and faded scaffolding before independent implementation.

19. A strong classroom exercise

Use four symbols on a 4×4 grid. Give each learner the same rule table and initial forced cell.

For every propagation step record:

cell changed | removed state | reason | neighbours affected

Then compare traces. Different propagation order may still reach the same fixed point before observation, which is a useful lesson about implementation order versus logical consequence.

20. Validation needs more than “looks good”

Visual inspection is useful but insufficient. Test measurable properties:

• every local adjacency is legal;
• all required anchors are present;
• forbidden patterns never appear;
• path connectivity holds when required;
• contradiction rate across seeds;
• generation time distribution;
• pattern-frequency drift from target weights;
• diversity across generated samples.

Separate hard validity constraints from aesthetic preferences.

21. Benchmark the failure distribution, not only successful runs

If 95 runs finish in 10 ms but five runs take repeated restarts and 10 seconds, the average can hide an operational problem.

Record percentiles, restart counts, contradiction locations and seeds. Large-scale content generation often cares more about tail behaviour than average speed.

22. Common implementation data structures

A practical implementation may maintain:

• a boolean or bitset domain for each output location;
• pattern weights and precomputed weight sums;
• compatibility tables by direction;
• a propagation stack or queue;
• per-state support counts;
• cached entropy values;
• random generator state;
• optional history for backtracking.

Bitsets can make state elimination and compatibility checks dramatically faster when the number of patterns fits the representation well.

23. WFC and AC-style consistency are related but not identical labels

The original project explicitly connects WFC to classical constraint-consistency work and notes use of AC-4-style propagation ideas. The exact implementation should be described precisely rather than saying “WFC is AC-4” as if the whole generator were only one consistency algorithm.

Observation, weighting, model extraction and contradiction policy are additional parts of the generative system.

24. Common failure states

• Explaining WFC as real quantum simulation.
• Assuming local validity guarantees global level quality.
• Ignoring contradictions because sample demos happen to succeed.
• Failing to record random seeds.
• Using incomplete adjacency rules.
• Allowing too many rules and then wondering why outputs lack structure.
• Comparing models only by one attractive screenshot.
• Changing tiles, weights and constraints simultaneously so the cause of improvement is unknowable.
• Benchmarking only successful runs.

25. Practice ladder

• Beginner: manually propagate tile possibilities on a 3×3 grid.
• Foundation: implement adjacency filtering with deterministic choices.
• Intermediate: add weighted entropy and seeded observation.
• Advanced: implement overlapping-pattern extraction, symmetry handling and contradiction statistics.
• Professional: build a versioned generation pipeline with global validation, reproducible seeds, failure telemetry, backtracking/restart experiments and workload-scale benchmarks.

26. Ownership boundary

This article owns Wave Function Collapse as a procedural constraint-generation algorithm: state domains, local compatibility, entropy selection, observation, propagation, contradictions and production validation. It does not replace general constraint programming, game design, global path planning, artistic direction, learner measurement or student-interface systems.

Sources and further reading

• Maxim Gumin, original WaveFunctionCollapse project and algorithm notes: GitHub repository.
• Hugo Scurti and Clark Verbrugge, “Generating Paths with WFC,” AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 2018: AAAI AIIDE.
• Michael Beukman et al., “Hierarchical WaveFunction Collapse,” AAAI AIIDE, 2023: AAAI AIIDE.
• María Beatriz Villar López and Miguel Chover, “Procedural Generation of 3D Maps with Wave Function Collapse: Optimization and Advanced Constraints,” Eurographics, 2025: Eurographics Digital Library.
• ACM/IEEE-CS/AAAI CS2023, Algorithmic Foundations: CS2023.
• Sue Sentance, Jane Waite and Maria Kallia, PRIMM programming pedagogy: SIGCSE 2019.

Professional rule: you understand Wave Function Collapse when you can distinguish the model from the search process, explain every state removal as a consequence of an explicit compatibility rule, reproduce failures from a seed, and prove that your final validation checks the global properties your application actually requires.