An introduction to procedural lock and key dungeon generation

i've been down a bit of a rabbit hole regarding procedural generation lately in particular i've been studying techniques on lock and key dungeon generation as it's often called at its core the lock and key model is about specifying paths of progression alongside the constraints to that progression so while you absolutely can use it to generate say a zelda-like dungeon where you need to obtain keys or abilities to unlock new areas you could also use it to model investigative games where uncovering clues allows for new dialogue options that can affect the outcome of your mission or even use it to design an entire game world where each area once completed provides an item or triggers an event that lets you progress to the next area my research so far suggests that while this is an established form of content generation the actual methodologies and discussions on the subject are somewhat limited and spread around the web a bit so today i'm going to provide an introduction to the concept of locking key generation and demonstrate a basic implementation of it that can be used for any type of game let's dive in so to kick things off as previously mentioned the concept behind lock and key generation is that there is a series of steps that must be taken in order to progress in the game these steps can be entirely linear i.e you get a green key to open the green door which then lets you get the red key to open the red door or non-linear such as requiring the player to complete four different tasks in any order before being able to progress the game further there really aren't any hard requirements about the composition of the game content at a high level though you will want to refine the method for your particular use case such as taking the spatial relationships and connectivity of rooms into account if trying to make a dungeon we can get more specific though based on our interest and i would generally break down the types of locks into three categories big key locks small key locks and stateful locks let's look at each and order big key locks are things like the boss key and a legend of zelda game the boss itself in that and just about any other game or say an ability in a metroidvania there is a lock that has one and only one way to open it you cannot access a legend of zelda boss without the boss key you can't go on to the next dungeon without being that boss usually and you can't access a new area without the right ability or equipment these are the most common types of locks seen in video games procedurally generated or not since the vast majority of games have at least some hard requirements that must be completed in order to progress even if it's just completing the tutorial area they're also the easiest to generate since all you have to do is make sure the key whatever it actually may be implemented as comes before the lock doorway behind the boss is locked until it dies that's a big key need to find a specific clue to confront the suspect big key even just a collection of levels in a puzzle game can be modeled as a very linear big key progression system taking things one step further we can generalize our keys so they work with multiple locks but are usually consumed after use i call this type of key a small key based on the legend of zelda series where you can collect a literal small key that can be used to open one or more locks in a dungeon you can often open up the locks out of order from the required path of progression but will eventually find more keys so that you can unlock other locks and get on the right path again this type of semi-linearity is good in my opinion as it lets the player explore the dungeon how they wish and make middle notes of its layout while still keeping their options somewhat focused and limited allowing for the type of level design that linear gameplay offers while adding a little bit of interest based off of their exploration for procedural generation though this method provides a non-trivial challenge ensuring that the player always has access to enough keys so they don't get locked out of progression just because they open the wrong lock there may be a way to code this rule entirely at the time of generation that i've yet to discover but otherwise so far it seems that you need to pre-solve the dungeon after its generation and make sure this is always the case regardless of the path the player takes in the dungeon potentially making modifications to the dungeon if that's not the case or starting over from scratch and generating a fresh one the final type of locking key combo is one that is stateful think of the water level in the water temple in ocarina of time or maybe bollards in some of the 2d zelda games or even how games like animal crossing or pokemon have items or events and pokemon that are only available at certain times of the day or even year these locks are complex enough to design by hand as it's important to make sure the player doesn't get stuck in an unsolvable situation no matter what path they take to the level for procedural generation the problem is amplified to do it right you'd most likely need to either drastically reduce the scope of these locks compared to a hand design level which is reasonable or use a solver to simulate all possible paths to make sure the player never gets stuck both methods are valid they just might make your brain hurt a bit if you try to get too complex too fast with them so with the conceptual overview out of the way how do we actually generate content based around this technique well that's the million dollar question and one that doesn't have a simple answer as there's no one generally accepted way to do it entire academic papers have been written proposing different methodologies for making dungeons using these concepts which is partially how i ended up down this rabbit hole to begin with i'll visit some of these techniques at some point in the future but for today and to keep things at an introductory level in line with the rest of the video i'll demonstrate a simple and approachable form of generation that i think will still be useful to a lot of people tree based big locking key dungeons hopefully it's obvious why i'm sticking the big lock in key dungeons by ignoring small unstateful locks we can vastly simplify the requirements of the content generator since we just have to make sure that we place a key somewhere in the dungeon before it's matching lock and keeping things tree based makes creating this kind of dungeon super fast and easy to code the caveat to this method is that since i'm keeping it extremely generic so it can be used for any type of game and not just zelda clones it won't tell you the exact layout of your content or dungeon if you're going that way only the order it should be traversed in by the player this could be seen as a benefit though since it means you can use any sort of dungeon generator you want as long as you can get that generator talking to this one this method can be expanded to do both though without too much effort and i'll talk about that a bit after i show the generic generator so now let's talk the algorithm which is really simple here's what we're going to do first we'll generate a list of nodes that serve as steps in the game's progression we will then connect each node to a random node that came before it in the list and then we'll place a key for that node in a random node that came before it and that's it from there we can iterate on and configure the technique however we want but first let's look at a bit of code written in gdscript the tree node class is essentially just a data container to hold a reference to its children and the key it holds the id is there to make it easier to look up later but in this example the id is just the node's placement in the nodes array and so it is a bit redundant the generate function chooses how large of a tree to make and then attaches each node to a random one that came before it before more or less repeating the process to place the key by attaching nodes and keys this way we can ensure that the player will always be able to access the key they need to progress and that's all there is to the code of this method so let's look at a few examples of the dungeon this method creates also note that while i did add a graphical component to the code on my end it turns out that making an aesthetically pleasing enery tree which is what this technically is is way more complicated than generating one so i'm redoing the output in affinity designer for presentation purposes so overall it's not a bad first pass as we do end up with progression paths that are unique from one another and non-linear but there are some pretty obvious limitations for one we often end up with one or two nodes toward the beginning containing most of the keys for the dungeon that combined with the fact that there are dead ends with no keys makes the non-linearity actually just feel a bit tedious if the player chooses the wrong path this method also encourages a lot of backtracking since the notes can appear anywhere and often will appear far from their keys to fix the issue of key distribution we can modify our code so that each node has a soft limit to how many keys it can hold only placing keys and nodes over that limit if there's no other choice this way we can create a more balanced output that requires the player to traverse more of the level in order to complete it for the issue of dead ends it's a bit harder to make a one-size-fits-all solution i think in general though you should just make use of the dead ends to offer valuable but optional items to encourage the player to explore these endnotes are a great place to put valuable loot in a dungeon crawler world building information and a more narrative focused game etc as long as each node can offer something of interest to the player then it's not necessarily a waste just because it doesn't serve the main path of progression for the issue of backtracking that once again is going to come down to your game as it may not even really be an issue in a non-dungeon based game for dungeons a shortcut to another part of the level could be added to some nodes to make things more interconnected you could also bias the parent selection process to favor nodes close to where the key is placed so that the player is never too far from where they need to go the technique for that is a bit beyond the scope of this video but to point you in the right direction if i were to go that route then i would use a distance formula to sort each potential parent based on distance from the key and shuffle a sub selection say those within one or two maybe three nodes of the key to choose from you can also use this distance formula to help with making shortcuts in the level so you could for instance take a dead end node that also has a valuable loot and maybe put a hidden door or even just the locked door that connects to the other side of the level to make things more interconnected and a bit more interesting and now let's finally talk about how to make this method work specifically in a dungeon generation context since the space relationship of nodes is important in that use case i won't be sharing code though as this video is already getting a bit long but hopefully there's going to be enough here to spark ideas and point you in the right direction at some point though i may come back to the spatial side of dungeon generation and talk about it a bit more in depth with code examples so at a high level there are three main ways i'd approach generating a dungeon spatially the first would be to generate your dungeon using whatever means you prefer and then group it to match the nodes generated via this method this is the most flexible way to do it as it does let you use literally any method you want but it does require analyzing and modifying the dungeon as and after it's been created to ensure it can be grouped according to the generated progression system the next method is to use the nodes to represent regions of a dungeon and then generate mini dungeons for each node for instance each node could represent say four or five rooms that you generate using your method of choice and then you connect them according to the generated tree i like this method a lot as it gives you a lot of freedom with how you generate your levels but also lets the progression generator decide the general level layout for you and provides a decent integration of the two systems this is the approach i would probably start with and generally focus on for my own projects the final method would be to let the progression generator generate the entire level for you this could be done by creating a grid and letting each note represent a room on that grid to make sure we don't end up with any invalid connections based off of current room placement with each node representing a room though you may decide you want more rooms and for not all of them to be locked to do this you could just place a few unlocked rooms in the tree after each locked node essentially either duplicating or reusing with a bit of modification the main generate function to create a sub tree with locked nodes as the root and that's an introduction to locking key dungeon generation i recognize there's a lot i haven't covered and that i did gloss over some details and ways of implementing what i discussed but that's because this is a really broad area of study with a lot of ways of tackling it so there's just no way to cover even a small fraction of it in one video so i'm going to leave you with enough to hopefully get your feet wet for today but i do intend to revisit this topic from time to time and hopefully share some more interesting techniques with you as i learn more about it myself i'll also mention that the algorithm from lena's inception named metazota is an impressively advanced take on locking key dungeon generation and it's worth checking out if you want to see this method in use i'll link to that in the description along with one or two other resources you may find interesting until next time [Music]

Channel: The Shaggy Dev

Views: 6,443

Keywords:

Id: BM_4Z27d4rI

Length: 11min 41sec (701 seconds)

Published: Fri Dec 17 2021