Hidden Markov models

Why you need this

In a side-scroller the designer thinks in sections: a flat run, a gap, a climb, a hazard. The player never sees a section label. They see tiles: flat ground, a pit, a step up, a spike, a flower. The label is a hidden state and the tile is what it emits. A hidden Markov model (HMM) is a Markov chain over the labels plus a second table saying what each label tends to show. The same structure appears whenever the thing you want to reason about is one layer below the thing you observe.

The idea

There are two sequences. The hidden chain $X_1, X_2, \dots, X_T$ takes values in $N$ states, and moves by an ordinary Markov chain with transition matrix $A$, $A_{ij} = P(X_{t+1} = j \mid X_t = i)$, rows summing to 1. The observations $O_1, \dots, O_T$ take values in $M$ symbols. Each observation depends only on the hidden state at the same time, through the emission matrix $B$:

$$B_{jk} = P(O_t = k \mid X_t = j), \qquad \sum_k B_{jk} = 1.$$

Row $j$ of $B$ is "what state $j$ looks like". Together with the initial distribution $\pi$, $\pi_i = P(X_1 = i)$, the full parameter set is $(\pi, A, B)$: $N$ numbers, $N \times N$ numbers, and $N \times M$ numbers.

Generation is "step the chain, then emit": pick $X_1$ from $\pi$, emit $O_1$ from row $X_1$ of $B$, pick $X_2$ from row $X_1$ of $A$, emit $O_2$ from row $X_2$ of $B$, and so on. Two uniform draws per time step.

The joint probability of one particular pair of sequences is a product, one factor per arrow in the picture:

$$P(X_1..X_T, O_1..O_T) = \pi_{X_1} B_{X_1 O_1} \prod_{t=2}^{T} A_{X_{t-1} X_t} B_{X_t O_t}.$$

With $N = 2$, $T = 2$, $\pi = (0.8, 0.2)$, $A_{11} = 0.7$, $B_{11} = 0.9$, $B_{12} = 0.1$: the path (1, 1) emitting (symbol 1, symbol 2) has probability $0.8 \cdot 0.9 \cdot 0.7 \cdot 0.1 = 0.0504$.

The three classical problems

Once you have an HMM, three questions come up, and each has a standard algorithm.

Evaluation. How likely is this observation sequence under this model, $P(O_1..O_T \mid \pi, A, B)$? Summing the product above over every hidden path is $N^T$ terms. The forward algorithm gets the same number in $O(T N^2)$ by filling a table one column at a time. Use it to score a candidate level, or to compare two models.

Decoding. Given the observations, which hidden path $X_1..X_T$ is most likely? The Viterbi algorithm is the forward table with a max in place of each sum, plus backpointers. Use it to label the columns of an existing level with section types.

Learning. Given observation sequences and nothing else, what $A$ and $B$ (and $\pi$) explain them best? Baum-Welch starts from a guess, computes how often each transition and emission probably happened, re-estimates the tables from those expected counts, and repeats. Use it to fit the generator to levels a designer approved.

Worked example

A side-scroller generator with hidden section types and emitted tiles.

States ($N = 4$): 1 Run, 2 Gap, 3 Climb, 4 Hazard. Symbols ($M = 5$): 1 flat, 2 pit, 3 step, 4 spike, 5 flower.

Transition matrix $A$:

From \ To	Run	Gap	Climb	Hazard	Row sum
Run	0.60	0.15	0.15	0.10	1.00
Gap	0.70	0.10	0.10	0.10	1.00
Climb	0.40	0.10	0.40	0.10	1.00
Hazard	0.50	0.20	0.10	0.20	1.00

Emission matrix $B$:

State \ Tile	flat	pit	step	spike	flower	Row sum
Run	0.70	0.00	0.05	0.05	0.20	1.00
Gap	0.10	0.80	0.05	0.05	0.00	1.00
Climb	0.20	0.00	0.70	0.05	0.05	1.00
Hazard	0.20	0.10	0.10	0.60	0.00	1.00

Initial distribution $\pi = (1, 0, 0, 0)$: every level opens on a Run.

