The wave function collapse algorithm was on my ever-growing todo list since a while when a post on the POV-Ray forum pushed me to finally have a closer look at it. Well, the simple tiled model only as a POV-Ray script for now, because this algorithm is another rabbit hole that won't be covered in one article and a single week end.

The POV-Ray script implementing the wave function collapse algorithm and a complete example of how to use it is available at the end of this article.

If you don't know what the wave function collapse algorithm is about, follow its creator's twitter, look at this video or read this article. I would describe it as an algorithm to produce graphs of elements related by connectivity rules.

Lets start by defining some elements. Imagine you have a network of pipes, described as simple cylinders. To simplify even more, lets consider only straight pipes and crossing pipes, extending on a 2D plane. It leaves 3 elements: the cross, the pipe along the x-axis and the pipe along the z-axis:

To manipulate these elements easily, I put them in a dictionary:

#declare elements = dictionary { ["list"]: array {"cross", "pipeX", "pipeZ"} ["cross"]: union { cylinder {<0,.5,.5>,<1,.5,.5>,.1} cylinder {<.5,.5,0>,<.5,.5,1>,.1}} ["pipeX"]: cylinder {<0,.5,.5>,<1,.5,.5>,.1} ["pipeZ"]: cylinder {<.5,.5,0>,<.5,.5,1>,.1} }

The list key contains the list of elements, then each element is described by its own key.

Now, to create the network of pipes, we can place at random the three previous elements on a grid. (grid's cells are one unit in size, still to keep things simple)

// Declare the dimensions of the grid, memorise the number of element, and // initialise the random generator #declare sizeGrid = array {10, 10}; #declare rndSeed = seed(0); #declare nbElem = dimension_size(elements["list"], 1); // Loop on the grid cells #declare gridX = 0; #while (gridX < sizeGrid[0]) #declare gridZ = 0; #while (gridZ < sizeGrid[1]) object { // Choose at random the element for this cell #declare iElem = int(nbElem * rand(rndSeed)); // Create the element elements[elements["list"][iElem]] // Place the element in the grid translate <gridX -0.5 * sizeGrid[0], 0, gridZ -0.5 * sizeGrid[1]> } #declare gridZ = gridZ + 1; #end #declare gridX = gridX + 1; #end

Cool, but the network is purely random, hence poorly connected. We would like all those pipes plugged into each other. That's where the wave function collapse algorithm comes in handy. To use it we first need to describe the rules we want the network to follow: a cell can be a neighbour of another cell only if their pipes connect. To express this, I create another dictionary with one key per element, each containing 4 arrays (because each cell has 4 neighbours) of the possible neighbour cells. To identify the neighbour lets call px the neighbour at x+1 in the grid, mx the neighbour at x-1 in the grid, and so on for pz and mz.

#declare px = 0; #declare mx = 1; #declare pz = 2; #declare mz = 3; #declare rules = dictionary { ["cross"]: array[4] {array, array, array, array} ["pipeX"]: array[4] {array, array, array, array} ["pipeZ"]: array[4] {array, array, array, array} } #declare rules["cross"][px] = array {"cross", "pipeX"} #declare rules["cross"][mx] = array {"cross", "pipeX"} #declare rules["cross"][pz] = array {"cross", "pipeZ"} #declare rules["cross"][mz] = array {"cross", "pipeZ"} #declare rules["pipeX"][px] = array {"cross", "pipeX"} #declare rules["pipeX"][mx] = array {"cross", "pipeX"} #declare rules["pipeX"][pz] = array {"pipeX"} #declare rules["pipeX"][mz] = array {"pipeX"} #declare rules["pipeZ"][px] = array {"pipeZ"} #declare rules["pipeZ"][mx] = array {"pipeZ"} #declare rules["pipeZ"][pz] = array {"cross", "pipeZ"} #declare rules["pipeZ"][mz] = array {"cross", "pipeZ"}

The first rule says "a cross element can have another cross or an x-axis pipe as neighbour at position x+1 in the grid". The second rule says "a cross element can have another cross or an x-axis pipe as neighbour at position x-1 in the grid". The third rule says "a cross element can have another cross or a z-axis pipe as neighbour at position z+1 in the grid". And so on...

Now we have all the information we need, lets give it to a macro implementing the WFC algorithm (not to be mistaken with its cousin the WTF algorithm...).

// Create the grid using the WFC algorithm #local initGrid = WFCInitGrid(elements, sizeGrid); #declare theGrid = WFC(initGrid, elements, rules, sizeGrid, rndSeed); object { theGrid }

What does the WFC macro ? First, it creates the initial grid with, for each cell, an array of all possible elements (below, seen in superposition, hence they all look like cross).

Then, to start the algorithm, we choose a random cell and choose at random the actual element in that cell among all possible elements.

By choosing this element, it will probably imply that some of the elements in the neighbour cells are not possible any more according to the rules we have defined. We must then update the possible elements of all the cells in the grid, and this must be done recursively until we reach a situation where each cells respect all its neighbouring rules.

Now, we have reduced the number of possible elements in the cells (that's what's called 'collapsing'), but after only one step most of the cells probably still have several possible elements. The wave function collapse algorithm is just repeating the steps above (choose a cell, choose an element for this cell, update the possible elements for the other cells) until there is only one possible element per cell.

One element per cell ? Wait, are we sure to always find one ? There can be situation where we reach a cell for which none of the elements can fulfill its neighbouring rules given its current neighbours' element (that's called a 'contradiction'). What should we do in that case ? There are several approaches:

• Create an element that can have all the elements as a neighbour in all direction (hence, there will always be at least one element that fulfill the rules).
• Consider it an error, print a message to inform the user and stop.
• Try automatically again from the initial grid until you find a solution (if your rules are such that there is no way to collapse the grid without contradictions, you're in for an infinite loop).
• Simply consider the cell in contradiction as empty and move on. (being the easiest approach and cause I'm lazy, I'll use that one)

I left two points unspecified: at each step, how to choose the cell, and how to choose the element in that cell. The wave function collapse algorithm says to choose the cell with less entropy, cause it helps avoiding contradiction. The entropy of a cell can be calculated as the number of remaining possible elements for that cell. If several cells have same entropy, pick one of them at random. And about the choosen element, picking one at random just works fine.

However, it is also possible to affect a weight to each element, and choose it accordingly. In that case the entropy of a cell can be calculated using those weights: entropy = log(sum(weight)) - (sum(weight * log(weight)) / sum(weight)). This gives the user more control on the generated grid, pushing toward a given ratio between the number of each element (even though the exact ratio is not guaranteed to be achieved).

For now we have enough info to implement the WFC algorithm. We can render the grid as follow: for each cell, create its selected element and translate it to the cell position. Below are four examples with different seeds for the random generator:

Great, we've got our random pipe generator where pipes are always connected. What next ? Given the sparsity of the elements and rules I've used, the result isn't particularly interesting. It would take more elements (and something more interesting than pipes), and more rules to really get something out of this algorithm. It's not complicate per se, it's simply adding data to the two dictionaries, but it can quickly become tedious and impractical. Also, I've only used two dimensions here. In reality we would like to generate graphs in 3D, which works exactly the same but increase even more the size of the dictionaries.

In practice, these dictionaries (or there equivalent in another implementation) are not manually created, but procedurally generated. Examples are used as inputs of another algorithm which extracts possible elements, the rules specifying the way they relate in the example, and their weights. The output of that other algorithm then becomes the input of the WFC algorithm. However, explaining that other algorithm doesn't fit in the scope of this article, and anyway we reach here the limitation of what can be done with a simple scripting language like POV-Ray.

Does it mean the WFC algorithm is useless in the context of POV-Ray scripting ? I don't think so. By cleverly choosing the elements and rules, even within the computation limits of scripting and the human limits of editing the rules, there is surely a lot of room for interesting things. It took me just a few minutes to change the elements and rules to create a random pendant generator:

Another example with constraint on the borders: a celtic knot generator (not really sure what defines exactly a celtic knot, forgive me if they don't look celtic to you).

I leave it up to you to find some nice use cases to this algorithm. My implementation of the WFC algorithm is freely available here. It contains the code for the WFC algorithm in a standalone include file, and the POV-Ray script to generate the pendants and celtic knots. The script attached support 3D and weights, in addition to what's explained in this article. And there is a lot to explore from there if you want. For example: adding rules for cells in diagonal, or parameterize the rendering of elements to add more diversity.

If you need help, contact me by email, or ask on the POV-Ray forum. Have fun !