next »

[st33d]

I'm happy with my random dungeon generator. But one thing that's causing me trouble is that I have generated too many ladders.

I have marked wherever there is a point of no return (a cliff edge) and at those marks I have generated ladders.

I could easily build a graph of all the connections in the dungeon, so I can see how one gets to all of these points.

But after I've built my graph, how do I prune excess graph connections? How can I break connections and still know that it is still possible to access all points of the graph?

Going the long way round through many other graph nodes isn't a problem, that would actually make for a more interesting level. It's having too many connections and ending up with ladders all over the shop that's the problem.

Does anyone have an idea how to solve this? Is there an algorithm out there or graph model that already deals with this?

Thanks in advance.

[raigan]

You could start with your current (dense) graph, calculate a minimum spanning tree, then discard all edges that aren't part of the tree; this should be the absolute minimum number of edges needed. You could then randomly add some extra edges to taste.

Or, instead of starting with a full graph and pruning edges, you could start with just a set of nodes (no edges) and iteratively add edges; after adding an edge, you would check the graph for the number of connected components, and if it's more than one you add another edge and repeat. The heuristic you use to decide which nodes to connect may be a bit tricky -- you'd want to know that it would attach two previously disjoint components. Probably there's some way to determine this, I don't really know graph theory though

Also, if you're not already doing so, it might be useful to make the graph directed rather than undirected -- this way you could e.g model a cliff with no ladder as a one-way connection (from the high ground to the low ground).

[muku]

Yeah, what Raigan said.

Basically, the naive approach should work quite well: choose an edge at random, delete it tentatively, and then check if its two vertices are still connected, which you can do by a simple breadth-first search. If they are not, add the edge back in. Then try the next edge. Of course you have to remember which edges you already tried. It turns out that this is the Reverse-Delete algorithm. If you run it until you have tried all edges, you get a minimum spanning tree, but of course you can stop before if you just want to prune a little.

The other approach, starting from nothing and building up a MST, is Kruskal's algorithm, though since you just want to prune I guess the first approach is a nicer fit.

[st33d]

Practically had a lightbulb appear over my head whilst looking at this step by step solver of Prim's algorithm (which I got to from looking up Reverse-Delete):

http://students.ceid.upatras.gr/~papagel/project/prim.htm

The key thing I was missing was to visit each vertex only once.

I think that it should go like this:

• pick a vertex, tag it visited
• look out along the immediate edges for a vertex that hasn't been visited
• visit that vertex and tag the edge to keep and the new vertex as visited
• then we repeat step 2, but for all vertices that have been visited - looking out for unvisited vertices

Once all the vertices have been visited once, then we have the minimum edges needed. On a weighted graph we would visit along the shortest edges - but for my task we can ignore that requirement.

I'll upload once I get a proof of concept.

[Falmil]

Weird, I just learned this stuff in my Discrete Math class last week.

[st33d]

Mapping the graph on to the map is not as easy as I thought. Aaargh!!

[John Nesky]

Mapping the graph on to the map is not as easy as I thought.

If you're talking about converting an arbitrary graph into a 2D grid, yes it's hard. In fact, planarity is not easy to prove, and even if you know it's planar, putting it on a grid in a way that feels natural is still hard.

If you come up with any good algorithms or even heuristics I'd like to know about them.

I think most map generators do the reverse: They start with rooms randomly placed in a grid, and then connect them.

[st33d]

Yah, my dungeon generator already builds dungeons by randomly buddying rooms that are dug out of a grid.

Because the walkable surfaces are determined by gravity (it's a platform game), that means I've reduced the search area by a lot.

I use floodfills to determine connectivity on the room digging, so I've got a bitmap to look at and I've drawn where all of the walkways are if I have maximum ladder coverage.

If there weren't ladders next to each other I might have had a way to flood along the walkways.

[raigan]

Couldn't you just consider each contiguous horizontal surface to be a node in the graph? How are you mapping from graph to game world currently?

[st33d]

The graph is an abstraction I'm laying on top of the map I've got already. The dungeon digger tends to go a bit crazy and carve out some odd shapes, so I can't rely on the original graph, I have to start fresh from the carved shape.

I think I've cracked it though!

 

So here's the bitmap I'm working with (I use a bitmap, because it's easier to debug).



The yellow area is where the dungeon digger has carved out rooms and tunnels randomly. The cyan area shows where the player can walk and all of the ladders, and the magenta squares are the tops and bottoms of ladders. Note that they're next to every cliff - that's where they start out, at the point of no return. There's my graph right there, staring me in the face.

So I just went with the tops and bottoms of ladders as my nodes. And then walked along those cyan paths till I got to a node.

Then I ran my pruning algorithm - just as I described. The black lines show the edges of the graph that remain. On any missing vertical edge I can now remove that ladder - there's another way to get there.

The code I've written is worst case scenario at the moment, so I'll clean it up before I upload it.

[grapefrukt]

great work!

[bateleur]

Nice screenshot!

I'm wondering how hard it would be to write an iterative thing which takes the output of what you already have and makes a more sensible dungeon. Something like adding an edge, removing an edge to reduce back down to minimal spanning and then checking whether the resulting network is more efficient.

Might try something like that for my next project. I'll have to resist the temptation to write a genetic algorithm.

(Aside: I was doing something very similar for digital circuit diagrams for my Masters thesis many years ago... it's an NP Hard problem to find an optimal layout.)

[st33d]

All I'm doing really is a cut down version of Prim's algorithm. Instead of iterating over connections to activate the shortest path, I'm just activating any old path, so I get a more windy dungeon with one way routes - but you can always work your way back.

How about a nice demo and some source code?

http://www.robotacid.com/flash/red_rogue/connections/

It should be all fairly well commented because I didn't want to make something I'd have to debug later.

[Tycho Brahe]

you may also want to remove walls with space all around them (all 8 sides), I noticed one in the bitmap you provided, and maybe some other asthetic optimisations. just to make it funner.