Procedurally Generated 3D Dungeons

what is up today I wanted to show off this project that I created in gdau it is a 3D dungeon generation system lethal company style that allows you to create these 3D dungeons that you can walk through and explore that are randomized and randomly generated each time um the way it works is it has a set of prefab rooms that it uses each time and then it will randomly place them and then connect them together with corridors like you're seeing here um long hallways to connect them together and based on the algorithm that I created to connect all these together it will have a multi-level fully connected fully explorable 3D dungeon so when I first started trying to tackle this project I couldn't find any similar tutorials or anything online so I started with a 2d version of the problem and the basic idea is that I just spawn a bunch of different size rooms into the level and then I check if they're overlapping and for the cases where two rooms are overlapping like these two rooms right here I basically just push them away from each other based on their Center of mass so because this one is to the left and slightly above this one it's going to go this way and this one will just go the opposite way and I basically just continue this process repeatedly for all the rooms and eventually they sort themselves out and they all become separated and then you get a nice distribution of rooms in the dungeon you can also run into some situations like this where all the rooms fail to separate and the solution for that is just to run the algorithm a couple times and with different room placements and after a couple times you'll run into a configuration that works and the rooms are able to separate properly once all the rooms have been nicely separated like this it's basically just a case of using a pathf finding algorithm to connect all their doors together in this case the green and yellow spots are doors yellow being optional and green being necessary doors that we need to connect in addition to connecting all the rooms one important thing is to make sure all the rooms are actually reachable from each other and you can see it's not perfect in this prototype that there are still some cases where you'll run into islands like this one which are not reachable from the rest of the dungeon so to solve this problem and make sure all rooms and floors are connected we can use a really basic algorithm called Union find the basic idea is we keep these pools or sets of trees of all the nodes and each tree's root is always going to be the lowest node value within that tree so when we're connecting two trees of nodes together we basically run through the tree and set all nodes to whatever the lowest value is in the new tree this way we can keep a list of rooms and Floors that still need to be connected here's the code for the class that I used to do this the dungeon is going to be made up of these prefab rooms that are predefined with doors and in different shapes and sizes and here you can see for the 3D version of the algorithm it's basically the same idea um but in 3D I place a bunch of rooms just as before in 2D and then I use the same separation algorithm of just pushing them apart from each other and then I connect them with these corridors to make it fully explorable in 3D there's also the case of there needing to be stairs between floors and that is a similar problem to the one of all the dungeon rooms on each floor being reachable and there's no isolated Islands it's really important for all the different floors to be reachable if it's like a large vertical dungeon um so I'll talk about how I solve that next so to start off the algorithm obviously we're going to place a bunch of rooms and then after we've placed all of our normal rooms the next task is going to be to place stairs in the dungeon and now this is going to be a pretty straightforward application of our Union find algorithm we're simply going to keep track of which floors of the dungeon are already connected by stairs which span two floors and we'll just keep going up the chain and adding stair rooms until all the floors of the dungeon are connected and for connecting rooms on the same floor it's basically going to be the same concept we're we're going to keep a list of rooms in a union find list and keep connecting them with a pathf finding algorithm until they're all connected fortunately this algorithm adapts easily to dungeons of different shapes and sizes with any different room types this leads to some interesting Poss possibilities for procedural level [Music] generation [Music] [Music] [Music] [Music] [Music] moving over to gdau the structure I used for the actual gdau add-on portion of this is I have these dungeon kit prefab scenes which Define each of the rooms inside of the dungeon or for the dungeon to use and I basically just create all of the rooms individually that I want the dungeon to be able to spawn in and I connect them all together the initial placement in this uh prefab scene does it matter this is just to get an idea of how they fit together but I do find these rooms of different shapes and sizes with doors and each door can either be a required or optional door so for instance this orange piece is the corridor or hallway portion which is going to connect all the rooms together so all the doors on this room are optional and then in the editor when you spawn a dungeon generator instance which we will actually use in the levels to spawn in the Dungeons and run the algorithm it gives you this preview scene which allows you to see kind of the size and shape of the dungeon and how it's going to look and it runs the exact same algorithm that I just described pretty much but within gdau and it spawns in prefab scenes for each of the rooms and this results in this same um fully explorable dungeon thing that uh you can use in your levels in gdau of course you can use it with actual 3D models so here's a little mockup I made of an example dungeon um which uses real 3D models from a free 3D model set I found online here are the individual pieces of the models I used to piece together Lego style for this dungeon here and we have all the same rooms here's our Corridor or hallway room here's our stair room we have a hallway room here a little greeting area with a friendly little skeleton here here there's a trapo room there's a longer hallway room with spikes and there's a treasure room so you can see how you could um swap SW out different types of rooms for whatever type of game that you're creating and when generating dungeons you can just swap out the dungeon kit and it will select the rooms that you provide and create a dungeon using those rooms of whatever Dimensions that you specify and yeah pretty quick with these new 3D models um to make it actually look professional pretty quickly we get something that looks pretty nice and we get a nice kind of maze thing that's pretty easy to get lost in and offers a lot of room for exploration and yeah that's the video I hope you enjoyed I'm going to leave a link to the GitHub repo with this gdau add-on available for free for to use if you want um I hope you enjoy and hope you got something out of this video if you have any questions you can leave them in the comments and hopefully I can help and thanks for [Music] watching

Channel: Majikayo Games

Views: 28,456

Keywords:

Id: TPvxWIKHE6Q

Length: 10min 25sec (625 seconds)

Published: Tue Mar 19 2024