Roguelike: BSP Dungeons

Build structured dungeon layouts with Binary Space Partitioning — recursively subdivide space, place rooms in leaves, and connect them with corridors.

No login required.

Chapter 1

Partitioning Space

BSP recursively subdivides the map into leaves. You'll define the root partition, add a size guard to stop splitting, choose a split axis, and recurse into children.

Binary Space Partitioning guarantees non-overlapping rooms -- every room gets its own leaf, so dungeons look structured, not chaotic.

Loading game...

Click the game window to interact with it

What You'll Build

You will implement Binary Space Partitioning, the algorithm behind classic roguelike dungeons. BSP takes the full map rectangle and recursively cuts it in half — sometimes horizontally, sometimes vertically — until every piece is too small to split further. Those final pieces (leaves) each get a room placed inside them with random size and position. Then you walk back up the tree and connect each pair of sibling rooms with an L-shaped corridor. Because the tree structure ensures every branch connects, every room is reachable without needing flood fill. The result is well-spaced rooms with corridors between them — the layout most people picture when they think "roguelike dungeon."

How it works

1
Define the root partition
The root covers the entire map as a single Rect2i. It stores position, size, and pointers to left/right children (initially null). Every partition in the BSP tree follows this same structure.
2
Check if the partition is small enough to stop
If both dimensions are smaller than MIN_PARTITION * 2, this partition is a leaf — it can't be split further without making children too small. This is where recursion stops.
3
Choose a split axis and position
Split the longer dimension to keep partitions roughly square. Pick a random split position using randi_range(), constrained so both children are at least MIN_PARTITION wide. This randomness is what makes each dungeon layout different.
4
Recurse into both children
Create left and right child partitions from the split, then call the split function recursively on each. This builds a binary tree — each level doubles the number of partitions until all leaves are small enough for rooms.
5
Place rooms in leaf partitions
Leaves (partitions with no children) each get a room. The room is a randomly-sized Rect2i placed within the leaf's bounds with padding so it doesn't touch the partition edges. Because leaves don't overlap, rooms never overlap either.
6
Connect siblings with corridors
Walk back up the tree and connect each pair of sibling rooms with an L-shaped corridor. Find the center of each room, draw a horizontal line from one center, then a vertical line to the other. The tree structure guarantees that connecting all siblings makes every room reachable.

Learning Goals

✓Recursive subdivision of a 2D rectangle into a binary tree of partitions
✓Leaf detection — partitions with no children are where rooms go
✓Random room placement within leaf bounds using randi_range() with padding
✓L-shaped corridor carving between sibling rooms using their center points
✓Minimum size constraints (MIN_PARTITION) to prevent single-tile slivers

GDScript Concepts in This Part

GDScript Randomness Practicerandf_range, randi_range, RandomNumberGenerator, pick_random, rand_weighted, and shuffle bags. Master randomness for spawns, loot, procedural content, and fair variation.GDScript Arrays & Loops PracticeLearn GDScript arrays and loops in Godot 4 with game-ready patterns: iterating with indices, safe removal, sorting enemies by distance, and choosing Array vs typed vs packed arrays.GDScript Resources PracticeCustom Resource classes, @export arrays, load/save .tres, and how to fix shared-mutation bugs with duplicate() and local_to_scene (including array caveats). Tested with Godot 4.3+.GDScript Procedural Generation PracticeLearn procedural map generation in Godot 4: drunkard's walk, cellular automata, BSP dungeons, noise terrain, flood fill connectivity, and seeded RandomNumberGenerator. Build roguelike dungeon generators in GDScript.

Tips

✨Stop subdividing when a partition is below MIN_PARTITION * 2 in both dimensions — the leaf needs room for an actual room plus padding.
✨Connect rooms by drawing a corridor from the center of one sibling's room to the center of the other. Horizontal-then-vertical creates clean L-shapes.
✨Tune MIN_PARTITION to control dungeon density. Smaller values produce more, smaller rooms. Larger values produce fewer, bigger rooms with longer corridors.

What You'll Build

How it works

Define the root partition

The root covers the entire map as a single Rect2i. It stores position, size, and pointers to left/right children (initially null). Every partition in the BSP tree follows this same structure.

Check if the partition is small enough to stop

If both dimensions are smaller than MIN_PARTITION * 2, this partition is a leaf — it can't be split further without making children too small. This is where recursion stops.

Choose a split axis and position

Split the longer dimension to keep partitions roughly square. Pick a random split position using randi_range(), constrained so both children are at least MIN_PARTITION wide. This randomness is what makes each dungeon layout different.

Recurse into both children

Create left and right child partitions from the split, then call the split function recursively on each. This builds a binary tree — each level doubles the number of partitions until all leaves are small enough for rooms.

Place rooms in leaf partitions

Leaves (partitions with no children) each get a room. The room is a randomly-sized Rect2i placed within the leaf's bounds with padding so it doesn't touch the partition edges. Because leaves don't overlap, rooms never overlap either.

Connect siblings with corridors

Walk back up the tree and connect each pair of sibling rooms with an L-shaped corridor. Find the center of each room, draw a horizontal line from one center, then a vertical line to the other. The tree structure guarantees that connecting all siblings makes every room reachable.

Learning Goals

✓Recursive subdivision of a 2D rectangle into a binary tree of partitions

✓Leaf detection — partitions with no children are where rooms go

✓Random room placement within leaf bounds using randi_range() with padding

✓L-shaped corridor carving between sibling rooms using their center points

✓Minimum size constraints (MIN_PARTITION) to prevent single-tile slivers

Tips

✨Stop subdividing when a partition is below MIN_PARTITION * 2 in both dimensions — the leaf needs room for an actual room plus padding.

✨Connect rooms by drawing a corridor from the center of one sibling's room to the center of the other. Horizontal-then-vertical creates clean L-shapes.

✨Tune MIN_PARTITION to control dungeon density. Smaller values produce more, smaller rooms. Larger values produce fewer, bigger rooms with longer corridors.