Generating Dungeons with a Room Graph (Building Delve, Part 2)

Graph, not grid

My first instinct was a grid: chop the map into cells, drop a room in some of them, connect neighbours. It’s simple, but it looks like a grid — everything axis-aligned and evenly spaced. I wanted rooms of varied sizes scattered in open space, joined by corridors. That’s a graph: each room is a node, each corridor an edge.

The generator is five steps, and every one of them is just data:

1. Scatter rooms of random size at random positions, rejecting overlaps.
2. Connect their centres with a minimum spanning tree (so everything is reachable) plus a couple of extra edges for loops.
3. Carve L-shaped corridors along each edge.
4. Derive walls as the border around all floor.
5. Decorate — openings where corridors meet rooms, then populate.

Scatter and connect

Placement is rejection sampling — try a spot, keep it only if it clears the others by a margin:

while rooms.size() < ROOM_COUNT and attempts < 2000:
    attempts += 1
    var rect := Rect2i(rng.randi_range(-SPREAD, SPREAD), rng.randi_range(-SPREAD, SPREAD),
        rng.randi_range(ROOM_MIN, ROOM_MAX), rng.randi_range(ROOM_MIN, ROOM_MAX))
    var clear := true
    for other in rooms:
        if rect.grow(ROOM_MARGIN).intersects(other):
            clear = false
            break
    if clear:
        rooms.append(rect)

Then a minimum spanning tree over the room centres (plain Prim’s — for ~10 nodes you don’t need anything cleverer) guarantees the dungeon is one connected piece. A pure tree feels a bit sterile, so I add a few extra edges to create loops you can circle back through.

Corridors are deliberately boring — an L from one centre to the other:

for x in range(mini(a.x, b.x), maxi(a.x, b.x) + 1):
    floors[Vector2i(x, a.y)] = true
for y in range(mini(a.y, b.y), maxi(a.y, b.y) + 1):
    floors[Vector2i(b.x, y)] = true

Walls then fall out for free: any cell touching a floor cell that isn’t itself floor is a wall. One pass over the floor set’s 8-neighbours and the rooms and corridors are ringed automatically.

Prove it before you draw it

Because generation is pure data, I can test the whole algorithm headless, with no rendering. The check that matters most: is every floor cell reachable from the spawn? A stranded room with no way in is the classic generator failure. Flood-fill answers it in milliseconds:

func _flood(floors: Dictionary, start: Vector2i) -> int:
    var seen := {}
    var stack := [start]
    while not stack.is_empty():
        var c: Vector2i = stack.pop_back()
        if seen.has(c) or not floors.has(c):
            continue
        seen[c] = true
        for d in [Vector2i(1,0), Vector2i(-1,0), Vector2i(0,1), Vector2i(0,-1)]:
            stack.append(c + d)
    return seen.size()

If reached == floors.size(), nothing is stranded. The test also asserts the rooms don’t overlap and that the same seed produces an identical dungeon. I had all of that green — 1,184 tiles, 10 rooms, 100% reachable — before I’d looked at a single wall. When you generate to data, “does it work?” is a unit test, not a staring contest.

Rendering is the dumb part

Only then does a separate level.gd turn the data into tiles. And here’s a perf lesson I’m glad I hit early: instancing ~1,700 individual tile scenes tanks the frame rate. The fix is a MultiMesh — one mesh, thousands of instances, ~one draw call:

var mm := MultiMesh.new()
mm.transform_format = MultiMesh.TRANSFORM_3D
mm.mesh = tile_mesh
mm.instance_count = cells.size()
var i := 0
for cell in cells:
    mm.set_instance_transform(i, Transform3D(Basis(), Vector3(cell.x, 0, cell.y)))
    i += 1

Floors and walls each became a single MultiMesh; collision stayed as a separate (invisible) body. The “data first” split paid off again — the renderer just consumes cells, so swapping per-tile nodes for a MultiMesh changed nothing about how the dungeon is generated.

The bug that ate an afternoon

Where a corridor meets a room I frame the gap with an archway (and gate the stairs room with a door). My first rule for “this is a doorway” was naïve: a room-edge floor cell whose neighbour outside the room is also floor.

It worked — until a corridor ran parallel to a room wall. Then every cell along that wall passed the test, and I got arches marching down the entire length of the wall. The fix is to insist a doorway is genuinely one cell wide — the gap must be flanked by walls on both sides:

var perp := Vector2i(dir.y, dir.x)
if walls.has(nb + perp) and walls.has(nb - perp):
    openings[nb] = { "kind": kind, "rot": ... }   # a real 1-cell doorway

A parallel corridor has open floor beside the gap, not walls, so it’s correctly ignored. Openings dropped from 27 to 17 — exactly the spurious ones.

Making it a place, not a maze

A correct layout is not yet a dungeon. The last pass gives it texture, all driven from the same seed so a run is reproducible:

• Enemy variety — one orc model, three stat blocks. Grunts die in a hit; scouts are small and fast; brutes are scaled up, take three hits and hit back hard. The generator picks a variant per spawn; the spawner applies it.
• Loot rolls — chests are mostly modest gold, sometimes a treasure haul, sometimes a health cache (which matters once enemies hit back).
• Props with collision — barrels, columns, rocks, scattered by room size and given real colliders, but never placed on a doorway cell (a blocked-cell set keeps the paths clear).
• Long corridors get a junction — any edge over a length cap drops a small room at its midpoint, so you never get one endless hallway.
• Stairs that read as down — the kit only ships an up staircase block, so I leave a one-cell hole in the floor and sink the model into it. Now it looks like you descend.

Verify by playing, too

Headless tests prove the logic; they can’t tell me the dungeon feels good or that the colours survived the MultiMesh swap. So the other half of the workflow is an in-game debug overlay (toggle with F3) showing FPS, draw calls, the seed, player and entity state — plus F4 to reroll the layout at the current depth and F6 for god mode. Tests for correctness, overlay for feel; together they cover what either alone misses.

Next time: the enemies get smarter and the run gets stakes — but the foundation is set. The dungeon makes itself now, and I can prove it.