Game dev
Saved & recent

Dungeon generation

Related terms: BSP, binary space partitioning, rooms and corridors, random walk

A classic recipe uses binary space partitioning. Take the whole map as one rectangle and split it in two. Split each half again, and repeat. Put a room inside every final piece. Then join sibling pieces with corridors, working back up the tree.

Rooms can never overlap and every room is reachable. Other recipes: a random walk that digs as it wanders, cellular automata for caves, or hand-made rooms stitched together at random.

Further reading
Noor Shaker et al.: Constructive Generation Methods for Dungeons and Levels
room partition corridor
Seven dashed splits make eight partitions. Each gets one room, and corridors join sibling partitions as the generator works back up the tree.

View in the full Game dev collection