Procedural Dungeon Generation
Dungeon generation was the first widely adopted form of procedural content in games, and it remains one of the most active areas of research and experimentation. The core challenge is generating a spatial layout that is structurally valid (all areas are reachable, no overlapping geometry), gameplay-viable (appropriate difficulty, interesting decisions, fair resource distribution), and aesthetically coherent (the dungeon looks and feels like a real place, not a random scattering of boxes).
Choose the Right Algorithm for Your Dungeon Style
Each dungeon generation algorithm produces a distinctive visual style and gameplay feel. The choice of algorithm should match the kind of experience you want to deliver.
Binary Space Partitioning (BSP) produces clean, architectural dungeon layouts with rectangular rooms connected by straight corridors. The algorithm recursively divides the available space with alternating horizontal and vertical splits until each partition is small enough to contain a single room. Rooms are placed within each leaf partition with random padding from the walls, and corridors connect sibling partitions through the tree hierarchy. BSP dungeons feel man-made, structured, and orderly, making them ideal for castle interiors, office buildings, space stations, and other constructed environments.
Cellular automata produce organic, cave-like environments with smooth walls, natural pillars, and irregular chambers. The algorithm starts with a grid where roughly 45% of cells are randomly filled (wall) and the rest are empty (floor). A smoothing rule runs for 4 to 6 iterations: cells with 5 or more filled neighbors become filled, and cells with fewer than 4 filled neighbors become empty. The result resembles a natural cave system carved by water over millennia. Cellular automata dungeons work well for natural caverns, underground rivers, alien hives, and other organic environments.
Room placement generates rooms of random sizes and positions them on the map without overlapping. Collision is handled either by rejection (discarding rooms that overlap existing ones) or by separation physics (pushing overlapping rooms apart until none overlap). After placement, a graph algorithm connects rooms with corridors. This approach offers the most flexibility in room shapes and sizes, and the connection graph gives direct control over the dungeon's topology.
Random walk (drunkard's walk) carves out cells by starting at a point and moving in random directions, clearing cells along the path. The walk continues until a target percentage of the map is excavated. The result is a winding, organic tunnel system without distinct rooms. Variations include directed walks that bias toward unexplored areas, multiple simultaneous walkers for branching tunnels, and walks that periodically open up into wider chambers.
Implement Room and Corridor Generation
Regardless of algorithm, most dungeon generators work on a 2D grid where each cell is either a wall or a floor. The grid representation makes collision detection simple (check if a cell is already carved), rendering straightforward (each cell maps to a tile), and pathfinding easy (standard grid-based pathfinding algorithms work directly on the dungeon grid).
For BSP generation, start with the full map as the root rectangle. Choose a split direction (horizontal or vertical, often alternating) and a split position (random, biased toward the center to avoid very thin partitions). Recurse on both halves until each partition meets a minimum size constraint. Place a room in each leaf partition with random offsets from the walls. Connect sibling rooms by carving a corridor from a random point on one room's edge to a random point on the sibling's edge, typically using an L-shaped or Z-shaped path.
For room placement, generate each room with a random width and height within specified bounds. Place rooms one at a time, checking for overlap with all previously placed rooms and adding a minimum gap between them. If a room overlaps, either reject it and try a new random position, or push it away from the colliding room using a separation vector. After all rooms are placed, build a Delaunay triangulation of room centers to determine potential corridor connections.
Corridor carving between rooms typically uses one of two approaches. The simpler method carves an L-shaped corridor: move horizontally from one room's center to the other room's x-coordinate, then move vertically to reach the destination. The more sophisticated method uses A* pathfinding on the grid, with wall cells having higher traversal cost than empty cells. Pathfinding-based corridors follow more natural routes and can avoid carving through other rooms.
Room shapes need not be rectangular. Circular rooms carved by testing each cell against a radius threshold, irregular rooms generated by cellular automata within a bounded region, and L-shaped or T-shaped rooms created by combining overlapping rectangles all add variety to the dungeon's visual character.
Verify Connectivity and Add Loops
A dungeon where some rooms are unreachable is broken. Every generation algorithm must guarantee or verify connectivity before the dungeon is considered complete.
BSP generation guarantees connectivity by construction because corridors connect every pair of sibling partitions in the tree, creating a path from every leaf to every other leaf. Room placement algorithms that use a minimum spanning tree for corridor connections also guarantee connectivity, since a spanning tree by definition connects all nodes.
For cellular automata and random walk generators, connectivity must be verified after generation. Flood fill from the player's starting position identifies all reachable floor cells. Any disconnected regions (floor cells not reached by the flood fill) need to be connected to the main area. The standard approach finds the closest pair of cells between the main region and each disconnected region, then carves a tunnel between them.
Pure tree connectivity (whether from BSP or spanning trees) produces dungeons with no loops, meaning there is exactly one path between any two rooms. This creates dead ends and forces backtracking, which can be frustrating for players. Adding extra corridors creates loops that give players alternate routes and reduce backtracking. A common technique builds the minimum spanning tree for guaranteed connectivity, then adds back 10-20% of the Delaunay triangulation edges that were not in the spanning tree. Each added edge creates a loop, and the percentage controls how many alternate routes exist.
Door placement at corridor-room junctions controls the pacing and tactical flow of the dungeon. Doors create chokepoints where the player transitions between spaces, and they naturally segment the dungeon into distinct areas. Placing doors at every junction makes the dungeon feel compartmentalized and tactical. Omitting doors creates an open, flowing layout where encounters can spill across multiple rooms.
Place Gameplay Elements
A dungeon layout is just the skeleton. Gameplay elements, including enemies, items, keys, locks, traps, treasure, and objectives, transform the layout into an actual game level.
The dungeon's graph structure (rooms as nodes, corridors as edges) provides the foundation for gameplay placement. The graph distance from the entrance determines difficulty progression: rooms near the entrance contain weaker enemies and basic items, while rooms far from the entrance contain stronger enemies and better rewards. This distance-based scaling creates a natural difficulty curve without manual tuning for each generated dungeon.
Key-and-lock puzzles use the graph structure directly. Place a locked door on a critical path corridor, then place the required key in a room that is accessible without passing through that door. The graph's tree structure (from the spanning tree) makes it easy to identify which rooms can reach which, ensuring the player can always find the key before encountering the lock. Multiple key-lock pairs can be layered by processing them in sequence, each constraining the placement of subsequent pairs.
Enemy placement should consider room size (large rooms can hold groups of enemies, small rooms suit ambushes or single strong enemies), distance from the last safe area (giving the player recovery time between encounters), and line-of-sight from the room entrance (enemies positioned behind cover or around corners create more interesting tactical situations than enemies standing in the open).
Item and treasure placement follows risk-reward principles. The most valuable items should be in the hardest-to-reach locations: behind optional locked doors, at the end of dangerous dead-end branches, or guarded by the toughest enemies. Common consumables like health potions should appear along the critical path at regular intervals, creating a baseline resource flow that prevents the player from being starved or flooded.
Polish with Decorations and Theming
The final step transforms a functional layout into an atmospheric space. Decoration placement, wall variation, lighting, and thematic consistency turn abstract grid cells into a place that feels real and tells a story.
Wall tiles should vary based on context. A wall cell adjacent to a floor cell is a visible wall face that needs a textured tile. A wall cell surrounded by other wall cells is hidden interior geometry that can use a simple fill. Corner cells where two wall faces meet need corner-specific tiles. Autotiling systems handle this classification automatically by examining each wall cell's neighbors and selecting the appropriate tile from a lookup table.
Decorative props placed using the dungeon's graph structure reinforce theming. A dungeon themed as an abandoned mine might have broken minecarts in corridors, support timbers at room entrances, ore veins in wall tiles, and collapsed sections where the ceiling has fallen. These decorations are placed procedurally based on simple rules: props near walls, special tiles at room entrances, random scatter within rooms, and themed objects in dead-end rooms.
Lighting creates atmosphere and guides the player. Torches or sconces placed at regular intervals along corridors provide baseline illumination. Key rooms like the boss chamber or treasure vault receive distinctive lighting (brighter, colored, or flickering) that signals their importance before the player enters. Dark rooms with reduced visibility create tension and encourage cautious exploration.
Environmental storytelling, placed procedurally, gives the dungeon a narrative context. Scattered bones near a trap suggest previous victims. Discarded equipment near the boss room hints at failed adventurers. Graffiti or signs placed at corridor junctions provide flavor text. These small details accumulate to create the impression of a place with history, even though every element was placed by an algorithm.
Procedural dungeon generation combines spatial algorithms for layout, graph-based logic for connectivity and gameplay placement, and context-aware decoration for atmosphere. The choice of core algorithm determines the dungeon's visual character, but the polish layers of gameplay elements and thematic decorations are what make a generated dungeon feel like a designed game level.