# Wave function collapse: an algorithm inspired by quantum mechanics

- Transfer

The Wave Function Collapse algorithm generates bitmaps that are locally similar to the input bitmap.

Local similarity means that

- (C1) Each NxN pixel pattern in the output must occur at least once in the input.
- (Weak C2 condition) The distribution of NxN patterns in the input data should be similar to the distribution of NxN patterns in a much larger number of output data sets. In other words, the probability of meeting a certain pattern in the output should be close to the density of such patterns in the input data.

In the examples, the standard value of N is 3.

The WaveFunctionCollapse (WFC) algorithm initializes the output bitmap as a completely unobservable state in which the value of each pixel is a superposition of the colors of the input bitmap (so if the input image is black and white, the unobservable states are displayed as different shades of gray). The coefficients of these superpositions are real, not imaginary numbers, so the real quantum mechanics is not used in the algorithm, rather, it was inspired by it. The program then goes into a watch-propagation cycle:

- At each stage of the observation, the NxN region with the lowest Shannon entropy is selected from the unobserved space. The state of this area then collapses to a state of certainty in accordance with the coefficients and distribution of NxN patterns in the incoming data.
- At each stage of distribution, the new information obtained during the collapse of the previous stage is distributed according to the output data.

At each stage, the total entropy decreases, and in the end we get a fully observable state, the collapse of the wave function is completed.

It may happen that during the distribution process all coefficients for a certain pixel become zero. This means that the algorithm came to a contradiction and can not be executed further. The task of determining whether a given bitmap provides other nontrivial bitmaps that satisfy condition (C1) is NP-hard, so it’s impossible to create a quick solution that always completes the algorithm. However, in practice, the algorithm encounters contradictions surprisingly rarely.

The wave function collapse algorithm is implemented in C ++ , Python , Kotlin ,Rust , Julia , Haxe , JavaScript and adapted to Unity . Official executables can be downloaded from itch.io or run in a browser . WFC generates levels Bad North , Caves of Qud , several more minor games, as well as many prototypes. His creation led to a new study . Other related work , explanations , interactive demos , tutorials , tutorials andFor examples, see the section on ports, forks and spin-offs .

Watch a demonstration of the WFC algorithm on YouTube: https://youtu.be/DOQTr2Xmlz0

## Algorithm

- Count the incoming bitmap and count the number of NxN patterns.
- (optional) Complete the patterns with rotated and mirrored patterns.

- Create an array with the size of the output (in the source called "wave"). Each element of this array indicates the state of a region with a size of NxN in the output. The state of the NxN region is a superposition of the NxN patterns of incoming data with Boolean coefficients (that is, the state of a pixel in the output data is a superposition of incoming colors with real coefficients). The False coefficient means that the corresponding pattern is not allowed, the true coefficient means that the corresponding pattern is not yet prohibited.
- Initialize a wave in a completely unobservable state, that is, where all Boolean coefficients are true.
- Repeat the following steps:
- Observation:
- Find the wave element with the minimum non-zero entropy. If there are no such elements (if all elements have entropy zero or indefinite), then complete the cycle (4) and go to step (5).
- Collapse this element into a state of certainty in accordance with its coefficients and the distribution of NxN patterns of incoming data.

- Propagation: disseminate information obtained in the previous step of observation.

- Observation:
- By this time, all the elements of the wave either have a fully observable state (all coefficients, except one, are equal to zero) or are in a state of contradiction (all coefficients are zero). In the first case, return the output. In the second case, complete the work without returning anything.

## Generation of tile cards

The simplest nontrivial case of the algorithm is the pattern NxN = 1x2 (more precisely, NxM). If we simplify it even more, saving not the probabilities of pairs of colors, but the probabilities of the colors themselves, then we get what is called the “simple tile model”. The propagation phase in this model is simply the propagation of the neighborhood dependency. It is convenient to initialize a simple tile model with a list of tiles and data about their neighborhood (data about the neighborhood can be viewed as a large number of very small samples), rather than with a sampled bitmap.

Gif | GIFV

Lists of all possible pairs of adjacent tiles in practical tilesets can be long enough, so in order to shorten the enumeration, I implemented a symmetry system for tiles. In this system, each tile must be assigned its type of symmetry.

Notice that tiles have the same symmetry as the letters assigned to them (in other words, the actions of the dihedral group D4 are isometric for tiles and corresponding letters). Thanks to this system, it is enough to list the pairs of neighboring tiles only up to their symmetry, shortens the list of neighbors for tilesets with a set of symmetric tiles several times (even in the Summer relief tileset, although the drawings are not symmetrical, the system considers such tiles symmetrical).

Note that an unlimited tileset from nodes (in which all 5 tiles are valid) is not interesting for the WFC algorithm, because you cannot get into a situation where it is impossible to place a tile. We call tilesets with this property “simple”. Without complex heuristics, simple tilesets do not create interesting global structures, because correlations in simple tilesets decrease rapidly from a distance. A number of simple tiles can be found on cr31 . Take a look at the Dual Dual Tileset. How can he create nodes (without T-shaped connections, that is, uneasy) while being simple? The answer is that it can only generate a narrow type of nodes and cannot create an arbitrary node.

