Recently, I've been futzing around with the wave function collapse algorithm. The original WFC is a titch heavy for PICO-8, so I've been experimenting with shortcuts and hacks to make something small and light enough to be practical in a PICO-8 game.
It's still quite early in development: it's optimized for readability, not compactness, there's probably more performance I can get out of it, and I'm pretty sure I have an off-by-one error lurking somewhere. All that said, it's giving interesting, useful results so far!
This is interesting, @MagicChopstick.
I have a question. In the samples provided is it just pixels that is changing or are you using some different calculations or tables depending upon the sample chosen ?
Hello, @dw817! The algorithm itself is a general-purpose tiling algorithm that doesn't change based on the input.
The basic steps are:
-
For each pixel in the input image, create a 3x3 tile of that pixel and its neighbors. These are your pattern tiles.
-
Choose the location on the output image with the lowest entropy and place a pattern tile that "fits" there. "Lowest entropy" simply means "fewest valid pattern tiles to choose from". So, in the houses-with-red-roofs input pattern, a lone red pixel will have lower entropy than a lone green pixel, because there are a lot fewer pattern tiles with red pixels in them than there are pattern tiles with green pixels in them. Similarly, a pixel where most of its neighbors have already been set will have lower entropy than a pixel with a lot of unset neighbors, because there'll be that many fewer pattern tiles that match the already-set pixels. Then, once you've picked the pixel with the fewest pattern tile options to choose from, select one of those pattern tiles at random and place it.
-
Calculate the entropy for the pixels in the immediate vicinity of the pattern tile you just placed. In the original WFC algorithm, this was done with a fairly memory- and processor-intensive method that involved literally calculating the Shannon entropy for each pixel (which uses a log function, something PICO-8 doesn't directly support). In qdlst(), I'm cheating this calculation by using color frequency as a stand-in for actual entropy: if a neighboring pixel has an uncommon color (like the red in the houses-with-red-roofs example,) assign it a lower entropy value than you would for a green pixel, because as noted above, there are a lot more pattern tiles with green in them than red in them. It works pretty well.
- Repeat this process until you've fully generated an output image.
There are some nuances–for example, you want to try to use all your pattern tiles evenly–but that's the crux of how this algorithm works.
Nice cart ! It's funny, I posted a WFC implementation literally yesterday! But I went with the simple tiled model first because I'm guessing the output is easier to control and more fitted for what I'd like to use it for but I definitively want to give the overlapping model a try. Too bad it's too heavy for Pico-8 but your way of computing entropy seem to work well.
oh very cool, @pck404–I hadn't even seen that! Liked!
Yeah, the tiled model is a lot faster than the overlapping model, but I like the overlapping approach for its flexibility and quick setup (once the algorithm is done, of course :P ) I'm planning on building off qdlst() and creating a map generator for a Diablo/Gauntlet-style crawl game. Need to incorporate a guaranteed-path routine, though, since qdlst() can introduce blockages that the inputs wouldn't normally allow...
Nice! I'd been playing a ton of Caves of Qud this year and have been itching to try making wave function collapse function myself, and now that I'm seeing more people do it on Pico-8, I'm inspired to give it a shot myself.
@UnitVector it's a surprisingly fun algorithm to work with. It's straightforward enough that once you get it, it makes sense, but there's a whole lot of room to get fancy with it, too.
Pico-8 is a great, great place to futz with it. If something isn't particularly efficient, you'll see the effects right away (typically in the form of an out-of-memory error, in my experience)
Good talk by one of the Qud folks about their use of WFC: https://youtu.be/AdCgi9E90jw?si=uqDrMlCV9Zjhm2-k.
He mentions the guaranteed path issue. They solve it by using A-star to the needs-to-be-reachable point and setting walls to a very high cost, so that it would break down as few as possible.
[Please log in to post a comment]
