How to Guarantee Every Room in a Generated Dungeon Is Reachable

The generator says it made nine rooms. You play the floor and find four. The other five are there, complete with loot and enemies, sealed in rock with no corridor that reaches them. Or worse, the boss is in one of them, and the run cannot be finished.

A room nobody can reach is the most common way a procedural dungeon breaks, and it is easy to prevent. This is part 3 of a series that builds one generator, pass by pass.

The first idea most people have is to join each room to its nearest neighbour. Close rooms get short corridors, which sounds tidy. It also strands rooms almost every time.

Here is why. Nearest is a choice each room makes for itself. Rooms 1, 5 and 7 can all pick each other, because each is closest to one of the others, and nobody in that group ever picks a room outside it. You get islands: little groups joined to each other and to nothing else.

On seed 214, nearest-neighbour joining makes three islands of three rooms. The entrance's island reaches only rooms 0, 3 and 4, so six rooms are lost. Across seeds 1 to 500, it strands at least one room on 449 of them.

A flood fill, also called a breadth-first search, is how a program walks a map. Start at one cell and give it the number 0. Every floor cell next to it gets 1. Every unvisited floor cell next to those gets 2, and so on, ring by ring, until there is nothing new to reach.

Each number is the shortest walk to that cell, in steps. Any floor cell that never got a number is somewhere the player cannot go. Amit Patel's introduction to A* has a lovely animated version of the same idea.

Step through it below. Start with Nearest neighbour, watch where the fill stops, then try the other two.

The chain. Join room 1 to room 0, room 2 to room 1, room 3 to room 2, and so on. Every room is joined to one that was joined before it, all the way back to the entrance, so the fill always gets through. This is what the 3D dungeon course does. On seeds 1 to 500 of this series' generator, the chain never lost a room.

The cost is length. A chain follows the order rooms happened to be placed in, which zigzags across the map. On seed 214 its 8 corridors add up to 105 cells of corridor.

The spanning tree. Start a group with the entrance. Find the room outside the group that is closest to any room inside it, join those two, and add it to the group. Repeat until every room is in. This is Prim's algorithm for a minimum spanning tree: every room is connected, there are no loops, and the total length is as short as possible. On seed 214 it also uses 8 corridors, but they add up to 54 cells.

Both use exactly one corridor fewer than the number of rooms, which is the fewest you can use and still join everything. In the plan, that leaves exactly one route between any two rooms, unless two corridors happen to cross. Block one corridor and everything behind it is cut off.

A level with exactly one route everywhere plays like a tree of dead ends. You walk to the end of a branch, then walk all the way back. Most generators add a few extra corridors on purpose, to make loops.

TinyKeep's generator, as A Adonaac describes on Game Developer, builds a minimum spanning tree and then adds back some of the edges it left out: 15% in the original, 8 to 10% in Adonaac's version. Bob Nystrom's Rooms and Mazes gives extra connectors "a slight chance of being opened up" for the same reason. The tree guarantees reachability. The extras make it fun.

Sometimes you inherit a generator that strands rooms, or you want a rule like nearest-neighbour for how it looks. You do not need to start over. Repair it:

1. Flood fill from the entrance.
2. Split the rooms into reached and lost.
3. Find the closest pair: one reached room, one lost room. Join them.
4. Flood fill again. Stop when nothing is lost.

Each repair joins at least one whole island, so it always finishes. On seed 214 it adds 2 corridors. Across seeds 1 to 500 it never needed more than 4. Press Repair lost rooms in the demo to see the new corridors outlined.

• Props block the way. A layout can be fully joined and still be unplayable once a crate lands in a one-cell doorway. Flood fill the finished level, with props counted as solid. How to test whether a generated level is playable covers it.
• Locked doors and keys. A fill that walks through locked doors will say the boss room is reachable before you have the key. Fill with locked doors as walls, from the entrance, and the key must be in the area it reaches.
• One-way drops. In a platformer you can drop down a ledge you cannot climb back up. A fill that ignores direction will say you can. Fill along the moves the player can really make.
• Diagonal gaps. If the player can move diagonally, two floor cells that touch only at a corner may be joined in your game but not in a 4-way fill. Use the same neighbours your movement uses.

