# Procedural Dungeon Generation: Is there a simple algorithm to make sure all of these rooms get connected using minimal corridors?

Is it possible to get a hive-like structure, connecting all the rooms without having too many corridors? (Too many being 3-4+ corridors coming from a single room)

Below is the output of how my rooms look, basically they randomly placed.

What I'm hoping to get corridor-wise.

-
I don't think 3 or 4 is "too many corridors". Especially if you have 9 rooms in your dungeon. Plus, I'm not sure what you mean by "hive-like structure", could you elaborate on what look you're trying to go for? – fnord Aug 6 '13 at 18:39
Maybe include a "completed" map to show what you're interested in having. – Byte56 Aug 6 '13 at 18:43
Ah yes, I meant a max of 3 or 4 corriders coming from each room. – Blenderer Aug 6 '13 at 18:49
I've added an image of what I am working towards as far as corridors. – Blenderer Aug 6 '13 at 18:53
If you don't have 3 corridors from any rooms, you will only be able to make a simple linear joining of the rooms, and so simply pick one, and join it to its two nearest unjoined neighbours. – Nick Aug 6 '13 at 19:09

Well, the simplest way I can think of starts with making sure all rooms are connected by at least 1 corridor:

2. Grab a random room within 1 distance, which is not already connected to some room (all rooms start disconnected, so you'll be keeping track of this as you go).
3. If there is no such room, go to distance +1. If it's ok to tunnel over/under another room this is easier, assuming you don't want connecting corridors.
4. Work your way through pseudo-randomly until all rooms are connected.

Now we know you can get to all rooms, but now if you want more than this strictly linear maze you can just step through your rooms and randomly make a new path to connect rooms, up to a limit per room of 2-3, or until a certain percentage of rooms hits the max connections - etc.

As a final step you can add rules that would alter your results to suite various situations. For instance, you might observe that any room with only 1 corridor is, by definition, a dead-end; You could make more dead ends, or you could eliminate them all by making sure everything has at least 2 connections. You could make dead-ends have a secret passage. You could make sure a boss-room is a dead-end. You can make sure your start room is a dead-end, but then make sure the second room has a minimum of X connections. Ad infinitum.

Each assumption and rule can radically shift how your levels look, but that's part of the fun! This should at least get you hive/cave-like rooms to start.

-
This is fairly close to Kruskal's Minimum Spanning Tree algorithm - this modifies the condition in 2 from "not already connected to some room" to "not already connected to the same cluster" which fixes a bug in the rules described above where you could have a situation where each room is connected to some room but the dungeon as a whole still forms multiple disconnected islands. Kruskal's is guaranteed to find a connection graph with minimum total corridor length. – DMGregory Dec 21 '15 at 18:31