Wave Function Collapse Algorithm

Unity Engine
1

hey,
so this awesome guy: ExUtumno mxgmn, created this awesome Algorithm inspired by Quantum Mechanics Wave Function Collapse.
you can see it at work here:

and:
Wave - by Oskar Stålberg (Oskar Stalberg, also awesome dude doing amazing stuff)

I’m trying to get my head around this algorithm, if anyone is up to discuss this, please feel free to do so here.

Algorithm

  • Read the input bitmap and count NxN patterns.

  • (optional) Augment pattern data with rotations and reflections.

  • Create an array with the dimensions of the output (called “wave” in the source). Each element of this array represents a state of an NxN region in the output. A state of an NxN region is a superpostion of NxN patterns of the input with boolean coefficients (so a state of a pixel in the output is a superposition of input colors with real coefficients). False coefficient means that the corresponding pattern is forbidden, true coefficient means that the corresponding pattern is not yet forbidden.

  • Initialize the wave in the completely unobserved state, i.e. with all the boolean coefficients being true.

  • Repeat the following steps:

  • Observation:

  • Find a wave element with the minimal nonzero entropy. If there is no such elements (if all elements have zero or undefined entropy) then break the cycle (4) and go to step (5).

  • Collapse this element into a definite state according to its coefficients and the distribution of NxN patterns in the input.

  • Propagation: propagate information gained on the previous observation step.

  • By now all the wave elements are either in a completely observed state (all the coefficients except one being zero) or in the contradictive state (all the coefficients being zero). In the first case return the output. In the second case finish the work without returning anything.

As far as I understand it:
1 Make patterns of NxN pixels big from a bitmap. Optional (??)
2 make a Dictionary with allocated size being the count of all the patterns from the previous step.
make the key boolean and the value a pattern?
3 set key default to true.
4.1.1 where and how do the elements get they’re Entropy Value?
4.1.2 when and how to change the coefficients (boolean key in dictionary?) and what is meant with the distribution of NxN patterns in the input here?
4.2 what does an observation step include here?
5 finish up :slight_smile:

you see, it’s getting unclear to me from step 4, if anyone understands the details of step 4 and 5, please do share them. :slight_smile:

hope you enjoy the info.
J.

1 Like
2

It looks like they are using density matrices to describe the states. If this is the case, then I would imagine they’d calculate entropy by the Von Neumann method.

3

ok thanks, i had to look up Von Neumann method :slight_smile:
Still after going through the code for a day, I get where the magic happens but not how it happens :frowning:

anyone who can follow and understand what’s happening in the code, would be great to have a commented version :slight_smile:

4

I found this because I’ve been playing around with this WaveFunctionCollapse stuff in Unity after seeing Oskar’s Wave thing.

I’ve started making my own generic implementation of this from scratch, just to see if I can figure out how it works. I have something that works pretty well (example here) but still runs into impossible states more than it should. I think the problem with my current implementation is the way it propagates the changes. I haven some ideas for how to fix it, but haven’t gotten around to trying them yet.

So about how my version of the algorithm works, first let’s start with some terms that I use for my pipes example:

  • Grid: filled with rows and columns of slots
  • Slot: a thing that has a tile
  • Tile: a type of tile (ex empty tile, north-to-south pipe, south-to-east pipe, etc). Oskar calls these “modules”
  • Edge: connects a slot to another slot, each slot has 4 (north,south,east,west)
  • EdgeType: a type of an edge (ex empty, pipe)

The core concept behind WFC is actually pretty simple. It’s kind of like Sudoku where you’re eliminating possibilities until you arrive at the solution. Every slot starts out that it COULD be ANY of the tiles. You keep eliminating possibilities from each slot until you are only left with one tile left for each slot, each slot is “solved”.

The key thing is HOW you eliminate possibilities from each slot. Here are the steps as I see it:

  • Start by picking one of the slots at random and giving it a random tile type, in other words, solving it.
  • Propagate that change outwards to the surrounding slots. If our chosen tile has a pipe on the east side, we know that the tile to the east of us (let’s call it “Slot B”) has to have a pipe on its west side.
  • We can eliminate all of the tiles from Slot B that don’t have a pipe on the west side.
  • Now that Slot B has changed, propagate the changes from Slot B to the slots surrounding it.
  • Repeat steps 2-5 until we have checked every slot surrounding every slot that has changed, and no more slots have needed changes. In other words, our grid should be back in a state where all of the slots only have valid possibile tiles.
  • Return to step 1. Find the tile that is closest to being solved (the fewest tile possibilities left) and solve it with a random tile.

That’s really about it! The key thing that I’m not sure about is how to propagate the change. Right now my thing does a depth-first search, so if a change to my initial slot causes changes, I follow the trail of changes (the “solve stack”) before popping back up to the original slot. This seems to be how Oskar’s thing does it as well, though his doesn’t ever make changes to slot that is already earlier in the “solve stack”, which mine does do (I think this is part of the problem with mine!).

The WaveFunctionCollapse tilemap generator does some other neat stuff to make it work well for pixel maps.

It samples NxN (let’s say 3x3) chunks of the input image, and uses those for tiles in the output image. Otherwise the idea behind the algorithm is basically the same (though it uses a lot of quantum mechanics terminology, which I personally find confusing even though it’s probably more accurate).

There are two other fun little features that WFC adds on top of the base algorithm:

  • fun feature one: the probability of 3x3 tiles in the input is used as the probability of 3x3 tiles in the output. So you know in my explanation where we sometimes choose a random tile type for a slot? WFC weighs those tile types based on how common they were in the original image. So if the input image had one flower tile in every 10 tiles, then it will be picked 10% of the time in the output as well.

  • fun feature two: WFC wraps the edge connections around the outside of the grid. The eastmost slot of the grid has an edge that connects it to the westmost slot of the grid, and vice-versa. This allows the algorithm to solve for the edges, which ends up resulting in a tileable pattern (you’ll noticed that I’ve implemented this in my examples as well).

Hope this helps!

I’ll let you know if I make any further progress on figuring out exactly how the propagation works :slight_smile:

3 Likes