Adding cycles to a tree-based dungeon generator

Dungeon-themed games often pick one: hand-build every room and accept that players will memorize it, or generate everything procedurally and accept that it’ll look machine-made. We chose the hybrid approach. Rooms are hand-built, layouts are procedural.

The design goal

The dungeon has to look good. Each biome needs its own hand-crafted detail, and rooms need to feel like someone designed them with intent.

That rules out fully procedural generation. Noise-based or block-by-block algorithms can produce dungeons, but the results feel artificial. In Minecraft there is a lot to get right: how block palettes work together, where furniture and props sit, how a layout communicates the room’s purpose.

A procedurally generated library room that feels coherent would require heavy custom tuning. Multiply that across the hundreds of distinct rooms a dungeon needs and the approach becomes infeasible.

We hand-build the rooms and let the generator handle assembly. Players spend as much time as possible inside authored content.

Tree-based generation

The first implementation: each room is a pre-built schematic with a set of connectors, doorways on its walls described by position and facing direction. The generator picks a starting room, places it, then repeatedly picks an open connector, selects a compatible room whose connector faces the opposite direction, and pastes it in. Each new room gets a node in the graph and a single edge back to the room it attached to, via a matching connector pair ¹. The dungeon grows by branching ².

Dungeon room schematics in the building world, with observers marking connector points.

It works, and the rooms themselves look good. The problem is the shape it produces. Every room has exactly one parent and no room can be reached by two different paths, so the dungeon just branches outward, dead end after dead end. Getting from one branch to another means backtracking all the way to where they diverge. For a high-tension dungeon crawler game where players move, retreat under pressure, and try to find their way back to the portal, that layout is bad. It turns navigation into a chore.

An acyclic graph (tree): every node connects back to exactly one parent, with no loops. The dungeon’s first implementation produced the same structure.³

Most roguelikes fix this by scattering rooms across a grid and connecting them with corridors to form loops. It gives you connectivity, but it sacrifices authored quality. Corridors are the generator showing its limitations, and it arguably worsens the gameplay experience.

I wouldn’t enjoy a game where I’m stuck passing empty corridors between every single room. We needed cycles without losing the room-snapping approach.

Things that didn’t work

Room-based A*

The most promising idea is using A* to connect distant parts of the dungeon by placing rooms as edges rather than carving corridors. Given two points that need a shortcut, the pathfinder navigates from one to the other by treating each room as a step in the search. Its connectors define where the next step can land. The dungeon gets its cycles through authored content rather than procedural hallways.

This is exactly like the traditional roguelike approach of “rooms and corridors” described in the previous section, except the corridors also become rooms.

The problem is the search space. Rooms vary in size and connector placement. A one-block misalignment between two candidates means they can’t connect, so the pathfinder backtracks and tries another combination. The number of combinations grows fast. A* heuristics and bounding box checks help, but not enough. The search becomes slow in any dungeon of real size.

Room-based A* placing rooms 1–9 to connect room A to room B. Even a slight misalignment anywhere in the chain forces the search to backtrack and try another path.

One fix is to build enough rooms of varying sizes so that a short aligned path can always be found. That’s a lot of content to build before the approach can even be tested, and in my attempts, resulted in atrocious performance. The more practical version is a hybrid: room-based A* that allows very short procedural corridors to resolve alignment gaps, with a high cost attached so the search treats them as a last resort.

Landmark rooms

If room-based A* can connect arbitrary points, the next question is where those connections should go. One idea was to divide the map into a grid and place a landmark room at a random point within each cell. Connect the landmarks to each other using room-based A*, giving the dungeon a guaranteed skeleton of connectivity across the full map, then fill the remaining space with smaller branching tree sections as before.

Landmark rooms placed randomly within grid cells.

The problem is ordering. Connecting landmarks greedily, one pair at a time, means early connections claim space that later ones might need. By the time the last few pairs are being connected, an earlier path may have already cut through the only viable route between them. Backtracking to fix this is expensive.

Density is the other issue. Landmarks far apart on the grid end up connected by a single chain of rooms with nothing around them, so you still need smaller tree sections to fill the gaps. Push the landmarks closer together and the path-blocking problem gets worse. We couldn’t find a setting that balanced both. The algorithm could’ve certainly been made smarter and less greedy, but at a serious increase to complexity for a result that might still not be good enough.

Adding cycles

Neither approach was appropriate, hence we settled on the current one: generate the dungeon as a tree, then repairs its topology as each room is placed, inserting cycles wherever the graph needs them most.

A graph showing rooms and their connections, with cycles inserted.

