Wave Function Collapse — Tutorial of a Basic Example Implementation in Python
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:
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:
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:
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.
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…
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.
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:
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.
