Unexplored's Secret: 'Cyclic Dungeon Generation'

'AI and Games' is a crowdfunded YouTube series that explores research and applications of artificial intelligence in video games.  You can support this work by visiting my Patreon page.

Procedural generation of levels has a long history in video game development: crafting worlds that feel novel and unique with each playthrough.  But it's an idea that has no defined method of how to pull it off.  Of course it makes sense that a world generated for Dwarf Fortress does not have the same design considerations as platforming in Spelunky or the dungeons of Binding of Isaac.  But the focus in each of these cases, the real technical and design challenge, is finding an approach that will build a game world that feels coherent and sensible while maintaining novelty and randomness.

So let's take a look at Ludomotion's 2017 roguelike dungeon crawler, Unexplored.  What makes this game interesting is that it doesn't procedurally generate its levels directly, instead, it relies on a cyclic generation system that creates cycles of interesting gameplay that are then translated into a series of fully playable dungeons.

Cycles in Level Design

Now, this might sound confusing on first passing: but the idea of cyclic generation originates from the real world.  When we look at objects in the real world built by humans there is a tendency to build in ways that enable cycles. This can be in building layouts and city blocks or in parks and road networks.  It enables interesting structures and layouts, as well as paths for people to navigate.

And when you then look at many video game levels designed by humans, there are cycles.  Be it in maps for online multiplayer games, or even in more traditional single-player games.  Players find a lock or obstacle, have to take a fixed path through the map to find the solution, and then return back to the beginning of the loop to see if it is now resolved.

But when you look at a lot of games that create levels or environments using procedural generation, they're don't loop, they branch.  They start from a point of origin and move forward to the exit while creating dead-ends and offshoots along the way. While this works well, it's increasingly noticeable as levels increase in size, and quite often the design of a game will mitigate against this. Spelunky's levels are constrained to a 4x4 grid of rooms, and branches are made more appealing first with collectibles and then items that help destroy parts of the terrain.  Meanwhile, Dead Cells levels are much larger, but exploit this as part of the risk/reward tradeoff: spawning useful items and boss cell doors down dead-ends, but then leaves portals throughout the level to allow you to teleport back to the last fork in the road.

And this is what makes Unexplored so interesting, in that it generates levels that are typically smaller but have rather sophisticated structures and puzzles designed to be solved either on the way down to collecting the Amulet of Yendor, or alternatively on the way back up as you try to escape.

Cyclic Dungeon Generation

Cyclic generation is a concept devised by Dr. Joris Dormans, the creator of Unexplored, that emerged as part of his ongoing research into procedural level generation.

So how does cyclic generation work?  Typically, a level generation algorithm will focus on finding a path that goes from the start to the goal.  Regardless of whether parts of the level are built as the path is constructed or it's a search through existing level chunks, provided there is at least one complete path from the start point to the exit, then the level is at least functional and the generation process can continue to add more features.

However, in cyclic generation, the idea is there isn't just a path from the start to the goal, but there is also another path that goes back to the start.
And this is the crux from which all of Unexplored dungeons are built.  Dungeons start as one simple cycle like so.  But unlike most generators, these arcs between the start and endpoint are not necessarily physical paths in the level space.  Instead, they represent the gameplay that's going to happen between these two points irrespective of how far apart they are in the actual level.

Now the trick is that this loop can then have a particular gameplay pattern embedded within it.  One of the two paths might be quite short while the other is long.  It might be you can only take one path in each direction, or both provide valid paths.  Risk and reward can also be modeled onto each path, one could be longer with fewer enemies, while the other is shorter but with significantly more monsters.

But where it really gets interesting is with the locked door pattern, the player takes path A to the goal, only to discover a locked door.  They're then forced to take path B, and as they traverse it, they find a key that will open the door.  So having completed path B, the player is back at the start, so they take path A again to get to the door and unlock it.

Now there's a lot of nuances and subtleties that are added to make this interesting and maintain the integrity of the puzzle.  For example, path B might not be accessible from the start because it's on a high ledge.  Path A might have traps that only activate after the player has picked up the key on path B.  Plus the entrance to path B from the goal might be closed upon entry, forcing the player to complete the loop via A.

But the key part is that the entire level is built as a cycle.  Players may experience that whole cycle as they play through it the first time, or just part of it as they head for the exit to the next level.

Cycles Within Cycles

Now the real trick of cyclic generation, is that provided the pattern within the cycle works, then more nodes can be added.  But they're not added next to the current cycle, they're added *into the existing* cycle.

The dungeon cycles are built in a transformational grammar system that allows the current mission graph to be transformed based on a variety of rules built by the designers.  This can mean a new node can be added to the graph that extends the cycle and introduces a new part of the dungeon: a shortcut from one part of the map to another, a new room full of traps and monsters.  Or a rule can be used to embellish existing parts of the dungeon.  This can mean adding a theme or property such as a style of the room to be used or a treasure chest that will appear in the room when the mission graph is translated into a playable dungeon.

