Combinatorial Terrain

How simple adjacency rules generate diverse landscapes

A small set of terrain tiles and adjacency rules produces coherent landscapes through constraint propagation. There's no region-filling algorithm, no multi-scale noise — just local preferences combining multiplicatively until the grid resolves into terrain that makes visual sense. The technique is constraint satisfaction in disguise: each tile wants certain neighbors, and the cascade of those wants becomes the world.

The Constraint Model

Each terrain type has adjacency rules defining which neighbors it accepts and with what probability. These rules form a matrix: for every pair of terrain types (A, B), there's a weight indicating how likely A is to appear next to B. A weight of zero means forbidden; higher weights mean more likely. This is not binary allow/deny but a soft constraint system where rules combine multiplicatively.

const RULES = {
  GRASS: {
    GRASS: 10, FOREST: 8, SAND: 6, WATER: 4, MOUNTAIN: 1, SNOW: 0
  },
  MOUNTAIN: {
    GRASS: 1, FOREST: 2, SAND: 3, WATER: 0, MOUNTAIN: 10, SNOW: 8
  },
  // ... rules for each terrain type
};

The zero entries are the key insight: snow never borders grass or water because mountain peaks only connect to other mountains or snow. These forbidden adjacencies create the visual coherence we recognize as "terrain" — the rules encode geographic logic that grass belongs near forests, sand near water, and mountains at high elevations.

Entropy Minimization

Rather than filling tiles in scanline order, the algorithm always picks the cell with lowest entropy — the cell with the fewest valid options. This is the same principle behind Wave Function Collapse: collapse the most constrained cells first so that early decisions propagate their constraints to neighbors while those neighbors are still empty and can adapt.

function findLowestEntropy() {
  let minEntropy = Infinity;
  let candidates = [];
  
  for (let y = 0; y < ROWS; y++) {
    for (let x = 0; x < COLS; x++) {
      if (grid[y][x] === null) {
        const possibilities = getPossibleTiles(x, y);
        let count = Object.values(possibilities).filter(p => p > 0).length;
        
        if (count < minEntropy) {
          minEntropy = count;
          candidates = [{ x, y, possibilities }];
        } else if (count === minEntropy) {
          candidates.push({ x, y, possibilities });
        }
      }
    }
  }
  return candidates[Math.floor(Math.random() * candidates.length)];
}

If we filled cells randomly, we'd quickly paint ourselves into contradictions — a cell surrounded by water and mountain would have zero valid options. Entropy minimization prevents this by always working on the cell whose fate is most determined by its neighbors, letting the cascade of constraints resolve naturally.

Weighted Random Selection

Once we know what tiles are possible, we choose randomly but weighted by the combined probability. This keeps the generation stochastic rather than deterministic: the same seed placement can produce dramatically different results based on which way the weighted coin flips during propagation.

function weightedChoice(possibilities) {
  const keys = Object.keys(possibilities);
  let total = Object.values(possibilities).reduce((a, b) => a + b, 0);
  if (total === 0) return keys[0];
  
  let random = Math.random() * total;
  for (const key of keys) {
    random -= possibilities[key];
    if (random <= 0) return key;
  }
  return keys[0];
}

The weighting comes from multiplying constraints across all filled neighbors. If a cell has a water neighbor weight 7 and a mountain neighbor weight 0 for sand, sand gets weight 0. If both neighbors weight sand at 6 and 10, the combined weight is 60 — much higher than a cell with only one strong supporter. Multiplication rather than addition is crucial: it means a single zero cancels all support, creating the hard constraints that define terrain logic.

Constraint Propagation

When a tile is placed, it doesn't immediately determine all its neighbors. Instead, it narrows the possibility space for adjacent empty cells. Each empty cell consults all its filled neighbors, multiplies their preferences, and arrives at a distribution. The cell isn't locked in until entropy minimization selects it — at which point it makes a weighted choice, becomes fixed, and propagates its constraints outward.

function getPossibleTiles(x, y) {
  const possibilities = {};
  for (const type in TILES) possibilities[type] = 1;
  
  const neighbors = getNeighbors(x, y);
  for (const neighbor of neighbors) {
    if (neighbor.tile !== null) {
      const allowed = RULES[neighbor.tile];
      for (const type in possibilities) {
        possibilities[type] *= (allowed[type] || 0);
      }
    }
  }
  return possibilities;
}

This is why the algorithm "wants" to form coherent regions: placing a forest tile makes forest more likely next to it, which makes forest more likely beyond that, creating the clustered patterns we see. The rules don't say "create forests" — they say "forests prefer forests" — and the propagation turns that preference into structure through the cascade of constrained choices.

Wave Expansion from Seed

Generation starts with a single seed at the center: a randomly chosen terrain type. From there, the wave expands outward by always collapsing the cell with lowest entropy, which naturally tends to be on the frontier where constraints from multiple filled neighbors concentrate. This creates the wave-like growth pattern visible when watching the animation.

// Place initial seed at center
const seedX = Math.floor(COLS / 2);
const seedY = Math.floor(ROWS / 2);
const seedTypes = Object.keys(TILES);
grid[seedY][seedX] = seedTypes[Math.floor(Math.random() * seedTypes.length)];

// Animate: repeatedly find lowest entropy and collapse
function animate() {
  if (step()) setTimeout(animate, delay);
}

The frontier cells have filled neighbors (constraints) but are still empty (high uncertainty about what to become). Interior cells are already fixed. So entropy minimization naturally produces the wave: it's not programmed to fill outward, it's just that frontier cells are always more constrained than distant empty cells and always less constrained than already-placed cells. The wave is an emergent property of the algorithm's bias toward constrained decisions.

What This Reveals

Local rules produce global coherence. No cell knows it's building a forest or a coastline — each one only knows what its immediate neighbors prefer. The terrain emerges from the interaction of simple adjacency constraints cascading through the grid. This is why procedural generation works: you don't encode "forest" as a region-filling algorithm, you encode "forest tiles like being near forest tiles" and let the cascade build the region for you.

The same principle underlies constraint satisfaction in combinatorics, Markov random fields in statistics, and the actual physics of crystallization — local preferences creating large-scale order. The terrain generator is a toy version of what happens whenever coherent structure emerges from decentralized decisions.