ฝัง
- เผยแพร่เมื่อ 3 มิ.ย. 2024
- This video describes an algorithm for procedurally generating 2D and 3D dungeons.
Read the original blog post here: vazgriz.com/119/procedurally-...
Github repo: github.com/vazgriz/DungeonGen...
0:00 Intro
1:03 2D Algorithm
3:40 2D Dungeon Example
4:17 3D Algorithm
8:39 3D Dungeon Example
#gamedev #unity3d - วิทยาศาสตร์และเทคโนโลยี
![แข่งแลกของ 1 วัน!! ของใครแพงสุดชนะ!! [Ver.2024]](http://i.ytimg.com/vi/joRT59ilPHg/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.
The emergent features are genuinely pretty fantastic. Thanks for the video
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.
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. 😂
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. :)
For added realism/variation, I would have tried a few things differently:
1. Allow a small chance that if a room is above a certain size, it could also be multiple stories tall (vaulted ceiling). Pathfinding from the lower floor would be normal. Pathfinding from the upper floors would require the insertion of a balcony, either at that point or full/partial perimeter of the room.
2. I would have done each floor separately, then used a dedicated algorithm to place stairways. That would allow for some variations in the stairs, including having them switch back with a landing, or even be spirals. It would look for a suitable space that connects to at least one upper or lower room or corridor, then do an additional pathfinding pass to make sure it's connected on both.
3. I would designate some room types, including a "master corridor" type. There would be rules for where they could be placed and how they could be connected. (Good RNG is never fully random.)
4. Large rooms could be split into "sub rooms" for the sake of pathfinding to create doors, allowing large rooms to have several entrances and exits. A large enough room would also have a small chance of allowing a staircase to be placed inside it, with a much higher chance if it is the "master corridor" room type.
You're free to do so. I'd like to see the result, but I don't get my hopes up.
This is wonderful! I have just gotten started with random level generation and this is the kind of stuff I'd love to do one day. The way you incorporated the stairs is brilliant.
Some seriously good content here, thanks for sharing, Vaz. Loved the ending too!
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.
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
You could call the new pathfinding algorithm A-Stair
Beautiful work man! Congrats! Saved the video for future consultations. Cheers.
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!
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 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 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!
This looks amazing, thanks for sharing your work!
This video is criminally underviewed imo
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
@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.
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.
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.
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...
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 had a real problem concentrating near the end. That music was all over the place and distracting as hell XD
I loved the first 3/4 though and your tech is a thing of beauty :)
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?
The best thing here is that you name all algorithms you used. This is so useful! I would probably never found half of them otherwise but now I know about their existence and can use them!
You 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 thing makes the game unique for each player. Keep up the good work...
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.
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.
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 good explanation, and great video, thank you
a BIG thank you, man! your code really helped me whith my own generator
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 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!
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.
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
Thanks for sharing and keep up the good work :)
Great explanation! Are you planning to make this dungeon game a full release?
Don't get your hopes up. ;-)
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 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 am working on a game and I will definitely revisit this video a few times! Thanks a lot for the content! I just gave you a subscriber.
You sounded from the video that you "hacked" a variant of the A* algorithm. But the abstract A* algorithm is implemented on a mathematical graph, not on a 2D grid. Did you think of adding a specific edge for staircases with its own distance weight that would be used to connect cells that are 2 across and one up and then implementing the classic A* algorithm for graphs? It's mathematically a bit more involved but you might recover your performance you were looking for.
In other words, each cell would have 12 neighbors instead of 4 (minus obstructions): the four cells adjacent to it, and the 8 possible staircases that can connect to it (all four directions, but going up and down are options). Then you just give staircases the appropriate weight for the distance they take and you run classical A*
In the approach that Vazgriz described, stairs consist of multiple cells, and classical A* does not address that.
Because of that, the paths that A* generates, will often have self-intersections (stairs can intersect other stairs and corridors).
For example, nothing stops classical A* from generating two adjacent staircases that go (0, 0, 0) -> (3, 1, 0) -> (0, 2, 0).
This is 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.
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
could this be done at runtime to create infinite dungeons from a seed value? points being generated randomly based on a specified distance from the camera with a height constraint. it would need a little tweaking with the MST to have it not immediately flag all rooms as "essential".
the trick being, not to let it end up as a long single pathway through every room generated as you move around. better to have many branches and loops back to another room. I could definitely see it making for an awesome dungeon crawler with fully randomized loot, assets, themes, specific structures, randomized but somewhat levelled combat. could be as simple as spawning enemies and items during generation, then ofc you could have a few dozen huge setpiece rooms that only ever spawned in once in a seed and occasionally have a boss fight in them.
This is very interesting. I will try to implement something like this for my game in my own engine.
great vid. gonna try to implement this in ue4 for fun :-)
Really well done! But how do you get the rooms and corridors or prefabs integrated?
Job well done, really nice work!!!!!
Thanks for sharing the 'm gonna try it out later.
if you do a follow up video of setting this up and getting it runnin that would be great
Let's fill the floor halfway with green juice ...
SEWER COUNT INTENSIFIES !!! Hehehe
Great work, Vazgriz:) Thanks for showing this off.
Sweet!
★Ladders
★Trap-doors (especially in very small rooms/toilet)
★Large rooms separated by walls with doors or barred windows
★Long rooms having dungeon cells beside the corridor
★4th dimension (trendy and rarely done properly)🤞
I thought your tone would be too offputting, but the content of the video is actually really good.
Amazing job done, so cool
I was wondering how it decides where to place the doors when multiple hallway tiles are adjacent to a room
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.
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.
that ending is beautiful
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...
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.)
How would you code the placement of the tiles?
That's interesting, now I lowkey wanna make a dungeon game
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!
Nice! Great work.
9:15 Bruh, you had an emergent ROOM! :D
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 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?
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?
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?)
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
Managing expectations is a good thing. I guess. Not going to lie. It made me subscribe
Very cool! I like it a lot.
useful for my new dungeon setup. noone shall escape.
How do you go about turning the colored cubes into hollowed rooms, hallways, and stairs
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?
the new youtube feature is actually interesting because it shows the ending is the most replayed section of the video
Very interesting video ! IMO, the music is a bit too loud and is a bit disturbing.
Awesome work
I like this video and want to see the final game produced.
Nicely done.
hey which assets for textures and 3D Models did you use please ?
Nice. Better than my 3D dungeon generator. I just made a 2D maze for each floor with recursive backtracking, then carved it into rooms....
I’m having trouble getting floors or ceilings to generate around the rooms… any tips?
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*
Implement this into an ARPG looter dungeon crawler in VR. Would be INSANE!
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.
Damn you crushed the ending. My hopes and dreams lie in ruin 😭
9:27 If you like this video and want to see more like it, DONT GET YOUR HOPES UP
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.
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
Can you explain the actual meaning of "step5.pathfind hallways"?
Does that technique makes the cycle manually and randomly?
Thanks, that was interesting
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!
beautiful algorithm!!