10
\$\begingroup\$

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.

output of a grid rooms, placed randomly

What I'm hoping to get corridor-wise.

http://i.imgur.com/9GUi6Yy.png

Improve this question
\$\endgroup\$
7
  • \$\begingroup\$ 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? \$\endgroup\$ – fnord Aug 6 '13 at 18:39
  • \$\begingroup\$ Maybe include a "completed" map to show what you're interested in having. \$\endgroup\$ – MichaelHouse♦ Aug 6 '13 at 18:43
  • \$\begingroup\$ Ah yes, I meant a max of 3 or 4 corriders coming from each room. \$\endgroup\$ – Blenderer Aug 6 '13 at 18:49
  • \$\begingroup\$ I've added an image of what I am working towards as far as corridors. \$\endgroup\$ – Blenderer Aug 6 '13 at 18:53
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Nick Aug 6 '13 at 19:09
6
\$\begingroup\$

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

  1. Start with the last, or first, room.
  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.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ – DMGregory♦ Dec 21 '15 at 18:31
3
\$\begingroup\$

Just build your rooms already connected. Start with one room, then build 1-3 corridors to other rooms. Then recurse until you've added enough rooms.

Improve this answer
\$\endgroup\$
0
3
\$\begingroup\$

Since these rooms are Graph vertices embedded in a 2d plain, this could in theory be done by solving the traveling salesman problem (which would be fine with only a few rooms). Obviously, a simple heuristic would be fine and allow reasonable scalability.

You compute the edges (corridor lengths) between all rooms. You sort them by length. You add the shortest corridor unless it creates a cycle or increases the degree of the vertex (room) above your desired max value (3-4) (Repeat). To check for cycles you could apply UnionFind or do a quick BFS on small data.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ This answer is better than the accepted answer. A greedy strategy of picking the shortest connecting corridors first should work. To avoid cycles, don't make connections to rooms that already have a corridor connected to them. \$\endgroup\$ – Jelle van Campen Aug 21 '15 at 13:33
  • \$\begingroup\$ @JellevanCampen Thanks. ;) You may have two isolated connected components. So you'd probably want to use union find or check with BFS if the two nodes are connected. \$\endgroup\$ – AturSams Aug 21 '15 at 14:11
  • \$\begingroup\$ Ah yeah, your right about that, my bad. \$\endgroup\$ – Jelle van Campen Aug 21 '15 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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