After placing each room, check whether any of its open connectors are spatially close to connectors on other branches that sit far away in the graph. If two connectors are sitting a few blocks apart in the world but dozens of rooms apart by any walkable path, connecting them creates a valuable shortcut. The spatial check queries a bucket index of all open connectors.⁴

The graph-distance check is trickier. A full BFS from the new room outward is $O(n)$ per placement, and across $n$ placements generation becomes $O(n^2)$. The fix is depth-limited BFS capped at $k$ hops. If the connector’s room isn’t reachable within $k$ steps, it’s graph-far regardless of how far the search would go. The cost drops to $O(b^k)$ where $b$ is the branching factor⁵. Total generation stays linear, since both $k$ and $b$ are small and mostly fixed.

Stretch

Every room has two distances to every other room: how far apart they sit in the world, and how many rooms you have to walk through to get between them. Stretch is the ratio of the second to the first. Two branches that grew close but share only a distant ancestor have high stretch: the walking route between them is far worse than their proximity suggests. A tree has unbounded stretch. Nothing stops two branches from ending up right next to each other in space while being dozens of rooms apart by any walkable path. The cycle-insertion pass targets these pairs.

The system measures stretch for every candidate connection and connects the worst one first, then repeats. A shortcut that cuts a 40-room detour down to 4, between two branches sitting a few blocks apart, is worth more than one that saves a handful of steps across the dungeon. The greedy order ensures the worst navigation bottlenecks get fixed before the smaller ones. It also tends to be physically feasible.

High-stretch pairs are rooms that grew toward each other from different branches without colliding, which means the space between them is likely still empty. The connections that help navigation the most are usually the ones the pathfinder can make.⁶

Carving the connection

Once a cycle candidate is identified, A* carves a corridor through empty space to connect the two open connectors. This A* does not pathfind on individual blocks. Each step is a cross-section corridor segment matching the room connector width. The state space is position plus approach direction, since arriving at the target connector from the wrong side is not a valid connection. Turns carry a high cost so the pathfinder prefers straight runs. Every candidate step gets its full bounding box checked against the occupancy index before expansion, routing around existing rooms.

A procedural corridor generated during a cycle candidate pass.

The result is corridors that appear only where the topology demands them, connecting branches that grew close to each other and filling in loops without consuming space that a room could have used.

A large generated dungeon with aggressive cycle additions.

Floor plan of a multi-level generated dungeon.

A 25,000 room dungeon (screenshot up to max view distance).

What’s next

The procedural corridors are the weakest part of the current system. They work, but every one is a small failure of the original goal. The path forward is the hybrid room-based A* described earlier: a pathfinder that places real rooms as edges and reserves procedural corridors for resolving alignment gaps, with a high cost so the search avoids them where possible. With enough room variety per biome, those gaps shrink. The end state is a dungeon where every block is authored content and the generator’s job is assembly and topology. That’s still some way off, but the dungeon is already playable, and each run feels different.

If you’d like to see the generation in action, the server is up at mc.runebind.net during time of writing. Or you may join us on discord

Footnotes

1. Each room schematic stores its connectors as a list of positions and facing directions. Two connectors are compatible if they face opposite directions. When two rooms snap together, the generator aligns their connectors, pastes the schematic, and removes the connecting door blocks to open the passage. In the building world, observers mark connector positions since they have a clear facing direction and are easy to spot visually. ↩

2. The generator uses a priority queue of open connectors ordered by Manhattan distance from the dungeon center. Polling the nearest connector first produces roughly uniform radial growth: the dungeon expands outward in all directions rather than one branch shooting off. ↩

3. “Rectilinear minimum spanning tree” by Rocchini, CC BY 3.0 ↩

4. The bucket index divides the world into a grid of fixed-size cells and bins each connector into the cell it occupies. Finding connectors near a given position means checking only the surrounding cells rather than scanning every open connector in the dungeon. As the dungeon grows, each spatial query stays roughly constant in cost instead of growing linearly with room count. A separate occupancy index stores the bounding boxes of every placed room and corridor segment for collision detection. When placing a new room or carving a corridor step, the generator checks this index to ensure nothing overlaps before committing the placement. ↩

5. The branching factor is the average number of rooms connected to any given room. ↩

6. More precisely, the dungeon graph is a Euclidean graph. Its vertices have positions in 3D space and edge weights correspond to physical distance. The cycle-insertion pass is a greedy approximation of stretch factor minimization by edge augmentation: given an Euclidean graph and a budget of edges to add, find the set that minimizes the worst-case ratio of graph distance to spatial distance across all vertex pairs. The greedy approach of repeatedly adding the highest-stretch edge is a known approximation for this problem. ↩