Home|Projects|About

Wave Function Collapse Algorithm, C++, 9.14.2022

This project is actually part of Rogue Adjacent 5, but it was enough of its own rabbithole -- and the page for RA5 is so long -- that I decided to put it in its own page.

I was first introduced to the idea of wave function collapse in this video. In another bid to prove I was capable of what other, more skilled programmers were, I decided to make my own. I checked a variety of different tutorials and articles about it, and decided I would try making a tile based algorithm first.




I'm gonna be honest, the tiled approach is super easy, especially if youre using one that has really rigid rules like this. I wasn't even propegating the changes more than one level deep (which ended up being an issue later) and it just worked. I suppose if you really think about it, the cell based approach is just the tiled approach but a little more extreme- but I digress. It was time to tackle a cell/image based approach.

IT WAS CONSIDERABLY HARDER.

Part of an image based generator invovles taking an input image and building a tileset off that. This is what makes the algorithm really interesting, you can seed it by drawing an example, and it'll just make more for you.
Unfortunately, I was still in the phase of "do it myself." Nobody made a tutorial for how to do an image based algorithm, and having mostly accidentally succeeded in making the tiled approach, I was completely lost. I did somewhat have an idea of how to generate tiles, though.


Heres a visualization of the tiles I generated (using the tiled output as its input now) where each tile is surrounded by an area which says what the confidence it is that there will be another wall there (it's black and white for now)
Issue: these are not entirely correct. Theres also far more tiles than there needs to be, but thats neither here nor there.
Depending on the input image, I did manage to get some decent results with it though


Input on left, output on right. This was just something I sorta scribbled, I was trying to obey some basic rules, but I made mistakes in places. This ended up being an issue, since I attributed the mistakes to my input image and not my algorithm (both were to blame.)

This was using the T shaped tiles. The issue was that it would make one mistake, then the mistakes would compound, and it would end up overwriting cells over and over again. I thought I knew how to fix this issue, but I didn't.
Ends up the issue is that I wasn't propegating the tile availability enough. Basically, the way this algorithm works is somewhat like solving minesweeper, where you set the state of one piece, then update the probabilities of the surrounding pieces, and then guess what the pieces are based on which tiles surround them.
What I was doing was somewhat similar to when you first learn minesweeper and only make moves you're 100 percent certain of based on the surroundings of a single cell. It gets you pretty far, but you need to be very lucky for it to not make mistakes.

I would try... SO many things, just trying to get this basic idea to work. It was actually maddening redesigning the entire system from the ground up, only to have it produce essentially identical results.

Here, I made it very slightly better by just changing some values around, fixing a few bugs, etc. Its still awful, though. Like, I had to scroll up through my devlog to see which input image its supposed to be.

After completely rewriting it from scratch, and allowing it to check a 9x9 area surrounding the tile, I was able to get better results. I think this was mostly due to it having a similar effect to propegating the changes out further, though it still failed in sone cases.

After this was just failure after failure of trying to adapt it to more complex patterns. I don't have many pictures of this, since at this point I was quietly questioning my own intelligence quite a bit and didn't want people to see me suffer.

Eventually, I decide to try propegating the change out, and instantly I see significant changes for the better.

After this it was success after mild success.

The biggest issue now was optimization. It also would occasionally hang up for indefinite amounts of time, due to there not being a correct orientation (my code still wasn't perfect)
Like a true programmer, my solution was to allow it to occasionally make mistakes, and to decrease the amount of recursive calls to the propegate function.

Project more or less done! I kept making tweaks once I ported it to RA5, but they're minor. No download for this one, since you can't really do much with it, and it was just a part of another project.