Don't restart, backtrack

One of my favourite games when I was younger was Spore, the fact that you could play "god" and rise a being from a cell to a multigalaxy "monster" was one thing that made it fascinating, the other one was that in Spore the universe was generated on the fly. It used procedural generation. “Procedural” just means the game uses algorithms/rules to generate content instead of hand-designing everything. Since then I loved these kind of games with infinity possibilities, but never really dived to understand how this is done.

Last year there was another weird game that was a big success, Blue Prince, a mystery game where you navigate a mansion that you build yourself by placing room tiles. Every room is a procedural puzzle.

Spore uses deformable meshes and heightmaps—a different, more involved approach than what I'll describe here. What connects games like Blue Prince (and many tile-based procedural worlds) is something else: constraint-based generation. If you've ever wondered how those tiles fit together so seamlessly, that's usually how. The idea is simple: define which tiles can sit next to which, then let an algorithm figure out a valid arrangement. The most popular version of this idea is Wave Function Collapse (WFC). It works beautifully on small grids but has a critical flaw that makes it struggle at scale.

Breakout Model Synthesis (BMS) fixes that flaw with one key insight: when something goes wrong, don't throw everything away. Just fix the part that broke.

Wave function collapse in 30 seconds

WFC borrows its name from quantum mechanics. Every cell in a grid starts in a superposition of all possible tile types. The algorithm repeats three steps:

1. Observe — pick the cell with the fewest remaining possibilities (lowest entropy)
2. Collapse — randomly assign it one of its valid tiles
3. Propagate — remove tile options from neighboring cells that would violate adjacency rules

When propagation finishes without issues, go back to step 1. When every cell has exactly one tile, you are done.

The contradiction problem

Sometimes propagation paints the algorithm into a corner. A cell ends up with zero valid possibilities, every tile it could be would violate at least one neighbor's constraint. This is a contradiction.

WFC's answer to a contradiction is brutal: restart the entire grid from scratch. Every cell goes back to full superposition and the algorithm tries again from zero. On a 10x10 grid with simple rules, restarts are cheap. On a 64x64 grid with complex tilesets, you might restart dozens or hundreds of times before getting lucky with a valid arrangement. Each restart throws away all the useful partial progress that was perfectly fine everywhere except around the point of failure.

This is the bottleneck. The algorithm does not distinguish between "this corner has a problem" and "everything is broken." It treats every contradiction as a global failure.

Enter BMS: local backtracking

Breakout Model Synthesis, introduced by Oskar Stalberg and formalized by researchers exploring constraint-based procedural content generation, replaces the global restart with stochastic local backtracking.

When a contradiction occurs at cell (r, c), BMS:

1. Identifies a small region around the contradiction (typically within Manhattan distance 2-3)
2. Softens that region: resets those cells back to superposition, clearing their resolved tiles
3. Re-constrains the softened cells based on their still-resolved neighbors at the boundary
4. Continues the normal observe-collapse-propagate loop

The rest of the grid is untouched. The algorithm only redoes work in the neighborhood that actually failed. This is why it is called "breakout" — instead of getting stuck and restarting, the algorithm breaks out of local dead-ends.

See it in action

The simulation below runs BMS on a 24x24 grid with five terrain tile types. Each tile has adjacency rules: water can only border water or sand, sand can border water/sand/grass, and so on. Watch for the moments when a cell turns red (contradiction) and its neighborhood reverts to gray (softening) before the algorithm continues.

How to use the simulation:

• Play runs the algorithm continuously at the selected speed
• Step advances one iteration at a time so you can watch each collapse and propagation
• Reset clears the grid and starts fresh
• The speed slider controls the delay between automatic steps (left = faster, right = slower)

Pay attention to the status indicator. When it says "Local backtracking (softening)" you are seeing BMS do its thing: resolving a contradiction locally instead of restarting globally.

The algorithm

Here is the core BMS loop in pseudocode:

function bmsGenerate(grid, tileset, rules) {
  // Initialize all cells to full superposition
  for (const cell of grid.cells) {
    cell.tile = null;
    cell.possibilities = [...tileset];
  }

  while (grid.hasUnresolvedCells()) {
    const cell = selectLowestEntropy(grid);

    if (cell.possibilities.length === 0) {
      // Contradiction at selection time
      softenRegion(grid, cell, 2);
      continue;
    }

    cell.tile = randomChoice(cell.possibilities);
    const contradiction = propagateConstraints(grid, rules);

    if (contradiction) {
      // BMS: local backtracking
      softenRegion(grid, contradiction.cell, 2);
      // Do NOT restart — just continue the loop
    }
  }

  return grid;
}

function randomChoice(array) {
  return array[Math.floor(Math.random() * array.length)];
}

function selectLowestEntropy(grid) {
  let best = null;
  let bestCount = Infinity;

  for (const cell of grid.cells) {
    if (cell.tile !== null) continue;
    // Random jitter breaks ties to avoid top-left sweep bias
    const score = cell.possibilities.length + Math.random() * 0.1;
    if (score < bestCount) {
      bestCount = score;
      best = cell;
    }
  }

  return best;
}

function softenRegion(grid, center, radius) {
  const softened = grid.cells.filter(
    (cell) => manhattanDistance(cell, center) <= radius
  );

  // Reset softened cells to full superposition
  for (const cell of softened) {
    cell.tile = null;
    cell.possibilities = [...ALL_TILES];
  }

  // Re-constrain softened cells from boundary neighbors
  for (const cell of softened) {
    for (const neighbor of grid.getNeighbors(cell)) {
      if (neighbor.tile !== null) {
        cell.possibilities = cell.possibilities.filter((tile) =>
          rules.canBeAdjacent(tile, neighbor.tile)
        );
      }
    }
  }
}

The critical difference from WFC is in the contradiction handler. WFC would have grid = createEmptyGrid() there. BMS has softenRegion(), a surgical reset of only the cells involved.

When BMS is a good fit

BMS shines in scenarios where:

• Large grids: The probability of contradiction grows with grid size. Local backtracking avoids the exponential restart cost.
• Complex tilesets: More tile types and stricter adjacency rules mean more contradictions. BMS handles them gracefully.
• Real-time generation: Games that generate terrain on the fly cannot afford to restart. BMS offers more predictable completion times.
• Streaming/chunked generation: You can generate a grid in chunks, and BMS can resolve contradictions at chunk boundaries without regenerating everything.

For small grids with simple rules where contradictions are rare, plain WFC is perfectly fine. The overhead of tracking regions and softening is not worth it when restarts are cheap.

Limitations

BMS is not a silver bullet:

• No termination guarantee: In theory, the algorithm could soften the same region forever without making progress. In practice, the stochastic nature of tile selection means it almost always converges, but there is no formal proof of termination for arbitrary tilesets.
• Softening radius is a heuristic: Too small and you might not clear enough state to escape the dead-end. Too large and you lose more progress than necessary. The right radius depends on your tileset's constraint density.
• Local optima: Because BMS never sees the global picture, it can produce locally valid but globally suboptimal arrangements. If you need specific global properties (e.g., "exactly one lake"), you need additional constraints on top.
• Bias in output: The softening-and-retry mechanism can introduce subtle biases in the distribution of generated patterns compared to uniform WFC sampling. Areas that were softened may show different statistical properties than areas that resolved cleanly on the first pass.

Despite these limitations, BMS represents a practical and meaningful improvement over WFC for real-world procedural generation. It turns an algorithm that works on toy problems into one that works on production-scale grids.

I found it fascinating to learn more about it and will certainly dive into more algorithms of these sort, because although it was originally developed for games it can find applications in other areas.