Building dungeon cycles from authored rooms

I’m building a Minecraft extraction dungeon crawler game, and its dungeons are assembled from hand-built rooms: a person builds every room, and a generator decides how they fit together. I wrote about the first version of that generator in an earlier post, which ended on the part I called weakest, the procedural corridors, and a plan to replace them. This is that replacement, and it ended up working way better than I thought it would.

Table of contents

• The setup

• The failed prototype

• Inside the search

  • Pathfinding
  • Rooms as moves
  • The pattern database

• Making it fast

  • Knowing when to stop
  • Shims that fit
  • Deduplicating the moves
  • The whole sequence
  • Measuring instead of guessing

• Where it landed

• Things that didn’t work

The setup

A room is a schematic with connectors: doorways on its walls, each with a position and a facing. Two connectors are compatible when they face opposite ways. The generator starts from one room and grows: it takes an open connector, finds a room with a compatible one, snaps them together, and repeats.¹

Rooms in the building world. The observers mark each connector and the way it faces.

Every room attaches to exactly one room already placed, so the dungeon is a tree, and trees have no loops. The only route between two branches runs back through the point where they split, and in a game about pushing deep into a dungeon and retreating toward the exit, a dungeon with no loops turns every retreat into a long backtrack. Not exactly fun.

The fix is to add cycles, and some are worth far more than others. Every two rooms have two distances between them: how far apart they sit in the world, and how many rooms you walk through to get from one to the other. Stretch is the ratio of the two. So:

• Two room branches that curled back toward each other, a few blocks apart in space but a hundred rooms apart through the tree, have enormous stretch.
• Two rooms right next to each other could be connected, but their distance is low in both physical block space and in room graph distance. Hence, low stretch.
• Creating a high-stretch connection adds a great shortcut (a cycle!) into what’d otherwise be a hundred-room detour. Those are the pairs worth connecting, and they are cheap to find.² The question is what to build in the gap.

The failed prototype

The first version carved a corridor: a small pathfinder routed a tunnel between the two connectors, and the generator filled it in. The corridors were entirely procedurally generated, unauthored builds. It works, but the whole game is authored rooms, and a procedurally generated corridor’s build quality is going to be significantly more repetitive and bland. Not only this, but we’d need to code a separate corridor generator for every single building style (in our case, one per biome) in the dungeon, so the connections would look seamless.

A procedurally generated corridor, the thing I wanted gone.

I wanted to fill the gap with real rooms instead, a short chain of authored rooms that happens to connect the two branches. I had tried that in an early prototype and abandoned it, for two reasons:

• Rooms are rigid, so two connect only when their connectors line up exactly, and a gap one block too long has no solution but to back up and try another combination, which explodes in complexity.
• The prototype planned these connections across the whole map at once, where an early one claims space a later one needed and you end up unwinding the lot.

Both problems have a fix. The planning one dissolved once I stopped planning globally: the cycle pass hands the search two connectors that already sit close together, so every search is reasonably short and local. Rigidity needed a piece of content, short filler rooms whose only job is to take up a little space, so a gap with no exact solution closes when the search drops one in.

Inside the search

Pathfinding

The search is A*, the standard pathfinding algorithm. It keeps a frontier of places it could go next and always expands the one that looks cheapest, where cheapest means the cost $g$ already spent to reach it plus a heuristic estimate of the cost $h$ still to come. A good heuristic makes or breaks A*. The issue is, pathfinding can be slow.

Rooms as moves

To search over rooms in A*, I precompute the possible moves to save constant time per lookup. For each room, each connector, and each orientation, I bake a record where the room lands relative to the connector it attaches to, the space it fills, and where its other doorways end up, with a cost. In other words, we can actually think of connectors as nodes and rooms as edges in a graph pathfinding algorithm.

A chain of rooms bridging one connector to another. Each placed room is one edge in the search.

The search does no placement math in its inner loop. It looks up precomputed moves and checks them against the occupancy index (with localized buckets for fast AABB collision checks).

The pattern database

The obvious heuristic is Manhattan distance, but it fails at the one place that matters, right next to the goal. A connector five blocks away but facing the wrong way is way more than five blocks of work: you have to overshoot it, turn, and come back, maybe 50 blocks of rooms. Straight-line distance says “almost there,” so the search crowds the target and tries every combination in that pocket before finding each one faces the wrong way.

