Reduce the number of edges of a graph, keeping it connected

Question

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.

Answer 1

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.

Answer 2

You could also try Kruskal's Algorithm

Answer 3

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.