PCG Dungeon WIP

[narrow dock]

Been working with the PCG plugin for generating random dungeon layouts. Finally got to a decent generator for blocking out rooms and hallways.
I'm following a common strategy:

1. start with a set of points that represent rooms
2. perform a Delaunay triangulation to get edges between rooms
3. reduce the edges to a minimum spanning tree, I'm using Kruskal's algorithm here
4. randomly select a small set of pruned edges to add back in
5. generate hallways to connect rooms along the edges
   I had to learn to make c++ nodes for the pcg graph to implement the triangulation and mst operations, as well as generating parameter data to represent the graph edges between the pcg point data.
   Unreal has a Delaunay implementation I was able to use but I had to implement Kruskal myself.

[lyric sail]

great stuff! would love a tutorial on this

[willow sky]

hey, I just made basically the same thing but solely in c++! nice work, might not have been a bad idea to have taken the PCG plugin route... 😅 Nicely done!

Jw but are you also using A* to generate hallways? I am using it right now but I'm not a huge fan of the jaged paths it choses to form... there are ways around this but just curious.

[narrow dock]

some updated vids

@willow sky no A* here. I'm just voxelizing the graph edges. The pathing is implied by the triangulation so there's no need for a path finding step.

[narrow dock]

@willow sky Also I'm just starting with a grid space just to get something going but I intend to experiment with solutions for making more organic layouts

I think what I might try is to replace the graph edges with splines that I can deform. I have some assets for cave interiors I want to try that with

[willow sky]

ah i see yeah that’s probably far more efficient as the path is always clear… also is this all via blueprint/pct the generator you made? is there any c++?

[fallow jasper]

I wish I could put the effort in to learn C++ for stuff like this. Keep it up! 🤗

[narrow dock]

I made a c++ struct to represent a point graph, then a couple c++ pcg nodes to generate, modify, and sample the graph data. It’s brought all together in the pcg graph

The point graph is literally just three integers, a start and end index for pcg points and a cost that I just set to be distance

[elfin viper]

Hey there, by any chance do you remember which was the UE class you used for Delaunay? I’m currently trying to find docs for that

[narrow dock]

UE::Geometry::FDelaunay3 and UE::Geometry::FDelaunay2 if 3d fails