Thread by @exppad

The #WaveFunctionCollapse algorithm has been introduced by @ExUtumno as a texture synthesis method and nicely used by @OskSta for procedural generation of 3D buildings. Wait, what, how do those relate? Sounds like totaly different applications!
⬇️ Answers in the thread! 1/18

Discrete pixel values: WFC is different from many other texture synthesis algorithms because it never blends pixel colors. It does not need to know that a little bit of blue and some red creates purple. Others do require this, e.g. hal.inria.fr/hal-01824773/f…
2/18

This is a strength because it makes WFC more general. Pixels don't even need to contain colors. They just contain "stuff" or, more properly said, "abstract symbols". Can be an integer, a letter, a shape, whatever.
3/18

It has some drawbacks though, don't wonder why all original examples are pixelart-ish! The algorithm cannot recognize a pixel color "close to" another one, they are either the very same or totally different to its eyes.
4/18

So, what exact problem does WFC solve? There are two major steps. The first is the extraction (or "learning" but the word is a bit strong) of tiles and adjacency rules from an example image.
5/18

The second step is the constraint solving. For each location - or "slot" - in the new image, we pick a tile that respects the adjacency rules with its neighbors. @OskSta made a nice demo to show it in action: oskarstalberg.com/game/wave/wave…
6/18

There are two variants provided by the original implementation: "tiled model" and "overlapping model". The former simply cuts the input image in NxN patterns (here 3x3) and treat them as "abstract symbols".
7/18

The overlapping model extracts patterns using a sliding window. A tile is then a single pixel together with information about its neighborhood. Adjacency rules are derived from this neighborhood.
8/18

The notion of slot differs depending on the model. But anyways for the solving the output image remains a bunch of slots to fill with abstract symbols.
9/18

The true difference between tiled and overlapping models is the relations between slots. There are much more with overlapping model. With patterns larger than 3x3 there would be even more types of adjacency.
10/18

Overall both #WaveFunctionCollapse models are the same thing, the solving step does not care: it's still all tiles, slots, adjacencies and rules.
11/18

What about 3D then? Once again, it is just a change of adjacencies! There are with tiled model 6 adjacency relations: Left, Right, Forward, Backward, Above and Bellow. Overlapping model can also be applied.
12/18

All right then, the solving does not care? What if it's not a grid? "I still don't care", says the solving.
Examples on spheres by @boris_brave

https://twitter.com/boris_brave/status/1244387278732091392

and @OskSta oskarstalberg.com/game/planet/pl…
13/18

It even works with irregular grids, here on my reproduction of #Townscape. A notable difference is that there is no more symmetry in adjacencies. If slot A is "in front of" slot B, B is NOT necessarily "behind" A.
14/18

Here we are, Gumin's texture synthesis and Stalberg's procedural village use the same Wave Function Collapse algorithm, it's "just" a variation of tiles, adjacency rules and slot topology!
15/18

Pixels don't contain colors. And the image is no longer a grid. We've totally deconstructed the texture sythesis approach. But once again, this is good news! It illustrates the versatility of Wave Function Collapse.
16/18

NB: I don't know exactly how OskSta actually handles connection rules, I can only guess. Here is how I did in my implementation: tile faces are labled to tell which other tiles it can connect to.
17/18

📚Other resources to go further (and see the core algo, not presented here)
@ExUtumno's original implementation github.com/mxgmn/WaveFunc…
@ambrosiussen_p's talk about WFC in Houdini at GDC20
@OskSta's talk about Bad North at EPC18