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.
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.
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).
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.
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.
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. 😅
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!
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.
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.
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.
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 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.
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.
@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.
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)🤞
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)
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!
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.
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.
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.
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.
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.
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.
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?
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!
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).
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.
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
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.
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.🙏🏼
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...
Might be neat to have AI creatures that compete to hide loot from one another. And different AI with different ideas on what "loot" is. Creating automatic dungeon scenery placement. Rats that hide trash, wardens that hide torture implements, goblins that hide shiny things, dogs that hide bones. Etc.
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.)
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...
I would like you to check out blender geometry nodes - I think we are only missing A* - I have A* for bpy - final evaluated mesh - but we need it in c++ / geonodes next
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.
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.
I would love to play a multiplayer version of who can collect the first 5000 pts of gems in total which most gems worth 10 points will reappear on the lower level after 20 seconds, while the gems worth 250 points will reappear on the upper level every 30 seconds.
This is great! You can definitely travel vertically between rooms though, ladders and elevators exist, maybe they would add even more intrigue and emergent structures to the generator.
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.
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.
Since the Ai places rooms, then attaches pathways then any Ai that builds the content loops (boos room, keys,leavers ,extras, ect) would be having to force it into place rather then having the AI build the dungeon to accommodate the loop. Personally im wondering if the Ai can be taught to give the generation more structure on command allowing more precious in procedural crafting the intend experience. This dungeon design would work great for a open ended design, or an actual maze design. But random dungeons would have more weight if the AI could also build a structured dungeon with a focus design.
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 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.
Great video! I've done 2D procedural generation a fair bit and my latest approach was similar in some ways. I randomly placed buildings and then used A* path finding to make connections between them, but these are not corridors, they are roads which npcs use to get from place to place. I made the generator calculate a path from each building to every other one, but favoured road tiles, so I end up with a fairly decent looking settlement + roads. Sometimes it means that a building has a longer path to another one than if I just took the shortest route and I'm not decided on if that's a good or had thing yet.
![[MV] A leap of faith...ความเชื่อใจครั้งสุดท้าย (From "Petrichor the series")](http://i.ytimg.com/vi/U1piZH2CNXA/mqdefault.jpg)
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.
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.
The emergent features are genuinely pretty fantastic. Thanks for the video
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. 😂
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.
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. :)
This video is criminally underviewed imo
You could call the new pathfinding algorithm A-Stair
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.
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.
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. 😅
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
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!
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.
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.
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 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.
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
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.
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.
@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.
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)🤞
This is honestly rather incredible... No hopes of doing anything like this in Godot any time soon, but I'd love to one day.
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!
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)
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!
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.
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.
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.
Still Best TH-cam Algo Vid I've seen on this
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!
the new youtube feature is actually interesting because it shows the ending is the most replayed section of the video
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.
9:15 Bruh, you had an emergent ROOM! :D
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!
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.
Let's fill the floor halfway with green juice ...
SEWER COUNT INTENSIFIES !!! Hehehe
Great work, Vazgriz:) Thanks for showing this off.
9:27 If you like this video and want to see more like it, DONT GET YOUR HOPES UP
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.
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?
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 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.
Beautiful work man! Congrats! Saved the video for future consultations. Cheers.
if you do a follow up video of setting this up and getting it runnin that would be great
I was wondering how it decides where to place the doors when multiple hallway tiles are adjacent to a room
Implement this into an ARPG looter dungeon crawler in VR. Would be INSANE!
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?
I thought your tone would be too offputting, but the content of the video is actually really good.
Nice. Better than my 3D dungeon generator. I just made a 2D maze for each floor with recursive backtracking, then carved it into rooms....
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!
I like this video and want to see the final game produced.
That's interesting, now I lowkey wanna make a dungeon game
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).
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.
*Vazgriz when researches don't outline an algorithm for the mathematically complex procedure he needs*: Fine, I'll do it myself
Wouldn't a Wave Function Collapse algorithm be more suitable for this purpose?
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
Damn you crushed the ending. My hopes and dreams lie in ruin 😭
Really well done! But how do you get the rooms and corridors or prefabs integrated?
5:21 Oh, NOW he says "This is where it gets complicated".
This thing makes the game unique for each player. Keep up the good work...
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 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
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.🙏🏼
useful for my new dungeon setup. noone shall escape.
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...
"dont get your hopes up" best CTA ever
Might be neat to have AI creatures that compete to hide loot from one another. And different AI with different ideas on what "loot" is. Creating automatic dungeon scenery placement. Rats that hide trash, wardens that hide torture implements, goblins that hide shiny things, dogs that hide bones. Etc.
What bullshit is this
The future of gaming: Click generate a game button.
Give it a title. Sell it. Be rich.
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.)
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...
Managing expectations is a good thing. I guess. Not going to lie. It made me subscribe
I would like you to check out blender geometry nodes - I think we are only missing A* - I have A* for bpy - final evaluated mesh - but we need it in c++ / geonodes next
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.
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.
Great explanation! Are you planning to make this dungeon game a full release?
Don't get your hopes up. ;-)
a BIG thank you, man! your code really helped me whith my own generator
that ending is beautiful
This is very interesting. I will try to implement something like this for my game in my own engine.
I would love to play a multiplayer version of who can collect the first 5000 pts of gems in total which most gems worth 10 points will reappear on the lower level after 20 seconds, while the gems worth 250 points will reappear on the upper level every 30 seconds.
This is great! You can definitely travel vertically between rooms though, ladders and elevators exist, maybe they would add even more intrigue and emergent structures to the generator.
And don't forget about one-way passages, like pits, jump offs and slopes.
This really got the creative juices flowing. BRB going to build a monstrous thing in Pygame haha
or just pre-fab wave function collapse (block matching generator in 3d, or just pipe fitting simulator)
This is really good. Why not turn it into a Unity Asset and put it in the store ? I would defo buy it.
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.
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.
Since the Ai places rooms, then attaches pathways then any Ai that builds the content loops (boos room, keys,leavers ,extras, ect) would be having to force it into place rather then having the AI build the dungeon to accommodate the loop. Personally im wondering if the Ai can be taught to give the generation more structure on command allowing more precious in procedural crafting the intend experience.
This dungeon design would work great for a open ended design, or an actual maze design. But random dungeons would have more weight if the AI could also build a structured dungeon with a focus design.
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.
This looks amazing, thanks for sharing your work!
Very interesting video ! IMO, the music is a bit too loud and is a bit disturbing.
cant stop thinking about the phrase "degenerate tetrahedra"
i would've just checked the difference in y and determine if there is no path next to us make it incredibly expensive to move up
that's great! you probably just need to add more hallway with more random assets.
I would so play a stylised dungeon game like this that’s random generated
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.
dat sounds like rapping over the music. awesome :)
Great video!
I've done 2D procedural generation a fair bit and my latest approach was similar in some ways. I randomly placed buildings and then used A* path finding to make connections between them, but these are not corridors, they are roads which npcs use to get from place to place.
I made the generator calculate a path from each building to every other one, but favoured road tiles, so I end up with a fairly decent looking settlement + roads.
Sometimes it means that a building has a longer path to another one than if I just took the shortest route and I'm not decided on if that's a good or had thing yet.