The fix I chose is to precompute the real answer. Search backward from the goal through every combination in empty space, and record the exact cheapest cost to reach it from every nearby position. The estimate becomes a lookup which is fully accurate as long as there’s no obstacles in the way, which is why it’s still just a heuristic rather than an answer. This is otherwise close to the idea of endgame tablebases in chess engines.

There’s another important point. A* returns the shortest path only when its heuristic never exceeds the real remaining cost, an admissible heuristic. This is because the heuristic decides what to explore, and an overshoot can steer the search off the best route and settle for a worse one early. Our table stays under by construction: it measures cost in empty space, and obstacles only ever lengthen a route.

Then we break the rule on purpose and roll with WA*. A* normally ranks what to explore next by $f = g + h$, weighing the two equally. We multiply the estimate by a weight $w$ first, so the search leans harder toward whatever looks closest to the goal: $f = g + wh$. This is weighted A*, and $w$ is the inflation factor: it expands far fewer nodes, and in exchange the resulting path can run up to $w$ times longer than the shortest possible one.

That suits us just fine. A connection only has to feel natural to walk through, and one that takes a slightly roundabout path looks natural. We spend a little optimality for a lot of speed. And since the greed is controlled by $w$, we can fine-tune the parameter to never end up with cycles that look insane.

The table is large, about 600,000 states, so it is packed: each state becomes a single integer and the whole thing lives in two flat arrays instead of a graph of objects.³

	Object map	Packed arrays
Memory	65 MB	16 MB
Build time	7.3 s	1.6 s

The table has a free bonus in it. A gap with no entry at all is an impossible state to connect, so A* can fail fast in those scenarios.

Making it fast

Knowing when to stop

The first working version took 80 seconds for a 700-room dungeon, almost all of it the search grinding hopeless connections to the end. The fix was knowing when to stop. A futile search expands towards the goal and then stalls, making no progress against an obstacle or a gap the rooms cannot fill. And since the search is stalled, A* never even explores any of the search space that would’ve led to a successful chain before giving up.

Most failed connections fail before any real search, typically because their doorway opens into a wall. A minority run far enough to stall, and those are our enemies.

Failed connection	Cost
Median	0.05 ms
75th percentile	9.8 ms
90th percentile	12.9 ms
99th percentile	23.8 ms

Half cost almost nothing. The slowest tenth cost hundreds of times more. Failed searches are about 90% of all cycle time, so dealing with them was crucial. It is the least clever change in this post and the most important. By the time I fixed on a 1000-room benchmark, generation was near twelve seconds. The biggest cut left was tuning this very knob, exactly how long to let a stalled search run before killing it, which I come to below.

Shims that fit

The filler rooms are what let a near-miss close. The two most useful are two and three blocks long, and two and three shims combine to any length of at least two. They are authored content, styled per biome, and look like narrow connecting passages. Adding them fixed cases that used to stall and fail, and since a successful cycle is cheap versus an expensive failure, they made generation faster while also producing way more cycles. Here is a 250-room dungeon before and after, where conversion rate is the share of attempted connections that end in a placed cycle.⁴

	No shims	With shims
Cycles placed	30	38
Conversion rate	6%	10%
Cost per cycle	75 ms	46 ms

A failed connection is now almost always blocked space or a gap the rooms cannot fit.

Deduplicating the moves

Many rooms are the same shape with different decoration and produce identical moves, so the search was exploring each several times over. I group moves by geometry and explore each group once, picking a concrete room only at commit-time. For example, our default biome which had 428 moves has now been reduced to 340, a whole 20% less of state space for A* to worry about.

It unfortunately barely affected performance, since our greedy A* was already doing a good job of ignoring branches and doing focused exploration. Its eventual value was elsewhere, though. The rooms in a chain are now chosen by their spawn weight rather than by whichever duplicate came up first, a build quality fix that came as a side-effect.

The whole sequence

By the first 1000-room benchmark the generator took near twelve seconds. From there came packing the tables the search keeps while it runs (heap allocations are evil), more shims, better move grouping, and finally a tighter stall cutoff, the value the calibration had pointed at all along and the biggest single drop of the lot:⁵

