Devlog: Wave Function Collapse #0: Intro to WFC
2023-05-21
| GitHub | Next |
As it turns out, game design is hard. I mean, how do you actually make something fun? I think this is something a lot of programmers underestimate and stumble on. You can’t just implement fun and if you can, I’m terrible at it. I hope I can get better with more practice.
For now, however, I decided to switch to something more programmer-y. There are many interesting domains I wanted to dig into, a lot of them gamedev-related. And my next project would be related to… Wave Function Collapse.
Wave Function Collapse (or WFC) is an algorithm for procedural generation of images, levels, and other things. It accepts a reference image as input, analyses it for patterns, and constructs the output piece-by-piece as if it were solving a constraint problem. It randomly places patterns next to each other while trying to satisfy adjacency criteria. What you end up with is a larger image that: 1) exhibits local similarities with the input, 2) statistically follows pattern distributions seen in the input.
Do yourself a favor and visit https://github.com/mxgmn/WaveFunctionCollapse to learn more and to look at some nice animations. Make sure to check out the links in their README. I’ll do my best to explain how WFC works, but I won’t bother with visualizations, so I really suggest checking out other links.
The algorithm
WFC has two modes of operation - overlapping pattern model and simple tiled model.
Overlapping pattern model
Input: source image, pattern size (NxN), desired dimensions of the output image
Output: image of given dimensions
Steps:
Gather patterns. Walk through each pixel of the source image and collect the sub-image of NxN pixels as a single pattern (the source image’s pixel being the top-left corner of that pattern). In case of overflow, wrap around to the other side of the source image. Optionally, also collect rotations and mirror reflections of the pattern. (Check out this post for a nice visualization.) Notice that patterns may overlap, hence the name of this mode. Identical patterns may be found multiple times - pattern frequencies in this step will be used as weights in future steps.
Initialize the wave matrix and other solver data. Initialize a matrix called the wave and give it the same dimensions as the source image. At each point, the wave keeps track of which NxN patterns we can overlay on the output image anchored at that point as its top-left pixel (wrapping on overflow). Initially, all points can accept all patterns - we say that they are unobserved (I also think of them as being uncollapsed).
Deciding which single pattern to place at each point will be the goal of the remainder of WFC. As you can imagine, values of one element in the wave matrix affect what patterns can be placed at neighbouring points. Eg. if all potential patterns at wave point(20, 20)intend to place a blue pixel one point to the right of it, then the pattern at wave point(21, 20)must place the same-coloured blue pixel on its top-left corner. Any other option is illegal. The goal of WFC is to allocate a single pattern at each wave point, while satisfying adjacency criteria, ie. making sure that overlapping pixels of any two patterns are of the same colours.
(Neighbouring points are those that have non-empty overlap in their NxN pixel sub-images. What is a neighbour depends on the input parameter N, which is the width and height of each pattern.)Pick a point in the wave matrix with the lowest or tied for the lowest entropy. Meaning Shannon entropy. How is it calculated? Let’s say patterns 1, 2, and 3 can be placed at a certain point and that their frequencies from step 1 were
f1,f2, andf3. Then, the probability of randomly picking pattern 1 will be:
p1 = f1 / (f1 + f2 + f3)
and the entropy of the wave point is:
entropy = -p1 * log2(p1) - p2 * log2(p2) - p3 * log2(p3)
Initially, all wave points will have the same entropy, so the very first point picked will simply be a random one.Observe the wave point. Or collapse it, whatever you prefer to call it. Pick a single pattern from that wave point and remove all others. The pattern is picked in a weighted random fashion, with pattern frequencies from step 1 being used as weights.
Propagate constraints. As explained earlier, removing pattern options at one wave point may result in restricting the legal options at neighbouring points. In this step, update all neighbouring points of the previously observed point to remove any patterns that could never legally end up being placed for the remainder of this algorithm.
Now here’s the trick - this process ripples outwards to neighbouring points of any point that was updated along the way. If a pattern was removed from any wave point, that may affect its neighbours, so queue up and apply the same operation on those neighbours (and then potentially neighbours of neighbours, etc.).
If any wave point has been emptied, ie. it had all potential patterns removed from it, the algorithm has reached a contradiction and has failed. The original implementation would simply retry from the start in this case. Other implementations have introduced ways of backtracking to previous choices and changing them.
If all wave points have been observed (reduced to a single pattern), the algorithm has nearly finished. Proceed to the last step. Otherwise, go back to step 3.Render the output. This one is simple. Each wave point corresponds to a pattern. The actual pixel being placed at that point in the output image is the top-left pixel from its pattern.
Simple tiled model
In this mode, there’s no analyzing of a source image for patterns. Instead of a single source image, the user supplies a list of images and WFC will tile them onto the output. There’s no overlap, each tile will occupy its own part of the image. The user also supplies adjacency rules, describing which pairs of tiles may be placed above/below/to the left/to the right of each other.
The algorithm still goes through the steps of picking a point with the lowest entropy, observing it, and propagating the adjacency constraints until all tiles have been observed or a contradiction was reached.
Overall, it is a simplified version of the overlapping pattern model.
My plans
I was thinking of writing yet another WFC library. This one would be a single-header library written in C99. Most of my coding is done in C++, but I wanted to force myself into the C way of doing things in hopes I would learn something from the endeavour.
WFC is a base that can be extended in a great many ways. I am considering covering both operation modes, covering both 2D and 3D, and letting users control how certain decisions are made. I’ll see how much of that I actually end up doing.
What I’ve done so far
I wrote a very simple SDL program that renders an image, but this was the first time I did it in C.
Since C does not have destructors, I used goto for error handling. It looks something like this:
int ret = 0;
if (SDL_Init(SDL_INIT_VIDEO) != 0) {
ret = 1;
goto exit_sdl_init;
}
SDL_Window *window = SDL_CreateWindow(...);
if (window == NULL) {
ret = 1;
goto exit_sdl_create_window;
}
SDL_Renderer *renderer = SDL_CreateRenderer(window, -1, SDL_RENDERER_PRESENTVSYNC);
if (renderer == NULL) {
ret = 1;
goto exit_sdl_create_renderer;
}
// ...
if (renderer != NULL) SDL_DestroyRenderer(renderer);
exit_sdl_create_renderer:
if (window != NULL) SDL_DestroyWindow(window);
exit_sdl_create_window:
SDL_Quit();
exit_sdl_init:
return ret;Oh, and C99 doesn’t let you omit parameter names and my warning flags complain about unused parameters. But, SDL wants main to have a certain signature, so I had to do this:
int main(int argc, char *argv[]) {
(void)argc;
(void)argv;Otherwise, I had no problems so far.
Link dump
https://github.com/mxgmn/WaveFunctionCollapse
https://discourse.processing.org/t/wave-collapse-function-algorithm-in-processing/12983
https://escholarship.org/content/qt3rm1w0mn/qt3rm1w0mn.pdf
https://adamsmith.as/papers/wfc_is_constraint_solving_in_the_wild.pdf
https://www.gridbugs.org/wave-function-collapse/