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

2023-08-29

Work on this project slowed down, but I finally managed to implement more features. The code is now available at https://github.com/vplesko/libwfc.

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 https://github.com/vplesko/unargs. 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]
Positionals:
        <string>
                (required)
                Input image file path.
Options:
        -n <int>
                (required)
                N parameter for WFC - patterns will be NxN pixels.
        -w <int>
                (required)
                Width of the generated image.
        -h <int>
                (required)
                Height of the generated image.
        -o <string>
                (required)
                Output image file path.
        -seed <unsigned>
                Seed value for the random number generator.
                Default: 1693290053
        -flip-h
                Enables horizontal flipping of patterns (think of y-axis as the mirror).
        -flip-v
                Enables vertical flipping of patterns (think of x-axis as the mirror).
        -flip
                Enables flipping of patterns both horizontally and vertically.
        -rot
                Enables rotating of patterns.
        -edge-h
                Fixes left and right edges so that patterns may not wrap around them.
        -edge-v
                Fixes top and bottom edges so that patterns may not wrap around them.
        -edge
                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:

They keep room for 50 state objects (because I’m still stubbornly not using resizable arrays).
The last element of the array is the current state object on which observations are being done.
Every 100 steps (WFC observations), the current state object is cloned and its clone added to the array, if there is still room. A counter tracks this.
When a contradiction is reached, the current state object is deallocated and removed from the array. Algorithm continues from the previous state object in the array.
After a backtrack, the counter is reset to 0. Even though 100 steps were done on the previous state, another 100 steps now need to be done before cloning again.
If the array is empty and no further backtracking is possible, the entire process has failed to generate any image.

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.

Link dump

https://github.com/vplesko/libwfc

https://github.com/vplesko/unargs

https://en.wikipedia.org/wiki/Rotation_matrix

https://github.com/nothings/stb

https://github.com/nothings/stb/blob/master/stb_image.h

https://github.com/nothings/stb/blob/master/stb_image_write.h

https://github.com/nothings/stb/blob/master/docs/stb_howto.txt

https://www.doxygen.nl/manual/starting.html

https://www.doxygen.nl/manual/commands.html

https://www.screentogif.com