/WaveFunctionCollapse

Bitmap & tilemap generation from a single example with the help of ideas from quantum mechanics

Primary LanguageC#OtherNOASSERTION

WaveFunctionCollapse

This program generates bitmaps that are locally similar to the input bitmap.

main collage

main gif

Local similarity means that

  • (C1) Each NxN pattern of pixels in the output should occur at least once in the input.
  • (Weak C2) Distribution of NxN patterns in the input should be similar to the distribution of NxN patterns over a sufficiently large number of outputs. In other words, probability to meet a particular pattern in the output should be close to the density of such patterns in the input.

In the examples a typical value of N is 3.

local similarity

WFC initializes output bitmap in a completely unobserved state, where each pixel value is in superposition of colors of the input bitmap (so if the input was black & white then the unobserved states are shown in different shades of grey). The coefficients in these superpositions are real numbers, not complex numbers, so it doesn't do the actual quantum mechanics, but it was inspired by QM. Then the program goes into the observation-propagation cycle:

  • On each observation step an NxN region is chosen among the unobserved which has the lowest Shannon entropy. This region's state then collapses into a definite state according to its coefficients and the distribution of NxN patterns in the input.
  • On each propagation step new information gained from the collapse on the previous step propagates through the output.

On each step the number of non-zero coefficients decreases and in the end we have a completely observed state, the wave function has collapsed.

It may happen that during propagation all the coefficients for a certain pixel become zero. That means that the algorithm has run into a contradiction and can not continue. The problem of determining whether a certain bitmap allows other nontrivial bitmaps satisfying condition (C1) is NP-hard, so it's impossible to create a fast solution that always finishes. In practice, however, the algorithm runs into contradictions surprisingly rarely.

Wave Function Collapse algorithm has been implemented in C++, Python, Kotlin, Rust, Julia, Go, Haxe, Java, Clojure, JavaScript and adapted to Unity and Houdini. You can download official executables from itch.io or run it in the browser. WFC generates levels in Bad North, Caves of Qud, Dead Static Drive, Townscaper, several smaller games and many prototypes. It led to new research. For more related work, explanations, interactive demos, guides, tutorials and examples see the ports, forks and spinoffs section.

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

Algorithm

  1. Read the input bitmap and count NxN patterns.
    1. (optional) Augment pattern data with rotations and reflections.
  2. Create an array with the dimensions of the output (called "wave" in the source). Each element of this array represents a state of an NxN region in the output. A state of an NxN region is a superposition of NxN patterns of the input with boolean coefficients (so a state of a pixel in the output is a superposition of input colors with real coefficients). False coefficient means that the corresponding pattern is forbidden, true coefficient means that the corresponding pattern is not yet forbidden.
  3. Initialize the wave in the completely unobserved state, i.e. with all the boolean coefficients being true.
  4. Repeat the following steps:
    1. Observation:
      1. Find a wave element with the minimal nonzero entropy. If there is no such elements (if all elements have zero or undefined entropy) then break the cycle (4) and go to step (5).
      2. Collapse this element into a definite state according to its coefficients and the distribution of NxN patterns in the input.
    2. Propagation: propagate information gained on the previous observation step.
  5. By now all the wave elements are either in a completely observed state (all the coefficients except one being zero) or in the contradictory state (all the coefficients being zero). In the first case return the output. In the second case finish the work without returning anything.

Tilemap generation

The simplest nontrivial case of the algorithm is when NxN=1x2 (well, NxM). If we simplify it even further by storing not the probabilities of pairs of colors but the probabilities of colors themselves, we get what we call a "simple tiled model". The propagation phase in this model is just adjacency constraint propagation. It's convenient to initialize the simple tiled model with a list of tiles and their adjacency data (adjacency data can be viewed as a large set of very small samples) rather than a sample bitmap.

GIF | GIFV

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

symmetries

Note that the tiles have the same symmetry type as their assigned letters (or, in other words, actions of the dihedral group D4 are isomorphic for tiles and their corresponding letters). With this system it's enough to enumerate pairs of adjacent tiles only up to symmetry, which makes lists of adjacencies for tilesets with many symmetrical tiles (even the summer tileset, despite drawings not being symmetrical the system considers such tiles to be symmetrical) several times shorter.

knots tiled rooms circuit 1 circuit 2 circles castle summer 1 summer 2

