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.
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.
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.
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).
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.
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.
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!
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.
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!
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.
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!
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 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 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.
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'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)
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
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?
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.
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 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 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.
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)🤞
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.
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.
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).
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.
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.
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?
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...
Does anyone know how to generate wider hallways? What I've done is change the A* cost function so it's more expensive to join existing hallways, then I made the hallway generation between two given rooms run a certain amount of times to create wider hallways. This works most of the time but has the obvious side-effect of creating some very bizarre corridors. Is there a better way to implement this?
Figured out another way to do this: lowering the cost for empty tiles adjacent to hallways tiles while increasing the cost of hallway tiles. This makes the pathfinder want to run in parallel to existing hallways. It doesn't always work, however, some one-unit-wide hallways still appear from time to time.
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.
is there a way to make the behavior predictable? could you make the randomizer run from a seed that would always produce the same dungeon given the same inputs?
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!
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
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.
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.
Btw do you think having specific rooms that the generator can pick from based on conditions would be possible like a spiraling staircase for a hall gong straight up?
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 wanted to try the 2d code for this and I have not been successful, because it doesn't work with the 'using Graphs;' line of code, and removing it doesn't resolve all errors, because there's also the times where you USED the graphs library. How do I fix this?
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.
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.
@@milanstevic8424 autocorrect played me badly... 😅
@@Heloin42 did you mean stairs? lol
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.
Some seriously good content here, thanks for sharing, Vaz. Loved the ending too!
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 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
This video is criminally underviewed imo
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.
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. 😅
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!
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.
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!
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!
9:27 If you like this video and want to see more like it, DONT GET YOUR HOPES UP
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!
Beautiful work man! Congrats! Saved the video for future consultations. Cheers.
You could call the new pathfinding algorithm A-Stair
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 was wondering how it decides where to place the doors when multiple hallway tiles are adjacent to a room
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
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!!
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 is honestly rather incredible... No hopes of doing anything like this in Godot any time soon, but I'd love to one day.
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!
This looks amazing, thanks for sharing your work!
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 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 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 thing makes the game unique for each player. Keep up the good work...
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'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)
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.
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
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.
This may be a long shot, but does anyone know why my delauney would be generating longer lines than it should be?
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?
Let's fill the floor halfway with green juice ...
SEWER COUNT INTENSIFIES !!! Hehehe
Great work, Vazgriz:) Thanks for showing this off.
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.
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 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 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.
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)🤞
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.
Still Best UA-cam Algo Vid I've seen on this
what’s the song that starts around 4:23
How would you code the placement of the tiles?
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!
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.
the new youtube feature is actually interesting because it shows the ending is the most replayed section of the video
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.
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).
if you do a follow up video of setting this up and getting it runnin that would be great
How do you go about turning the colored cubes into hollowed rooms, hallways, and 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.
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.
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?
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...
Does anyone know how to generate wider hallways? What I've done is change the A* cost function so it's more expensive to join existing hallways, then I made the hallway generation between two given rooms run a certain amount of times to create wider hallways. This works most of the time but has the obvious side-effect of creating some very bizarre corridors. Is there a better way to implement this?
Figured out another way to do this: lowering the cost for empty tiles adjacent to hallways tiles while increasing the cost of hallway tiles. This makes the pathfinder want to run in parallel to existing hallways. It doesn't always work, however, some one-unit-wide hallways still appear from time to time.
@@rodbot Have you tried widening the hallways after the fact as a postprocessing step?
What version of Unity was this created in, and how high in version do you think it would go?
Very good explanation, and great video, thank you
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.
Wouldn't a Wave Function Collapse algorithm be more suitable for this purpose?
9:15 Bruh, you had an emergent ROOM! :D
is there a way to make the behavior predictable? could you make the randomizer run from a seed that would always produce the same dungeon given the same inputs?
Im very new to programming so this is a dumb question but how wpuld i go about making my code remember it's route like you did with the A*
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!
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
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.
This is very interesting. I will try to implement something like this for my game in my own engine.
Managing expectations is a good thing. I guess. Not going to lie. It made me subscribe
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
I’m having trouble getting floors or ceilings to generate around the rooms… any tips?
For staircases, could you not have given an infinite cost to going up more than once in a row?
What about use ladders to climb up the straight up blue boxes?
That's interesting, now I lowkey wanna make a dungeon game
Btw do you think having specific rooms that the generator can pick from based on conditions would be possible like a spiraling staircase for a hall gong straight up?
that ending is beautiful
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
How did you then get it to know where to place doors and walls? (Ie, how does each hallway cube know where to connect to other hallways and to rooms?)
How can i combine this Gitrepo with assets like he did at the end of the video. Never did Dungeon generation or anything like that.
do you add your own art after the generation?
Can you explain the actual meaning of "step5.pathfind hallways"?
Does that technique makes the cycle manually and randomly?
Great explanation! Are you planning to make this dungeon game a full release?
Don't get your hopes up. ;-)
5:21 Oh, NOW he says "This is where it gets complicated".
I like this video and want to see the final game produced.
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
or just pre-fab wave function collapse (block matching generator in 3d, or just pipe fitting simulator)
I wanted to try the 2d code for this and I have not been successful, because it doesn't work with the 'using Graphs;' line of code, and removing it doesn't resolve all errors, because there's also the times where you USED the graphs library. How do I fix this?
Graphs.cs is included in the repo. You have to download the entire repo to use it properly.