It is also worth noting that Circuit, Summer and Rooms tile are not Van tiles. That is, the data of their neighborhood can not be generated from the colors of the edges. For example, in the Circuit tile, two corners (Corner) cannot be adjacent, although they can be connected by a tile (Connection), and diagonal tracks cannot change directions.

## Higher dimensions

The WFC algorithm in higher dimensions works in exactly the same way as in two dimensions, however, performance becomes a problem here. These voxel models were generated with N = 2 in the tile model with overlapping using 5x5x5 and 5x5x2 blocks and additional heuristics (heights, density, curvature ...).

Screenshots of higher dimensions: 1 , 2 , 3 .

The voxel models generated using the WFC and other algorithms will be in a separate repository.

## Restriction Synthesis

WFC algorithm supports restrictions. Therefore, it can be easily combined with other generative algorithms or manually created.

Here's how the WFC automatically completes a person-initiated level:

GIF | GIFV

Algorithm ConvChainsatisfies the strict version of the condition (C2): the distribution of the NxN pattern limits in the output data created by it is exactly the same as the pattern distribution in the input data. However, ConvChain does not satisfy (C1): it often creates noticeable artifacts. It is logical to run ConvChain first to get a well-sampled configuration, and then the WFC to correct local artifacts. This is similar to the strategy common in optimization: first, we perform the Monte Carlo method to find the point. close to the global optimum, and then perform gradient descent from this point for greater accuracy. Texture Synthesis

AlgorithmPF Harrison is much faster than the WFC, but he has problems with long correlations (for example, it is difficult for this algorithm to synthesize the textures of brick walls with properly aligned bricks). It is in such cases that the WFC demonstrates its superiority, and the Harrison algorithm supports the constraints. It makes sense to first generate with WFC an ideal brick wall scheme, and then execute an algorithm for limited texture synthesis for this scheme.

## Comments

Why is the minimum entropy heuristics used? I noticed that when people draw something, they often follow the minimal entropy heuristics themselves. That is why the algorithm is so interesting to watch.

A model with overlap correlates with a simple model in the same way that high-order Markov chains correspond to first-order Markov chains.

It is necessary to take into account that the entropy of any node cannot increase at the stage of distribution, i.e. probabilities do not increase, but can be reset to zero. When the propagation stage cannot further reduce the entropy, we will activate the observation phase. If the observation stage cannot reduce the entropy, it means that the algorithm has finished its work.

The propagation stage in the WFC algorithm is very similar to the cyclic message transfer algorithm (loopy belief propagation algorithm). In fact, I initially programmed the belief propagation (BP), but then I switched to propagation with constraints with the stationary distribution preserved, because BP is much slower without massive parallelization (in the CPU) and it did not create significantly better results for my tasks.

Note that the “Simple Knot” and “Trick Knot” samples are not 2, but 3 colors.

Time can be one of the measurements. In particular, d-dimensional WFC displays the behavior of any (d-1) -dimensional cellular automaton.

## Reference materials

This project is based on the work of Paul Merrell on the synthesis of models, in particular, on the chapter on the discrete synthesis of models from his dissertation . Gender extends neighborhood constraints in what we have called a simple tile model, with a heuristic seeking to calculate distribution in a small moving area.

Also, my project was strongly influenced by a chapter on declarative texture synthesis from the thesis of Paul F. Harrison . The floor sets the data about the neighborhood of tiles, marking their borders and using search in return to fill the tile map.

## Assembly

WFC is a console application that depends only on the standard library. Download .NET Core for Windows, Linux or macOS and follow.

dotnet run WaveFunctionCollapse.csproj

Or you can use the build community instructions for different platforms in the appropriate issue . Casey Marshall created a pull request that simplifies the use of the program with the command line and includes the snap package.

## Interesting ports, forks and spin-offs

