Procedural Generation with Wave Function Collapse

a day ago

Copy Link

Wave Function Collapse (WFC) is a procedural generation algorithm that arranges tiles based on adjacency rules and frequency hints.
The algorithm maintains a probability distribution of tiles for each pixel and collapses pixels iteratively to generate the output image.
WFC is inspired by quantum physics and the Model Synthesis algorithm.
The algorithm consists of two main parts: the core solver and the image processor.
The core solver arranges tiles into a grid according to adjacency rules and frequency hints.
Adjacency rules define which tiles can appear next to each other in each direction.
Frequency hints determine the relative likelihood of each tile appearing in the output.
The image processor generates adjacency rules and frequency hints from an input image.
Tiles can include rotations and reflections to increase variety in the output.
The core algorithm uses entropy to choose which cell to collapse next, minimizing contradictions.
Propagation ensures that the adjacency rules are respected by eliminating incompatible tile choices.
Contradictions (cells with no valid tile choices) can occur, and the algorithm may need to restart.
The algorithm can be visualized and debugged using tools like the animate example in the Rust implementation.
Further reading includes the original WFC repository, fast-wfc, and Model Synthesis resources.

Hasty Briefsbeta