What does the 'top tile on the deck' constraint do in the process?

The top tile constraint forces tiles to be drawn in a predetermined order. The wave function is conditioned on the current top tile, so neighboring cells' possibilities are limited accordingly, and the deck state becomes entangled with the grid state.

How is entropy used to decide which cell to collapse next?

Entropy measures how surprising the outcome would be if a particular cell were resolved. In practice, you collapse the cell with the lowest entropy (fewest possibilities) to minimize future conflicts and holes in the map.

How can you encourage longer roads with the wave function?

By weighting the wave function to favor options that extend existing roads (and longer roads) over creating new short or isolated features, you bias the collapse toward more connected and aesthetically pleasing results.

What does combining road and city wave functions look like in practice?

You can compose separate wave functions for roads and for cities, then prioritize one (e.g., cities) while still allowing the other (roads) to influence placement. This yields maps with more coherent networks and prominent cities.

Where can I find the code or more resources to experiment?

The code is publicly available on GitHub, and the creator mentions sharing a link in the description. You can clone or study the implementation to run your own simulations and define custom wave functions and entropy functions.

Procedural Generation in Games - Computerphile

Computerphile

Education4 min read36 min video

Dec 11, 2025|59,825 views|2,463|172

computers computerphile computer science

Save to Pod

Key Moments

TL;DR

WFC maps: big, connected maps from simple local rules using entropy.

Key Insights

WFC turns local constraints into global map structure.

Cells hold multiple tile possibilities until observed.

Entropy guides collapse to minimize holes and maintain coherence.

Deck top tile introduces entanglement with the map.

Weights and multi-function wave combos encourage longer roads and bigger cities.

Shannon entropy refines probabilities for realistic layouts.

INTRODUCTION TO PROCEDURAL GENERATION

Procedural generation creates complex outcomes from simple rules. The video uses Carcasson as a practical playground to show how tiny, local decisions—matching roads and cities as tiles are placed—can scale up into large, interconnected maps. The Wave Function Collapse (WFC) idea is introduced as a compact, physics-inspired framework for this behavior: each grid cell holds a set of possible tiles, and the global map evolves when those local choices collide with neighbors. In this view, huge worlds emerge from small interactions.

THE WAVE FUNCTION COLLAPSE IDEA

Wave Function Collapse (WFC) treats a map as a collection of cells, each with a wave function listing all tiles that could fit given the current state. When you observe a cell, you select one possibility and propagate its effects to adjacent cells, reducing their options. Repeating this observation across the grid gradually collapses the sea of possibilities into a single, consistent arrangement. The analogy to quantum superposition helps convey why uncertainty matters in generation.

CARCASSON AS A PROOF-OF-CONCEPT

Carcasson provides a tangible testbed: you draw tiles from a deck and place them so features align (roads, cities) and you score for long roads or large cities. The video uses this setting to illustrate how a WFC-like process can automate map-building while preserving the game's rules. Unlike manual placement, the system evolves, offering many layouts that respect the deck order, orientation, and feature interactions, producing surprisingly varied yet familiar board states.

CELLS, WAVE FUNCTIONS, AND NEIGHBOR CONSTRAINTS

Each cell carries a wave function—the set of tiles that could occupy it given the already placed neighbors. Constraints are directional: roads must align with neighboring roads, cities with adjacent cities, and so on. This local dependency means a single collapse can prune many distant options, creating a chain reaction that shapes the entire map. The result is that small decisions propagate into cohesive network structures.

DECK-STATE ENTANGLEMENT AND ITS EFFECTS

To mimic a real game, the top tile of the deck restricts what you may place next, entangling deck state with the grid. The wave function is extended to condition on the current top tile, so a cell’s allowable options depend on what has just been drawn. As tiles are drawn (including monasteries or shields), new constraints appear and the map begins to reflect both the deck and the spatial rules.

OBSERVATION, PROPAGATION, AND HOLE PREVENTION

After selecting a tile for a chosen cell, the algorithm propagates its implications to neighbors, reducing their options. This continues until no cell has multiple possibilities. Collapsing the fewest-option cell first minimizes the chance of creating disconnected holes, and helps steer the map toward longer roads and larger towns. The dynamic visualization shows how a finished Carcasson board emerges from successive, constrained observations.

WEIGHTING ROAD AND CITY OPTIONS

Beyond neutral constraints, the system uses weights to push outcomes toward desirable features. A tile that continues a road or expands an existing city can be given higher probability, biasing the collapse toward coherent continuations. Weights are applied within the wave functions, so they alter the likelihood of specific tiles while preserving the core WFC mechanics.

COMPOSING ROAD AND CITY WAVE FUNCTIONS

The simulation combines separate wave functions for roads and cities and then resolves them with priority rules—often giving cities precedence to create urban cores, while still allowing roads to stretch across the board. This composition yields maps with connected networks and prominent centers, resembling deliberate human planning rather than random assembly, yet still resulting from local, rule-based decisions.

SHANNON ENTROPY AND PRACTICAL IMPACT

Entropy here is refined with Shannon's formula, using normalized tile weights to compute probabilities. The minus sum p log p measure captures how surprising a collapse would be. Cells with many unlikely options have high entropy; those with a single likely option have near-zero entropy. This formulation explains why certain paths emerge and others are suppressed, guiding the collapse toward meaningful patterns like long roads and big cities.

TWEAKING THE MODEL: MAX VS MIN ENTROPY AND VARIANTS

Experimentation can explore different collapse strategies, such as always choosing the maximum entropy cell or tweaking the weight balance between roads and cities. Orientation and special tiles (monasteries, shields) can be added with their own rules and scoring. The talk even demonstrates running the model with an endless deck to simulate very large maps, highlighting how policy choices alter the resulting landscapes.

LARGE-SCALE MAPS AND INFINITE DECKS

With an expansive board and many tiles, the map develops longer roads and more expansive cities, and the process becomes slower but visually striking in real time. An infinite deck setup emphasizes the scalability of WFC: constraints propagate across a wide canvas, revealing emergent structures and patterns that resemble a living, evolving world rather than a static construction.

TAKEAWAYS, CODE ACCESS, AND FUTURE WORK

The core takeaway is that simple, local rules, when combined with thoughtful measures of constraint and preference, can generate rich, interconnected game content. The author shares a public GitHub implementation and invites readers to define their own wave functions and entropy functions. The message is to explore, iterate, and enjoy how physics-inspired ideas can shape creative design in procedural generation.

Mentioned in This Episode

●Tools & Products

●People Referenced

Wave Function Collapse for Carcasson (dos and don'ts)

Practical takeaways from this episode

Do This

Collapse the cell with the fewest possibilities (lowest entropy) to reduce holes.

Use the top tile from the deck as part of the local constraint set.

Weigh options to favor continuing existing roads/cities over creating new separate branches.

Consider composing road and city wave functions to encourage connected features.

Experiment with different entropy definitions (e.g., Shannon entropy) and observe resulting map styles.

Avoid This

Ignore adjacency constraints between neighboring tiles; you’ll get inconsistent maps.

End roads or cities in ways that create many isolated fragments or holes.

Common Questions

Wave function collapse treats each map cell as a superposition of possible tile states. You observe (collapse) one cell to a concrete tile, then propagate constraints to neighboring cells. This yields a self-consistent map as the grid resolves, mirroring the idea of selecting outcomes from a probabilistic wave function.