I rewrote my dungeon generator!
Вставка
- Опубліковано 28 лип 2023
- ⁍ Play: mythfall.com
⁍ Discord: / discord
⁍ Patreon: / unitoftime
⁍ Github: github.com/sponsors/unitoftime
⁍ Twitter: / unitoftime
// References
⁍ Boris the Brave: www.boristhebrave.com/2019/07...
⁍ Planarity: www.jasondavies.com/planarity/
⁍ Force Directed Graph Drawing: en.wikipedia.org/wiki/Force-d...
// Description
This week I worked rewrote my dungeon generation algorithm to support multiple room sizes and a more natural layout. - Наука та технологія
the graph generating would make a sick loading screen
imagine venom's tendrils doing this durng loading screens
They still have those?
True, tho 'loading screen takes as much if not more CPU than actually loading the game' sounds funny
@@CentreMetreyou can record it and just use the recording in the loading screen
@@koibubbles3302 you could, but then you'd only have a set amount, and it'd take more storage space. I guess you could pre make some and record the movements and then play the movements back, so it'd take less space, but again limited amount.
I like the fact that they're no longer in a grid. This is the thing that's been bothering me with every other dungeon generation I've tried. It just never felt right.
Just enough un-grid looking that the dungeons doesn't feel like city blocks and cubes. Feels more organic. Especially with the varying room sizes. Slick solution to just collapse everything inward without allowing them to violate the basic constraints.
Alternatively, you could create random rectangles with various dimensions, placed all over the map, and then do the crunching together process with collision detection. Then connect them all with a minimum-spanning tree. This would work in 3D, too, for a multi-leveled dungeon.
This is the same algorithm that the knowledge-base note-taking application I use (Obsidian) uses for graph view of how all your notes relate to each other.
Ah yeah obsidian is great. I use it to store all my game ideas. A lot of graph-viewer type applications use that force based approach, I think for those it ends up usually looking pretty nice.
I love obsidian notes! I use it for almost everything and even look for things to use it for. Kudos
@@UnitOfTimeYT I also just came across Obsidian and it's interesting how I'm finding more and more uses for Data Structures and Algorithms in GameDev than I ever have as a SWE/DE
Thanks for the heads up on this! I recently was looking for EXACTLY that but I couldn't find it so I settled on OneNote
Is Obsidian free and open source?
I liked the part where he said "it's dungeoning time" and then dungeoned all over the place
I like how you can see the algorithm signature in its final form.
Yeah I like how the visualizations turned out for this one too :)
I solved this problem in the past with Voronoi diagrams (they don't have to use manhattan or l2 distance). Merging nearby cells randomly, allowing for any room size/shape and eliminating any potential for crossing edges.
It seems like a very roundabout way to do something, friend.
Could you make a video on it or link to examples or source?
Huge thank you to all of the supporters that made this video possible:
Kenta Dracula Andrew Brudnak gugaskhan Dave
Jomy10 SamieZaurus Jonas Uliana Mqix CD
ok didn't know i needed monospace comments and now i need more
haha in retrospect I should have thought of that as I separated everyone's names. I don't even have a monospace font. What was I even thinking lol.
I feel like the only reason all fonts aren't monospaced is because we're drawing our glyphs wrong.
Or start with a fully connected temokate graph (ie a grid) then random walk free node only (visited nodes goes to close list, neighbors of last visited goes to open list, randomly chose within the open list at each step) after it's done randomly drop (or use designed heuristic) links between nodes not in the generation path, up to a set number, to get some cycles, bonus round, generate long distance link between nodes that aren't neighbors.
You should have assigned the room properties right when generating, with this approach you can even have more advanced properties like constraining the the boss room to be 3 rooms away from the spawn instead of doing it based on distance
I need a 10 hour version of the intro
1:30,
For both 2D-Arrays and Connected-Graphs, you are able to control all of those things:
1) How far from the start should the boss room be? That could be a random value between some min and max, call that value D for depth. When creating the dungeon, only a node with the value D can be the boss room - this can be done during the dynamic procedural construction of the dungeon, or you can assign the ideal bossroom after the dungeon layout is generated - both are fine.
2) Room sizes can be different for both. With Generalized graphs, it is easier to have accidental overlap - you can control this during the generating steps: create some kind of BitMap or Rasterization that keeps track of which pixels contain a room - if a new room would overlap those pixels, don’t create it altogether. If the rooms have a predictable geometry (ie. The rooms are rectangles or polygons, then you can check for overlapping easier).
An alternative approach to this problem is to use some kind of generating function that builds off of randomness:
- Wave Function Collapse (this is probably what you should be using)
- Noise generating dungeons (perlin noise is better for heightmap generation) Whorley noise creates cell-like areas, that you can use for things like cave generation - there are probably better noise algorithms for caves, but this one is pretty good. Ie, Voronoi diagrams are pretty interesting.
- Maze generation can be turned into dungeon generation, to my understanding- but I don’t know the name of the algorithm.
If you have irregular shapes, if you use some kind of noise, then you’re likely going to have some added difficulty navigating through the dungeon. Add some extra checks for the players size (ie, having a player width and height that collide with walls),
use the “A* pathfinding algorithm” to make sure it is possible to get from the Start to the End of the dungeon.
Id peep at the comment below this one, as i had an epiphany while writing it.
If you havent yet, you could have a look at A* and Dykstra's algorithms. Then compare against binary tree algorithms. You can then use your gap to prune shortest paths from spawn to boss, until minimum separation is achieved.
Graph theory studying could also be helpful.
Quantum wave function collapse might be most helpful to you.
Worth having a look at. (Start with this actually)
ua-cam.com/video/20KHNA9jTsE/v-deo.htmlsi=nk6JITQyLTgTM1IA
This video has been the best explainer ive seen on using the algorithms in games.
For your purposes, a biome is a room type, and the ability to designate what kind of rooms can share adhacency should be very helpful.
Will also let you retain grid power, and you can even designate dead-end and hallway rooms. You can also dictate the connection count of rooms, their min or max radius from spawn, or any other room.
For instance, maybe item rooms are like "islands" and must have four "water" type tiles between them.
Much can be done! Could make for maximal replayability with different and new tilesets. Excited to see what you come up with!
Very cool and elegant! Nice job, man, and wish you good luck on your game-dev journey.
Thanks! Good luck to you as well!
This is really cool. I'm just getting into game dev and want to learn how to build proc gen dungeons. Subbed!
Ooh, I love how you solved the crossing constraint by mixing both algorithms! The second one was neat, but required too much tuning and still couldn't enforce the constraints. Graphs are definitely the way to go, but I like the simplicity of using a random walk combined with some collision based constraints.
Thanks! Glad you enjoyed!
I tackled that problem last during my first years of programming. Very interesting - never came across a physics based approach in a post processing.
Very well done and communicated , concise and useful, ty!
for the first issue, i like the multiple lines solution. you have a dungeon generate rooms connected. going in a random direction. for a iteration account. storing each room, then once iteration is done, start either back at the spawn, or in a random room along the first iteration, and iterate again, making a "second path" place something at the end room, boss, treasure, dungeon key, etc. then redo that algorithm from the start, and making something else at the end of another path, this makes sure the boss room, isn't connected right next to spawn, that there is always a path to the boss, and to treasures and such.
Very cool to see your process :)
Very Nice! Thanks for sharing your process ❤
Thanks! Glad you liked it!
Fantastic explanation and the visuals were terrific!
Thanks! Glad you liked it!
I've been thinking about this approach forever. I want to see more of what you've done since this video. I also wanted to work on a 3d force graph dungeon.
For dungeon generation, I haven't changed much about my approach, other than experimenting with splicing "bonus" rooms into my dungeon DAG (Treasure rooms, miniboss rooms, etc). But for my overall game I've made a lot of new changes, I'm working on a new video about that as we speak!
Would love the generation to be available on a website for generating dungeons for TTRPG nerds like myself. Love the generator!
Intresting approach
This is incredible. I feel it would be really easy for you to add dynamically sized rooms as well. For spawn>boss routes, for rpgs with open worlds, it is not that you want them far apart, but just the approach to the boss room being long. Exiting the boss room to somewhere near spawn via a one way avenue (door/height, etc) is often a nicer experience. If you made one vein that somehow looped around or a secret passage hallway, maybe with the rewards? :o
Obviously depends on what overall game/playloop is
Yeah there's a lot of cool dag preprocessing stuff that I think I can do!
That's a very clever idea!
Great video, I have a few ideas that may be useful when improving the force based graph drawing algorithm. If you added the repelling force to the edges too it would greatly improve the algorithms ability to produce graphs with no crossings. had you frozen the positions of some nodes and edges as soon as they met some condition it would help prevent forces from tangling them up, as an example: a node acquires 4 neighbours and the edges towards the neighbours have no crossings, in such case a node is considered to have a good placing and is frozen in place with its neighbours.
Thanks for the suggestions. I think they are good ideas! Ill have to try them out!
The very first approach you showed was sufficient. All you need to do to ensure enough distance from spawn to boss room is to perform any pathfinding algorithm that returns the distance between nodes and if that distance is less than your defined accepted threshold, move the boss room and repeat this process until satisfaction of the condition.
0:29 "because grid, rooms must be the same size" If the minimap only needed to be accurate from the perspective of your current room, and you didn't care whether people can count paces to map the whole thing out, the actual room size could be arbitrary. You could just graft and cull the exit rooms as you cross the threshold, and have doorway colliders that transform raycasts through the "portal". In a fast-paced game, I doubt anyone would notice the floor plan doesn't add up, and it might even add to the pressure/confusion.
I bsicaly made first version of tile generator you showed. In mine when rooms collide the just connect with each other and it done with a simple line trace chech. I think the graph searching algorithms can be used for solving the problems with speciall rooms placement i implemented basic BFS algorithm in my scince i use linked list. Video is cool
The only time I did something like this, I also ended up with a physics based approach relying on gravity to pack rooms together, then just sorta cut holes in the rooms where they connected to make 'hallways'. Funny that the physics stuff is kinda the best solution, and as a bonus it really does make a cool loading screen
Oh that's interesting. Haha yeah the loading screen made it worth it for sure lol
I've always wondered how someone could recreate a dungeon system like this, very smart! I wonder if it could be extended to place rooms in 3D space, or non rectangular rooms... Thanks for sharing!
Yeah. For 3D it might be a little tricky to route hallways because you need things like stairs. But for 2D I actually use prefabricated rooms (that can be any shape or size, and have custom objects), then I just use the rectangle as a bounding box to make sure the rooms don't overlap.
@@UnitOfTimeYT I got suggested a video by Vazgriz right after watching this that goes into a similar method in 3D, using the 3D A* algorithm to map out grid-aligned hallways and stairwells
Dungeon generation is hard. The end result looks really good. I dabbled with it myself a bit, but with no good results. Due to a deadline, i just ended up using a maze generator and a few extra steps. Anyway, great video and presentation.
Could you elaborate on the post processing you did? Did you use Maximum Shortest Distance to place spawn and boss rooms? And maybe add a constraint what is considered good enough?
Thanks! Yeah, I'm slowly learning how difficult procedural generation is in general lol. When I generate the planar graph version of the dungeon, I simultaneously generate a DAG which holds every room and all of the connections between rooms. So for postprocessing I just need to decide "which room goes at which node in the DAG". My game is pretty simple so far, (I only have "spawn rooms", "normal rooms", and "boss rooms"), So for now I just take a topological sort of the DAG and choose the first node as the "spawn room", and choose the last node as the "boss room". I think in future, I might do some extra steps to regulate a few things: room difficulties, monsters selected per room (to prevent neighbored duplicates), potentially adding special encounter style rooms in interesting locations, stuff like that.
That's pretty neato!
Nice! I feel inspired
Could watch the graph redraw for hours.
checkout wave function collapse.
u give constraints to the different types of rooms and then it procedurally generates a map.
You could also randomly generate some points in space and do a Delaunay triangulation on them, which gives you a planar embedding for free. I'm pretty sure Unexplored uses this kind of approach for its level generation.
Edit: They don't, but I think they used to.
Cool. Thanks for the suggestion!
I use a hand base estimate to make cities... It seems to work pretty well
i zoned out after a bit and was not hearing what you were saying but liked the video anyways because you use kde
hahaha
the larger dungeons make me think of Daggerfall... those dungeons could be MASSIVE and often were. is there a way to have rooms that colide during the shift merger into a single larger room? could be neat but could also be pointless as the are just representations of where they are right? They could still be whatever shape that you want/need?
Ah yeah that's an interesting idea. I can definitely merge rooms. but rooms (at least how I have them now) are kinda "prefabricated". Like they might have boxes in a corner, things like that. So if i'd have to ensure the entities inside the room dont end up causing a weird situation.
Interesting! How about Voronoi diagram algorythm with some edges removal?
I wrote something similar recently. But instead of gravitating towards the start room - I generated all rooms one by one and slided them to the top left corner. Which is simplier, but the result is not that natural.
Cool! Yeah I didn't start with Voronoi diagrams because originally I wanted to generate a dungeon based on the abstract DAG representation of a dungeon.
Gravitating towards a corner sounds interesting, I hadn't even thought about doing something like that.
I have zero idea of this, but I have a degree in watching informative youtube videos and I kept thinking about wave function collapse and how it could help with defining room types. Is this, like, an option?
Yeah. I'm not super familiar with WFC, but it might be helpful if my dungeon needed to bridge multiple rooms together. right now the dungeons are designed to have several rooms connected via hallways, so the hallways are kindof the joining point. Maybe I'll use WFC for future dungeons though.
What's the problem with edge crossing? I mean, what could be a hallway and the other is a small tunnel under it.. right?
I didn't really explain in the video but my game is 2d. So when the hallways overlap they end up making the dungeon more connected then I wanted
You could use graph grammars to make the graph procedural
Oh cool I actually hadn't heard of graph grammers before. Thanks for sharing!
Hello, could you tell me how you created your video animations?
Hey for these ones I just rendered them using opengl and recorded them. But there's some nice anim libraries out there like: manim and motioncanvas which I've heard are pretty good too.
@@UnitOfTimeYT Thank you :)
how did this journey start im interested in stuff like this are you self taught or school...curious good job though this is very cool
Thanks! I went to school for Electrical Engineering, but transitioned after college to software engineering. If you want to learn. I'd recommend taking some *free* intro programming courses (like how to code basic things). then as you get more advanced you can take more advanced college-level courses that "MIT open courseware" offers. They have a YT channel where you can basically go and learn data structures and algorithms and all about how computers function under the hood. Best of luck!
How do you visualize this? Im starting to learn game dev now
I made these visualizations with a rendering library that I wrote on top of opengl. If you're just starting gamedev, I'd highly recommend an engine (unity, godot, unreal, etc). Best of luck!
@@UnitOfTimeYTCool. Im gonna start using Unity. Started yesterday actually. I see a lot of these visualisations in tutorials though without completely understanding. Is this part of the game project? Like a renderer in the map generator for example? Do you run it by running the game or can you run a separate renderer to just render stuff like that you are curious about?
Yeah for this particular case I just render rectangles in a special project and its separate from my main game project. Though it is possible to set things up so that you can show debug rectangles and things like that@@lordfresh
big W
What engine do you use?
Hey! I don't use an engine. My game is basically from scratch on top of opengl and webgl
This presentation makes me feel dumb, but this also makes me wonder how large world/map design works, like Helldivers 2 and their levels.
Haha. yeah it was a struggle figuring all this out, and I'm not really sure my solution is all that great. but it does work for my game at least. But yeah I'm not really sure how large 3d games do level gen. Mine is a 2d game which is probably much simpler.
hypergraphs son
But what are you going ro "DO" with the rooms and layout. Why so you need these layouts at all? Why these many rooms? Why these sizes? Why square?
Hang on, I recognise that cursor. KDE Plasma?
haha yep! You found me out!
where can we find this algorithm?
Ah I probably put links in the description to various sources that I used during my research. I don't think its like an official algorithm though. Hope that helps!
Is the code for this posted anywhere??
Yeah some of the dungeon generation code can be found here: github.com/unitoftime/flow/blob/master/pgen/dungeon.go
And the original example which generated and rendered the dungeon is here: github.com/unitoftime/flow/blob/master/pgen/example/main.go
So each node has a room type which contains the dimensions of the room which is then used for collision detection for the rooms?
Looks very awesome!
Thanks! Yeah, exactly. I maintain a pool of different rooms based on the "RoomType". Right now I just have 3 rooms: Spawn Rooms, Normal Rooms, and Boss Rooms. Then right before I do the initial grid layout of all of my room rectangles, I first need to decide which room will go into which grid location. So I randomly select a room out of the room pool, based on which RoomType is is at that grid location. Once I've selected the room, I will know the bounding rectangle of that room, so for the "gravity compression" stage, I just do collision detection based on that room rectangle. Hope that makes sense!
@@UnitOfTimeYT incredibly clear explanation, thank you very much 😄
Fake solutions to simulate systems are more fun solutions. Applies to a lot of things; kart handling physics, physical health, and yes, also 2D topology.
"gungeon generator"
where rendered dungeon?
I guess I never showed a picture of it You can go here to play and run to one of the dungeon portals (NorthWest or South) if you want to see what the dungeons look like : mythfall.com
Or if you check out this video it has some gameplay as well: ua-cam.com/video/rp0KWg2Z9G8/v-deo.html
Why not have the edge crossings mean the corridors are in different "elevations."
Yeah you could do that if you wanted. I am making a 2d game and didn't want elevation levels
You might appreciate looking at how Path of Exile solved this problem too
Cool. Ill take a look!
Looks like you found a solution, I just wanted to point out that I think wave function collapse sounds like very good solution for what you were looking for. Its very customizable beyond its basic rules. A pretty popular game that uses this algorithm is Bad North (ua-cam.com/video/0bcZb-SsnrA/v-deo.html)
Phew, is there some kind of competition who can narrate the most words within 5 minutes? That's exhausting to listen to.
Couldn't you just add stairs when there were overlaps of rooms? Over simplifying here, but it's a genuine question
Yeah you could definitely do multileveled dungeons. In my case, I'm making a 2D game. and I wanted the connectivity of the dungeon to match the initial DAG that I used so that I could do some preprocessing steps more easily. But yeah, there's lots of ways to go about procedural dungeon generation, depending on the type of game and feel you are going for. Thanks for watching!
Just wait until you realize you really want it to be 3D 😬
Haha. hopefully I'll never have to go down that road :P
@@UnitOfTimeYT Literally the next video in my feed: ua-cam.com/video/rBY2Dzej03A/v-deo.html ("Procedurally Generated 3D Dungeons" by Vazgriz)
@@UnitOfTimeYT It would be a trick, but crosses in the graph would actually become easier to handle, since you can simply make them different levels within the dungeon, and the hallways with elevation changes would become stairwells. You'd need some checks to be sure elevation changes don't happen too quickly, but it still may make some things actually easier.
Why would you do this it seems like a lot of work when there are better less expensive solutions
I'm always open to learn about other dungeon generation algorithms, this was the best I could come up with for my requirements in the couple of days I spent working on it
the end results in this video are kinda underwhelming
Have a like for putting the music source into the description.
Haha thanks. I'm pretty sure YT automatically adds it even if I don't. Lol