Procedural generation lets a game create levels, maps or items through algorithms instead of by hand. It is what makes every run of a roguelike different from the last, and what allows some games to offer enormous worlds without anyone drawing them cell by cell. It is not, however, a shortcut to avoid level design: it is a different way of doing it, in which you design the rules instead of the result.
The seed: random but reproducible
At the heart of every generator is a pseudorandom number generator (PRNG). Starting from an initial value, the seed, it produces a sequence that looks random but is entirely determined: the same seed always generates the same sequence.
This property is invaluable:
- players can share a seed to play the same world;
- a bug in a generated level can be reproduced exactly;
- in multiplayer you only need to send the seed, not the whole map;
- a save can store the seed instead of the entire level.
To keep things reproducible you must use a generator dedicated to level generation, separate from the one used for gameplay events such as critical hits. Otherwise, an enemy firing one extra shot changes the sequence and the next level comes out different.
Noise for terrain and landscapes
Pure random numbers produce something like television static: each point is independent of its neighbours. For terrain, clouds or vegetation distribution you need values that vary continuously. That is the role of coherent noise functions, such as Perlin noise, developed by Ken Perlin in the 1980s, and its variants.
A noise function takes coordinates and returns a value, for example between −1 and 1, that changes gradually as the coordinates vary. Adding several layers, or octaves, at increasing frequencies and decreasing amplitudes produces more natural shapes:
height = 0
amplitude = 1
frequency = 1
for octave from 1 to 5:
height += noise(x * frequency, y * frequency) * amplitude
amplitude *= 0.5
frequency *= 2
Low octaves define the large shapes, hills and valleys; high ones add detail. Thresholds on height assign terrain types: water below a certain value, sand just above, then grass, rock, snow.
Caves with cellular automata
For organic-looking caves, a cellular automaton works very well: a grid in which each cell changes state based on its neighbours:
- fill the grid randomly, with about 45% solid cells;
- for a few iterations, each cell becomes solid if at least five of its eight neighbours are solid, otherwise it becomes empty;
- after four or five passes the initial noise has turned into caves with rounded walls.
A further pass is essential: checking connectivity. With a flood fill you identify separate empty regions; you keep only the largest or dig corridors to connect them.
Dungeons of rooms and corridors
For more structured levels with rectangular rooms, there are several methods.
Random placement
Generate rooms of random size at random positions, discard those that overlap, and connect them in order with «L»-shaped corridors. It is simple and works well for small maps.
Binary space partitioning
Recursively split the map in two, alternating horizontal and vertical cuts, until you get areas of the desired size. Place a room in each leaf, then connect sibling rooms while climbing back up the tree. The result is an even distribution with no overlaps.
Room graphs
Place the rooms, build a graph connecting them, for example all nearby pairs, and derive a minimum spanning tree to guarantee that everything is reachable with the fewest corridors. Adding back a few discarded edges then creates loops, which make exploration less linear.
Generating playable levels
A generated level can be technically valid and still terrible to play. Some rules help:
| Problem | Countermeasure |
|---|---|
| Unreachable exit | Check with pathfinding after generation |
| Random difficulty | Place enemies based on distance from the entrance |
| Monotonous levels | Mix hand-made pieces with generated parts |
| Extreme results | Regenerate with another seed if certain criteria are not met |
The mixed approach is very widespread: hand-designed rooms or blocks, assembled by an algorithm. It combines the quality of human design with the variety of generation.
In short
- Procedural generation designs rules instead of individual levels.
- A PRNG with a dedicated seed makes results random yet reproducible.
- Multi-octave coherent noise produces natural terrain and landscapes.
- Cellular automata, binary partitioning and room graphs generate caves and dungeons.
- Connectivity checks, difficulty rules and hand-made pieces make levels truly playable.
