📜 ⬆️ ⬇️

Wave function collapse: an algorithm inspired by quantum mechanics

image

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

Local similarity means that






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, 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 for Unity . Official executables can be downloaded from itch.io or run in a browser . WFC generates levels in Bad North , Caves of Qud , several smaller games, as well as in a variety of prototypes. His creation led to a new study . For other related works , explanations , interactive demos , tutorials , tutorials and examples, see the section on ports, forks and spin-offs .

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

Algorithm


  1. Count the incoming bitmap and count the number of NxN patterns.
    1. (optional) Complete the patterns with rotated and mirrored patterns.
  2. 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.
  3. Initialize a wave in a completely unobservable state, that is, where all Boolean coefficients are true.
  4. Repeat the following steps:
    1. Observation:
      1. 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).
      2. Collapse this element into a state of certainty in accordance with its coefficients and the distribution of NxN patterns of incoming data.
    2. Propagation: disseminate information obtained in the previous step of observation.
  5. By this time, all 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 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

The ConvChain algorithm satisfies the strict version of the condition (C2): the distribution of the NxN pattern limits it creates in the output 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.

PF Harrison’s texture synthesis algorithm is much faster than WFC, but he has problems with long correlations (for example, it’s difficult to synthesize brick wall textures 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 . Paul extends the 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

Alternatively, you can use the build 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



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 .


Source: https://habr.com/ru/post/437604/

More articles: