The Wave Function Collapse (WFC) Algorithm


Here is a blog post from 2018 explaining the principles behind the algorithm.

There is a popular implementation written in C++ for which we'll run through an example.


Before we can trace through an example of the values at runtime, one must understand the data structures that we're going to be tracking. The sections below aim to explain that.



This very low-level intermediate-level class lies just above the 2d-array implementation! It contains just a few key components:


This class contains:


Remarkably, this class contains a forward-declaration of the Wave class! But it also contains nitty-gritty data structures like:

An Example (Code Trace)

Let's trace through the code using an example. Suppose we have a total of 5 distinct patterns (nb_patterns).

Well, shoot, that means I have to write a full configuration for the rules that dictate which patterns can be placed next to which other patterns.

Suppose the ruleset looks something like:

You can treat each letter as representing a unique color or type, or shape, or however you want to envision it. And I guess I need some frequencies for these letters, eh?

visualization of placement rules, as a PNG

Let's use this: {'A': 0.05, 'B':0.5, 'C':0.15, 'D':0.25, 'E':0.05}

Notice that, under this ruleset, the only symbol that can be repeated in a contiguous chunk is "B." No wonder it has the highest frequency!

Now that that's out of the way, how does an iteration of our algorithm look? Let's step through it.


This is one of only three functions defined on the Propagator, and it is the only one called in the body of the Constructor. It does what it sounds like — populates the compatible private instance variable (see above).

It will be interesting to see where and how this variable gets updated every time a new choice is made.


So, already, in the first eight lines of the Propagator::propagate() function, we see the following:

// The cell and pattern that has been set to false.
unsigned y1, x1, pattern;
std::tie(y1, x1, pattern) = propagating.back();

I am reminded of a 2012 Jontron episode where he says, "So immediately he's doing this annoying s***. Like, immediately, he's doing this."

Why do I react so sharply? Well, because I went to a nonsensical university, they didn't offer courses in C++, or at least, not for my major programs. So I am left wondering, how the hell is it possible to use a constructor invocation on the left-hand side of an apparent assignment? I understand that the assignment operator doesn't always mean what you think it means in C++, but this goes a step further. It doesn't even assign a variable name to the result of the tie!

If you are confused by this, then you're not alone. However, the key to understanding is that the tie function, from <tuple>, returns a tuple "containing lvalue references."

So we extract the final triplet (y_ind, x_ind, letter) and save the values into our lvalue references y1, x1, and pattern.