Topic hub
Dynamic map generation
How a game grows a level from a seed and a parameter file, keeps it changing while you play, and which technique does which job.
The problem
You own a library of game art: side-scroller packs with layered backgrounds and platform tiles, and top-down tilesets for ground, forest, town, and dungeon. Placing those tiles by hand is slow, and every game that wants a level ends up with its own one-off generator. You want a map to be a seed plus a parameter file: type the same seed, get the same map; turn a knob, get a family of related maps; and let the map keep changing while the game runs.
"Dynamic" means two different things here, and a good generator does both:
- Generated from a seed rather than authored tile by tile.
- Changing over time. Regions shift between regimes such as calm, contested, depleted, or flooded, and the visible map responds.
This cluster teaches every technique a generator like that needs, and every piece of math underneath those techniques, down to first-year college level. Each page names what you should read first. Follow those links downward until you land on something you already know, then read back up.
The pipeline
Every page in this cluster points back to this five-stage picture.
| Stage | Question it answers | Techniques that live here |
|---|---|---|
| 1. Catalog | What tiles do I have and how may they touch? | Tilemaps and autotiling, Graphs and grids |
| 2. Layout | What is the coarse shape of this map? | Markov chains, Hidden Markov models, Noise fields, Graph grammars and L-systems |
| 3. Fill | Which exact tile goes in each cell? | Wave Function Collapse, Cellular automata, Markov random fields, Noise fields |
| 4. Regime over time | How does a region change while you play? | Regime chains, promoted to HMMs and fitted with Baum-Welch once you have play logs |
| 5. Export | How does a game read the result? | Layered generation covers chunking, seams, and per-chunk seeds |
Two of these stages are about structure (layout and fill) and one is about time (regime). The other two are plumbing that every generator needs regardless of algorithm.
Which technique for which job
The right technique follows the shape of the thing being generated.
Anything that is really one-dimensional. A side-scroller level is a sequence of columns. A dungeon crawl is a sequence of rooms. A run of encounters is a sequence. For sequences, a Markov chain is the simplest tool that works: pick the next thing based only on the current thing, using a table of probabilities. When the thing you sample is not the thing the player sees, for example a "section type" that then emits platform tiles, you have a hidden Markov model. The HMM also gives you three algorithms for free: the forward algorithm to score a sequence, Viterbi to recover the hidden sections from the tiles, and Baum-Welch to learn the tables from examples.
Anything that is genuinely two-dimensional. A tile on a grid has four or eight neighbors, not one predecessor. Forcing a grid through a sequence model produces visible row-by-row seams. The 2D tools are Wave Function Collapse, which learns which tiles may sit next to which from a small example and fills a region without contradictions; cellular automata, which grow caves and blobs by applying a local rule repeatedly; and Markov random fields, the general theory that says what "each cell depends only on its neighbors" means mathematically. Noise fields are the cheapest of all: a smooth random height function, sliced by thresholds into water, sand, grass, and rock.
Anything with a story structure. Locks and keys, a boss room that must come after the key room, a critical path with optional branches. That is a graph problem before it is a tile problem, and graph grammars and L-systems generate the graph.
Anything that changes while you play. Give each region a state and a table of how it moves between states each tick. That is a regime chain. It is a Markov chain again, so the same code serves layout and time.
Putting the layers together. Real generators run coarse to fine. A Markov chain or noise field assigns a biome to each chunk of a grid, then WFC fills each chunk with tiles from that biome's subset, then a regime chain animates the chunks over time. Layered generation covers how to hand seeds down the layers so that any chunk can be regenerated on its own, and how to hide the seams.
The math underneath
The techniques rest on a small set of first-year ideas. None of them needs calculus.
| You need | For |
|---|---|
| Probability basics | Everything. Conditional probability is the whole idea behind a Markov chain. |
| Random variables and distributions | Sampling a next state from a row of a table. |
| Matrices and vectors | Transition tables are matrices, and multiplying by one advances the chain one step. |
| Logarithms and underflow | Multiplying 200 probabilities together produces zero on a computer. Logs fix it. |
| Dynamic programming | Forward, Viterbi, and Baum-Welch are all the same trick: fill a table one column at a time. |
| Entropy | Wave Function Collapse picks the cell with the fewest remaining choices. Entropy is how it measures that. |
| Constraint satisfaction | WFC is a constraint solver with a random tie-breaker. |
| Graphs and grids | Neighborhoods, adjacency, and why a grid is a graph. |
| Interpolation and smoothing | Noise fields are random numbers on a lattice, smoothed between lattice points. |
| Pseudo-random numbers | A seed is only a seed if the generator is deterministic. |
| Tilemaps and autotiling | The data format everything reads and writes. |
A concrete target
To keep the pages honest, the whole cluster uses one running example: a design tool that reads a purchased asset library and writes maps a game can load. It has three generators behind one interface.
| Asset family | Primary generator | Why |
|---|---|---|
| Side-scroller packs | HMM over columns | Hidden state is the section type: flat run, gap, climb, platform stack, hazard, rest. Emissions are the tile and decor in that column. The parallax backdrop rides along as a per-state choice. |
| Top-down tilesets | WFC within chunks, Markov chain over biomes across chunks | The tilesets carry adjacency rules that WFC learns from a small painted example. A coarse chunk grid picks biomes; WFC fills each chunk from that biome's tiles. |
| Both | Regime chain per region | Each chunk or section carries a state advanced per tick. Emissions are spawn rates, decor swaps, weather, palette swaps. |
A map in this tool is exactly a seed and a parameter file. Same seed, same file, same map. Every knob is an entry in a transition matrix or a tile weight.
How to read this cluster
The learning path below is sorted so that each row depends only on the rows above it. If you already know probability and matrices, start at Markov chains. If you want the 2D side first, start at Graphs and grids and go straight to Cellular automata, which needs the least machinery of any technique here. If you are here for the HMM question specifically, read Markov chains, then Hidden Markov models, then Viterbi, and you will know enough to decide for yourself.
Learning path
Each row depends only on rows above it. Read top to bottom, or jump to a technique and follow its "Before this" links downward.
- prerequisiteGraphs and gridsA tile grid is a graph whose vertices are cells and whose edges are neighbor relations, which is why every 2D generator talks about neighborhoods and connected regions.
- prerequisiteDynamic programmingFill a table one column at a time so every cell reuses the column before it, the single pattern behind the forward algorithm and Viterbi
- prerequisiteProbability basicsSample spaces, events, conditional probability, independence, the chain rule, and Bayes' rule, worked through with dice and a small tile chunk
- prerequisiteInterpolation and smoothingHow to fill in values between known points on a line and on a square, and why a small curve with flat ends removes the creases that plain averaging leaves behind.
- prerequisiteMatrices and vectorsVectors as lists, matrices as grids, the two products a Markov chain needs, and why a row vector times a row-stochastic matrix is one step of the chain
- prerequisitePseudo-random numbersA seeded generator turns one integer into a repeatable stream of random-looking numbers, which is the only reason a map can be stored as a seed instead of as tiles.
- prerequisiteConstraint satisfactionVariables with shrinking sets of allowed values, rules between neighbors, and a search that backtracks or restarts when a set runs empty, which is the machinery under Wave Function Collapse.
- prerequisiteRandom variables and distributionsDiscrete random variables, probability mass functions, categorical distributions, expectation, and how to sample any of them with a single uniform draw
- prerequisiteLogarithms and underflowWhy multiplying hundreds of probabilities gives zero on a computer, and how adding logs, comparing in log space, and the log-sum-exp trick fix it
- prerequisiteTilemaps and autotilingTile sheets, tile ids, layered 2D arrays, and the neighbor bitmasks that pick the right edge art, which together form the data every generator in this cluster reads and writes.
- techniqueCellular automataFill a grid with random noise, apply one neighbor-counting rule to every cell a few times, and the noise organizes itself into caves with rounded walls and no straight lines.
- techniqueGraph grammars and L-systemsGrow the structure of a level, its rooms, locks, keys, and branches, by rewriting symbols and graphs with rules, before any tile is placed.
- techniqueNoise fieldsA smooth random function of position, built from a lattice of seeded values and interpolation, then sliced by thresholds into water, sand, grass, and rock.
- prerequisiteEntropyShannon entropy as one number for how unsure a distribution is, computed for small examples, and why Wave Function Collapse uses it to choose the next cell
- techniqueMarkov chainsA table of "given this, what comes next" probabilities that you sample one step at a time to grow a sequence of biomes, rooms, or level sections.
- techniqueHidden Markov modelsA Markov chain you cannot see, driving tiles you can, plus the three algorithms that score, decode, and fit it.
- techniqueWave Function CollapseFill a grid with tiles so that every neighboring pair is one the algorithm has seen in a small example, by repeatedly resolving the most constrained cell and propagating the consequences.
- techniqueMarkov random fieldsWhat "each cell depends only on its neighbors" means on a grid, why you sample it with Gibbs sweeps instead of computing it, and why the HMM tricks do not survive the move from a chain to a grid.
- techniqueForward algorithmScore an observation sequence under a hidden Markov model, and read off the current hidden state along the way, in one left-to-right pass.
- techniqueViterbi algorithmRecover the single most likely hidden path behind an observation sequence by filling the forward table with max instead of sum and walking backpointers.
- techniqueLayered generationRun the pipeline coarse to fine, biome per chunk then tiles per chunk then a regime per chunk over time, with seeds handed down so any chunk can be rebuilt alone and the seams do not show.
- techniqueRegime chainsGive every region a state that a Markov chain advances each tick, and let that state drive spawns, yields, weather, and decor so the map keeps changing while you play.