Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm designing a game with random generated dungeons. I'd like to view this as a connected, undirected graph in which nodes are rooms and edges are doors or corridors. Then I choose a "side" node as the dungeon entrance, I calculate the distance between this entrance and all other nodes, and decide that one of the farthest nodes is the "goal" of the dungeon (the location of the treasure, boss, princess, etc.).

I saw 2 ways to generate the final dungeon topography:

  • Generate first a random graph, then try to fill the 2d world with rooms at random locations, respecting the edge connections. I figured this would be sometimes difficult because the room generation could be "locked" trying to fit rooms in impossible places.
  • Generate first rooms, placing them randomly where they fit, then map the result to nodes and edges. I decided to try this.

My idea consists in :

  • First generate a big room that would contain the whole dungeon.
  • Put a wall inside the big room, at a random location, dividing the big room into 2 smaller rooms of different area.
  • Then I continue to divide each room into 2, until they are too small, or the total number of room reach a maximum (or any other condition). Each new room is a node.
  • Once finished, I check each room and find all adjacent other rooms, marking the 2 nodes as connected by an edge.

That way I ensure that all rooms have a possible location in the 2D world, and are correctly mapped by a connected graph.

My problem is that there are too many doors and corridors connecting the rooms.

So I'd like an algorithm that reduces the number of edges of a connected undirected graph, but keeping it connected (all nodes stay reachable) in the end.

share|improve this question
    
Your idea is basically a binary search tree, if you want to know. I used it; it does make rather nice dungeons and is easy. :) –  The Communist Duck Nov 22 '10 at 19:01
2  
FYI: A complete graph has edges between all pairs of vertices, so (assuming duplicate edges are not allowed) you can't remove any edges and still have a complete graph. The right term is a connected graph. –  Michael Madsen Nov 22 '10 at 20:16
    
Binary search tree, connected graph, right. I'm so bad with conventional name of things. –  Splo Nov 23 '10 at 8:53

3 Answers 3

up vote 12 down vote accepted

Use Prim's Algorithm to obtain the minimum spanning tree for your graph (add randomized weights, or add the higher weights near the entrance, or do an algorithm of your choice) and re-add some doors/edges at random. This way you'll have all the rooms connected and a few extra redundant paths.

share|improve this answer
1  
Oh right, the minimum spanning tree, of course! Good idea, thanks. –  Splo Nov 22 '10 at 19:41

Some of the dungeon generators on this list from Inkwell Ideas are open source or provide documentation on their algorithms. Google will also give you plenty by a search for '[programminglanguagename] dungeon generator'. Unfortunately my favorite is not findable by either of those methods, despite being the most well documented I ever encountered, and I cannot remember its name as I lost it to a hard drive crash recently. I will update this answer after I perform recovery on that drive.

share|improve this answer

You could also try Kruskal's Algorithm

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.