Note that the unrestrained knot tileset (with all 5 tiles being allowed) is not interesting for WFC, because you can't run into a situation where you can't place a tile. We call tilesets with this property "easy". Without special heuristics easy tilesets don't produce interesting global arrangements, because correlations of tiles in easy tilesets quickly fall off with a distance. Many easy tilesets can be found on cr31's site. Consider the "Dual" 2-edge tileset there. How can it generate knots (without t-junctions, not easy) while being easy? The answer is, it can only generate a narrow class of knots, it can't produce an arbitrary knot.

Note also that Circuit, Summer and Rooms tilesets are non-Wang. That is, their adjacency data cannot be induced from edge coloring. For example, in Circuit two Corners cannot be adjacent, yet they can be connected with a Connection tile, and diagonal tracks cannot change direction.

Higher dimensions

WFC algorithm in higher dimensions works completely the same way as in dimension 2, though performance becomes an issue. These voxel models were generated with N=2 overlapping tiled model using 5x5x5 and 5x5x2 blocks and additional heuristics (height, density, curvature, ...).

voxels

Higher resolution screenshots: 1, 2, 3.

Voxel models generated with WFC and other algorithms will be in a separate repo.

Constrained synthesis

WFC algorithm supports constraints. Therefore, it can be easily combined with other generative algorithms or with manual creation.

Here is WFC autocompleting a level started by a human:

GIF | GIFV

ConvChain algorithm satisfies the strong version of the condition (C2): the limit distribution of NxN patterns in the outputs it is producing is exactly the same as the distributions of patterns in the input. However, ConvChain doesn't satisfy (C1): it often produces noticeable defects. It makes sense to run ConvChain first to get a well-sampled configuration and then run WFC to correct local defects. This is similar to a common strategy in optimization: first run a Monte-Carlo method to find a point close to a global optimum and then run a gradient descent from that point for greater accuracy.

P. F. Harrison's texture synthesis algorithm is significantly faster than WFC, but it has trouble with long correlations (for example, it's difficult for this algorithm to synthesize brick wall textures with correctly aligned bricks). But this is exactly where WFC shines, and Harrison's algorithm supports constraints. It makes sense first to generate a perfect brick wall blueprint with WFC and then run a constrained texture synthesis algorithm on that blueprint.

Comments

Why the minimal entropy heuristic? I noticed that when humans draw something they often follow the minimal entropy heuristic themselves. That's why the algorithm is so enjoyable to watch.

The overlapping model relates to the simple tiled model the same way higher order Markov chains relate to order one Markov chains.

WFC's propagation phase is very similar to the loopy belief propagation algorithm. In fact, I first programmed belief propagation, but then switched to constraint propagation with a saved stationary distribution, because BP is significantly slower without a massive parallelization (on a CPU) and didn't produce significantly better results in my problems.

Note that the "Simple Knot" and "Trick Knot" samples have 3 colors, not 2.

One of the dimensions can be time. In particular, d-dimensional WFC captures the behaviour of any (d-1)-dimensional cellular automata.

References

This project builds upon Paul Merrell's work on model synthesis, in particular discrete model synthesis chapter of his dissertation. Paul propagates adjacency constraints in what we call a simple tiled model with a heuristic that tries to complete propagation in a small moving region.

It was also heavily influenced by declarative texture synthesis chapter of Paul F. Harrison's dissertation. Paul defines adjacency data of tiles by labeling their borders and uses backtracking search to fill the tilemap.

How to build

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

dotnet run WaveFunctionCollapse.csproj

Alternatively, use build instructions from the community for various platforms from the relevant issue. Casey Marshall made a pull request that makes using the program with the command line more convenient and includes snap packaging.

Notable ports, forks and spinoffs

Credits

Some samples are taken from the games Ultima IV and Dungeon Crawl Stone Soup. Circles tileset is taken from Mario Klingemann. FloorPlan tileset is taken from Lingdong Huang. Idea of generating integrated circuits was suggested to me by Moonasaur and their style was taken from Zachtronics' Ruckingenur II. Cat overlapping sample is taken from the Nyan Cat video, Qud sample was made by Brian Bucklew, MagicOffice + Spirals samples - by rid5x, ColoredCity + Link + Link 2 + Mazelike + RedDot + SmileCity samples - by Arvi Teikari, Wall sample - by Arcaniax, NotKnot + Sand + Wrinkles samples - by Krystian Samp. Summer tileset was made by Hermann Hillmann. Voxel models were rendered in MagicaVoxel.

second collage

voxel perspective