Wave Function Collapse for Level Generation

Define Your Tileset and Adjacency Rules

The quality of WFC output depends entirely on the quality of the input: the tileset and the adjacency rules that govern how tiles connect.

In the simple tiled model, you explicitly define a set of tiles and the rules for which tiles can appear next to each other on each edge. Each tile has four edges (in a 2D grid: north, south, east, west), and each edge has a label or socket type. Two tiles can be placed adjacent to each other only if their touching edges have compatible socket types. For example, a "grass" tile might have "grass" sockets on all four edges, while a "path-horizontal" tile has "path" sockets on east and west and "grass" sockets on north and south. This ensures paths only connect to other path tiles at path edges.

Socket design is the most important creative decision in WFC level generation. Well-designed sockets produce output that tiles naturally and avoids visual glitches. Each distinct edge pattern in your tileset needs its own socket type. Symmetric tiles (like a plain grass tile that looks the same on all edges) simplify socket design, while asymmetric tiles (like corner pieces or T-junctions) require careful attention to rotational variants.

Tile rotation and reflection multiply the effective tileset size. A single corner tile, when rotated to all four orientations, becomes four distinct tiles in the WFC solver. Most implementations handle rotation automatically, generating rotated variants from a base tileset and computing their socket connections by rotating the original socket assignments.

In the overlapping model, you provide a sample image and specify a pattern size (typically 2x2 or 3x3 pixels). The algorithm scans the sample with a sliding window, extracting every unique pattern and recording which patterns appear adjacent to each other in the sample. These extracted patterns and adjacency statistics become the tileset and rules automatically, requiring no manual socket design. The overlapping model is ideal for pixel art generation and texture synthesis where manual rule specification would be impractical.

Initialize the Output Grid

The output grid has the dimensions you want for your generated level. Each cell in the grid starts in a superposition state, meaning it could potentially become any tile in the tileset. Internally, each cell maintains a set of all tiles that are still valid options for that position.

The entropy of each cell is a measure of how many options remain. A cell that could be any of 20 tiles has high entropy. A cell that has been narrowed down to 3 possible tiles has low entropy. A cell that has been collapsed to a single tile has zero entropy, and it is considered resolved.

Some implementations pre-constrain certain cells before generation begins. For example, you might fix the border cells of the grid to a specific tile type (like walls) to ensure the generated level has a clean boundary. Or you might fix the player's spawn point to a specific walkable tile. These pre-set cells act as anchor points that guide the generation, and their constraints propagate outward to influence the surrounding cells before the main generation loop begins.

Weight initialization assigns a frequency weight to each tile based on how often you want it to appear in the output. A tile with weight 10 is ten times more likely to be selected than a tile with weight 1 when a cell is collapsed. In the overlapping model, weights come directly from the frequency of each pattern in the sample image. In the simple tiled model, you set weights manually to control the density of different tile types.

Observe the Lowest-Entropy Cell

The main generation loop starts by selecting the unresolved cell with the lowest entropy, meaning the cell with the fewest remaining valid tile options. This heuristic, borrowed from constraint satisfaction problem solvers, tends to make the best use of available information by resolving the most constrained cells first.

When multiple cells share the same lowest entropy, the algorithm selects among them randomly, often with a small noise factor added to the entropy calculation to prevent bias toward grid-order processing. This noise ensures that the generation does not always proceed in a predictable pattern (like left-to-right, top-to-bottom), which would produce visible directional artifacts in the output.

Collapsing the selected cell means choosing one tile from its remaining valid options and discarding all others. The choice is made randomly, weighted by the tile frequencies. A common grass tile with weight 10 is much more likely to be selected than a rare treasure chest tile with weight 1. This weighted selection ensures the output has a natural distribution of common and rare elements without requiring explicit placement logic.

The observation step is where randomness enters the algorithm. The seed for the random number generator determines which specific tiles are selected at each observation, which means the same seed always produces the same output. This seed-based determinism is essential for reproducible generation and seed sharing.

Propagate Constraints to Neighbors

After collapsing a cell to a single tile, the algorithm must update all neighboring cells to reflect the new constraint. If the collapsed cell is now a "path going east" tile, then the cell to its east must have a tile with a west edge compatible with a path connection. Any tiles in the eastern neighbor's option set that do not have a compatible west edge are removed.

Propagation cascades through the grid. When a neighbor loses some of its options, its other neighbors may also need updating, because some of their options might have been valid only because of the now-removed options. The algorithm uses a propagation queue (similar to a BFS queue) to process these cascading updates efficiently. Each cell whose option set changes is added to the queue, and the algorithm continues until the queue is empty, meaning no more changes need to propagate.

Arc consistency is the formal name for the constraint propagation technique used in WFC. The algorithm enforces that for every remaining option in a cell, there exists at least one compatible option in each neighboring cell. This is known as AC-3 in constraint satisfaction literature. The propagation step is the most computationally expensive part of WFC, especially for large grids with many tile types, but efficient implementations using bitmask representations can process thousands of cells per millisecond.

The propagation step is what gives WFC its characteristic behavior of influencing distant cells from a single observation. A tile placed in one corner of the grid can cascade constraints across the entire grid, potentially resolving cells on the opposite side. This long-range influence is both a strength (producing globally coherent output) and a potential source of contradictions (a bad early choice can eliminate all valid options for a distant cell).

Handle Contradictions

A contradiction occurs when propagation empties a cell's option set entirely, meaning no valid tile can be placed there given the current state of the grid. Contradictions happen when the choices made during observation create an impossible situation where the adjacency rules cannot be simultaneously satisfied for all cells.

The simplest response to a contradiction is to restart the entire generation from scratch with a different random seed or random choices. For small grids and well-designed tilesets, contradictions are rare enough that restarts are fast and infrequent. Many practical implementations use this restart approach because of its simplicity.

Backtracking offers a more sophisticated solution. When a contradiction is detected, the algorithm reverts to a saved state from before the most recent observation, removes the tile that led to the contradiction from the options, and tries a different tile. This can be implemented with a stack of grid states (snapshots saved before each observation) and is equivalent to depth-first search with constraint propagation. Backtracking avoids restarting from scratch but requires more memory for the state history and more complex implementation logic.

Tileset design is the most effective way to prevent contradictions. Tilesets where every tile has at least one compatible neighbor on every edge in every situation will never produce contradictions. Adding "wildcard" tiles that can connect to any edge type provides fallback options that prevent the algorithm from painting itself into a corner. Testing the tileset exhaustively before using it in production, by running thousands of generations and checking for contradiction rates, identifies problematic tile combinations early.

For game applications where generation must complete within a frame budget, a hybrid approach works well: run WFC with a maximum iteration count, and if a contradiction occurs or the iteration budget is exceeded, fall back to a simpler generation algorithm (like random placement with manual cleanup) to ensure the player always receives a valid level.