Devlog: Wave Function Collapse #3: Transformations, Backtracking, Erase-Redo, Release


Prev GitHub Next

Work on this project slowed down, but I finally managed to implement more features. The code is now available at

Most WFC implementations allow patterns to be transformed after being picked up from the reference image. In my implementation, you can allow patterns to be flipped around, like in a mirror, either horizontally or vertically.

You can allow them to be rotated by 90, 180, or 270 degrees.

I used the well-known rotation matrix to derive how to rotate an image:

 cos(A) -sin(A)
 sin(A)  cos(A)

For example, for 90 degrees this becomes:

 0 -1
 1  0

and in an NxN image, pixel (x, y) becomes (n - 1 - y, x). If you ever deal with rotations, my advice is to make sure you are rotating the right way. It is an easy mistake to make ending up with the inverse transform of the one you expect.

You can also enable what I ended up calling edge-fixing, horizontally or vertically. This means that patterns will not wrap around image boundaries and the algorithm will only allow pixels found at those boundaries in the reference image to be found at output image boundaries.

You can see in the example above that brown pixels are found only at the bottom and the other bounding pixels are either the sky color or are yellow flower petals. Stems don’t wrap around between left and right.

I wanted to make the CLI and GUI tools useful, but I had to do a couple of things first.

I polished the library’s public API and added new functions. You can either call one function that performs the entire algorithm from start to finish or call a different set of functions to run the algorithm step-by-step. You facilitate this by passing around an opaque pointer to a state object that was handed to you. CLI and GUI only call into public functions, and I found it’s easier to design a good API if you are also using it yourself.

All toggleable options and input and output paths have been hard-coded so far. I went off on a tangent and started coding a mini-library for parsing arguments passed to the main function. Shortly after, I decided this should be a library of its own and it now lives as Normally, I dislike binding myself to my old code between projects, instead I prefer to endlessly cannibalize old projects and reinvent the wheel (*gasp* the horror, I know). But argument parsing is something I needed a few times already, so I decided to package it in a way I can reuse in the future.

With that in hand, the user can now enable flipping, rotating, edge fixing, etc. from the command line. If arguments are invalid, they get a help text:

Usage: bin/cli <string> -n <int> -w <int> -h <int> -o <string> [options]
                Input image file path.
        -n <int>
                N parameter for WFC - patterns will be NxN pixels.
        -w <int>
                Width of the generated image.
        -h <int>
                Height of the generated image.
        -o <string>
                Output image file path.
        -seed <unsigned>
                Seed value for the random number generator.
                Default: 1693290053
                Enables horizontal flipping of patterns (think of y-axis as the mirror).
                Enables vertical flipping of patterns (think of x-axis as the mirror).
                Enables flipping of patterns both horizontally and vertically.
                Enables rotating of patterns.
                Fixes left and right edges so that patterns may not wrap around them.
                Fixes top and bottom edges so that patterns may not wrap around them.
                Fixes all four edges so that patterns may not wrap around them.

I switched to using stb_image and stb_image_write for file I/O. Since they compile slowly, I split their inclusion into a separate translation unit that gets compiled separately.

GUI lets you watch the algorithm run and it now colors each pixel based on which patterns can still be placed there.

Those weird jumps you see near the end are from the tool backtracking when WFC finds a contradiction and cannot continue. My library does not handle this (just like it doesn’t handle file I/O), instead letting the user implement backtracking in whatever way they like. What they are provided with is a function that fully copies data owned by a single state object. They can then advance the generation in one state object while keeping the other as a checkpoint and fallback.

Backtracking in CLI and GUI works like this:

If contradictions are run into more frequently than every 100 steps, this will cause the process to backtrack further and further into the past, which is what you’d want to happen. The logic is rather simple, but effective. Here’s another example of this in action:

One more feature I implemented that I think is kinda cool is the ability to tell WFC that some pixels in the output buffer already have fixed values and to only generate the remaining part of the image. I used this in GUI to let users “erase” parts of the generated image and force GUI to generate them anew. So, if you don’t like how a part of the image turned out, you can just have it redone. Example:

(By the way, I used ScreenToGif to record these GIFs. The tool’s pretty nice so far and simple to use, though I’m still struggling to get it to not cut pixels from left and right.)

Since this is meant to be a single-header library, I followed these recommendations on what to do (#define WFC_IMPLEMENTATION, extern "C", etc.). Users can provide their own macros for assert, memory allocation, and RNG. They can provide a void* to a context object that will get passed to these macros. Each public function has a documentation comment and there is a giant comment near the top of the header with more detailed instructions on how to use the library.

And that’s most of what’s worth writing about. As for what next, I’m still not happy with the performance of my implementation and it even got slower with all these changes, so that’s what I’ll be focusing on next.