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. I'm Tommy Thompson, welcome to AI and Games and
in this episode we're going to take a look at the secret behind 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.
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 for 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 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 collectables 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 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 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 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 end point 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 modelled 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.
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 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 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.
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 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 dungeons? 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.
Unexploreds 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 the 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.
At the time of writing, Unexplored 2: The Wayfarer's Legacy is currently in development
and thanks to the team at Ludomotion I had the chance to try it out in advance,
and wanted to share some of it with you now. 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.
Unexplored 2 is currently lined up for a 2021 launch and I hope to be back with a video
later in the year where we get to go into even more detail on the big changes under the hood.
In the meantime, links are in the description where you can find out more about the game.
Thanks for watching this episode of AI and Games. I hope you found this topic interesting
as Unexplored is still one of the most unique examples of procedural generation in commercial
games. For game devs keen to learn more about cyclic generation, be sure to check the video
description as I list a number of resources that you can use to get your head around it.
Plus, a special thanks to Joris Dormans - the creator of cyclic generation
and Unexplored's game director - who shared with me some of the materials I used in this video,
double checked I wasn't talking nonsense, and also for giving me a chance to play
the current build of Unexplored 2. AI and Games is brought to you by my
crowdfunding supporters on Patreon. To join our community, vote on topics and have your
name displayed alongside all these lovely people shown right here, check out the links on screen
and in the description. I'll be back soon with another episode voted for by the Patreon
community and I look forward to sharing it with you. Take care folks, I'll be back.