Stream Quest: BSP Dungeon Generator

Overview

A standalone, drop-in dungeon generator built as a contracted deliverable for RichardStampDev's game Stream Quest, developed solo in about a week. Binary space partitioning carves a bounded area into rooms, which are then merged, connected, and populated into a fully connected, guaranteed-solvable dungeon. Every object in the dungeon, from doors to enemies to loot, is a placeholder so Richard can drop his own prefabs directly into the generator.

The Problem

The hardest problem was guaranteeing that every generated dungeon was actually solvable. Locked doors and their keys are placed after the room layout and its connections already exist, which makes it easy to accidentally seal a key behind the very door it's meant to open, or create a chain of locked doors with no valid order to unlock them in.

That sat on top of two earlier problems the generator also had to solve. Binary space partitioning splits the bounded area into a tree of rooms, but the resulting room-adjacency graph isn't guaranteed to be fully connected on its own, especially after small rooms get merged together. And even with both of those solved, a specific unlucky seed could still occasionally violate some other constraint, like not leaving enough boundary rooms to place a start and an end.

The Solution

Keys are placed using a reachability-expansion algorithm: starting from the entrance, it walks outward through unlocked doors only, and only places a key once the room in front of its lock is already confirmed reachable. Locks are resolved in shuffled passes so the exact order and key placement varies between seeds, and the algorithm throws an explicit exception if it ever detects a dependency cycle instead of silently generating a broken dungeon.

Connectivity is guaranteed by running a minimum spanning tree (Kruskal's algorithm with union-find) over the room adjacency graph after merging, so every room is reachable through exactly one path before any doors get placed.

For everything else, the whole generation pipeline runs inside a retry loop with deterministic reseeding: if a layout ever fails a constraint, it's thrown out and regenerated from a new seed automatically, up to 30 attempts, instead of shipping a broken dungeon.

Result

A standalone dungeon generator delivered as a contracted deliverable, built solo in about a week. Every run produces a fully connected, guaranteed-solvable dungeon with locked doors, keys, and budgeted enemy and loot placement, using placeholder assets that drop out in favor of Richard's own prefabs.