Log In  

Cart #mcg_qdlst-0 | 2022-10-26 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA

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!

P#119580 2022-10-26 03:39

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 ?

P#119585 2022-10-26 06:04

Hello, @dw817! The algorithm itself is a general-purpose tiling algorithm that doesn't change based on the input.

The basic steps are:

  1. For each pixel in the input image, create a 3x3 tile of that pixel and its neighbors. These are your pattern tiles.

  2. 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.

  3. 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.

  4. 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.

P#119592 2022-10-26 11:49

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.

P#119603 2022-10-26 15:30

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...

P#119627 2022-10-26 22:35

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.

P#119709 2022-10-28 01:16 ( Edited 2022-10-28 01:17)

@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)

P#119715 2022-10-28 02:53

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.

P#150375 2024-06-24 23:28

Oh that's really cool, @shastabolicious! Thanks for sharing!

P#150422 2024-06-25 21:10

[Please log in to post a comment]