Connecting rooms

[Vanguard]

Hey everybody,

I'm trying to come up with the best way I should connect all of my rooms.  I have all of them assigned a number for ease of working with them.  Anyway, what I'm thinking of for right now is I start at room zero, and I go through all the rooms to determine which one is closest to that one, and then make a hallway between those two.  Then, starting from the room it connected to, I find the closest room to that one that it is not already connected to and connect that one.

The problem with this idea is that the last few are going to often end up being a large distance away and have giant hallways going all across the map.  Do any of you know of a good/better way to do this?

[Anvilfolk]

Just some time ago there was a similar topic. Maybe you can find some ideas there? Here you go: http://www.roguetemple.com/forums/index.php?topic=396.0

[purestrain]

As for everytime i recommend using a space partitioning algorithm (not necessary bsp). It gives you lots of possibilities compared to a purely random approach, and the generated maps are very cool and not prone to errors.

http://roguebasin.roguelikedevelopment.org/index.php?title=Abstract_Dungeons

http://roguebasin.roguelikedevelopment.org/index.php?title=Grid_Based_Dungeon_Generator

Theese approaches are so cool that they even allow me to easily build polygonal representations for my current 2.5d game - I just need some information for each "area": type (room, tunnel, cave), neighbour areas and entrances.

[Krice]

Grid based or any strict style generation is just boring. I wouldn't suggest using it. You begin to see the algorithm (this happens particulary in Nethack) and there is never any surprises, it's always limited to certain kind of result. By the way, I'm trying to program a free-style dungeon generation in Agduria, but at the moment I haven't been developing it. Anyway, I have a good start with rooms connected when their walls are close to another room. I yet have to figure out connections for corridors, the same way as in Kaduria actually. It's surprisingly hard when you have total freedom for placing rooms.

[purestrain]

i bet they aren't boring and you can't distinguish between a "freestyle" and a "strict" one. Lets have a contest? 

[Anvilfolk]

I have to agree with Krice on this one. Most dungeons are rather limited, I find. Although Crawl has a fair bit of variety, I don't like its dungeons much either. They're still better than nethack's.

I imagine a roguelike with dungeons similar to those built by people on Dwarf Fortress. THAT would be interesting.

[Vanguard]

I probably should've given more information on what I was doing.  I already had my stuff for generating rooms in place, and what I was having them do is choose a random, empty location on the map, and then choosing a room from a list of static room designs (rather than having the room design itself randomly generated).

Anyway, what I ended up doing was marking one room as "connected," and then having that room connect to the nearest room to it, and then marking that room as connected and moving on.

To prevent the dungeon from becoming extremely linear and boring, every room has a chance to have more than one hallway generated for it, and hallways after the first one do not care about whether the rooms they connect to are marked as connected, and they do not mark new rooms as connected, so it's still easy to go through them one at a time.

Since exactly one room has its hallways done for each time a room is marked as connected, that means that once all rooms are marked as connected there is only one last room that has not had its own hallways generated, so the loop makes some for that last room, not worrying about whether its targets are connected to the rest already, since they all are.

Anyway, thanks for your advice everyone, and hopefully my explanation of what I did can help someone else who has trouble with this.

[Krice]

I have thought an idea where you create corridors first and then "grow" rooms to places where they fit, but I don't know if it is a good idea..

[stu]

works for 9/10ths of the population. easy to implement and makes nice layouts imo (i used an updated version in tomb of rawdin).

[Vanguard]

I have thought an idea where you create corridors first and then "grow" rooms to places where they fit, but I don't know if it is a good idea..

I never thought to try that, but it's an interesting idea that would probably work out just fine.

[SquashMonster]

If you want to minimize the amount of long corridors you end up with, try creating a minimum spanning tree.

Start by figuring out all the separate areas you have (if you don't know, a flood fill will do it), then figure out the distance between each pair of areas.  Take all of those distances and sort them by length.

Take the shortest of those distances and join the two areas linked by that distance, then mark those areas as being the same group.  Then take the next shorted distance and check that the two areas are different groups: if they are, link those and mark them as the same group.  If they're not, ignore it.  Either way, go to the next one.

Repeat that (going through the shortest remaining distance and connecting if they're not already connected to eachother) until you only have one area remaining.  Once you do, you have a fully connected level with a minimum number of corridors.


There's a few weaknesses to that approach.  It does tend to make lots of dead-ends, and never creates a loop, so you'd be wise to sometimes connect two rooms even if they're already in the same group.  Additionally, it's possible to make an even shorter set of corridors by allowing branching corridors, which this algorithm doesn't handle.  But you can scatter some 1x1 "rooms" around your level to give branches a chance to form and possibly make the level more interesting.  Just be careful because that can end up creating dead-end corridors as well.

[Z]

I found an algorithm which I find interesting, because it is different than the usual one: rather than creating rooms and then digging tunnels between them to connect them, it rather grows the walls until everything that is not a wall is a network of tunnels.

Initially, all cells are "unknown". When placing rooms, cells inside them are "passable", and corners (which you want to stay walls) are "impassable". The edge of the map is impassable.

Now, grow the "impassable" walls by changing "unknown" cells around them into "impassable", making sure that corridors remain between them (you need to perform some connectivity tests for this to work correctly, details are omitted).