Wave function collapse algorithm

Feb 24, 2019 09:32 · 744 words · 4 minute read tutorial procgen algorithm

What is Wave function collapse

Wave function collapse (wfc for short) is an algorithm used in game development to procedurally generate contents such as images or 3D models. It takes as input a sample, then generates an output based on that, the algorithm is able to capture its style.

How does it work?

From the sample, the wave function collapse algorithm creates a set of patterns. A pattern is a slice of the input. Let's say we are working with 2D content, for example, this 4x4 image:

sample

The set of patterns will be these:

patterns

In this case, we used a pattern size of 2x2. Concretely, we move a 2x2 window in the input image, and record each new pattern. Using a 2x2 pattern size with a 4x4 sample we get 9 patterns. With apply some pattern augmentation function to these first set, such as flipping and rotation, to generate more patterns. We end up with 12 patterns.

The set of patterns can be viewed as tileset that will be used to generate the output image.

Then, wfc generates some rules or constraints about the placement of those patterns. For instance, the following image shows which patterns can be placed on the right of the pattern A. Concretely, it will look at all the pattern that can fit in the green square, so having a blue pixel on the top left corner, and a white pixel on the bottom left corner.

patterns

Once we precomputed the constraints, we can now enter in the heart of the algorithm, the constraint solving part. Indeed, the wfc algorithm is about finding a valid solution with respect to those generated constraints, in this case, finding an image that for each part of it and pixel, is valid with respect of its neighborhood. We call this kind of problem a constraint satisfaction problem and the algorithm a constraint solving algorithm. The wave function collapse is in fact implicitly implementing some techniques of the AC-3 algorithm, but we do not need to know this to understand the wfc algorithm.

Observation

We initialize a grid where each cell has its decision variable unassigned. At the start, all the patterns are still valid. Iteratively, the wfc algorithm uses the “minimum remaining values” heuristic to selects the cell to fix. This heuristic will choose the grid location with the least non-zero entropy, the cell with the least patterns that are still valid. This selection method helps to reduce the number of dead-ends/conflicts encountered during the algorithm.

A valid pattern is then randomly sampled to set the cell variable.

Propagation

As we changed the state of the grid, we need to propagate these changes to cells that may have been affected, the valid remaining pattern in the neighboring cell may no longer satisfy the constraints. If a state modification occurs in these neighboring cells, we need again to propagate its neighboring cells. We recursively propagate the changes to cells until all the constraint is satisfied.

These two steps (observation and propagation) are repeated until no variable can be changed.

It happens rarely that conflict occurs, the constraints cannot be all satisfied. In this case, we can do backtracking, to return to a previous state where constraints are fine, or we can simply restart the algorithm.

A cool thing with this algorithm is that we can display the work in progress result and thus creating nice animation. Indeed, for the cell already stabilized, we can directly output the associated pixel for the 2D case, and for the partial assignation cell, a mix of pixel color or simply grey can be printed. An example of the process in the following image:

wfc

Some others examples

In the previous section, we saw a brief explanation of the algorithm for the 2D case. But the wfc algorithm can be applied in any number of dimension.

A midi file:

midi sample –> output

A 3D voxel model:

voxel


My understanding of the algorithm is based on this article, I encourage you to read it if you would like to get more details Link. The authors put more context and describe well the algorithm, they also reimplemented it using an answer set programming (ASP).

Also, you can check my python implementation of the wfc algorithm. I tried to use the same terminology as the article. Link

If you do not like Python, you can get the official C# implementation, other languages are also available in the readme Link

Have fun with this amazing algorithm!

tweet Share