- Emil Ernerfeld created a port in C ++ .
- Max Eller created the Kotlin (JVM) library called Kollapse . Joseph Roskopf created a line-by- port on the Kotlin optimized version of the 2018 algorithm. Edwin Jacobs created another Kotlin library .
- Kevin Chapeller created a javascript port .
- Oscar Stalberg has programmed a three-dimensional tile model, a two-dimensional tile model for irregular grids in a sphere. Here are beautiful 3D tilesets for them: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 .
- Joseph Parker adapted WFC for Unity and used it to generate skateparks in the 2016 Proc Skater game , a fantastic plateau in the 2017 Swapland game and platform levels in the 2018 Bug with a Gun game .
- Martin O'Leary applied a WFC-like algorithm to generate poetry: 1 , 2 , 3 , 4 .
- Nick Nenov created a three-dimensional voxel tileset based on my castle tileset. Nick uses the textual data output option in a tile model to recreate 3D models in Cinema 4D.
- Sean Lefler implemented a model with an overlap on Rust .
- rid5x creates a WFC version on OCaml .
- I published a simple three-dimensional tile model so that people could create their own 3D tile sets without waiting for the full repository of the three-dimensional algorithm.
- I created an interactive model of the model with overlapping. Executable file with a GUI can be downloaded WFC page on itch.io .
- Brian Bachlyu has assembled a level generation pipeline for the game Caves of Qud , in several passages of which WFC is used: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 .
- Danny Uyna implemented a three-dimensional tile model .
- Arvi Tekari has programmed a texture synthesis algorithm with entropy heuristics on Lua. Headchant ported it to work with LÖVE.
- Isaac Kert created an overlapping Python model port .
- Oscar Stalberg created an interactive version of the tile model that runs in the browser.
- Matt Rix implemented a three-dimensional tile model ( 1 , 2 , 3 , 4 ) and created a three-dimensional tile model in which one of the dimensions is time ( 1 , 2 , 3 , 4 , 5 ).
- Nick Nenov created a visual guide on the system of symmetry of tiles.
- Isaac Kert and Adam M. Smith wrote a research paper in which they formulate the WFC as an ASP task, use the generic common constraint resolver clingo to generate bitmaps, experiment with global constraints, trace the history of the WFC, and give a detailed description of the algorithm.
- Silvan Lefevre created a C ++ implementation of the synthesis of three-dimensional models, described the thinking process of creating a sample, and set an example in which the neighborhood constraints ensure that the output data is connected (they can be circumvented).
- I summarized the three-dimensional WFC, so that he worked with the symmetry group of the cube and created a tileset that generates scenes in the spirit of Escher .
- There are many ways to visualize partially observed wave states. In the code, the color values of the possible variants are averaged to obtain the final color. Oscar Stalberg shows partially observable states as translucent rectangles: the more options, the larger the rectangle. In the voxel scheme, I visualize the wave states by pixel-by-pixel voting.
- Remy Devo implemented the TIC model in PICO-8 and wrote an article on generating coherent data with an explanation to the WFC.
- For his game Bad North, Oscar Stalberg uses heuristics, which tries to select such secrets so that at each stage the resulting observed zone is passable.
- William Manning implemented the C # overlapping model; first of all, he wanted to make the code readable, and added a graphical interface to WPF.
- Joseph Parker wrote a WFC tutorial for Procjam 2017.
- Aman Tiwari formulated connection restriction as an ASP task for clingo.
- MatveyK has programmed a three-dimensional model with overlap .
- Silvan Lefevre , Lee Yu Wei and Connelly Barnes are exploring the possibility of hiding information inside textures. They created a tool to encode text messages as WFC tiles and decode them back. This technique allows you to use WFC tiles as QR codes.
- Mathieu Fer and Nathaniel Curan have significantly improved the WFC runtime, for the overlapped model - an order of magnitude. I integrated their enhancements into the code.
- Vasu Mahesh has ported a three-dimensional tile model in TypeScript, created a new tileset and visualized the generation process in WebGL.
- Kim Huanghi experimented with three-dimensional WFC and created / adapted many voxel tile sets: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 .
- Oscar Stalberg delivered a report on the generation of levels in Bad North at the Everything Procedural Conference 2018.
- I wrote about how to generate (approximately) undistorted paths between two points using the WFC and other algorithms.
- Ayzer Kert and Adam M. Smith published a preprint that describes a WFC-based system that learns from positive and negative examples, and talked about it in the general context of dialogues with example-based generators.
- Brendan Anthony uses the WFC to generate wall decorations in the game Rodina .
- Tim Kong implemented the overlap model on Haxe .
- For the generation of connected structures, Boris the Brave applied the chiseling method to the WFC . He published a library that supports hexagonal grids, additional restrictions, and a reversion.
- Marian Kleineberg created a city generator for Procjam 2018 based on a tile model. He wrote an article describing his approaches to setting a neighborhood, going back and online variations of the WFC.
- Sol Bekich has programmed the PyopenCL tile model running on the GPU. Instead of storing a queue of nodes from which to propagate, this model runs in parallel from each grid node.
- Wouter van Oortmerssen implemented a tile model in a single C ++ function with a structure to speed up the observation, similar to the priority queue.
- Robert Hoenig implemented the Julia overlap model with the option of distributing constraints only locally.
- Edwin Jacobs applied the WFC to style shifting and dithering .

## Thanks

Some examples are from Ultima IV and Dungeon Crawl . Taylset Circles taken from Mario Klingemann . The idea of generating integrated circuits was proposed by Moonasaur , and their style was taken from the game Ruckingenur II of Zachtronics. The Cat overlap example is taken from the Nyan Cat video, the Qud example was created by Brian Buckley , Magic Office + Spirals - rid5x examples, the Overlaid Examples Colored City + Link + Link 2 + Mazelike + Red Dot + Smile City - Arvi Tekari. Summer Tailset was created by Hermann Hillmann. Voxel models are rendered in MagicaVoxel .