Procedural Generation: Techniques and Trade-offs
A practical survey of procedural generation: noise, BSP, cellular automata, wave function collapse, grammars, and how to keep control of the output.
By Velloreth
Procedural generation is content leverage. You spend effort once on an algorithm and get a hundred outputs, which is exactly why it appears in roguelikes, survival games, open worlds, and anything with a loot system.
It is also a bad deal when misapplied. The effort does not disappear — it moves from authoring to validating, because a generator that produces one bad level in fifty will produce thousands of bad levels, and your players will find them in the first week.
The field’s own research literature agrees on where the difficulty lies. Surveys of procedural dungeon generation in games repeatedly identify control as the central problem: a generator whose parameters do not map to designer intent produces content nobody wants, no matter how sophisticated the algorithm. The question is never “can I generate a dungeon” — it is “can I generate the dungeon I mean, and prove it works.”
Pick by shape of the output
Each family produces a characteristic structure, and choosing wrongly costs you the whole feature:
| Technique | Produces | Best for | Weak at |
|---|---|---|---|
| Perlin / simplex noise | Smooth continuous fields | Terrain, heightmaps, biomes | Discrete structures, guarantees |
| Binary space partitioning | Nested rectangular rooms | Classic dungeons, floor plans | Organic shapes, variation in feel |
| Cellular automata | Blobby, eroded regions | Caves, mines, craters | Anything requiring a plan |
| Drunkard’s walk / DLA | Branching winding paths | Cave systems, rivers, veins | Density control |
| Wave Function Collapse | Locally coherent tile arrangements | Building interiors, patterned terrain | Global structure, can fail outright |
| Grammar / production rules | Nested hierarchical structures | Vegetation, architecture, languages | Spatial constraints |
| Graph + Voronoi | Regions with connections | Overworlds, faction maps, biomes | Tile-level detail |
| Hand-authored prefabs | Exactly what you drew | Landmark set pieces, tutorial rooms | Variety by definition |
Real projects combine two or three. Noise gives you an overworld, WFC generates the buildings on it, and a hand-authored prefab anchors the tutorial.
Noise: fields, octaves, and interpretation
Perlin noise (introduced by Ken Perlin at SIGGRAPH 1985) produces a smooth pseudo-random scalar at any coordinate. Sample it on a grid, and you get a rolling field of values between roughly −1 and 1. Simplex noise is a later variant with better behaviour in higher dimensions and no directional artefacts; use whichever your library provides.
Raw noise is rarely the final content. You interpret it:
elevation = fbm(x, y, octaves=5)
moisture = fbm(x + 1000, y, octaves=4)
if elevation < 0.30 -> water
else if elevation < 0.34 -> beach
else if moisture > 0.60 -> forest
else if elevation > 0.75 -> mountain
else -> grass
Two concepts do the heavy lifting:
Fractal Brownian motion (fBm) sums several octaves of noise — each one higher frequency and lower amplitude than the last. One octave looks like gentle hills; five octaves look like terrain. The amplitude falloff is called persistence, and the frequency growth lacunarity.
Domain warping feeds noise coordinates through another noise sample first, which breaks the tell-tale uniform blobbiness of raw fBm and produces ridges and bays that look shaped rather than random.
Layering a second, independent noise field for a different property (moisture, temperature, fertility) is the standard trick for biomes. Two fields crossed give you a plausible world map; one field gives you an elevation contour and nothing else.
Discrete structures: BSP, automata, walks
Binary space partitioning recursively splits the map into halves along the longer axis until regions are room-sized, then carves a room inside each leaf and connects siblings with corridors. It is about fifty lines, guarantees connectivity if you connect as you split, and produces very legible, architectural dungeons. Its weakness is exactly its structure: every dungeon has the same nested-rectangle silhouette.
Cellular automata start with random fill, then repeatedly apply a rule such as “a cell with fewer than 4 wall neighbours becomes floor; with more than 5 becomes wall.” After several generations the noisy noise collapses into smooth-walled caves with occasional pillars. It is ideal when you want geology rather than architecture, and it is trivially tunable by changing thresholds and generation count.
Drunkard’s walk picks a walker, lets it wander until it has carved a target percentage of the map, producing long branching tunnels with dead ends. Diffusion-limited aggregation is a related variant that grows dendritic structures — good for roots, veins, crack networks.
Each is cheap. The interesting work is in what you do afterwards: connect unreachable pockets, place the entrance and exit far apart using a distance transform or Dijkstra map, and add doors where a room meets a corridor.
Wave function collapse: coherence without a plan
Wave Function Collapse, popularised by Maxim Gumin’s 2016 implementation and analysed by Karth and Smith as constraint solving in practice, is a different beast: you give it a set of tiles and adjacency rules (or a sample image to learn from), and it produces output where every local patch follows the rules.
The loop:
- Every cell starts with the full set of possible tiles.
- Pick the cell with lowest Shannon entropy (fewest weighted options remaining).
- Collapse it to one tile, chosen by weight.
- Propagate the consequence: neighbours lose every option incompatible with the choice, and if any neighbour now has zero options, you have a contradiction.
- Repeat until all cells are collapsed.
The appeal is coherence: bridges connect, pipes meet, roofs sit on walls. No other technique on this list gives you that for free.
The costs are real. Rules must be authored up front, which is a substantial design job. Contradictions happen — the standard responses are restart, or backtracking to an earlier cell, and restart is what most implementations ship with. And WFC enforces local rules; nothing in the algorithm knows that the dungeon needs a boss room, or that the exit must be reachable. Global constraints are your job, enforced outside the loop.
Grammars, graphs, and set pieces
Production rules generate structure by rewriting: TREE -> BRANCH(BRANCH(LEAF)). Context-free grammars describing a floor as ENTRANCE HALL* CORRIDOR ROOM (CORRIDOR ROOM)* EXIT give designers direct control over pacing at the cost of spatial reasoning — the grammar knows the order of rooms, not where they sit. Research on hybrid roguelike generation typically combines a grammar for the description with a spatial process for the layout, and that combination is the practical pattern.
L-systems are the plant-world special case: iterative string rewriting interpreted as turtle geometry. Ten rules and a recursion depth give you convincing undergrowth.
Graph methods build an abstract map first — nodes, connections, perhaps a Voronoi partition into regions — and only then place geometry. This is how you get an overworld with distinct biomes, or a level with a guaranteed critical path of a given length.
Prefabs are hand-authored chunks inserted into generated space. They are not a compromise; they are how you put authored beats, set pieces, and the tutorial into a generated world. The best generators use them liberally — a landmark every few minutes gives players a memory to navigate by, which pure noise never does.
Seeds, determinism, and reproducibility
A seed is only useful if the whole chain is deterministic:
- Seed the RNG once per generation run and pass it explicitly; never reach for a global RNG inside a deep function.
- Do not iterate unordered containers (hash maps) during generation — output order becomes platform-dependent and the same seed diverges.
- Store the seed with the save, not the output, when content is large; store the output when patches must not invalidate saves.
- Record the algorithm version alongside. Changing a threshold changes every downstream result for the same seed.
Determinism also buys you debugging: a bug report with a seed reproduces exactly, which is the difference between fixing a level and guessing at one.
Validation is part of the generator
The step most first implementations skip, and the one that decides whether the feature ships.
Reachability. Flood fill or Dijkstra from the entrance. Assert that the exit, every required objective, and every key-gated door are reachable with the keys available. Box2D-style determinism thinking applies: run it every time, in CI, over thousands of seeds — a generator that fails 0.2% of the time fails constantly in production.
Structural repair. When validation fails, prefer patching to regenerating: connect the orphaned region with a corridor, delete unreachable pockets, move the misplaced key. Regeneration from scratch hides the bug and can loop forever on impossible configurations.
Balance checks. Count rooms on the critical path, measure total walk distance, tally enemy budget and loot value per region. If your generator has no notion of difficulty, difficulty will be whatever the random roll produced — sometimes a trivial map, sometimes a wall in the third minute.
Anti-repetition. Track how often each template, room shape, and biome combination appears within a single play session. Two cheap counters surface the problem that playtesters will otherwise report as “it feels samey” three weeks later.
Beyond maps: loot, items, and names
Map generation gets the attention, but the same techniques apply to anything with structure.
Item generation is usually a grammar problem: a base type, a rarity, one to three affixes drawn from pools gated by level and slot, and a numeric roll within a range. The design work is in the gating — which affixes can coexist, what combinations break the economy, which stats are multiplicative and therefore must never appear together. Encode those rules as constraints on the pools, not as post-hoc filters, or you will spend your life patching an item that rolled three separate damage multipliers.
Names are the cheapest win available. A Markov chain trained on a list of names in your genre, or a syllable table with consonant–vowel patterns, produces an endless supply of plausible ones for a few dozen lines of code. Seed it per world so a faction name is stable.
Vegetation and clutter is where grammars and L-systems pay off. A tree is a recursive structure; a vine is a constrained random walk; grass is instanced with noise-driven density and rotation. None of this needs validation, which is why it is the ideal first project if you have never built a generator — you get to see output variation immediately and learn the RNG plumbing without risking an unwinnable level.
The shared lesson across all of them: separate the rules from the rolls. Rules are authored and reviewed; rolls are random. Projects that mix the two into one opaque function cannot be tuned, and tuning is most of what makes generated content feel designed.
The workflow that holds up
Generate loosely, then constrain, then repair, then decorate.
1. structure pass graph / BSP / noise → the plan
2. geometry pass realize the plan as tiles or meshes
3. validation reachability, objectives, budget
4. repair patch or cull until it passes
5. decoration pass clutter, props, lighting cues
6. memoize cache the result with its seed
Decoration last matters: dressing content that validation will throw away wastes the most expensive step. It also lets the decoration pass read the validated structure — props can follow the confirmed critical path.
Keep a designer-facing control layer on top. Not noiseFrequency: 0.42, but roomCount, deadEndRate, criticalPathLength, lootDensity, biomeMix. Parameters that map to intent are the difference between a tool your team uses and one they work around.
Where this leaves you
Procedural generation earns its place when the content is voluminous, structurally checkable, and acceptable to vary — and fails when quality depends on authored judgement. Be honest about which of your content categories fall on which side.
Start with one technique, add validation immediately, and only then add a second generator. The temptation is to reach for a more elaborate algorithm when the output feels weak; in practice, layering two simple generators plus a prefab pass and a proper validator produces better content than one sophisticated one ever will — because the sophistication you actually needed was never in the generation. It was in knowing whether the result was any good.