Markov chains

Why you need this

A side-scroller level is a sequence of columns. A dungeon crawl is a sequence of rooms. A path across an overworld is a sequence of chunks, each with a biome. In every case you want the next thing to depend on the current thing (forest tends to continue as forest, a gap is rarely followed by another gap) without writing rules by hand for every history. A Markov chain is the smallest model that does exactly that: one table, one random draw per step.

The idea

A Markov chain has a finite set of states, numbered $1, 2, \dots, N$. At each time step $t$ the chain is in one state, written $X_t$. The chain moves by rolling weighted dice whose weights depend only on the current state.

That last clause is the Markov property. In words: the future depends on the present, not on the past. As an equation,

$$P(X_{t+1} = j \mid X_t = i, X_{t-1}, \dots, X_1) = P(X_{t+1} = j \mid X_t = i).$$

Whatever happened before step $t$ is irrelevant once you know $X_t$. This is a modeling choice, not a law of nature, and later on this page you will see what it costs you.

Because the next-state probability depends only on the current state, the whole model fits in one transition matrix $A$, with

$$A_{ij} = P(X_{t+1} = j \mid X_t = i).$$

Row $i$ lists the probabilities of going from state $i$ to every state $j$. Since the chain must go somewhere, every row sums to 1: $\sum_j A_{ij} = 1$. Entries are between 0 and 1. A zero means that move never happens.

You also need somewhere to start. The initial distribution $\pi$ has $\pi_i = P(X_1 = i)$, and it sums to 1 as well. Often $\pi$ puts all its weight on one state ("levels always start on flat ground").

Sampling a sequence

To sample $T$ states:

1. Draw $u \sim \mathrm{Uniform}(0, 1)$ from a seeded generator. Pick $X_1$ by walking along $\pi$: the first state whose cumulative probability exceeds $u$.
2. For $t = 1$ to $T-1$: draw a fresh $u$, take row $X_t$ of $A$, and pick $X_{t+1}$ by walking along that row the same way.

"Walking along a row" means adding entries left to right until the running total passes $u$. For the row $(0.6, 0.3, 0.1)$ the running totals are $0.6, 0.9, 1.0$. A draw of $u = 0.72$ passes $0.6$ but not $0.9$, so it lands on state 2.

In JavaScript, using the same mulberry32 generator the demos use (states are indexed from 0 in code, from 1 in the math):