Change	Cost per cycle	Total generation
First 1000-room benchmark	56 ms	11.9 s
Packed search tables	44 ms	9.8 s
More shims	42 ms	8.9 s
Move deduplication	40 ms	8.8 s
Tighter stall cutoff	26 ms	6.0 s

Measuring instead of guessing

Every number in this post came from instrumentation I added before making a decision. Rather than guess at a stall cutoff, the generator logged what each possible cutoff would save and what it would cost in lost cycles, so I could read the tradeoff off a curve and pick the point where the wasted failure time fell away but real successes were not yet getting clipped. That one pass, moving the cutoff to where the data pointed, took the last big chunk off the clock.

Where it landed

The same 1000-room dungeon, the same seed, once with the old procedural corridor generation method and once with everything above.

	Procedural corridors	Room chains
Cycles placed	61	216
Conversion rate	0.9%	8.9%
Authored rooms added	0	1,168
Cost per cycle	20 ms	26 ms
Total generation	1.5 s	6.0 s

We see 3.5x times the cycles, all of higher quality. It costs more, 26 ms a cycle against a corridor’s 20 ms, aka 30% more, and the whole run is about four times slower, though most of that is just running the pathfinder 3.5x as often. And each of those cycles is a chain of authored rooms instead of a bland tunnel.

The dungeon graphs below show the generated rooms and their connections. Here are the old and new cycle generation algorithms, side-by-side on an identical dungeon seed with 100 rooms.

Here we see the old corridor-based cycle algorithm failing. The (1) point marks the origin room from where generation branches out. Following it into the (2) branch, we see it split into two more sub-branches (3) and (4), and neither of them has any loops. Boring dead ends that force you to backtrack.

Here’s the same dungeon, but now with proper rooms. We see that the dungeon expands from the origin room (1) onwards to (2), same as the previous approach. But then, if we follow the (3) sub-branch, we see that it ends up connecting to the (4) sub-branch as well as another one.

And if we zoom out on our 1000-room graph, we see a well-connected, dense graph across the entire dungeon.

Things that didn’t work

A few ideas that seemed good and were not.

• Searching from both ends at once. The usual pathfinder speedup. But the pattern database is already the backward half, precomputed for every connection, so a live backward search buys almost nothing. It also adds a problem: the two halves each avoid the dungeon, yet nothing stops them overlapping each other in the empty middle, and a meeting matched on position and facing cannot see it. That said, the approach might still have potential and is something that I may explore in the future if more optimizations are demanded - for now, world peace is achieved.
• Caching multi-room combinations. The instinct is to remember useful chains of rooms. The pattern database already stores every endgame combination compressed to its cost, so it’s useless there. And outside that, you’d end up with combinatory explosion, which would make A* very sad.
• Generating the dungeon before it is needed. The clean way to erase the wait is to build the dungeon ahead of time, but generation parameters depend on the player who is joining, so there is nothing concrete to build until they commit to a game. A softer version might pay off, starting when players join the lobby rather than when they queue, to steal a head start on the wait. The latter is certainly something worth adding eventually.

Footnotes

1. The generator keeps a priority queue of open connectors ordered by distance from the dungeon center and always extends the nearest one, which produces roughly uniform radial growth: the dungeon expands in all directions at once rather than shooting off down a single branch. ↩

2. The pairs are found with a spatial bucket index for the “close in space” test and a depth-limited breadth-first search for the “far in the tree” test, then ranked worst-first so the biggest shortcuts get built before the space between them fills up. The graph-distance search is capped at a small number of hops: past that, a pair is far enough in the tree to be worth connecting regardless of exactly how far, and stopping early keeps the whole check cheap as the dungeon grows. ↩

3. The states are packed into an open-addressed hash table: a pair of flat integer arrays with linear probing, rather than a general-purpose map that allocates a node object per entry. The state key, a position and a facing, fits in a single integer, so the whole table is two contiguous arrays the CPU can walk without chasing pointers. ↩

4. This comparison predates the 1000-room benchmark, so it is at 250 rooms. The direction is the same at every size I have measured. ↩

5. I only started benchmarking at a fixed 1000-room dungeon partway through this work, so earlier figures are at whatever size I was testing at the time and are labeled as such. The generator is deterministic within a run, so a fixed seed reproduces a dungeon exactly, but changing the room set changes the dungeon a seed produces, which is why cycle counts wobble slightly between steps. Cost per cycle and total time are the trustworthy columns. ↩