But each map doesn't need to be only one cycle.  The patterns can be used to nest a new cycle inside of an existing one.  So while the dungeon might have two paths that take you from the start point to the goal, with a locked door in between, there might be a second lock and key cycle injected into one of the existing paths.  Or a new split path is added into another segment of the map.

The patterns are encoded using a system called Ludoscope, a game design tool previously developed by Dormans as part of their formative research in level design principles.  Users are able to encode the mission structures they require and the patterns and rules they wish for it to have available.  And so it makes for an interesting process, given that when working in Ludoscope, none of this is playable.  It's merely an abstract design concept for creating levels in games.  In order for it to work in a game such as Unexplored, the game needs to be able to translate what those grammars mean in the context of the game.  Hence it's possible that different games could interpret the same grammar in an entirely different way.  But for now, let's look at how Unexplored translates these cyclic dungeons into fully playable levels.

From Cycles to Dungeons

In Unexplored, the level generator needs to create 20 complete dungeons for any given run, but each is designed such that they can be solved in either direction.  Given that once you've worked your way down to grab the Amulet of Yendor, you then have to traverse back up to the starting point to complete the run.  The cyclic generation is designed to enable this, given when a cycle is built it should be plausible to reach the goal from the starting point and vice versa.  However, while this cyclic system could enable for incredibly large and complex dungeons, the average map in the game only contains a couple of embedded cycles, with the additional data embedded in the graph that decorates the rooms and dungeons helping ensure diversity in each run through.

But the big question here, is how do the mission graphs translate into an in-game dungeon?  There's the issue of mapping the graphs into a limited game space, as well as how the lock and key puzzles can from the mission cycles can be translated in multiple ways in order to bring some diversity to the dungeon designs.

So first up, how does the game build maps from the level graph?  This is arguably the most complicated part of the process, given the level graph does not contain spatial information.  It contains some structural information, in that room B sits somewhere between room A and C, and it contains relationships between things like keys and locks, but it doesn't say *where* those items will actually be.  So Unexplored's generation engine has a separate system for parsing a level graph and turning it into a high-resolution tilemap, that is then rendered in-game.

Unexplored's dungeon generation starts with a graph of empty nodes in a grid shape.  It then runs the cyclic generation system on this node grid to build a dungeon.  While this is something of a compromise, it's really a clever design decision that ensures any dungeon generated will map into a two-dimensional level space.  Once the dungeon is generated in the grid, it then runs multiple passes translating it first into a very low-resolution tilemap and then making multiple passes to increase the resolution.  Once the high-resolution version of the map is built, it then takes all of the extra information stored in the level graph such as the monsters that should appear in corridors, traps in specific rooms, and the keys and locks for the main puzzles.

While there is the main lock and key rule in the grammar system, how that manifests in the game world can vary from one instance to another.  Keys can be designed such that they can be used for a specific lock or any lock it fits.  They could be built for multiple uses or they are consumed once they get put in a lock.  But critically, a key is dependent on what the lock it is used for.

Locks aren't always padlocks on doors, and keys are not always physical keys.  Unexplored has multiple types of key/lock combos, and the idea of what key/lock combos are and how they're designed lifts from similar tropes found in the likes of classic Legend of Zelda games.  So for example, you could have a physical key that needs picked up and used in a specific lock - known as a conditional lock - but the lock could be an enemy and the key is a weapon, or the lock is a pit of lava that will hurt the player to cross it, but there is a potion nearby that will make you immune to lava for a short time.  This is an interesting key/lock combo, given the key is a perishable item and once consumed it cannot be used again.  Meanwhile, the lock is non-conditional: meaning you don't need the key to unlock it, but it will certainly make your life easier.

Locks can have a variety of features, they might unlock permanently or only temporarily (if you open them using a timed switch).  Some locked doors with switches can be relocked by hitting the switch again.  Locks can also be unidirectional, such as a collapsing bridge, meaning that once you cross it, you can't go back.  In fact, one of the most interesting features is that some locks can be designed to be unsafe, meaning that sometimes depending on how you've played your run of the game, a solution that unlocks it is not guaranteed.  This isn't something that's used all that often, given the main key/lock cycles that let you complete the level will be safe and therefore guaranteed to have a solution.  Unsafe locks are more likely to be found off the main dungeon path for the likes of secret doorways.

Unexplored 2

At the time of writing, Unexplored 2: The Wayfarer's Legacy is currently in development and unlike the previous game, players leave the confines of the ever-darkening dungeons and are now exploring a vast open world.

While players have vast new worlds to explore, there are still dungeons that are part of each playthrough.  The cyclic generation system is still very much in play, but the focus is not just how the mission graphs are being translated, but new grammars are being built for different parts of the game.  With separate generators in play for open-world, environmental puzzles, dungeons, and even the overarching narrative.

References