🏰 Procedural Dungeon Generator

Generate game levels with three classic algorithms. A seeded LCG makes every map reproducible — the same seed always yields the same dungeon.

0
Rooms created
0
Floor tiles
0%
Floor %
–
Longest path
–
Connectivity
Three algorithms. BSP recursively splits the map into sub-regions, drops one room into each leaf, then connects sibling rooms with corridors (tree splits shown as the overlay). Rooms drops non-overlapping rooms and links them with L-shaped corridors along a nearest-neighbour spanning chain. Cave random-fills the grid, then applies the 4-5 cellular-automata rule (a cell becomes wall if ≥5 of its 8 neighbours are walls) for organic caverns. Start (green) and exit (red) mark the two most distant floor regions; the longest path is a BFS flood distance and connectivity is the share of floor tiles reachable from the start.

About this simulation

Written by MySimulator Team · Reviewed by MySimulator Editorial Review

Last updated: 5 July 2026

This simulation builds a game-level map on the fly using three switchable algorithms: Binary Space Partitioning (BSP), which recursively splits the map and drops a room into each leaf; a random-rooms generator that scatters non-overlapping rectangles and links them along a nearest-neighbour spanning chain; and a cellular-automata cave that starts from random noise and smooths it with the classic 4-5 rule. A seeded LCG (linear congruential generator) drives every random choice, so the same seed always reproduces the exact same map.

🔬 What it shows

A grid-based dungeon rendered on canvas, where tiles are coloured by type: dark for walls, green-tinted for room floors, blue-grey for corridors, and grey for organic cave floor. After generation, a double breadth-first search finds the two most distant floor tiles (marked green for start, red for exit) and reports the longest path length and what percentage of floor tiles are reachable from the start — a direct measure of map connectivity.

🎮 How to use

Switch between BSP, Rooms and Cave with the algorithm buttons. Adjust map size (24–80 tiles per side), room count target, and min/max room size for BSP and Rooms; for Cave, control the initial fill percentage and the number of smoothing passes. Enter a numeric seed or click "New seed" to explore different layouts, and toggle the structure overlay to see the BSP split lines and room outlines.

💡 Did you know?

The cellular-automata cave rule used here — a tile becomes wall if 5 or more of its 8 neighbours are walls, otherwise floor — is the same "4-5 rule" popularised for roguelike cave generation because a handful of smoothing passes reliably turns random noise into connected, organic-looking caverns without any pathfinding logic at all.

Frequently asked questions

What is Binary Space Partitioning (BSP) dungeon generation?

BSP generation recursively splits a rectangular area into two smaller rectangles, alternating between horizontal and vertical cuts, until each region is small enough to hold one room. A room is then placed inside each leaf node, and rooms are connected with straight or L-shaped corridors following the order they were created. This produces dungeons with a natural tree-like structure and few overlapping rooms, and it is one of the most widely used techniques in roguelikes because it guarantees non-overlapping rooms without any collision checking.

How does the random-rooms algorithm avoid overlapping rooms?

The generator repeatedly proposes a room of random width and height at a random position, then checks it against every previously placed room using axis-aligned bounding-box overlap (with a one-tile buffer). If it overlaps an existing room, the attempt is discarded and a new one is tried, up to a capped number of attempts. Once enough non-overlapping rooms exist, they are linked using a greedy nearest-neighbour chain — at each step the closest not-yet-connected room is joined to the growing network with an L-shaped corridor, similar in spirit to building a minimum spanning tree.

What is the cellular-automata rule used for the cave algorithm?

The cave starts as a grid randomly filled with walls at a chosen percentage (35–60%). It is then smoothed for a number of passes: in each pass, every tile counts how many of its 8 surrounding neighbours are walls, and becomes a wall itself if 5 or more neighbours are walls, otherwise it becomes floor. Repeating this several times erodes isolated noise and grows small wall clusters into smooth, organic cave walls — the same principle behind Conway's Game of Life, applied to level generation instead of simulating living cells.

How does the seeded random number generator make maps reproducible?

The simulation uses a linear congruential generator (LCG): a simple formula that repeatedly transforms an internal 32-bit state using multiplication and addition with fixed constants, producing a deterministic stream of pseudo-random numbers. Because the generator is reset to the same seed value every time "Generate" is pressed, entering the same seed with the same algorithm and parameters always produces an identical dungeon layout, which is why the seed field and "New seed" button let you save or reproduce a specific map.

What do the connectivity and longest-path statistics mean?

After a dungeon is generated, the simulation runs a breadth-first search from one floor tile to find the farthest reachable tile, then runs a second BFS from that tile to find the true diameter of the connected region — this is the classic "double BFS" technique for finding the longest shortest-path in an unweighted graph. The two endpoints become the start and exit markers, the path length between them is shown as "Longest path", and "Connectivity" reports what percentage of all floor tiles are reachable from the start, which flags whether the cave or dungeon has isolated, unreachable pockets.