This is honestly amazing. Apart from the wonderful research and thinking behind this, the results also look amazing. Although some results might be unrealistic or complex-looking, I personally love how they turn out like that because it add a feeling of exploration (especially that central room with the multiple hallways and staircases). I'd love to see more videos about this. Keep up the amazing work!
One cool modification you can do is that you can modify the minimum spanning tree algorithm to used weighted distances instead of straight Euclidian distances. That way you can make rooms that are supposed to be well connected in fact have more connections instead of being leaf nodes. For instance you give the great halls an artificially small Euclidian weight and the closets a high weight so that they are the last connected and thus act as leaf nodes.
FYI the circumcircle is the circle you can draw around any polygon that has all the vertices either on or inside the circle. When the polygons are regular, the circum circle will have all the verts on the circle. if the polygon is symmetric, points will have pairs that you can probably find with a shortcut. a rectangle will always have 4 points on the circle, and 2 axes of reflection at the midpoints of the edges. it's effectively the smallest circle you need to include all the points and lines. or the maximum circle you need to search to ensure you find all the points of a polygon. So the circumsphere is just the 3D analog for polyhedra. A prism (3D rectangle) will have 8 points on the circumsphere, and 3 planes of reflection again midway between the points. you need not have all the points to find the others, you only need the minimum to construct the n-sphere: (n+1) points not on a line. so 3 points for 2D, and 4 points for 3D. the rest of the verticies are implied by the reflection planes and the condition that they fall on the circum-n-sphere...
No, a circumcircle is a circle that contains _all_ of the vertices of the polygon. It always exists and is unique for a triangle, but polygons with more vertices generally do not have a circumcircle. The Delaunay triangulation has the property that no vertex lies inside of any triangle's circumcircle. It avoids long thin triangles because those have big circumcircles.
Well done! This is great work and the level of detail provided is truly appreciated. I absolutely hate videos that pander to the lowest common denominator and skip the really important stuff.
At step 4, when adding extra hallways, instead of a flat rate, increase the odds based on the distance according to the tree, so rooms that would be far from each other on the tree from the previous step would be more likely to connect, while two rooms with very short connection already will be less likely to gain a clearly redundant path.
I'd think you'd actually do the opposite; two rooms nearby would obviously be connected, but two further away would not waste resources and would just connect via intermediate rooms.
@@JD2jr. I'm talking about after the initial tree of connections is established, so during the step of jacqueying the dungeon to create looping paths instead linear branches, that's the point that far away rooms on the tree should be more likely to connect, (especially if they are close physically).
The great thing with this is, with the MST, you can define the critical path and as a result, add keys and/or puzzles to make sure that the player is always able to traverse from the beginning to the end.
Wow this is very great work! Especially figuring out the hallways with the Stars in 3D was very impressive. Your channel deserve a lot more views and subscribers, keep going!
it's not the "Stars" it's an A* pathfinder algorithm (pronounced A-Star), a further heuristics-based development of the original Dijkstra's pathfinding algorithm. en.wikipedia.org/wiki/Dijkstra%27s_algorithm en.wikipedia.org/wiki/A*_search_algorithm While Delaunay triangulation is typically used for computer graphics and other visual domains, A* is another of the non-trivial algorithms famed for its ubiquity. Naturally, A* is a staple in the indie game dev, fully implemented in virtually every programming language. Though several other extended variants and heavily improved algorithms supersede it in the actual domain of graph search and pathfinding (and more often than not this is necessary for performance reasons), it is still heavily used a) for learning, b) because its highly customizable, but also c) as a precursor to more complex algorithms, for example in planning solutions (aka the AI) such as GOAP, where it finds the shortest path between any two abstract world states in memory, helping the planner to backtrack from the desired outcome back to the steps preceding it, in the most optimal way thanks to easily configurable costs and heuristics.
For added realism/variation, I would have tried a few things differently: 1. Allow a small chance that if a room is above a certain size, it could also be multiple stories tall (vaulted ceiling). Pathfinding from the lower floor would be normal. Pathfinding from the upper floors would require the insertion of a balcony, either at that point or full/partial perimeter of the room. 2. I would have done each floor separately, then used a dedicated algorithm to place stairways. That would allow for some variations in the stairs, including having them switch back with a landing, or even be spirals. It would look for a suitable space that connects to at least one upper or lower room or corridor, then do an additional pathfinding pass to make sure it's connected on both. 3. I would designate some room types, including a "master corridor" type. There would be rules for where they could be placed and how they could be connected. (Good RNG is never fully random.) 4. Large rooms could be split into "sub rooms" for the sake of pathfinding to create doors, allowing large rooms to have several entrances and exits. A large enough room would also have a small chance of allowing a staircase to be placed inside it, with a much higher chance if it is the "master corridor" room type.
This is wonderful! I have just gotten started with random level generation and this is the kind of stuff I'd love to do one day. The way you incorporated the stairs is brilliant.
I'm just getting started in game design with plans to do 3d games down the road, and I like this concept. One thing I'd point out is that stairs and hallways shouldn't be given equal opportunity to generate as in a "real" dungeon (you know what I mean) choke-points offer crowd control options in case of invaders. Instead, each floor should generate separately then have one main stairway with a higher percentage chance to generate closer to the entrance and two to four others generate with low chance to generate close to the entrance but raises further away. Alternately, in castles staircases were opportunities to ambush invaders withthe exception of the Grand Enterance. The Grand Enterance could be generated as a two-level tall entity and then treated as the generation point for the second floor. Then add a low chance for another two-level entity to generate on teh second floor that would be the spawn point for the next floor and so-on. Then find places where all three floors can connect vertically to drop in spiral staircases, and finally add the servants' staircases around the edges of each floor. Of course, I recognize I might be spouting nonsense as I don't understand coding any better than cuniform. 😅
Honestly pretty sweet. I was thinking about creating an open-world game that takes place in an underground city or something like that, and procedural generation like this is definitely something I'm going to keep my eye on.
The best thing here is that you name all algorithms you used. This is so useful! I would probably never found half of them otherwise but now I know about their existence and can use them!
As you said at the end it's a good base for dungeon generation, my brain was already flying through different tweaks and addition rules I would add so that the starting rooms, boss rooms, shops, or whatever special rooms would all be paced properly, as to not rush with one connection between the start and end of the dungeon. Whatever you end up making be sure to at least show the finished project! And as a final note, this reminded me of this indie title called Necropolis that has 3D procedural dungeons, it's system was not the most polished, and the game itself has a lot of issues just in the design choices, but I can't believe I never inquired as to how the generation works before now!
This is incredible! with several options (random or chosen by the programmer) like several design tastes by area, spiral staircases, elevators, outside zones or things like that, the result can be even more mind-blowing.
@Vazgriz Just wanted to let you know that I followed your guide loosely and was able to get a proper level generation system up and running! I already had a prototype for my gameplay and plan to continue working on my 3rd person ARPG roguelike.
I also wrote a 3D Dungeon generator for my bachelor topic, but yours is a better and more general approach. Mine was a bit rushed due to time constraints. I only had about two weeks to create the rooms and code.
I actually read a book where an unexplored dev talks about the generation of their dungeons. It's based on graph manipulation, starting with a "start" and "end" node that lead to each other, then adding nodes between them until the dungeon is complex enough. It's actually pretty interesting, the book is called "procedural generation in game design," and it was co-written by the guy who made dwarf fortress.
@@DavidSilva-el7el Yeah there's probably an advantage to that approach instead of throwing up random rooms and then looking for a good way to connect them. Although this random room approach in the video might make less repetitive results that feel less contrived, possibly. I really have nothing to back up that statement, other than intuition.
This makes incredibly natural and clean looking layouts for a procedural algorithm! Excellent work. How did you handle the hallways that failed to pathfind? Are you guaranteed to still have some path through the dungeon to get from any one room to any other room or are there potentially breaks that split the dungeon?
That's an interesting approach, it differs a lot from the commol voxel engine approach to generate the hallways/staircases first (aka like minecraft cave system) then automatically add the room tiles afterwards in spaces that match given criteria.
At the spanning tree stage, the level could be the longest path; keys at dead-ends open doors at prior junctions. When adding random loop-back paths, place locked doors in them with keys nearby on the side reached later in the level. (FTL Dungeon Master 1987 and Captive (procedurally generated from a floppy disk) 1990 were like this)
Sweet! ★Ladders ★Trap-doors (especially in very small rooms/toilet) ★Large rooms separated by walls with doors or barred windows ★Long rooms having dungeon cells beside the corridor ★4th dimension (trendy and rarely done properly)🤞
Thanks so much for sharing! I've been using Delaunay triangulation for generating FPS maps but I've hit a rut, I think this might help me continue my work in a new direction!
You also can run alg in two projections and just impose them together. Only problem is when cube placed in dioganal direction to previous. But it’s exception case witch can be solved by predefined chose or for example rounding middle point of the line to compute belonging to nearest avaluable coorinate position. Also cool visualization
could this be done at runtime to create infinite dungeons from a seed value? points being generated randomly based on a specified distance from the camera with a height constraint. it would need a little tweaking with the MST to have it not immediately flag all rooms as "essential". the trick being, not to let it end up as a long single pathway through every room generated as you move around. better to have many branches and loops back to another room. I could definitely see it making for an awesome dungeon crawler with fully randomized loot, assets, themes, specific structures, randomized but somewhat levelled combat. could be as simple as spawning enemies and items during generation, then ofc you could have a few dozen huge setpiece rooms that only ever spawned in once in a seed and occasionally have a boss fight in them.
Amazing breakdown of a way to automate a 3d layout . I have ideas for better generation but it's very much beginner thoughts on how to achieve / transition : I basically used multiple counting loops example you have a 500 room maze setup a matrix then for room = 1 to 500 ---then used a matrix check in another loop that counts like room but we will call him loop to see if the room has data if yes see if finished tagged no ? then run a loop test for a hit (the test can always be a variable /prior set ) oh it hit what number we on ? room 1 loop 12 well now room 1 and room 12 should be linked... That is about all I can recall of the old program I wrote in basic but it was a text adventure ai that I made back in 1995.. I kind of got out of computers and wouldn't try programming again for years oh I exited the loop for the room if the loop had more then 2 to 5 hits (it was rng) but yeah this structure was memory intense and on the slug 486 pc it would take a whole 30 to 40 minutes to just figure out how to write the text adventure , so the code even when it was complete was pretty awful. Still it could easily combine with the given concept happy trails and don't go making a terminator or do, I no longer care.
I very rarely subscribe on command but when you told me not to get my hopes up I smashed that button. Very informative, well produced and, evidently, under-appreciated content.
This looks like such huge amount of work! Well done I suppose you can always try again if your algorithm cant create a certain dungeon, or even go non-euclidean (like mc escher) with the hallways...
I am working on a game and I will definitely revisit this video a few times! Thanks a lot for the content! I just gave you a subscriber. You sounded from the video that you "hacked" a variant of the A* algorithm. But the abstract A* algorithm is implemented on a mathematical graph, not on a 2D grid. Did you think of adding a specific edge for staircases with its own distance weight that would be used to connect cells that are 2 across and one up and then implementing the classic A* algorithm for graphs? It's mathematically a bit more involved but you might recover your performance you were looking for. In other words, each cell would have 12 neighbors instead of 4 (minus obstructions): the four cells adjacent to it, and the 8 possible staircases that can connect to it (all four directions, but going up and down are options). Then you just give staircases the appropriate weight for the distance they take and you run classical A*
In the approach that Vazgriz described, stairs consist of multiple cells, and classical A* does not address that. Because of that, the paths that A* generates, will often have self-intersections (stairs can intersect other stairs and corridors). For example, nothing stops classical A* from generating two adjacent staircases that go (0, 0, 0) -> (3, 1, 0) -> (0, 2, 0).
God imagine this sort of algorithm in a 'modernized' Pokemon Mystery Dungeon game, swapping out the tile movement for real time action combat. That would be fucking sweet.
I presume doors are added by using the start and end tiles of a pathfind, but him showing two hallways that connect to the same door make me question this.
If I’d want to change the cubes for asset models. How can I change the code to recognise which rooms with which doors I should chose? I’m really interesting in that part of the algorithm modification. Thanks a lot for your video explanation.
I'd imagine the initial room size would be a function the algorithm would start with, so you have 20 or so unique rooms each with a regular footprint that fits neatly in a tile. Or, you could create a 3-d tileset that would be used to build each room allowing for more flexibility in room size. There are lots of videos on how to build and implement those tilesets, but I'm not going to pretend I know more about them other than they exist. 😅
@@RamDragon32 of course, I imagined there are one model of each room. However, as we’ve can see, the corridors fill more than one space next to the room. Moreover, the room is not always in the same wall or floor. What I want to know is how I can know where the door will go in the wall, if it is a checkpoint, if it is another extra implementation in the font code… Thanks in advance.🙏🏼
Im attempting to recreate this (with the same asset pack.) I'm making a room using all blank walls, then using ray casting to find/swap out walls for doors, and finally building a path from door to door. Eventually I want a logic script that will look at the room's "type" and size and the auto fill with appropriate assets.
I think the bug where hallways intersected stairs would be an interesting way to introduce fake stairs, or possibly overlooks on the other side of the staircase.
my god, my dream ! you're a genius...i would like to implement this ..but currently im too focused on completion of my game, however this brings me into a conundrum...if i could implement this, then the game could be completed in two days, because 29 levels could be generated so quickly...but the problem is implementing this algorithm would be a pain...it would itself take months to implement...
Are all the rooms premade prefabs? since the code generates the rooms randomly within a certain scale range, would you have to make room prefabs for all possible room scalings and have the code fetch them when that particular room is generated?
Amazing!! just what I was looking for!! I have one question. I looked up your github and it seem like github example doesnt have prefabs of dungeon walls and stairs like 8:39. Can you please share the dungeon prefab implemented version?? Since i am newbie, its hard for me to customize. Thank you!
You shouldve researched math that is used on architecture. By using modulor you are able to define an exact 3d grid that would remove any possibilities of unused connections. That way using a restriction on first step it will generate less headache down the path.
very nice- makes me think of Minecraft stronghold and fortress generation. One option would be to create the corridors and stairs in a random fashion then add rooms
Really cool! I'm glad I found this video. I am actually making a game where the levels are massive, but contain many of these "dungeons" placed throughout. And I am looking to see how other people are solving the problem. I've made my own version of this, but it's a bit more "primitive" and could be better. I had a problem with the room placement, and finding an efficient way to make sure a generated room doesn't occupy the same space as existing rooms. But I kinda just "fudged" that idea to make dungeons interesting. But with that being said, I am curious about how exactly you place the rooms at this step 1:11. Also, when you showed this 0:51 , that made a lightbulb go off in my head about certain things. But I am curious about the details to how you placed each dungeon, and any checks you might've done.
This is some next level (HA!) dungeon creation. Do you have anything for rough cut tunnels? How about natural looking caverns with stalagmites and stalactites? Or that really weird cavern down there in Mexico? The one with those huge crystals. I think it's in Mexico, anyways, no one has explored it fully because it is so hot in there. Geothermal something or other.
I realize this is nearly a year old now, but I went ahead and started recreating it (trying to use the repository as little as possible) and I noticed in a console log that it thinks there are a lot more edges than there actually are after completing the Bowyer Watson algorithm. I assume this gets taken care of automatically by the MST search, but I would be curious as to why it's happening here as if I could, I would prefer to clean it now for performance reasons.
I think you could have simplified the problem in 3D by doing it first in 2D and then adding vertical offsets. Not sure, if that would run into issues but just a suggestion.
This would work. But since the rooms are originally generated in 2D, it means that rooms won't overlap with each other. IE one room being over another. You would still need an algorithm to connect rooms on different levels. This would be fine if you just want verticality in your maps.
I have downloaded this and it is working well, but as the blog post says, "the art assets and the code for placing them is missing". Where can I find it, or at least does anyone want to collaborate on making asset placement code? I think I would like to make my own assets, maybe a more natural looking cave system with stalagmites and stalagmite, and rough cut stairs.
I did same thing inside Unreal Engine, that's also could be used for 2D and 3D maps totally works same as enter the gungeon procedural map generation. I wonder if I convert this to plugin, would people be insterested.Rooms are premade and corridors to connect one room to another if overlapping is involved is procedural.
Hello, what a blast. Thank you so much for doing this. Btw. Are there some obvious / non-obvious requirements for the input parameters? (talking about the 2D maze now) Time to time I have OutOfRange exception in CreateHallways when there are no edges calculated. Also, once I had a case when one room stayed as an isolated Island. The configuration was: Size [30,30], Roomcount:10, RoomMaxSize: [10,10] …random seed 3 (I guess the room size was too much or so. : ) I cannot wrap my head around the triangulation alg now, to debug it by my self.)
Wow, you really took a hard way to make a dungeon There is a much easier method that I used in my roguelike that produced nearly the same result. I placed the rooms in an area like you did and added the rooms coords to a list. Once I had all the rooms placed I selected the first room from the list and a random room from the list. I started at the center of the first room and walked to the center of the other room. I used the Manhattan algorithm to walk to the target room. If I encountered a room along the way, I ended the walk and removed the first room from the list. I marked the wall location and added a door to booth rooms. I did this for all the rooms on the list. Once all the room have been processed, there is a connection to every room in the floor. You don't need all those algorithms you used.
this is just a different approach. Another way to handle this is by predesigning all of the rooms, and marking the connections it has. Then you can place a random room, and connect another room/hallway on each connection. If a room is chosen decrease the chance of it appearing. Also keep a separate list of dead end rooms, and allow them to be used when the dungeon reaches a preferred size.
@@lintycarcass You run into problems placing rooms if you connect them as you place them. It is much easier to put a bunch of rooms into the dungeon space and then connect them. My method is very fast, every room is connected and you get interesting paths as corridors cross over each other. I have tried numerous dungeon building algorithms and this is fast, easy to implement and produces nice dungeon layouts. I use the Manhattan algorithm to ensure that corridors are square so you don't get any funny artifacts. This method is also easily adjusted to floor size by just adjusting the number of rooms. Nothing else needs to be changed. I have yet to see a method better than this.
@@RickClark58 i never said you can only use square rooms. a collision detection system is very easy to implement, you can even use that as a base for creating a map of the dungeon layout as well. Creating a dungeon really doesn't have to be fast either. Of course faster load times are always better, but even by implementing a bunch of algorithms like this video wouldn't take that long in runtime. Loading times in 3d games mainly come from all of the assets and models. Not from creating the dungeon layout.
You took A-star, and made it into A-stair
this is how he should name it!
"if you'd like to see more, dont get your hopes up", lmao. love the vid, interesting work.
This is honestly amazing. Apart from the wonderful research and thinking behind this, the results also look amazing. Although some results might be unrealistic or complex-looking, I personally love how they turn out like that because it add a feeling of exploration (especially that central room with the multiple hallways and staircases). I'd love to see more videos about this. Keep up the amazing work!
Don't get your hopes up.
The emergent features are genuinely pretty fantastic. Thanks for the video
One cool modification you can do is that you can modify the minimum spanning tree algorithm to used weighted distances instead of straight Euclidian distances. That way you can make rooms that are supposed to be well connected in fact have more connections instead of being leaf nodes. For instance you give the great halls an artificially small Euclidian weight and the closets a high weight so that they are the last connected and thus act as leaf nodes.
FYI the circumcircle is the circle you can draw around any polygon that has all the vertices either on or inside the circle. When the polygons are regular, the circum circle will have all the verts on the circle. if the polygon is symmetric, points will have pairs that you can probably find with a shortcut. a rectangle will always have 4 points on the circle, and 2 axes of reflection at the midpoints of the edges. it's effectively the smallest circle you need to include all the points and lines. or the maximum circle you need to search to ensure you find all the points of a polygon. So the circumsphere is just the 3D analog for polyhedra. A prism (3D rectangle) will have 8 points on the circumsphere, and 3 planes of reflection again midway between the points. you need not have all the points to find the others, you only need the minimum to construct the n-sphere: (n+1) points not on a line. so 3 points for 2D, and 4 points for 3D. the rest of the verticies are implied by the reflection planes and the condition that they fall on the circum-n-sphere...
Tl;dr: circumcircle is the bounding box but a circle.
No, a circumcircle is a circle that contains _all_ of the vertices of the polygon. It always exists and is unique for a triangle, but polygons with more vertices generally do not have a circumcircle. The Delaunay triangulation has the property that no vertex lies inside of any triangle's circumcircle. It avoids long thin triangles because those have big circumcircles.
Sounds painful
@@galoomba5559 As a wise man said, the best way to get info on the internet, is to post something wrong and wait until someone corrects you. 😂
Well done! This is great work and the level of detail provided is truly appreciated. I absolutely hate videos that pander to the lowest common denominator and skip the really important stuff.
This video is criminally underviewed imo
At step 4, when adding extra hallways, instead of a flat rate, increase the odds based on the distance according to the tree, so rooms that would be far from each other on the tree from the previous step would be more likely to connect, while two rooms with very short connection already will be less likely to gain a clearly redundant path.
I'd think you'd actually do the opposite; two rooms nearby would obviously be connected, but two further away would not waste resources and would just connect via intermediate rooms.
@@JD2jr. I'm talking about after the initial tree of connections is established, so during the step of jacqueying the dungeon to create looping paths instead linear branches, that's the point that far away rooms on the tree should be more likely to connect, (especially if they are close physically).
@@hikarihitomi7706 Oh, I thought you meant close physically, because... that's usually what "close" means. lol
@@JD2jr. That's why I specified "according to the tree." As they say, the devil's in the details. :)
The great thing with this is, with the MST, you can define the critical path and as a result, add keys and/or puzzles to make sure that the player is always able to traverse from the beginning to the end.
9:27 If you like this video and want to see more like it, DONT GET YOUR HOPES UP
Wow this is very great work! Especially figuring out the hallways with the Stars in 3D was very impressive. Your channel deserve a lot more views and subscribers, keep going!
it's not the "Stars" it's an A* pathfinder algorithm (pronounced A-Star), a further heuristics-based development of the original Dijkstra's pathfinding algorithm.
en.wikipedia.org/wiki/Dijkstra%27s_algorithm
en.wikipedia.org/wiki/A*_search_algorithm
While Delaunay triangulation is typically used for computer graphics and other visual domains, A* is another of the non-trivial algorithms famed for its ubiquity. Naturally, A* is a staple in the indie game dev, fully implemented in virtually every programming language. Though several other extended variants and heavily improved algorithms supersede it in the actual domain of graph search and pathfinding (and more often than not this is necessary for performance reasons), it is still heavily used a) for learning, b) because its highly customizable, but also c) as a precursor to more complex algorithms, for example in planning solutions (aka the AI) such as GOAP, where it finds the shortest path between any two abstract world states in memory, helping the planner to backtrack from the desired outcome back to the steps preceding it, in the most optimal way thanks to easily configurable costs and heuristics.
@@milanstevic8424 autocorrect played me badly... 😅
@@Heloin42 did you mean stairs? lol
Some seriously good content here, thanks for sharing, Vaz. Loved the ending too!
This is awesome I love it, the result is so satisfying to say that it was generated randomly. You did an incredible job !
wait what? randomly.You
@@lubu682 this wasn't intended ofc
@@nawakman ye but its funny
For added realism/variation, I would have tried a few things differently:
1. Allow a small chance that if a room is above a certain size, it could also be multiple stories tall (vaulted ceiling). Pathfinding from the lower floor would be normal. Pathfinding from the upper floors would require the insertion of a balcony, either at that point or full/partial perimeter of the room.
2. I would have done each floor separately, then used a dedicated algorithm to place stairways. That would allow for some variations in the stairs, including having them switch back with a landing, or even be spirals. It would look for a suitable space that connects to at least one upper or lower room or corridor, then do an additional pathfinding pass to make sure it's connected on both.
3. I would designate some room types, including a "master corridor" type. There would be rules for where they could be placed and how they could be connected. (Good RNG is never fully random.)
4. Large rooms could be split into "sub rooms" for the sake of pathfinding to create doors, allowing large rooms to have several entrances and exits. A large enough room would also have a small chance of allowing a staircase to be placed inside it, with a much higher chance if it is the "master corridor" room type.
You're free to do so. I'd like to see the result, but I don't get my hopes up.
This is wonderful! I have just gotten started with random level generation and this is the kind of stuff I'd love to do one day. The way you incorporated the stairs is brilliant.
I'm just getting started in game design with plans to do 3d games down the road, and I like this concept. One thing I'd point out is that stairs and hallways shouldn't be given equal opportunity to generate as in a "real" dungeon (you know what I mean) choke-points offer crowd control options in case of invaders. Instead, each floor should generate separately then have one main stairway with a higher percentage chance to generate closer to the entrance and two to four others generate with low chance to generate close to the entrance but raises further away.
Alternately, in castles staircases were opportunities to ambush invaders withthe exception of the Grand Enterance. The Grand Enterance could be generated as a two-level tall entity and then treated as the generation point for the second floor. Then add a low chance for another two-level entity to generate on teh second floor that would be the spawn point for the next floor and so-on. Then find places where all three floors can connect vertically to drop in spiral staircases, and finally add the servants' staircases around the edges of each floor.
Of course, I recognize I might be spouting nonsense as I don't understand coding any better than cuniform. 😅
Honestly pretty sweet. I was thinking about creating an open-world game that takes place in an underground city or something like that, and procedural generation like this is definitely something I'm going to keep my eye on.
Kinda cool. I love the last sentence, "If you like this video and want to see more like it don't get your hopes up." XD
The best thing here is that you name all algorithms you used. This is so useful! I would probably never found half of them otherwise but now I know about their existence and can use them!
You could call the new pathfinding algorithm A-Stair
As you said at the end it's a good base for dungeon generation, my brain was already flying through different tweaks and addition rules I would add so that the starting rooms, boss rooms, shops, or whatever special rooms would all be paced properly, as to not rush with one connection between the start and end of the dungeon. Whatever you end up making be sure to at least show the finished project! And as a final note, this reminded me of this indie title called Necropolis that has 3D procedural dungeons, it's system was not the most polished, and the game itself has a lot of issues just in the design choices, but I can't believe I never inquired as to how the generation works before now!
This is incredible! with several options (random or chosen by the programmer) like several design tastes by area, spiral staircases, elevators, outside zones or things like that, the result can be even more mind-blowing.
I had in mind to make a game with a randomly generated dungeon but now I realise that it's not time yet for this XD
Great video!
@Vazgriz Just wanted to let you know that I followed your guide loosely and was able to get a proper level generation system up and running! I already had a prototype for my gameplay and plan to continue working on my 3rd person ARPG roguelike.
I also wrote a 3D Dungeon generator for my bachelor topic, but yours is a better and more general approach.
Mine was a bit rushed due to time constraints. I only had about two weeks to create the rooms and code.
I wonder if replacing the MST with a cycle-finding algorithm would result in a cycle-oriented dungeon design(like in Unexplored)
I actually read a book where an unexplored dev talks about the generation of their dungeons. It's based on graph manipulation, starting with a "start" and "end" node that lead to each other, then adding nodes between them until the dungeon is complex enough. It's actually pretty interesting, the book is called "procedural generation in game design," and it was co-written by the guy who made dwarf fortress.
@@DavidSilva-el7el Yeah there's probably an advantage to that approach instead of throwing up random rooms and then looking for a good way to connect them.
Although this random room approach in the video might make less repetitive results that feel less contrived, possibly. I really have nothing to back up that statement, other than intuition.
This makes incredibly natural and clean looking layouts for a procedural algorithm! Excellent work. How did you handle the hallways that failed to pathfind? Are you guaranteed to still have some path through the dungeon to get from any one room to any other room or are there potentially breaks that split the dungeon?
This was awesome. And a great way of explaining it on a very good level. Also, I love how deeply you 'grok' A* and (ab)use it for your ends!
That's an interesting approach, it differs a lot from the commol voxel engine approach to generate the hallways/staircases first (aka like minecraft cave system) then automatically add the room tiles afterwards in spaces that match given criteria.
Beautiful work man! Congrats! Saved the video for future consultations. Cheers.
Still Best RUclips Algo Vid I've seen on this
This is honestly rather incredible... No hopes of doing anything like this in Godot any time soon, but I'd love to one day.
This thing makes the game unique for each player. Keep up the good work...
This looks amazing, thanks for sharing your work!
At the spanning tree stage, the level could be the longest path; keys at dead-ends open doors at prior junctions.
When adding random loop-back paths, place locked doors in them with keys nearby on the side reached later in the level.
(FTL Dungeon Master 1987 and Captive (procedurally generated from a floppy disk) 1990 were like this)
Let's fill the floor halfway with green juice ...
SEWER COUNT INTENSIFIES !!! Hehehe
Great work, Vazgriz:) Thanks for showing this off.
Sweet!
★Ladders
★Trap-doors (especially in very small rooms/toilet)
★Large rooms separated by walls with doors or barred windows
★Long rooms having dungeon cells beside the corridor
★4th dimension (trendy and rarely done properly)🤞
Thanks so much for sharing! I've been using Delaunay triangulation for generating FPS maps but I've hit a rut, I think this might help me continue my work in a new direction!
You also can run alg in two projections and just impose them together. Only problem is when cube placed in dioganal direction to previous. But it’s exception case witch can be solved by predefined chose or for example rounding middle point of the line to compute belonging to nearest avaluable coorinate position. Also cool visualization
could this be done at runtime to create infinite dungeons from a seed value? points being generated randomly based on a specified distance from the camera with a height constraint. it would need a little tweaking with the MST to have it not immediately flag all rooms as "essential".
the trick being, not to let it end up as a long single pathway through every room generated as you move around. better to have many branches and loops back to another room. I could definitely see it making for an awesome dungeon crawler with fully randomized loot, assets, themes, specific structures, randomized but somewhat levelled combat. could be as simple as spawning enemies and items during generation, then ofc you could have a few dozen huge setpiece rooms that only ever spawned in once in a seed and occasionally have a boss fight in them.
This is so cool!! I love your art too, looks great. This gives me inspiration to do something similar to create buildings in my own project!!
This is good stuff, I'm sure. A little over my head right now. It got really dificult around 4:35 when the background music went hog-wild.
Amazing breakdown of a way to automate a 3d layout . I have ideas for better generation but it's very much beginner thoughts on how to achieve / transition : I basically used multiple counting loops example you have a 500 room maze setup a matrix then for room = 1 to 500 ---then used a matrix check in another loop that counts like room but we will call him loop to see if the room has data if yes see if finished tagged no ? then run a loop test for a hit (the test can always be a variable /prior set ) oh it hit what number we on ? room 1 loop 12 well now room 1 and room 12 should be linked... That is about all I can recall of the old program I wrote in basic but it was a text adventure ai that I made back in 1995.. I kind of got out of computers and wouldn't try programming again for years oh I exited the loop for the room if the loop had more then 2 to 5 hits (it was rng) but yeah this structure was memory intense and on the slug 486 pc it would take a whole 30 to 40 minutes to just figure out how to write the text adventure , so the code even when it was complete was pretty awful. Still it could easily combine with the given concept happy trails and don't go making a terminator or do, I no longer care.
5:21 Oh, NOW he says "This is where it gets complicated".
I very rarely subscribe on command but when you told me not to get my hopes up I smashed that button. Very informative, well produced and, evidently, under-appreciated content.
Very nice! Reminds me of some of the work I did for my honours project. Mine was a sci-fi game, so I had lifts too, and preferred to avoid hallways.
This looks like such huge amount of work! Well done
I suppose you can always try again if your algorithm cant create a certain dungeon, or even go non-euclidean (like mc escher) with the hallways...
9:15 Bruh, you had an emergent ROOM! :D
a BIG thank you, man! your code really helped me whith my own generator
I thought your tone would be too offputting, but the content of the video is actually really good.
Wouldn't a Wave Function Collapse algorithm be more suitable for this purpose?
I was wondering how it decides where to place the doors when multiple hallway tiles are adjacent to a room
The future of gaming: Click generate a game button.
Give it a title. Sell it. Be rich.
I am working on a game and I will definitely revisit this video a few times! Thanks a lot for the content! I just gave you a subscriber.
You sounded from the video that you "hacked" a variant of the A* algorithm. But the abstract A* algorithm is implemented on a mathematical graph, not on a 2D grid. Did you think of adding a specific edge for staircases with its own distance weight that would be used to connect cells that are 2 across and one up and then implementing the classic A* algorithm for graphs? It's mathematically a bit more involved but you might recover your performance you were looking for.
In other words, each cell would have 12 neighbors instead of 4 (minus obstructions): the four cells adjacent to it, and the 8 possible staircases that can connect to it (all four directions, but going up and down are options). Then you just give staircases the appropriate weight for the distance they take and you run classical A*
In the approach that Vazgriz described, stairs consist of multiple cells, and classical A* does not address that.
Because of that, the paths that A* generates, will often have self-intersections (stairs can intersect other stairs and corridors).
For example, nothing stops classical A* from generating two adjacent staircases that go (0, 0, 0) -> (3, 1, 0) -> (0, 2, 0).
This is spectacular, but would anyone happen to know any resources on how to place custom walls, floors, ect in line with a script like this?
Great explanation! Are you planning to make this dungeon game a full release?
Don't get your hopes up. ;-)
God imagine this sort of algorithm in a 'modernized' Pokemon Mystery Dungeon game, swapping out the tile movement for real time action combat.
That would be fucking sweet.
the new youtube feature is actually interesting because it shows the ending is the most replayed section of the video
You never explained how the doors are located
There’s a github repo so thats a win
Some one know how to make this in BP UE5? @@nikefootbag
I presume doors are added by using the start and end tiles of a pathfind, but him showing two hallways that connect to the same door make me question this.
useful for my new dungeon setup. noone shall escape.
That's interesting, now I lowkey wanna make a dungeon game
If I’d want to change the cubes for asset models. How can I change the code to recognise which rooms with which doors I should chose? I’m really interesting in that part of the algorithm modification. Thanks a lot for your video explanation.
I'd imagine the initial room size would be a function the algorithm would start with, so you have 20 or so unique rooms each with a regular footprint that fits neatly in a tile. Or, you could create a 3-d tileset that would be used to build each room allowing for more flexibility in room size. There are lots of videos on how to build and implement those tilesets, but I'm not going to pretend I know more about them other than they exist. 😅
@@RamDragon32 of course, I imagined there are one model of each room. However, as we’ve can see, the corridors fill more than one space next to the room. Moreover, the room is not always in the same wall or floor.
What I want to know is how I can know where the door will go in the wall, if it is a checkpoint, if it is another extra implementation in the font code…
Thanks in advance.🙏🏼
that ending is beautiful
*Vazgriz when researches don't outline an algorithm for the mathematically complex procedure he needs*: Fine, I'll do it myself
Im attempting to recreate this (with the same asset pack.) I'm making a room using all blank walls, then using ray casting to find/swap out walls for doors, and finally building a path from door to door. Eventually I want a logic script that will look at the room's "type" and size and the auto fill with appropriate assets.
if you do a follow up video of setting this up and getting it runnin that would be great
Damn you crushed the ending. My hopes and dreams lie in ruin 😭
do you add your own art after the generation?
I think the bug where hallways intersected stairs would be an interesting way to introduce fake stairs, or possibly overlooks on the other side of the staircase.
Hey great video!
Could you please make a video on how to add assets? Doesn't have to be perfect, just so we can have an idead.
Thank you!
what’s the song that starts around 4:23
Really well done! But how do you get the rooms and corridors or prefabs integrated?
my god, my dream ! you're a genius...i would like to implement this ..but currently im too focused on completion of my game, however this brings me into a conundrum...if i could implement this, then the game could be completed in two days, because 29 levels could be generated so quickly...but the problem is implementing this algorithm would be a pain...it would itself take months to implement...
Are all the rooms premade prefabs? since the code generates the rooms randomly within a certain scale range, would you have to make room prefabs for all possible room scalings and have the code fetch them when that particular room is generated?
"dont get your hopes up" best CTA ever
I like this video and want to see the final game produced.
Managing expectations is a good thing. I guess. Not going to lie. It made me subscribe
This is really good. Why not turn it into a Unity Asset and put it in the store ? I would defo buy it.
This is very interesting. I will try to implement something like this for my game in my own engine.
Amazing!! just what I was looking for!!
I have one question. I looked up your github and it seem like github example doesnt have prefabs of dungeon walls and stairs like 8:39.
Can you please share the dungeon prefab implemented version??
Since i am newbie, its hard for me to customize.
Thank you!
The dungeon assets are from Synty Studios. I can't share them.
@@Vazgriz if its unsharable, can you please provide tutorial of how to implement wall and stairs prefabs?? Id be so happy if i learn how!
You shouldve researched math that is used on architecture. By using modulor you are able to define an exact 3d grid that would remove any possibilities of unused connections. That way using a restriction on first step it will generate less headache down the path.
Very good explanation, and great video, thank you
Can you explain the actual meaning of "step5.pathfind hallways"?
Does that technique makes the cycle manually and randomly?
This may be a long shot, but does anyone know why my delauney would be generating longer lines than it should be?
very nice- makes me think of Minecraft stronghold and fortress generation. One option would be to create the corridors and stairs in a random fashion then add rooms
or just pre-fab wave function collapse (block matching generator in 3d, or just pipe fitting simulator)
How would you code the placement of the tiles?
Really cool! I'm glad I found this video. I am actually making a game where the levels are massive, but contain many of these "dungeons" placed throughout. And I am looking to see how other people are solving the problem. I've made my own version of this, but it's a bit more "primitive" and could be better.
I had a problem with the room placement, and finding an efficient way to make sure a generated room doesn't occupy the same space as existing rooms. But I kinda just "fudged" that idea to make dungeons interesting.
But with that being said, I am curious about how exactly you place the rooms at this step 1:11.
Also, when you showed this 0:51 , that made a lightbulb go off in my head about certain things.
But I am curious about the details to how you placed each dungeon, and any checks you might've done.
If you like this video and want to see more like it don't get your hopes up - subbed!
For staircases, could you not have given an infinite cost to going up more than once in a row?
This is some next level (HA!) dungeon creation. Do you have anything for rough cut tunnels? How about natural looking caverns with stalagmites and stalactites? Or that really weird cavern down there in Mexico? The one with those huge crystals. I think it's in Mexico, anyways, no one has explored it fully because it is so hot in there. Geothermal something or other.
not sure if you've heard of it but Deep Rock Galactic implements procedural generation with caves- and does it extremely well
I realize this is nearly a year old now, but I went ahead and started recreating it (trying to use the repository as little as possible) and I noticed in a console log that it thinks there are a lot more edges than there actually are after completing the Bowyer Watson algorithm. I assume this gets taken care of automatically by the MST search, but I would be curious as to why it's happening here as if I could, I would prefer to clean it now for performance reasons.
What version of Unity was this created in, and how high in version do you think it would go?
Nice. Better than my 3D dungeon generator. I just made a 2D maze for each floor with recursive backtracking, then carved it into rooms....
I think you could have simplified the problem in 3D by doing it first in 2D and then adding vertical offsets. Not sure, if that would run into issues but just a suggestion.
This would work. But since the rooms are originally generated in 2D, it means that rooms won't overlap with each other. IE one room being over another. You would still need an algorithm to connect rooms on different levels.
This would be fine if you just want verticality in your maps.
I have downloaded this and it is working well, but as the blog post says, "the art assets and the code for placing them is missing". Where can I find it, or at least does anyone want to collaborate on making asset placement code? I think I would like to make my own assets, maybe a more natural looking cave system with stalagmites and stalagmite, and rough cut stairs.
I did same thing inside Unreal Engine, that's also could be used for 2D and 3D maps totally works same as enter the gungeon procedural map generation. I wonder if I convert this to plugin, would people be insterested.Rooms are premade and corridors to connect one room to another if overlapping is involved is procedural.
Hello, what a blast. Thank you so much for doing this.
Btw. Are there some obvious / non-obvious requirements for the input parameters? (talking about the 2D maze now)
Time to time I have OutOfRange exception in CreateHallways when there are no edges calculated.
Also, once I had a case when one room stayed as an isolated Island.
The configuration was: Size [30,30], Roomcount:10, RoomMaxSize: [10,10] …random seed 3
(I guess the room size was too much or so. : ) I cannot wrap my head around the triangulation alg now, to debug it by my self.)
Wow, you really took a hard way to make a dungeon There is a much easier method that I used in my roguelike that produced nearly the same result. I placed the rooms in an area like you did and added the rooms coords to a list. Once I had all the rooms placed I selected the first room from the list and a random room from the list. I started at the center of the first room and walked to the center of the other room. I used the Manhattan algorithm to walk to the target room. If I encountered a room along the way, I ended the walk and removed the first room from the list. I marked the wall location and added a door to booth rooms. I did this for all the rooms on the list. Once all the room have been processed, there is a connection to every room in the floor. You don't need all those algorithms you used.
this is just a different approach. Another way to handle this is by predesigning all of the rooms, and marking the connections it has. Then you can place a random room, and connect another room/hallway on each connection. If a room is chosen decrease the chance of it appearing. Also keep a separate list of dead end rooms, and allow them to be used when the dungeon reaches a preferred size.
@@lintycarcass You run into problems placing rooms if you connect them as you place them. It is much easier to put a bunch of rooms into the dungeon space and then connect them. My method is very fast, every room is connected and you get interesting paths as corridors cross over each other. I have tried numerous dungeon building algorithms and this is fast, easy to implement and produces nice dungeon layouts. I use the Manhattan algorithm to ensure that corridors are square so you don't get any funny artifacts. This method is also easily adjusted to floor size by just adjusting the number of rooms. Nothing else needs to be changed. I have yet to see a method better than this.
@@lintycarcass Btw, you can make rooms of any shape with my method, do you don't have to have square rooms.
@@RickClark58 i never said you can only use square rooms. a collision detection system is very easy to implement, you can even use that as a base for creating a map of the dungeon layout as well. Creating a dungeon really doesn't have to be fast either. Of course faster load times are always better, but even by implementing a bunch of algorithms like this video wouldn't take that long in runtime. Loading times in 3d games mainly come from all of the assets and models. Not from creating the dungeon layout.