ExtendedSource checked

Binary Space Partitioning Dungeon Generation

Builds dungeon rooms by recursively splitting space into partitions.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Procedural Generation
Difficulty: Intermediate
Family: Dungeon Generation
Tier: Extended
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 0
Relationships: 3
Code example: Not ready
Visualization: Ready
Aliases: BSP Dungeon Generation

Overview

BSP Dungeon Generation divides a map into rectangular regions, places rooms in leaves, and connects them with corridors.

Core Concepts

generated structureroom layouttree structuredungeon generationseeded variationrule expansionspatial structure

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n)

When to Use

Use Binary Space Partitioning Dungeon Generation when you need to recursively partition map space.
Use it for dungeon layouts with inputs like map rectangle.
Use it when repeatable content can be produced from compact rules, parameters, and seeds.
Use it when the Dungeon Generation tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when authored control matters more than variation or replayability.
Avoid it when the required output is not rooms and corridors.

What It Does

Recursively partitions map space
Places rooms and connects sibling regions

Use Cases

Dungeon layouts
Roguelike maps
Structured level generation

Inputs

Map rectangle
Split rules
Room size constraints

Outputs

Rooms and corridors

Pseudocode

1.Start with the whole map rectangle
2.Split rectangles until they are small enough
3.Place a room in each leaf rectangle
4.Connect rooms between sibling partitions
5.Carve rooms and corridors into the map

Canonical Example

Input: seed = 42, size = 8x8
Output: generated map, pattern, or noise field
Explanation: Binary Space Partitioning Dungeon Generation: The algorithm expands a small set of rules and random choices into structured content.

Implementation Notes

Keep the input contract explicit: Map rectangle; Split rules; Room size constraints.
Use this step as the implementation spine: Start with the whole map rectangle.
Then preserve the next state change: Split rectangles until they are small enough.
Expose seed and parameters so results can be reproduced and tuned.

Common Pitfalls

BSP layouts are easy to control but can look grid-like without variation.
Letting random choices create disconnected, invalid, or impossible-to-use output.
Returning rooms and corridors without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Spatial Primitive & Sweep-Line Canvas

Show rectangles splitting and rooms appearing in leaf partitions.

Step 1 of 5: Start with the whole map rectangle

bsp-rooms

Notes

Binary Space Partitioning Dungeon Generation operates in O(n log n) time and O(n) space within the Dungeon Generation family. Often compared with Drunkard's Walk and Cellular Automata Cave Generation.

Sources (1)

What each reference supports for this entry.

Procedural Content Generation in Games

Book

Procedural-generation reference supporting Binary Space Partitioning Dungeon Generation constraint solving, constructive generation, terrain, dungeon, or stochastic content workflow.

Open source