Don't restart, backtrack

If you have ever looked at a procedural game world and wondered how the terrain tiles fit together so seamlessly, chances are some variant of constraint-based generation is behind it. 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 to use BMS

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.