Wave Function Collapse — Tutorial of a Basic Example Implementation in Python

Mateusz Bugaj
Jul 31, 2020 · 5 min read
Image for post
Image for post

WaveFunctionCollapse algorithm created by Maxim Gummin and published on github as open source allows user to generate bitmaps and tilemaps based on given input which is extremely useful in creating tilesets, maps or other forms of art. For more information I highly recommend you to read WaveFunctionCollapse is Constraint Solving in the Wild as well as check out Gimmin’s repo.

What we are trying to achieve in this tutorial:

Image for post
Image for post
Example taken straight from Gummin’s github

Notice that in output image there is no red pixel next to white pixel since there is no configuration like this in the sample.

Load sample and extract patterns

Let’s start by defining image sample that we are going to use in this example. It is 4x4 pixels picture of a black square in corner with red center. Small size of this sample will help to simplify and better visualize whole process. We are also not going to use RGB colors so that our sample and later patterns can be written as simple array of integers with one value per pixel. Our sample looks like this:

Sample 4x4 pixels image ploted with matplotlib
Sample 4x4 pixels image ploted with matplotlib
[[255, 255, 255, 255], [255, 0, 0, 0], [255, 0, 138, 0], [255, 0, 0, 0]]

We will now extract all patterns of size 2x2 pixels and their rotations that can be found in our sample. This can be done by hand as there are only 12 unique patterns but I will use some code to help me out. We are also going to need weights telling us how many times given patterns occurs in sample so we can calculate probability of that pattern occuring in our output image. But we will get into that.
Here are our patterns:

Patterns extracted from sample with corresponding weight and probability
Patterns extracted from sample with corresponding weight and probability

Create Index data structure describing rules for placing patterns

After we collect our patterns, now comes part where we specify rules what can be in adjacent tiles. We need to have a way to tell if this pattern can be in this relative position to that pattern.
We will store these informations in Index object which will look like this:

Notice that this is a four dimentional data structure. There is list of possible patterns, for every direction for every existing pattern. There are 8 possible direction: UP, DOWN, LEFT, RIGHT, UP_LEFT, UP_RIGHT, DOWN_LEFT, DOWN_RIGHT. We need to specify how each direction corresponds to position of pixel on output image. In other word; tell that ‘up’ means 1 unit less on a Y axis (1 less because our sample has inverted Y axis where 0 is on top) and so on…
Because algorithm will check every position for every pixel, even pixels that are on the edge of our matrix where not all directions are available, we need a way to tell possible directions for each position.

We will define each rule based on intersection of our base pattern and pattern in question for every relative position.

Image for post
Image for post

If value of intersection is the same in both patterns, consider pattern in question to be valid in this relative position.

In this example we define 360 rules.
And now we can start to work on the WFC algorithm.

Define coefficients

We start by defining matrix of tiles with corresponding possible patterns later called matrix of coefficients. In original implementation this holds boolean values denoting which pattern is still available. For simplicity we will use patterns themself to tell which are still possible in this position.

At the beginning, all available patterns are possible at all positions in the matrix and what algorithm has to do is to reduce their number to only one pattern at each possition.

Utility functions

There are few functions that will help us run this algorithm:

For each iteration we need to start propagating our algorithm from the place with the highest entropy meaning level of “uncertainty”. Tile where only one pattern is possible has entropy equal to 0.

Algorithm itself

While there is a tile with more than one possible pattern, find tile with the lowest entropy. Colapse this tile meaning pick one of possible patterns at that location with the highest probability and assign it to that tile. Now there is only one possible pattern but since some patterns got deleted from that location, we need to check if all of patterns in adjacent tiles are still possible in their locations. So it’s time to propagate. For every change we do in our matrix, we add tile position into a stack. For every adjacent tile, if there is a change, we add it’s possition. If there is no change in neiberhood tiles, we take tiles from stack, check for changes and add changed tiles positions into a stack and so on…

Image for post
Image for post

This is how matrix of 20x20 tiles looks like when we translate number of possible patterns at each tile into a grayscale after first iteration. We can see that some tiles already have only one possible pattern available.

Image for post
Image for post

Now do this until there is no tiles with more than one possible pattern.

Post process

After our algorithm finishes we can now extract distinct pixels from patterns. Remember that each pattern has equal intersection with all of it’s adjacent patterns. If we get only first pixel from each pattern, we get unique part of each.

And here is our output:

Image for post
Image for post
Output image of the size 50x50 pixels

As you can see it’s quite easy. If you had hard time wrapping your head around it I hope this post helped you in some way. Now you can modify this code, make it better and more suitable for your creative needs.

References

Code on my github in form of Jupyter Notebook

Gummin’s repo on github

Resarch paper on which this post is based on

The Startup

Medium's largest active publication, followed by +775K people. Follow to join our community.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store