Procedural Generation
Noise, automata, and grammars that grow terrain, caves, dungeons, and plants from a seed.
Game Development
Before you start
Some lessons here build on lessons from other arcs: Minimum Spanning Trees: Kruskal and Prim.
- 1
Perlin Noisein progress
Games · Noise · ~20 minA lattice of random gradient arrows, four dot products, a fade curve, and a blend: smooth noise that is zero at every corner, never repeats, and follows from one seed.
- 2
Voronoi Noisein progress
Games · Noise · ~20 minOne feature point per lattice cell, nine cells scanned per pixel, the nearest two distances kept: bowls around each point, ridges between them, and flat cells painted by the nearest point.
- 3
Fractal Noise: Octavesin progress
Games · Noise · ~20 minOctaves of gradient noise summed, each finer by the lacunarity and fainter by the persistence: broad hills, then ridges on the hills, then rocks on the ridges, the grain of real terrain.
- 4
Terrain from Noisein progress
Games · Procedural Generation · ~20 minTwo fractal fields read as height and moisture, an island mask that drowns the edges, a sea level, and a ten-entry biome table: numbers become water, sand, grass, forest, rock, and snow.
- 5
Cellular Automatain progress
Games · Simulation · ~20 minA grid of cells, one born/survive rule, every cell deciding from its eight neighbours at once: Conway's Life with its gliders, Seeds that burns through everything, and a majority rule that smooths.
- 6
Caves from Cellular Automatain progress
Games · Procedural Generation · ~20 minFill a map with rock at random, run the majority rule a few passes, then flood-fill the chambers it left and keep the largest: a cave level a player can walk all of, from one seed.
- 7
Maze Generationin progress
Games · Procedural Generation · ~20 minA perfect maze is a spanning tree of the grid: carve one wall fewer than there are cells, never closing a loop. Three ways to pick the walls, three textures of maze.
- 8
Binary Space Partitioningin progress
Games · Simulation · ~20 minOne wall's line splits the map in two, and each half again, until every side is an empty convex region: a tree built once that gives the painter's order from any eye in a single walk, with no sorting.
- 9
BSP Dungeonsin progress
Games · Procedural Generation · ~20 minCut the map in two, and the halves in two, until the boxes are small; put a room in every leaf; then climb back up the tree joining a room of each half. Connected by construction.
- 10
Rooms and Corridorsin progress
Games · Procedural Generation · ~20 minScatter rooms at random and reject the ones that overlap; join the survivors by a minimum spanning tree over their centres, keep a few loops, and carve an L corridor per link. The roguelike level.
- 11
Wave Function Collapsein progress
Games · Procedural Generation · ~25 minEvery cell could be any tile; observe the least-entropy cell, collapse it to one, let the collapse propagate, repeat. Local socket rules alone grow a grid where every neighbour fits.
- 12
L-Systemsin progress
Games · Procedural Generation · ~20 minA string rewritten by the same rules every generation, then read by a turtle that steps, turns, and branches: plants, snowflakes, and dragon curves from a one-line grammar.
- 13
Shape Grammarsin progress
Games · Procedural Generation · ~25 minCut a lot into roof, floors, and ground; cut floors into tiles; let each tile choose window or wall. Three kinds of rule, applied breadth-first, derive a building facade from one box.