Stop creating branching paths, start using cyclic dungeon generation. Your levels will feel so much more hand crafted.

The most common strategy to generate dungeons in roguelike games is to keep adding generated or pre-designed dungeon pieces to the map. This way a dungeon is grown from a starting point much like a tree. However, trees end in branches and this creates a lot of dead-ends. To get around this problem most dungeon generators look for places to randomly reconnect the branches so that the player might actually wander in circles instead of having to backtrack all the time.

The dungeon crawler Unexplored changes this fundamentally (see figure 1). Instead of taking linear paths as its most basic structure, it generates everything in cycles from the get go. The differences are striking: where good cycles and interesting cycles might randomly appear using the old technique, in Unexplored they a planned feature of the generator’s output.

Basic cyclic explantion

Figure 1 – Cycles versus trees.

So how does this work? When Unexplored starts generating a dungeon it starts from an arbitrary starting point somewhere on the map. But instead of simply creating a branch to a target point it creates a cycle consisting of two paths connecting to the entrance to the goal. These cycles accommodate basic level design patterns far better than linear paths do.

Each cycle has a path ‘a’ that leads from the entry point towards the goal, and a path ‘b’ that leads back. Depending on the absolute and relative lengths of ‘a’ and ‘b’ you can change each cycle into a design pattern (see figure 2). For example when ‘a’ is short and ‘b’ is long, you can place a locked door at the cycles goal, and place the key at the end of ‘b’ just before you can cut back to the main path. This creates a level where players first encounter the locked door, and when they do find the right key they do not have to go far to reach the door it unlocks. Obviously, this requires that the player cannot reach ‘b’ from the cycle’s entrance straight away, although it might be interesting if they can already see ‘b’ and the key.

Another example that works well with a long ‘a’ and a short ‘b’ is to put a secret door between the entrance and ‘b’, creating a hidden shortcut. Or maybe ‘b’ is simply a more dangerous route then ‘a’, taking the player past a dangerous foe or requiring the player to navigate a trap infested room. There are many possibilities, figure 2 lists a couple more.

Cyclic patterns

Figure 2 – a couple of cyclic design patterns.

The results are awesome. Figure 3 shows a level generated by Unexplored. It consists of a large lock and key cycle with the cycle filled by a large chasm. A smaller gambit cycle was added to create more spice. The construction is simple but effective. In fact, we’ve come to realize that just a couple of cycles often is enough for most levels; with just a couple of cycles the levels end up with a distinct shape and character.

the ring level

Figure 3 – a level walkthrough.

Acknowledgements: The idea of cyclic dungeon creation arose during a research workshop at the Banff Center in Canada. I cannot take sole credit for this idea, instead I share it with everyone who was in that particular workgroup.

5 Responses

  1. Sebastiaan Zwezerijnen

    Very interesting read. For me, creating cycles was the hardest part during the creation of the level generator for Rogues with Benefits
    As I used pre-made rooms that are procedurally combined into a level, it was really hard to come up with an algorithm that successfully made cycles. It’s a bit like the mathematical problem of how to fit as much marbles in a jar. This becomes almost impossible to calculate in a decent time if the marbles all have different sizes.
    In the end, I ended up brute forcing all the rooms into place, which was both the easiest and fastest approach. As the rooms all have door layouts where they can be connected, I tried to come up with room layouts that would create as many cycles possible. With 42 room layouts the amount of cycles are between 2 to 5, which is pretty decent and could have been more if I did an additional pass to check if it could be optimized.
    The big question for me is now: how does this cycle approach hold up when generating X rooms? I do think the proposed solution is sound, but I can’t judge it by looking at 1 iteration of a level. So, is there any way I could see more generated levels?

      • Sebastiaan Zwezerijnen

        Thanks for the reply! I like it.
        Voted for greenlight too, good luck with that.