I rewrote my dungeon generator!
145,079
Published 2023-07-29
⁍ Discord: discord.gg/63YeahMKfJ
⁍ Patreon: www.patreon.com/UnitOfTime
⁍ Github: github.com/sponsors/unitoftime
⁍ Twitter: twitter.com/UnitOfTime
// References
⁍ Boris the Brave: www.boristhebrave.com/2019/07/28/dungeon-generatio…
⁍ Planarity: www.jasondavies.com/planarity/
⁍ Force Directed Graph Drawing: en.wikipedia.org/wiki/Force-directed_graph_drawing
// Description
This week I worked rewrote my dungeon generation algorithm to support multiple room sizes and a more natural layout.
All Comments (21)
-
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.
-
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.
-
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.
-
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
-
Very cool and elegant! Nice job, man, and wish you good luck on your game-dev journey.
-
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.
-
I need a 10 hour version of the intro
-
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
-
This is really cool. I'm just getting into game dev and want to learn how to build proc gen dungeons. Subbed!
-
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.
-
Very well done and communicated , concise and useful, ty!
-
Fantastic explanation and the visuals were terrific!
-
Very cool to see your process :)
-
Very Nice! Thanks for sharing your process ❤
-
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
-
I tackled that problem last during my first years of programming. Very interesting - never came across a physics based approach in a post processing.
-
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.
