the graph generating would make a sick loading screen

@vandanramakrishnan5782

13 күн бұрын

imagine venom's tendrils doing this durng loading screens

@user-so2fp8tz9o

2 күн бұрын

They still have those?

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.

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.

@UnitOfTimeYT

9 ай бұрын

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.

@jdarokhajiit9153

4 ай бұрын

I love obsidian notes! I use it for almost everything and even look for things to use it for. Kudos

@jerseyse410

25 күн бұрын

@@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

@clwnwrld

18 күн бұрын

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

@warlockpaladin2261

15 күн бұрын

Is Obsidian free and open source?

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.

I like how you can see the algorithm signature in its final form.

@UnitOfTimeYT

9 ай бұрын

Yeah I like how the visualizations turned out for this one too :)

I need a 10 hour version of the intro

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.

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

@mattshu

9 ай бұрын

ok didn't know i needed monospace comments and now i need more

@UnitOfTimeYT

9 ай бұрын

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 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.

@nicksrub

10 күн бұрын

Could you make a video on it or link to examples or source?

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

Very cool and elegant! Nice job, man, and wish you good luck on your game-dev journey.

@UnitOfTimeYT

9 ай бұрын

Thanks! Good luck to you as well!

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.

This is really cool. I'm just getting into game dev and want to learn how to build proc gen dungeons. Subbed!

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.

Very well done and communicated , concise and useful, ty!

That's a very clever idea!

Very Nice! Thanks for sharing your process ❤

@UnitOfTimeYT

Ай бұрын

Thanks! Glad you liked it!

I tackled that problem last during my first years of programming. Very interesting - never came across a physics based approach in a post processing.

Fantastic explanation and the visuals were terrific!

@UnitOfTimeYT

11 күн бұрын

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.

@UnitOfTimeYT

4 ай бұрын

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!

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

@UnitOfTimeYT

6 сағат бұрын

Oh that's interesting. Haha yeah the loading screen made it worth it for sure lol

Intresting approach

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

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

@UnitOfTimeYT

3 күн бұрын

Yeah there's a lot of cool dag preprocessing stuff that I think I can do!

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?

@UnitOfTimeYT

9 ай бұрын

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.

Nice! I feel inspired

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.

@UnitOfTimeYT

15 күн бұрын

Thanks for the suggestions. I think they are good ideas! Ill have to try them out!

Would love the generation to be available on a website for generating dungeons for TTRPG nerds like myself. Love the generator!

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!

@UnitOfTimeYT

8 күн бұрын

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.

@lauram5905

8 күн бұрын

@@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

That's pretty neato!

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.

@UnitOfTimeYT

6 ай бұрын

Cool. Thanks for the suggestion!

i zoned out after a bit and was not hearing what you were saying but liked the video anyways because you use kde

@UnitOfTimeYT

9 ай бұрын

hahaha

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)

@KagrithKriege

10 күн бұрын

kzread.info/dash/bejne/ZGR_qrB6ac26o6g.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!

I liked the part where he said "it's dungeoning time" and then dungeoned all over the place

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?

@UnitOfTimeYT

13 күн бұрын

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.

You could use graph grammars to make the graph procedural

@UnitOfTimeYT

7 ай бұрын

Oh cool I actually hadn't heard of graph grammers before. Thanks for sharing!

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?

@UnitOfTimeYT

14 күн бұрын

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.

@UnitOfTimeYT

7 күн бұрын

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.

big W

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

@UnitOfTimeYT

15 күн бұрын

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!

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!

@UnitOfTimeYT

9 ай бұрын

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!

@BboyKeny

9 ай бұрын

@@UnitOfTimeYT incredibly clear explanation, thank you very much 😄

Hang on, I recognise that cursor. KDE Plasma?

@UnitOfTimeYT

7 ай бұрын

haha yep! You found me out!

hypergraphs son

What's the problem with edge crossing? I mean, what could be a hallway and the other is a small tunnel under it.. right?

@UnitOfTimeYT

10 күн бұрын

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

How do you visualize this? Im starting to learn game dev now

@UnitOfTimeYT

2 ай бұрын

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!

@lordfresh

2 ай бұрын

​@@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?

@UnitOfTimeYT

2 ай бұрын

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

What engine do you use?

@UnitOfTimeYT

5 ай бұрын

Hey! I don't use an engine. My game is basically from scratch on top of opengl and webgl

where can we find this algorithm?

@UnitOfTimeYT

3 ай бұрын

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!

You might appreciate looking at how Path of Exile solved this problem too

@UnitOfTimeYT

3 ай бұрын

Cool. Ill take a look!

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.

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?

where rendered dungeon?

@UnitOfTimeYT

5 ай бұрын

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: kzread.info/dash/bejne/pKRkrbmgYr2fd5s.html

Phew, is there some kind of competition who can narrate the most words within 5 minutes? That's exhausting to listen to.

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 (kzread.info/dash/bejne/YpaXvMRmg9bUoqQ.html)

Just wait until you realize you really want it to be 3D 😬

@UnitOfTimeYT

7 күн бұрын

Haha. hopefully I'll never have to go down that road :P

@jamesalewis

7 күн бұрын

@@UnitOfTimeYT Literally the next video in my feed: kzread.info/dash/bejne/pHaNlKazlc2WY6Q.html ("Procedurally Generated 3D Dungeons" by Vazgriz)

@jamesalewis

7 күн бұрын

@@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.

Couldn't you just add stairs when there were overlaps of rooms? Over simplifying here, but it's a genuine question

@UnitOfTimeYT

2 күн бұрын

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!

Why would you do this it seems like a lot of work when there are better less expensive solutions

@UnitOfTimeYT

9 ай бұрын

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