Procedurally Generated 3D Dungeons

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.

How many times did it took you to do that?

This awesome!!!

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?)

How do you go about turning the colored cubes into hollowed rooms, hallways, and stairs

before watching the video
and I Don't want to complete it
he will use wave function collapse

maybe lol

I did same thing inside Unreal Engine, that's also could be used for 2D and 3D maps totally works same as enter the gungeon procedural map generation. I wonder if I convert this to plugin, would people be insterested.Rooms are premade and corridors to connect one room to another if overlapping is involved is procedural.

I REALLY WANT TO KNOW HOW TO DO THIS IN UE5 WITH BLUEPRINT!!!!

"if you'd like to see more, dont get your hopes up", lmao. love the vid, interesting work.

Nice done !

How this is implemented in the game engine itself? All those red, green and blue squares and the filling pathfinding process. :-) Was it already made in Unity or external soft?

neat, i tested that game a little, if im not wrong its that in the works magic and swordplay battleroyale

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.

Thanks, that was interesting

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*

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.

dont get my hopes up? I can taste the PTSD in your voice when you say that 😆

or just pre-fab wave function collapse (block matching generator in 3d, or just pipe fitting simulator)

Couldn't you have just removed the "straight up" direction from the A* adjacency list?

I would so play a stylised dungeon game like this that’s random generated

I think the basic style tickles me most

Great video!
I've done 2D procedural generation a fair bit and my latest approach was similar in some ways. I randomly placed buildings and then used A* path finding to make connections between them, but these are not corridors, they are roads which npcs use to get from place to place.
I made the generator calculate a path from each building to every other one, but favoured road tiles, so I end up with a fairly decent looking settlement + roads.
Sometimes it means that a building has a longer path to another one than if I just took the shortest route and I'm not decided on if that's a good or had thing yet.

Where are my hopes D':

If you use a Manhattan Heuristic in astar, you won't end up with as much zigzag hallways

Cleverwork.

Tastes like daggerfall

Does anyone know how to generate wider hallways? What I've done is change the A* cost function so it's more expensive to join existing hallways, then I made the hallway generation between two given rooms run a certain amount of times to create wider hallways. This works most of the time but has the obvious side-effect of creating some very bizarre corridors. Is there a better way to implement this?

would have been nice to know how to implement the walls and floors if you're not going to tell anyone throw a package on the asset store people will buy this but keep the room implementation instead of just the cubes its got me stumped trying to get everything to generate right all the walls I add either get stretched or stacked on top of each other

hey which assets for textures and 3D Models did you use please ?

This must've been used in Pixel Dungeon

i would've just checked the difference in y and determine if there is no path next to us make it incredibly expensive to move up

Very cool.

too bad there are very few good tutorials for writing the code for this especially in godot

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.

cant stop thinking about the phrase "degenerate tetrahedra"

Step one should be "learn code" :'')

I realize this is nearly a year old now, but I went ahead and started recreating it (trying to use the repository as little as possible) and I noticed in a console log that it thinks there are a lot more edges than there actually are after completing the Bowyer Watson algorithm. I assume this gets taken care of automatically by the MST search, but I would be curious as to why it's happening here as if I could, I would prefer to clean it now for performance reasons.

good stuff but the algorithms used are far too complicated, you can get the same result by just using BST rooms method.

*Vazgriz when researches don't outline an algorithm for the mathematically complex procedure he needs*: Fine, I'll do it myself

Very cool! I like it a lot.

I like your content, but the music steals too much focus.

This is all well and good but what about the reality of the how and why of the where of any facility. Nobody (ever to my knowledge) has ever just randomly designed a layout and built it. There is always an original purpose for the why, where, and how.

I like this video and want to see the final game produced.

I think you could have simplified the problem in 3D by doing it first in 2D and then adding vertical offsets. Not sure, if that would run into issues but just a suggestion.

Some seriously good content here, thanks for sharing, Vaz. Loved the ending too!

I thought your tone would be too offputting, but the content of the video is actually really good.

bro you are fucking smart. I did not think of using spanning trees

If you like this video and want to see more like it don't get your hopes up - subbed!