function mulberry32(seed) {
  let a = seed >>> 0;
  return () => {
    a = (a + 0x6d2b79f5) >>> 0;
    let t = a;
    t = Math.imul(t ^ (t >>> 15), t | 1);
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}
function sampleRow(row, u) {            // row sums to 1, u in [0, 1)
  let acc = 0;
  for (let j = 0; j < row.length; j++) { acc += row[j]; if (u < acc) return j; }
  return row.length - 1;                // guards against rounding at the tail
}
function sampleChain(A, pi, T, rand) {
  const X = [sampleRow(pi, rand())];
  for (let t = 1; t < T; t++) X.push(sampleRow(A[X[t - 1]], rand()));
  return X;
}
const A = [[0.6, 0.3, 0.1], [0.3, 0.6, 0.1], [0.2, 0.2, 0.6]];
console.log(sampleChain(A, [1, 0, 0], 20, mulberry32(42)).join(" "));

Same seed, same sequence, every time. That is what makes a map a seed plus a parameter file.

Worked example

Three biomes for an overworld path: state 1 is Field, 2 is Forest, 3 is Water.

From \ To	Field	Forest	Water	Row sum
Field	0.6	0.3	0.1	1.0
Forest	0.3	0.6	0.1	1.0
Water	0.2	0.2	0.6	1.0

Start in Field ($\pi = (1, 0, 0)$) and take six steps. Suppose the seeded generator hands out the draws in the second column.

Step	Draw $u$	Current row (running totals)	Lands on
$X_1$	(none)	$\pi$	Field
$X_2$	0.72	Field: 0.6, 0.9, 1.0	Forest
$X_3$	0.41	Forest: 0.3, 0.9, 1.0	Forest
$X_4$	0.95	Forest: 0.3, 0.9, 1.0	Water
$X_5$	0.63	Water: 0.2, 0.4, 1.0	Water
$X_6$	0.18	Water: 0.2, 0.4, 1.0	Field
$X_7$	0.55	Field: 0.6, 0.9, 1.0	Field

The path reads Field, Forest, Forest, Water, Water, Field, Field. Notice the runs: the 0.6 on the diagonal makes each biome tend to continue.

Where will the chain be after one step?

If you know the probabilities of being in each state at time $t$ as a row vector $p_t = (P(X_t = 1), \dots, P(X_t = N))$, the probabilities at $t+1$ are the vector times the matrix:

$$p_{t+1} = p_t A, \qquad (p_{t+1})_j = \sum_i (p_t)_i A_{ij}.$$

Take $p_1 = (0.5, 0.3, 0.2)$. Then

• Field: $0.5 \cdot 0.6 + 0.3 \cdot 0.3 + 0.2 \cdot 0.2 = 0.30 + 0.09 + 0.04 = 0.43$
• Forest: $0.5 \cdot 0.3 + 0.3 \cdot 0.6 + 0.2 \cdot 0.2 = 0.15 + 0.18 + 0.04 = 0.37$
• Water: $0.5 \cdot 0.1 + 0.3 \cdot 0.1 + 0.2 \cdot 0.6 = 0.05 + 0.03 + 0.12 = 0.20$

so $p_2 = (0.43, 0.37, 0.20)$, and it still sums to 1. Multiply by $A$ again for $p_3$, and so on.

The stationary distribution

Keep multiplying and $p_t$ stops changing. The vector it settles on is the stationary distribution $p^*$, defined by $p^* = p^* A$. For the matrix above it is $p^* = (0.4, 0.4, 0.2)$; check the Water entry: $0.4 \cdot 0.1 + 0.4 \cdot 0.1 + 0.2 \cdot 0.6 = 0.04 + 0.04 + 0.12 = 0.20$. This answers "how much water will my map have on average": over a long path, about 20% of the chunks are Water, regardless of where the path started. If your designer says "too much water", the stationary distribution tells you whether the matrix, not bad luck, is the cause. Any chain in which every state can eventually reach every other state, and which does not cycle in lockstep, has exactly one stationary distribution.

Authoring tips

The diagonal entry $A_{ii}$ is the probability of staying put, so it controls run length. Call the run length $L$ and $p = A_{ii}$. Each step, the run either ends (probability $1 - p$) or continues and the situation restarts, so $E[L] = 1 + p \, E[L]$, which rearranges to

$$E[L] = \frac{1}{1 - A_{ii}}.$$

With $A_{ii} = 0.6$ the average run is $1 / 0.4 = 2.5$ chunks. With $0.9$ it is $10$ chunks. With $0.95$ it is $20$. Set the diagonal from the run length you want, then spread the remainder of the row across the states you want to follow.

Off-diagonal zeros are your "never" rules: Water never directly touching Town, for instance. But a row of mostly zeros gives a chain that can get stuck or loop, so check that every state can reach every other.

Higher-order chains and why they blow up

If you want the next state to depend on the last two states, that is a second-order chain. It is still a Markov chain, but its state is the pair $(X_{t-1}, X_t)$, so with $N$ original states the table has $N^2$ rows. For $N = 6$ biomes: 36 rows of 6 entries. Third order: 216 rows. Every row is a distribution someone must author or fit from data, and the amount of data you need grows the same way. In practice, if first order is not enough, either add states that carry the memory you need ("Forest edge" as its own state) or move to a hidden Markov model, where a hidden state can remember what the visible one cannot.

In a map generator

• Layout, top-down. Walk a path of chunks and sample a biome per chunk. Chunk fill then draws tiles from that biome's subset.
• Layout, dungeon. Room type per room along the critical path: corridor, treasure, monster, puzzle, rest.
• Layout, side-scroller. Section type per column when the section type is also what you draw. Once the section type is hidden and only tiles show, you have an HMM.
• Regime over time. Each region carries a regime state (Calm, Contested, Depleted, Flooded) advanced by a chain every tick. The regime chains page is that use case in full.

Common mistakes

• A row that does not sum to 1. The sampler either never picks the last state or returns it far too often. Normalize every row when you load the file and assert on it.
• Diagonal too small. Biomes flicker every chunk and the map looks like confetti. Raise $A_{ii}$; the run-length formula tells you how far.
• Diagonal too large. One biome for the whole map. The stationary distribution looks fine but any single path is boring. Cap $A_{ii}$ around 0.9 for chunks a player crosses in seconds.
• Unreachable states. A state with a zero column is never entered after the first step. The designer added "Ruins" to the list and never saw one.
• Using Math.random(). The map is no longer reproducible from its seed. Every draw must come from the seeded generator.
• Confusing $p_t A$ with $A p_t$. The distribution is a row vector on the left. Multiplying on the wrong side gives numbers that do not sum to 1.

Cost

Sampling $T$ steps over $N$ states is $O(T \cdot N)$ time: one row scan of at most $N$ entries per step. Memory is $O(N^2)$ for the matrix plus $O(T)$ for the output. Neither hurts until $N$ reaches the hundreds, which only happens when you encode a higher-order chain as pairs or triples. Computing the stationary distribution by repeated multiplication is $O(k \cdot N^2)$ for $k$ multiplications, and a few dozen are usually enough.

Going further

• Hidden Markov models, when the thing you sample is not the thing the player sees.
• Regime chains, the same table driving change over time.
• Markov random fields, which extend "depends on the neighbor" from one predecessor to a grid.
• Absorbing states and expected time to absorption, for "how many rooms until the boss".
• The Perron-Frobenius theorem, if you want to know why the stationary distribution exists and is unique.