Loops on dungeon-type levels

[Slash]

Any of you has ideas of a good way to implement loops in a classic rooms and corridors dungeon?

My current generator places a room then selects a wall tile from all rooms to place a corridor + room branch and so on, and as such there are no possibilities for a corridor to connect to an existing room.

[reaver]

Why do you want loops? And what kind of loops? Last room connecting to first, or just more than 1 ways to reach a room from another room. Loops can't even be guaranteed depending on your generator.

[sokol815]

In Strife, I add loops later after generating the normal dungeon like you describe, then going back and picking a random room, then based on where it is on the map, start running a corridor towards the center of the map on a cardinal axis. After it runs outside the room's wall for n tiles without bumping into anything, it makes a 90 degree turn toward the center of the map and either finishes when it hits a room or corridor or it just dies if it becomes too long.

If it happens to run into something else before it makes a turn, it just makes a straight hallway between the two.

[Slash]

Loops make levels a bit more interesting to explore, or so the players say

@sokol815 thanks, I tried something similar but a bit more brute-forcish and didn't like it much really; after generating the level I was taking a random wall and doing a straight corridor on its normal direction, hoping to hit some other room and then link them... may be aiming for the center would increase the chance of positive links.

[sokol815]

Loops make levels a bit more interesting to explore, or so the players say

@sokol815 thanks, I tried something similar but a bit more brute-forcish and didn't like it much really; after generating the level I was taking a random wall and doing a straight corridor on its normal direction, hoping to hit some other room and then link them... may be aiming for the center would increase the chance of positive links.

You bet! Happy programming!

Why do you want loops? And what kind of loops? Last room connecting to first, or just more than 1 ways to reach a room from another room. Loops can't even be guaranteed depending on your generator.

Loops can easily be guaranteed via this method. The size of the loops is a different matter entirely. 

[reaver]

Loops can easily be guaranteed via this method. The size of the loops is a different matter entirely. 

Loops of the kind 'connect last room/corridor to first' cannot be guaranteed, e.g. rooms/corridors generated in a spiral formation. The innermost center area cannot connect *directly* to the outermost tip as it would have to cross other areas first. If by loops you mean multiple ways to reach a room from another ( == different paths on a connectivity graph), yes that's pretty much guaranteed.

Easiest way that I've found to connect two areas:
- pick one perimeter wall point from each area
- generate a cost function for every tile, where 'diggable' tiles have cost == 1 and nondiggable (e.g. other walls or areas) have cost == 1000.
- Run Dijkstra's algorithm for pathfinding, only checking the 4-neighbourhood.

if there's a path, it *will* be found.

[Paul Jeffries]

Your dungeon generation algorithm sounds fairly similar to mine - I place a starting room and then recursively branch other rooms off of it in random directions.  Creating loops in that scheme is fairly simple, though; before placing a room I first check the size of the available space in that direction; if I find a suitable existing room while doing that then (assuming various other criteria are met) I connect the two.  I find that tends to work quite well and produce a reasonable number of loops and it sounds like it should be fairly compatible with what you're already doing.

Something I've been thinking about but haven't implemented yet is guaranteeing a start-end loop by initially placing the first set of branches into a predefined (but randomly-shaped) ring; once this initial loop is created the recursion unwinds through the already-placed rooms randomly adding extra branches to make the level more interesting.

[Bear]

If you want large loops, pick a tile at random and do breadth-first floodfill to find the (walking) distance from that spot.  Then pick the most distant tile from it, which will be the last one you get in a breadth-first floodfill, and do a breadth-first floodfill to find distances from THAT tile. 

Whichever third tile is furthest from the second tile, the distance between second and third tiles will be  the longest walking distance that exists in your map.  If you can connect those two points without crossing anything else, you're guaranteed a maximal-size loop.  Often that isn't possible, but if you cross other open spaces while trying, look for the tunnel (between two open spaces) that connects tiles whose walking distance (the one you calculated with the second floodfill) has the most difference.

