Introduction to Wave Function Collapse

Wave Function Collapse is an algorithm that generates structured randomness.

There are plenty of reasons to want structured randomness. Maybe you want to create a randomized world map, with rivers coming out of lakes, and mountains ranges gradually sloping, like in Minecraft.

Or maybe you want to create randomized towns, with the layout of the houses changing, but the rules that connect them the same, like in Townscaper.

A game like Civilization or Settlers of Catan has rules regarding which tiles are allowed to be placed next to each other. They could use structured randomness to build their hex maps.

This sort of structured randomness is exactly what the Wave Function Collapse algorithm does. We’re going to spend the next few minutes discussing this fun algorithm and looking at some neat simulations.

What is Wave Function Collapse?

To learn more, let’s build a road together. Here’s a sandbox we can mess around in.

Roads are built using our handy Unicode box drawing characters:

[" ", "╵", "╴", "╷", "╶", "┘", "│", "└", "┐", "─", "┌", "┤", "┴", "├", "┬", "┼"]

These fellas can connect to each other in any of the four cardinal directions. This makes them easy to work with for building boxes, or in our case, building a path. In our simulation, a grid cell can be any one of these possible road tiles.

How would you play with these to construct a road?

Maybe like this. We slowly build the road piece by piece. From nothing, we are able to make smart random decisions until a road has been made.

Sometimes we’ll back ourselves into a corner. The piece we place depends on our neighbors, and only one or two pieces will work. Not every piece can be connected to every other piece. But we always have the piece we need, and the smarts to put it there.

That’s Wave Function Collapse (WFC)! It’s all about making random choices that still make sense. By understanding the rules that our road needs to follow, WFC can do the same thing we do: start with nothing, and slowly iterate until the road is complete. How does it do this?

WFC starts with an empty grid, just like we did. It will place some initial road and construct all other roads connecting off it.

Let’s start building our simulation, and we can gain more insight along the way.

The Setup (feat. JavaScript)

The first thing we’ll need is a grid.

class Grid {
  constructor(width, height) {
    this.width = width
    this.height = height
  }

What next? Let’s take a step back and look at the origins of Wave Function Collapse.

Wave Function Collapse is a concept that computer scientists lifted and repurposed from physics. In quantum physics, WFC is the physics of “observing” an unknown superposition to “collapse” it into a single certain state. Like Schrodinger’s Cat! The cat is both dead and alive until someone looks in the box.

Observing the cells in our grid functions the same way. Our cells are simultaneously every road state possible, until each cell is “observed” and forced to “collapse” into a state that continues the road.

Think of planning a road system in real life. With an empty field in front of you, you could choose to build roads whichever way you want. You just pick somewhere to start and branch off from there.

To start generating a random road, our algorithm will need something to observe and collapse. Let’s fill the Grid with objects we can interact with. We’ll make a Cell class that can be observed and collapse into a random state.

class Cell {
  constructor(x, y, possibleTransforms) {
    this.x = x
    this.y = y
    this.possibleTransforms = possibleTransforms // any of the road characters
    this.observed = false
    this.state = null
  }

  observe() {
    this.observed = true
    const i = Math.floor(Math.random() * this.possibleTransforms.length)
    this.state = this.possibleTransforms[i] // “collapse” into a random state
  }
}

We will populate every (x, y) on the Grid with a Cell class. Each cell will start with the potential to collapse into any possible road state.

We’ll start the simulation by observing the center cell. Let’s see what it looks like if we restart the simulation repeatedly. What will the center cell collapse into?

Upon observation, the cell collapses into a random one of its potential states. Now we’re getting somewhere. This is where our road will begin.

The Algorithm (feat. Quantum Mechanics)

Which cell should we choose next? We could pick any of them, but it makes the most sense for our target to be the cell with the fewest potential states. That is, the cell that has the most certainty about what it will collapse into. This is a cell’s entropy. Lower entropy means fewer potential states. Let’s place the entropy of a cell on the grid to make things clearer.

All the unobserved cells have an entropy of 16; they have 16 possible states they could collapse into. At this stage, every option is still allowed because no constraints have been applied yet, so each cell remains maximally uncertain. Let’s add a rule to tell the cell what states it can collapse into.

A road must connect to its neighbors.

This gif shows the road’s states that can be placed adjacent to the state in the middle. They either connect where the road connects, or they don’t connect where the road doesn’t connect.

Another way of putting that rule would be: A cell must collapse into a road state that connects with all incoming roads.

For a cell to collapse into a road that makes sense, they need to know what their neighbor cells have collapsed into. Let’s add some code so, when a cell is observed, it also tells its neighbors what it became, so they know what direction they’ll need to link to. This is called the “propagation of constraints”.

Let’s watch it in action on a smaller grid.

All our roads connect nicely. After constraint propagation, our neighboring cells have eight possible states left. When observed, they’ll select one of those eight states randomly to continue the road. Let’s put this on the main grid.

Now it’s time to turn it up a notch. From the cells with the lowest number of possible states, let’s pick a random one.

// class Grid
  getLowestEntropyCell() {
    let candidates = []
    let lowestEntropy = Infinity
    for (let y = 0; y < this.height; y++) {
      for (let x = 0; x < this.width; x++) {
        const cell = this.cells[y][x]
        if (cell.observed) continue
        const entropy = cell.possibleTransforms.length
        if (entropy < lowestEntropy) {
          lowestEntropy = entropy
          candidates = [cell]
        } else if (entropy === lowestEntropy) {
          candidates.push(cell)
        }
      }
    }
    return candidates[Math.floor(Math.random() * candidates.length)]
  }

It’s time for the main loop. Grab the lowest entropy cell, observe it, and propagate the constraints. Repeat.

// class Grid
  step() {
    const cell = this.getLowestEntropyCell()
    cell.observe()
    this.propogateConstraints(cell)
  }

This is Wave Function Collapse!

Notice that when two neighboring cells are observed, any remaining corner cells reduce to only having four possible states. The low-entropy focus of the algorithm acts as a priority queue, always keeping the focus on critical junctions and corners where the constraints are the tightest.

Let’s speed things up.

It works! You can see continuous roads stretching far across dozens of cells. This is WFC realized.

Innovating Further

But it’s not the peak of WFC. This demonstration is barely scratching the surface. The rules for grid creation can get much more complex. Let’s look just a little deeper into our simulation and explore some of this complexity.

Examining the map our simulation just made, there seem to be lots of “islands” where bits of floating road exist isolated. This is for two reasons: one, the empty state [” “] shuts down further road expansion; and two, the single-branch states [“╴“, “╷“, “╶“, “╵“] frequently serve as dead ends. We want the road to continue more, with fewer disconnects.

To solve this problem, we can introduce weights.

// Weight by number of connections: fewer connections = less likely to be chosen.
const WEIGHTS = { 0: 0.05, 1: 0.35, 2: 1, 3: 1, 4: 1 }

// We rework the Cell’s observe() method to respect the Transform’s weight.
// class Cell
  observe() {
    this.observed = true

    // Imagine lining up every possible transform on a number line.
    // Each one takes up a slice as wide as its `weight`.
    // We pick a random point on that line — whichever slice we land
    // in, that's our transform.

    const totalWeight = this.possibleTransforms.reduce((sum, t) => sum + t.weight, 0)
    let pick = Math.random() * totalWeight
    for (const t of this.possibleTransforms) {
      pick -= t.weight
      if (pick <= 0) {
        this.state = t
        return
      }
    }
  }

With the empty state and single-direction states made much less common (but still possible), our road is much more connected. These weights also give us another set of levers to play with. We can fine tune these numbers to get all sorts of different maps.

WFC City, Here We Come

We built a road, but you can build anything with this. You could build a world map and only place river tiles next to lakes or other rivers. You could generate endlessly twisting and turning cave systems. Or, you could construct a dungeon maze with the perfect traps and dead ends. The world is your randomly generated oyster.

There’s a lot of fun to Wave Function Collapse. I hope you put this algorithm in your toolkit and implement it your own way. The applications are limitless for game design, city simulation, digital art, and whatever else needs good, structured randomness.