Procedurally Generated 3D Dungeons

hello everyone in this video i'll demonstrate an algorithm for procedurally generating 3d dungeons i'm using unity 3d for this but these concepts can be used in any game engine the goal of this project is to generate dungeons that are unique and interesting to explore a dungeon consists of rooms connected by hallways dungeons can have multiple floors and rooms on different floors will be connected by stairs take a look at this randomly generated level from enter the gungeon while there is a simple path from the start room to the end room there are also branches into other areas these make the dungeon more interesting to explore since they contain extra items and encounters there are a lot of different ways to approach this problem i eventually decided to base my algorithm off of this reddit post which describes the algorithm for a game called tinykeep the original algorithm only works in 2d so i extended it to work in 3d the code for this project is available in the github repo linked in the description first i'll explain the dungeon generation algorithm for two dimensions it works more or less the same as the tiny keep algorithm step one place rooms in the dungeon it doesn't really matter how they're arranged so for this example i just gave them a random size and location [Music] step two create a delani triangulation graph from each room a delani triangulation is a triangle mesh created from a collection of points the triangulation tends to avoid long narrow triangles this creates a lot of connections between nearby points while having relatively short edges in this diagram each dot is a room and each edge is a potential hallway in the dungeon not every edge will be used since that would create a dungeon that is too cramped with too many paths to take we need some way to reduce the number of edges chosen for the final dungeon i used the boyer watson algorithm to produce this triangulation here you can see it being built with green lines [Music] step 3 create a minimum spanning tree from the triangulation graph for this i use prim's algorithm the mst guarantees that every room will be reachable however since it is a tree it contains no cycles there is only a single path from one room to any other room the edges in the mst are marked in green these will be used as hallways the remaining edges from the triangulation are marked in gray these hallways may potentially be used in the final dungeon [Music] step 4 randomly choose from the potential hallways while the msd contains every room it only contains a small number of edges take the gray edges that are not in the mst and randomly choose some of them to be hallways this will add some loops to the dungeon here i used a 12.5 chance for each edge to be chosen step five for every hallway use the a star algorithm to find a path between the two rooms this video won't explain how the a start algorithm works but there are plenty of resources online if you want to know more what you need to know is that a star will find the lowest cost path given a graph and a cost function the cost function i used makes it cheaper to go through an existing hallway than to carve out a new one this encourages the pathfinder to combine hallways that pass through the same area going through a room is possible but expensive so in most cases the pathfinder will prefer to go around rooms the pathfinder produces short and believable hallways between rooms here you can see the hallways being added as blue boxes [Music] here's some example of this algorithm using real art assets the assets and the code to place them are not in the github repo we now have our rooms and hallways in a real game you might mark one of their rooms at the start room and another as the boss room other rooms might contain monsters treasure or whatever in summary this dungeon is created with these steps step one place rooms step two create delani triangulation step three find mst step four choose random edges step 5 pathfind hallways to extend the dungeon generator to 3d we just need to use the 3d versions of each algorithm step 1 generate rooms in 3d instead of 2d some of the rooms are now placed on different floors this change was trivial step 2 find the 3d delani triangulation of the rooms since this is now in 3d this is actually the delani tetrahedralization searching for that on google returned a lot of research papers but no actual source code that i could find in the end i had to learn how the boyer watson algorithm actually worked so that i could change it myself i don't know what a circum circle is but replacing them with circumspheres makes everything work in 3d it's a little hard to see but instead of producing triangles with three vertices the algorithm now produces tetrahedra with four vertices at least one of those vertices will be on a different floor otherwise the tetrahedron would be degenerate step 3 an mst can be created trivially from the tetrahedron edges step 4 choosing hallways randomly is also trivial step 5 pathfind hallways this is where it gets complicated from here i'll assume that you're familiar with how a star works internally the version for the 2d dungeon is the standard dead simple implementation of a star to make it 3d i had to add the ability for the pathfinder to move up and down to connect rooms on different floors however the standard algorithm would have no special behavior for moving vertically it might create a staircase structure but it might also go straight up i needed a system to give more control over this this is where the problem lies i wanted the specific shape for the staircases but that adds a lot of constraints to how the pathfinder can operate i'm using a staircase that looks like this the staircase itself takes four tiles the blue boxes are normal hallway tiles the pathfinder can only connect to the staircase from those blue tiles using the blue boxes from earlier as hallways let's use green boxes to represent the staircases hallways and staircases might be placed in a dungeon like this if a hallway connected to any other part of the staircase it would create staircases that are impossible to use like this this happens when the pathfinder creates a hallway that intersects with the top half of a staircase this is because only the first tile of a staircase is considered used by the a-star algorithm the pathfinder thinks the rest of the staircase is available to use as regular hallways what i need is some way to mark every tile in the staircase as used then the pathfinder would know to avoid these tiles i can't add the staircases to the closed set of a star a star effectively calculates multiple paths simultaneously so one path might use a tile as a staircase while another uses the same tile as a regular hallway if i put the staircases in the closed set it'll prevent other paths from moving through the same tile even if that staircase ends up not being used but i can't just ignore them because then the hallways would intersect with the staircases like earlier the solution was for each tile to keep track of all previous tiles leading to it then when a neighbor tile is being evaluated it'll be rejected if it falls on the path of the current tile when a tile is updated with data for a new lower cost path its set of previous tiles is also updated this pathfinding algorithm isn't exactly a star at this point there are too many special cases just to handle stairs having to check the entire previous path on each step is expensive but this performance is acceptable since the algorithm only needs to be run once at the start of the level so here is the new pathfinding algorithm adding hallways and staircases to our dungeon the blue boxes are hallways and the green boxes are staircases [Music] [Music] there is one new limitation of this pathfinding step since the pathfinder has so many constraints from staircases it's possible that there won't be a path between two given rooms that's what these leftover green lines are they are hallways that did not successfully pathfind zooming in on some of the hallways you'll see that they can be simple or complex finally here's a 3d dungeon made using real assets from this perspective you can see some interesting emergent behavior from this algorithm here are two staircases side by side here are two staircases that lead to the same door this hallway descends two floors so there is a landing in between the stairs hallways that pass near each other are not always merged into a single hallway sometimes they combine to form a large area in general the hallways and staircases created can be very complex that's all i have for this video this algorithm is a good basis for a dungeon generator but there's plenty of work to be done before making it into a full game if you like this video and want to see more like it don't get your hopes up you