[Rickton]

It's not very controlled, but the way I add loops is this:
First, I make all the rooms. I use the so-called "BSP tree" method this article talks about (except I only use it to generate the rooms, not the tunnels), although this method should work with other methods of room generation too as long as when you make each room, you keep track of where it is and where its walls are.

Anyway, I go through all the rooms, select a random wall tile, and use a pathfinder that can't use diagonals to dig a tunnel to a random wall tile of another room. Then I run through the list of rooms again and make a second tunnel in the same way, so each room will have at least two exits.

Actually, to make it more interesting, the first time I do it, the pathfinder isn't allowed to go through any already-open space. It'll curve around other rooms (and tunnels too, I think. Don't remember if it ignores them or not).
The second time, it's allowed to go wherever it wants, including through other rooms, so some rooms might have multiple exits, and tunnels will intersect other tunnels.

[mushroom patch]

I think there's a lot to be said for starting with a graph that describes a tentative structure of how rooms and corridors fit together, so you have some a priori control over the presence of loops, multiple connectedness, and so on. I've commented on these issues before. Essentially, you want to use a planar graph as the basis of dungeon generation and compute random embeddings of it in the plane. There are various ways to do this, although I admit the ones that seem most obvious to me involve more complicated math than most people would want to do for a roguelike game.

The result of this approach is a bunch of vertices and line segments in the plane, which you can perform sanity tests on to make sure things are far enough apart and so on. Then you build rooms at the vertices and "straighten" the line segments into the usual piecewise axis-aligned corridors. The last bit is the most fiddly part, imo.

[Eben]

I just recently adapted the rot.js Rogue style generator into SquidLib and it does what you're looking for:

https://github.com/SquidPony/SquidLib/blob/experimental/src/squidpony/squidgrid/mapping/ClassicRogueMapGenerator.java

[Trystan]

I think there's a lot to be said for starting with a graph that describes a tentative structure of how rooms and corridors fit together, so you have some a priori control over the presence of loops, multiple connectedness, and so on.

That's what I've been doing the last couple years and I agree; it's a lot easier to work with an abstract representation of your dungeon. It makes it much easier to reason about the overall attributes like consecutiveness, zones, and even player flow. It also makes it much easier to reason about the individual parts of your dungeon (rooms etc.). So once you have the overall layout, you can create rooms with a really wild generator. If the room is invalid (all doors aren't connected, treasure is unobtainable, ice monsters in a fire room, etc), you can just retry until it is valid.

[reaver]

you can just retry until it is valid.

Blindly retrying can be a major source for slowdowns for the generator. If your random search space is small, you can store all the points in the list, shuffle them and try one by one. If your random search space is large, you can use a nicer random sampling method such as poisson disk.

[mushroom patch]

That's what I've been doing the last couple years and I agree; it's a lot easier to work with an abstract representation of your dungeon. It makes it much easier to reason about the overall attributes like consecutiveness, zones, and even player flow. It also makes it much easier to reason about the individual parts of your dungeon (rooms etc.).

Exactly so. There is great value in being able to coherently reason about your maps in terms of a single geometric data structure without reference to some ad hoc algorithm that made it or a raw bitmap representation of it. If you don't start with the structure baked into the cake, you're always going to be stuck trying to recover the structure whenever you try to do anything nontrivial. This kills the ambitious ideas.

[Trystan]

Blindly retrying can be a major source for slowdowns for the generator.

Theoretically. In the worst case at least. But that sounds like premature optimization to me.

If I had to choose between something that is pretty good at making valid dungeons and easy to retry vs something that is mathematically proven to always be valid, I know which I would choose: the good enough way. I've found that a good enough generation algorithm and a rock-solid validation algorithm are far easier for me to program, far more adaptable, and require far fewer tweaks as new monsters, terrain, puzzles, abilities, etc, are added.

Besides; with most algorithms, I'm guessing at least a hundred or a thousand levels or rooms can be generated per second anyway.