Generate six columns. Each column takes a transition draw $u_A$ (walk along the current row of $A$) and an emission draw $u_B$ (walk along the new state's row of $B$). Running totals for the rows you will need: Run in $A$ is 0.60, 0.75, 0.90, 1.00; Gap in $A$ is 0.70, 0.80, 0.90, 1.00; Climb in $A$ is 0.40, 0.50, 0.90, 1.00. Run in $B$ is 0.70, 0.70, 0.75, 0.80, 1.00; Gap in $B$ is 0.10, 0.90, 0.95, 1.00, 1.00; Climb in $B$ is 0.20, 0.20, 0.90, 0.95, 1.00; Hazard in $B$ is 0.20, 0.30, 0.40, 1.00, 1.00.

Column	$u_A$	Hidden $X_t$	$u_B$	Tile $O_t$
1	(from $\pi$)	Run	0.52	flat
2	0.44	Run	0.88	flower
3	0.67	Gap	0.35	pit
4	0.21	Run	0.09	flat
5	0.83	Climb	0.61	step
6	0.97	Hazard	0.74	spike

Column 3: from Run, $u_A = 0.67$ passes 0.60 but not 0.75, so Gap. Then $u_B = 0.35$ passes 0.10 but not 0.90, so pit. The level reads flat, flower, pit, flat, step, spike; the player sees the second row of the table and never the first.

When the hidden layer earns its keep

Be honest with yourself here. If you author $A$ and $B$ by hand and only ever generate, the hidden layer buys you nothing you could not get from a plain Markov chain whose states are (section, tile) pairs. That chain has $N \cdot M$ states, 20 in the example, and its transition matrix is just $A_{ij} B_{jk}$ written out. Same output, one table instead of two.

The hidden layer pays off in two situations.

1. You want to fit the model from approved levels. A designer paints or approves twenty levels in the tool. You do not have section labels for them, only tiles. Baum-Welch fits $A$ and $B$ from the tiles alone, and the hidden states become whatever grouping explains the tiles best. A flat chain over pairs cannot do this, because it needs the pair labels it does not have.
2. You want to infer the hidden state from what is observed. A player's action stream (jump, jump, idle, attack) is the observation; their "mode" (exploring, fighting, stuck) is hidden. An existing hand-built level's tiles are the observation; its section structure is hidden. The forward algorithm and Viterbi answer these, and there is no equivalent for a chain with no hidden layer.

If neither applies today, ship the plain chain and keep the HMM in reserve. Promoting later is cheap: the sampler is the same two-draw loop.

Why not 2D

An HMM has exactly one predecessor per step: $X_t$ depends on $X_{t-1}$ and nothing else. A cell in a tile grid has four neighbors (von Neumann) or eight (Moore), and the constraints run in every direction at once. If you force a grid through a chain by scanning rows left to right, top to bottom, each cell only knows about the cell to its left (and, with tricks, the one above). The result is horizontal streaks and visible row seams: the top edge of a lake lines up nicely, the bottom edge does not, because nothing below was consulted. The right tools for grids are Markov random fields, which generalize "depends on the neighbor" to all neighbors at once, and Wave Function Collapse, which fills a grid under adjacency constraints in all four directions. Keep HMMs for things that are truly sequences: columns, rooms, encounters, and time.

In a map generator

• Layout, side-scroller. The primary generator for the side-scroller packs on the hub page. Hidden state is the section type; emission is the platform tile and decor for that column. The parallax backdrop is a per-state choice, so it is part of the emission too.
• Scoring. Before exporting, run the forward algorithm on the generated tiles and reject levels whose log-probability is far below typical. This catches degenerate runs that the sampler produced fairly but a designer would not approve.
• Import. Hand a hand-built level to Viterbi to recover its section labels, then count transitions to seed $A$ and $B$ before running Baum-Welch.
• Regime over time. The regime chain starts as a plain chain and is promoted to an HMM once there are play logs to fit.

Common mistakes

• Rows of $B$ that do not sum to 1. The emission draw falls off the end of the row and returns the last tile every time. Every column after a Hazard is a flower.
• Emissions that overlap too much. If Run and Climb both emit flat 70% of the time, decoding cannot tell them apart and Baum-Welch merges them. Hidden states must look different, or they are not worth having.
• Treating hidden states as playable data. The exporter writes section labels into the tile layer. The hidden row is for the tool, not the game.
• Forgetting $\pi$. The code draws the first column from the Run row of $A$ instead, which is a different distribution, and every level starts as if it followed a Run. Harmless here because $\pi$ happens to be all Run, and a silent bias in any model where it is not.
• Forcing a grid through the chain. Row seams, as above. If you can see stripes, you used the wrong tool.

Cost

Generating $T$ columns is $O(T \cdot (N + M))$: one row scan of $A$ and one of $B$ per step, with $N$ the number of hidden states and $M$ the number of tile symbols. Memory is $O(N^2 + N M)$ for the tables. Generation never hurts. The three algorithms are where the cost lives: forward and Viterbi are $O(T N^2)$ each, and Baum-Welch is that again per iteration, per training sequence.

Going further

• The forward algorithm, for scoring and for filtering the current hidden state.
• The Viterbi algorithm, for recovering the hidden path.
• Baum-Welch, for fitting the tables from tiles alone.
• Rabiner's 1989 tutorial on hidden Markov models in speech recognition, which set the notation this cluster uses.
• Markov random fields and Wave Function Collapse, for the 2D case this page declines.