Channel: Vazgriz

Views: 133,937

Keywords:

Id: rBY2Dzej03A

Length: 9min 41sec (581 seconds)

Published: Tue Nov 16 2021

Reddit Comments

[u/Daxon]

Haha "If you want more videos like this, don't get your hopes up." That kind of statement gets my hopes up!

​

Really nice vid, enjoyed the share, thanks for that.

[u/vazgriz]

This is an algorithm that can be used to generate dungeons. This algorithm works in 2D or 3D.

Also available in text form here: https://vazgriz.com/119/procedurally-generated-dungeons/

[u/Azarro]

Nice algorithm and your writeup that you linked in another comment was very concise and easy to digest! I always like seeing room-based generation instead of just random cellular automata generation (which also serves a different purpose and can help produce more natural cave-like maps, for sure).

Another way to do room-based generation that I'm a huge fan of and have probably written countless times in various languages over past half decade is by, tl;dr,

1. Creating a bunch of room 'patterns' (essentially just the rectangles, but you could have blank tiles in parts of the rectangles or walls in between, so they don't have to actually always be rectangular rooms visually)
2. giving each room a bunch of openings/exits (by marking specific cells in each room's pattern as such)
3. Place a random root room
4. Basically, until there's still space (or any other constraints you have are satisfied), each iteration of the generative process, you find all available openings across rooms already placed on your map and then determine what room patterns can have their openings joined to any of these openings

Works pretty succinctly, especially if you want to create handcrafted rooms or handle your room generation modularly and separately! If you add hallway/corridor type room patterns, then you essentially get a similar effect as placing rooms and building out the hallways.

eg. https://stuff.worldof.xyz/gen/

[u/ProcessMe]

Interesting watch! Thanks for sharing

[u/raysoncoder]

This is pretty much porn for me. Thank you!

[u/FoxxPlays]

This looks fantastic!

[u/jdtec01]

Impressive, good production values and well explained.

[u/blorp02]

I found a nice way to do the first step of placing the rooms. Generate rooms and place them at the origin then add some random offsets to them. Then give them rigid bodies and bounding boxes and random physics materials and run a physics simulation for a bit and they will separate in a way that they are somewhat together but always a new interesting shape. Without doing this the dungeon always seems to be some squareish layout.

One thing i got stuck on before stopping was furniture layout generation, I had made some templates but they just get so repetitive.

[u/TuxedoTechno]

Nice work! Figuring some of that stuff out must've been mind bending.