10
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 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. :) \$\endgroup\$ Nov 22, 2010 at 19:01
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ Nov 22, 2010 at 20:16
  • \$\begingroup\$ Binary search tree, connected graph, right. I'm so bad with conventional name of things. \$\endgroup\$
    – Splo
    Nov 23, 2010 at 8:53

3 Answers 3

13
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Oh right, the minimum spanning tree, of course! Good idea, thanks. \$\endgroup\$
    – Splo
    Nov 22, 2010 at 19:41
1
\$\begingroup\$

You could also try Kruskal's Algorithm

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

You must log in to answer this question.

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