Wave Function Collapse

What is that?

I should start by saying I didn't come up with it. I also can't say that I fully understand all of the thought that went in to it, or some of its subleties. For the utmost in detail, please check out the original work here.

Wave Function Collapse is an algorithm that alows us to, for example, generate an image made of a tiling of smaller images with rules for which images may be adjacent. By guessing where we have to and updating our neighbors' legal options after each guess, we're able to generate a reasonable potential image. By identifying and correcting any eventual mistakes, we can assure the final product is a "legal" image.

The algorithm gets its name from Quantum Mechanics, where our cells are in superposition of multiple states, and by observing our cells we are able to collapse that superposition, revealing more information about the state of the cells around us, and eventually leading to the entropic collapse of the entire system.

Uh huh... Yeah, I know some of those words...

Err, right. Yeah. This is more of a visual thing. Luckily, I have visuals! Check these out and we'll keep talking about this after.

Tilesets

Okay, I saw what was happening... tell me what that means again?

So the process goes like this:

The Setup

  1. Define a grid that's X units by Y units, called "cells". This will hold our images eventually.
  2. Define a set of possible images for our options called "tiles", as well as the rules for how these tiles can connect to each other.
  3. Tell every cell in the grid that, by default, they are allowed to be any of the options.

The Algorithm

Now that we've set up our system, we can perform our algorithm over and over until our system is solved.

  1. Find the cell with the smallest number of available options.
    • If there's several tied for the lowest, pick one at random.
  2. "Collapse" the cell by assigning its state to one of its options at random.
  3. Tell all the neighbor cells their list of legal options is now reduced to those matching this new cell.
    • If any of those neighbors have their options reduced to zero, reset that neighbor and all of its neighbors.
  4. Repeat until all cells have been collapsed!

How do the tiles know what they're alowed to be next to?

Great question! You can provide rules for the tiles that explicitly say which tile edges are allowed to go next to each other. My code checks the pixels on the edges of the images and stores that to compare against the other images, so it detects the rules automatically!

This doesn't always work: not all tilesets can have their rules explained perfectly by a single method. Or at least, if there is one such method, I haven't found it yet. But so long as the edges of each matched image are identical, this algorithm will understand that as a rule.

Got it... I think. Is this useful though? It definitely looks cool...

Yes! I mean, maybe not to everyone, but we can definitely find places where this algorithm could come in handy. One example is creating video game textures! Maybe you want to have a bunch of backgrounds for your levels that should be similar, but not the same. Instead of sitting there arranging all the tiles by hand!

Let's come up with a more entertaining example though. What if instead of watching these images get drawn, we hid the whole process, and before revealing the image, we rotated some of the tiles and allowed the user to rotate them back by clicking.

Because we're generating the picture according to the tile rules, we can be sure we'll always have a solvable puzzle as opposed to randomly placing random tiles in random directions.

Oh and look! That game we just talked about is right here! Not yet implemented