walk_distances() returns the number of steps to every cell, or -1 where the fill never went. blocked lets you pass in props, so the same function checks a decorated level:

func walk_distances(start: Vector2i, blocked: Dictionary = {}) -> PackedInt32Array:
    var dist := PackedInt32Array()
    dist.resize(grid.size())
    dist.fill(-1)
    if not is_floor(start) or blocked.has(start):
        return dist
    dist[index(start)] = 0
    var frontier: Array[Vector2i] = [start]
    var head := 0
    while head < frontier.size():
        var cell := frontier[head]
        head += 1
        for dir in NEIGHBORS_4:
            var next := cell + dir
            if not is_floor(next) or blocked.has(next):
                continue
            if dist[index(next)] != -1:
                continue
            dist[index(next)] = dist[index(cell)] + 1
            frontier.append(next)
    return dist

frontier is a queue: cells are added at the back and read from the front, using head as a bookmark instead of removing them. Reading in that order is what makes it a ring-by-ring fill. A room counts as reached if any of its cells got a number:

func room_reached(room_index: int, dist: PackedInt32Array) -> bool:
    var rect := rooms[room_index]
    for y in range(rect.position.y, rect.end.y):
        for x in range(rect.position.x, rect.end.x):
            if dist[index(Vector2i(x, y))] != -1:
                return true
    return false

The spanning tree joins rooms by the distance between their centres. get_center() is a Rect2i method that returns the middle cell:

func connect_spanning_tree() -> void:
    if rooms.is_empty():
        return
    var joined: Array[int] = [0]
    var waiting: Array[int] = []
    for i in range(1, rooms.size()):
        waiting.append(i)
    while not waiting.is_empty():
        var best_from := -1
        var best_to := -1
        var best_distance := 1 << 30
        for i in joined:
            for j in waiting:
                var d := manhattan(rooms[i].get_center(), rooms[j].get_center())
                if d < best_distance:
                    best_distance = d
                    best_from = i
                    best_to = j
        carve_corridor(rooms[best_from].get_center(), rooms[best_to].get_center())
        joined.append(best_to)
        waiting.erase(best_to)

manhattan() is the distance along the grid: steps across plus steps down. With a few dozen rooms, looping over every pair like this is fast enough. Past a few hundred, look at a Delaunay triangulation first, as TinyKeep does. The repair, connect_lost_rooms(), is in the complete dungeon_layout.gd.

How do I make sure all rooms in a procedural dungeon are connected?

Join them with a rule that cannot leave one out. A chain links each new room to the previous one. A minimum spanning tree links each room to its closest already-joined neighbour. Then confirm with a flood fill from the entrance: any room it does not reach is cut off.

What is the simplest way to connect rooms with minimal corridors?

A minimum spanning tree. Using Prim's algorithm, start with one room and keep adding the closest room that is not yet joined. It uses one corridor fewer than the number of rooms, the fewest possible, and the shortest total length.

How do I find unreachable areas in a generated map?

Run a flood fill, also called a breadth-first search, from the player's start. Mark every floor cell you can walk to. Any floor cell left unmarked is unreachable, and so is any room made only of those cells.

• Amit Patel, Red Blob Games: Introduction to A* (breadth-first search) and distance fields
• Wikipedia: Flood fill, Minimum spanning tree, Prim's algorithm
• A Adonaac, Procedural Dungeon Generation Algorithm, Game Developer (2015)
• Bob Nystrom, Rooms and Mazes (2014)
• Developer questions this answers: Is there a simple algorithm to make sure all of these rooms get connected using minimal corridors? and Avoid unreachable rooms in dungeons on Game Development Stack Exchange

How this was tested. The GDScript on this page was run in Godot 4.7.2 (headless, on Windows) on 31 October 2026. The demo runs a browser port of the same script, checked against Godot's output on 40 seeds. An automated check also confirms, on seeds 1 to 500, that the chain and the spanning tree never lose a room and that the repair always finishes.