Maze generation
Algorithms — recursive backtracker, Prim's, Kruskal's, Wilson's — that carve a grid into a perfect maze with exactly one path between any two points.
A "perfect" maze is a spanning tree over the grid: fully connected, no loops, exactly one route between any pair of cells. The recursive backtracker (a depth-first walk) produces long winding corridors; Prim's and Kruskal's give shorter, more branching ones; Wilson's (loop-erased random walk) yields a completely unbiased maze. Each method stamps its own feel on how the passages read.
If the maze should have loops or rooms, you knock out walls deliberately afterward. Jamis Buck's writeups turned the algorithms into common knowledge among game makers.