I rewrote my dungeon generator! 

the graph generating would make a sick loading screen

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.

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.

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.

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

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

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.

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

You should have assigned the room properties 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

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.

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.

Its definitely different from the how I laid out the rooms for Doomlike Dungeons and Caverns of Evil, though both use a kind of random walk -- I placed node rooms, all destined to become important, at random locations, usually far apart, and used a random walk to have them grow towards each other by placing a series of rooms in meander paths from each start until the two paths met.

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

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.

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)

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

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

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

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.

Very Nice! Thanks for sharing your process ❤

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

Very cool to see your process :)

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.

Fantastic explanation and the visuals were terrific!

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

Could watch the graph redraw for hours.

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.

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.

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.

That's a very clever idea!

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

Classic physics issue: you meed to check for the boundary consitions (your design constraints) all the time

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?

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

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!

That's pretty neato!

Very cool!

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.

checkout wave function collapse. u give constraints to the different types of rooms and then it procedurally generates a map.

Any chance of an educational video or tutorial demonstrating how to create the logic for such a thing? Not necessarily looking for exact steps in any given game engine, but a precise overview of the math and logical steps used would be incredible.

Nice! I feel inspired

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?

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?

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

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.

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

You could use graph grammars to make the graph procedural

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

What engine do you use?

I wonder what happens if you were to build a city with this type of system this way you can have very large metropolises without doing every building, roads and various infrastructure. What would it build and would it give its own design philosophy following set rules of algorithm generation

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

big W

Hello, could you tell me how you created your video animations?

This presentation makes me feel dumb, but this also makes me wonder how large world/map design works, like Helldivers 2 and their levels.

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?

where can we find this algorithm?

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!

Is the code for this posted anywhere??

Why not have the edge crossings mean the corridors are in different "elevations."

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?

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

Bro took a feature and thought it was a bug. 🤦‍♂️ But more seriously, rather than a flat wide random assortment of squares, I'd rather see people generate layouts that include verticality and usage factors. Maybe where edges cross could have been an indicator for verticality or a 4 way hallway. Give rooms usages beyond boss, normal, and treasure. Where's the bathroom? The kitchen? They're going to need to get water either from the entrance or maybe an internal source. Where do they store the wine? Give each of these things weight for how close they should be together. But otherwise, cool. I acknowledge that you put in a lot of effort to stick random squares next to each other. 👍

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 (ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-0bcZb-SsnrA.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

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

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

the end results in this video are kinda underwhelming

Have a like for putting the music source into the description.