An introduction to procedural lock and key dungeon generation
Вставка
- Опубліковано 28 тра 2024
- Let's take an introductory look at lock-and-key procedural content generation. Using a lock-and-key framework to procedurally generate content, you specify paths of progression for the player in your games. Roguelikes, narrative games, and really any sort of game where you want the player to advance via a series of steps (whether linear or non-linear) can be modeled and created this way.
Intro: 00:00
Definition: 00:56
Big key locks: 01:43
Small key locks: 02:38
Stateful locks: 03:49
A sample technique for generating content: 04:36
Limitations: 07:14
Spatial methodologies: 09:09
Conclusion: 10:57
Video transcript and code snippets shown in the video available here: shaggydev.com/2021/12/17/lock...
Metazelda repo: bytten-studio.com/devlog//201...
IRDC 2014 - Roguey-Locks and the Three Graphs: • IRDC 2014 - Roguey-Loc...
Unexplored's unique cyclic graph generation technique: www.aiandgames.com/2021/01/28...
I always thought of implementing a tree based locks and keys dungeon generator since I saw the GMTK Zelda series. This motivates me to get it done.
Yeah! Give it a go! It wasn't too bad to figure out this basic implementation of, and some of the comments have provided some more interesting ways to build upon it once you're at that point.
Great video - seems super similar to cyclic generation like was done in unexplored. Using a graph grammar that is cyclic to create all the levels, keys, etc... Seems there is still a slight distinction here between unexplored. Very interesting.
1. Create a perfect maze (or a graph with no cycles), labeling every node with the number of steps away from the start square as you go.
2. Find the node that's the maximum number of steps from the start square. Mark it as the "Boss Room" or "Exit". The "main path" will be found by counting down from the highest number of steps to the lowest, from the exit square.
3. Divide the main path into n sections, as desired. Each section will have a locked door at the end. For example if the main path is 100 nodes long from the start to exit, dividing the dungeon into 5 sections would place a section exit every 20 steps down the main path. Mark these nodes as section exits. Place locked doors.
4. Floodfill each section from its entrance to its exit, marking the main path and all it's branches as being part of the current section. Count the nodes of each section as you go. Some sections may be randomly larger than others, with more branches, depending on the maze layout. Return to step 1 if these differences become too unbalanced.
5. Place the keys for the section exits in random nodes in each section, prefably in one of the side-branches, at a dead end. If desired, create loops in the maze by knocking out random walls (adding edges) between nodes of the current section only.
6. Fill each section with appropriately leveled enemies, puzzles, and traps, growing progressively more difficult as you advance through the sections. Optionally, you could have distictive tile sets and music for each section to help players orient themselves, and give them a sense of progression.
Because there will be only one main path from the entrance to the exit in a perfect maze, you won't need to test the maze to make sure it can be solved.
Ahh excellent algorithm! Appreciate you sharing this. Tracking the "depth" of the dungeon certainly seems useful for multiple use cases, especially difficulty as you mentioned
FWIW, I've played quite a few 2d platformers that use this concept well. For example, in the first area there might be a 'shiny' on a platform that is too high for you to reach with your current jump height. (This is actually an *excellent* way to let players know that they will be able to find items to increase their abilities.) At some point, the player will find the 'small key' that will allow them to jump high enough to 'unlock' the shinies/shortcuts/etc.
Underrated channel! All these videos are great
This video deserves so many more views, I loved it!
Thank you! I'm fond of this one as well so it's nice to see it appreciated by the smaller number of people that have seen it :)
Your channel is a goldmine! Thank you
A bit late, but haven't found the time to watch the last few videos earlier.
Placing locked doors and small keys (or other such mechanics) during creation is actually rather simple and might be something interesting for another video (not that different to what you did already).
You're generating your dungeon starting at the player's entry or exit point. For simplicity, I'm using the "start at the entrance" approach.
Now you'll just iterate over this:
- Place a new room.
- If you have keys available, you may lock the room's entrance. If you do so, subtract one key.
- Decide randomly, if the new room should include a key. If it does, add the key to the number of available keys.
- Rinse and repeat.
- If your dungeon algorithm decides to add a second entrance to a currently locked room, you can only do so, if you've got a spare key (to ensure players can't run out of keys), or you remove all the locks and "refund" the keys back into the available pool (or all its connections unlock at the same time consuming only one key).
Whether this whole approach is viable, is always dependent on how you generate the dungeon, obviously.
If you can get it working, you can extend it and play with it a lot, though. For example, rather than locking a room with a key, you could make it so it could only be passed after obtaining an item (think Zelda's hookshot). It would work the same way: You can only place a hookshot only room after the hookshot is already placed, but this flag won't reset after placement.
Ahh! This is really interesting and makes complete sense! I really like this approach and will be sure to play around with it. The approach to items is a good take as well. I had initially been looking at using them as big keys, which can also work but requires a bit more care regarding node placement, but this small key approach makes a lot of sense and provides some extra flexibility. Thanks for sharing!
@@TheShaggyDev You could also have enemies drop keys when there are no keys left on the player's side of the locks. You could even offer a hint by having the character say something like this when s/he comes to a lock: "Crud. I don't have a key. Maybe one of the {creeps} has one."
This will be helpful for me, even though I am a 5E GM, rather than a video game creator
That's cool! As a D&D player, and sometimes Call of Cthulhu GM, would be interested in seeing what you make with it.
Something to point out, your big-key tree based algorithm is very easy to extend to small-keys... just treat small keys as big keys DURING GENERATION, where each key has a unique association to a specific door... an association that doesn't exist in gameplay. The result will be all small-key doors are ensured to have enough keys 'ahead' of them to be opened, with no possibility of soft-lock.
Now, the trickier thing is figuring out how to incorporate alternate choice small-key doors, where you want to force a player to make interesting choices on what they can/can't unlock... On their own it's no problem (basically Slay the Spire/Hades levels), but if you mix them in with 'normal' small key doors then it's possible they re-introduce the risk of soft-lock, since in game there will be no difference between normal & 'choice' small keys
Hey, great video. Thanks for doing this. I'm interested in game-making but the thought of making "content" usually turns me off. I would love to develop a mostly proc gen game and your thoughts are very helpful. FYI, I moved from Unity to Godot, so you definitely have a new subscriber!
Thanks for subscribing! Glad you liked this video. I have a bit of a soft spot for proc gen content, and I think we're still only scratching the surface of its potential, so I plan to revisit the subject from time to time and hopefully show off some cool stuff!
Hey you should absolutely make the type of game you want to make, but I gotta say even in proc gen games you're gonna have to make content, and the best procgen incorporates a lot of hand made elements and a ton of manual tweaking. I get the sentiment though, I'm also pretty lazy about level design
Whoa 😮
thanks
Good content. How does Jacquaying a dungeon fit into this?
From my understanding of Jacquaying a dungeon, the concept of lock and key could work well with it since its primarily concerned with the content within your space (placing multiple keys to the same door or type of door so you don't have to go to a specific room to progress, for instance), but the tree-based example I gave is probably a bit too simple since it is more designed around one "proper" path with room for exploration along the way. No reason you couldn't put multiple exits in the tree, but it doesn't handle some of the spatial issues that would arise with making things more interconnected. Presumably you could expand the idea into a proper graph and then you could really get complex with your designs.
Grr. YT needs better AI implementation, it's obvious I would have been interested in a channel like this. This should have been in my recommended much sooner.
Ha, yeah the enigma that is the algorithm is finicky and seems to change all the time. Glad to have you watching now, though!
@@TheShaggyDev Oh yes sorry! Was too busy griping at google to say what an excellent video this was. Great mix of game design and game dev. Also the presentation and editing were to notch. Outstanding stuff. A channel destined for success I'd say.
Thank you! Appreciate the kind words :)
You should look up Unexplored's Cyclic generation. Your method sucks.