2
\$\begingroup\$

I am creating a procedural map using delaunay triangulation and an MST. I'd like to have a bit more control over my final graph. Like when i was looking looking at the MST I wondered how I can connect specific points of the MST? The following image shows the MST in green and the points I want to connect in red.

enter image description here

I was thinking about traversing from a dead end and counting the steps. When it gets within a certain treshhold add a connection. But this might add a connection when there is still a room closer to it. So I have to check for that as well.

Same goes for entrance, exit and perhaps other important places on the graph. I want to end up with a random yet fun and playable dungeon. There must be proven concepts about controlling a graph for procedural dungeons and I would love to learn from it.

\$\endgroup\$
2
  • \$\begingroup\$ How are you deciding that those red connections need to be made? What are the criteria? You mentioned something about dead ends but there are still two dead ends that you haven't connected in your example. \$\endgroup\$ Jul 16, 2015 at 13:33
  • \$\begingroup\$ @congusbongus The red lines are painted on the screen shot. So need an algorithm for that. I already posted an idea how to go about it. \$\endgroup\$
    – Madmenyo
    Jul 16, 2015 at 15:36

2 Answers 2

4
\$\begingroup\$

Given only the sparse information you've supplied, and assuming that when creating a red edge, you wish to avoid collisions against both other edges and rects (which I assume are rooms)...

What you are trying to avoid are crossings. What you want (red + green loops) are cycles in graph theory. Minimum Spanning Trees are tree-graphs - that means no cycles to start with. So MST should possibly not be your starting point(?). I assume that you generate the rects first, remove any overlaps, and then generate the MST from the remaining rects, in which I can see the reason why you have opted for this kind of graph, although it is by no means your only option to build a procedural map.

Option 1: Avoid MSTs. Consider ways of building a graph that can inherently contains cycles without the risk of generating crossings. How to do this runs the gamut from using the incredibly complex Boyer-Myrvold algorithm to pure trial and error approaches like you have already suggested.

If you insist on MSTs, and are using a grid (as it appears you are by the image background):

Option 2: Just walk the grid from one node to another, and check for obstacles along the way. You can even do this along multiple parallel lines to ensure you have sufficient space for passage. There is nothing wrong with this approach (for small/coarse grids), and it is trivial to implement.

Option 3: Check collisions geometrically, by doing line-vs.-line and line-vs.-rectangle tests. This avoids having to step too many times, as you would have to do using the above approach on a large/fine grid.

Option 4: Represent all connecting lines / passages as bounding rects. Now look at your bottom-most red line. Can you see how the the space it occupies between the two rects would actually fit into quite a small axis-aligned rect? Consider that if you can figure that rect out, and it does not occupy the same space as anything else, you can consider the passage to be valid. Of course this will not be as accurate as a direct walk, but it will probably be a lot cheaper. Not sure if this is of any use though.

Note: Trial and error processes are a fairly normal part of the process of procedurally generating paths. Don't be put off by it. The cost of backtracking is need not be prohibitive.

Disclaimer: There really is no canon when it comes to procedural approaches. You are operating in the realms of pure logic here. As such, there are as many ways to tackle one problem as you can imagine. So don't expect "proven concepts" or "established approaches". DO think and code creatively.

\$\endgroup\$
2
  • \$\begingroup\$ On my phone now, just read the first part. I have build my mst from a triangulation so I already have all the connections I need. But instead of adding some random connections from the triangulation i'd like more control. I have some ideas but there are probably already many wheels invented about this. \$\endgroup\$
    – Madmenyo
    Jul 16, 2015 at 15:41
  • \$\begingroup\$ @MennoGouw Right. I am guessing then that you can use one of several heuristics. One example might be loop path length, another might be average dead end length... are loops allowed to be interconnected or not... how many loops per map, maximum... max and min distances between nodes... there are so many parameters imaginable. I have worked on this in my own code and at some point, you will be obliged to just leave certain decisions up to the RNG once you get good results on average. Hope you find your critical parameters :) \$\endgroup\$
    – Engineer
    Jul 16, 2015 at 15:45
2
\$\begingroup\$

The simplest solution is to use the Relative Neighbourhood graph which provides a nice balance between the Delaunay Triangulation and MST.

\$\endgroup\$
2
  • \$\begingroup\$ That looks very promising. A bit to many cycles for a good dungeon I think. Do you have control over that besides removing random edges/connections while maintaining a reachable tree? \$\endgroup\$
    – Madmenyo
    Jul 16, 2015 at 18:29
  • \$\begingroup\$ Since the MST is a subgraph of the Relative neighbourhood graph, you can remove any edges not in the MST and keep the graph connected (for example - removing the longest 50% of nodes not in the MST would give you a pretty sparse graph, that still contains a couple of cycles, it depends on what you're looking for, really...) \$\endgroup\$
    – cjsearle
    Jul 16, 2015 at 18:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .