Tunneling algorithm.

[mike3]

Hi.

I'm wondering about this. I've been trying to make a tunnel generator, but am not sure if my current solution is really the best.

The goal is to make a tunneler that avoids this:

Code: [Select]

                .
                 .
..................
       .....................
       .
       .

That is two tunnels which have a stretch where they parallel each other so closely that no wall can be made between them, yet do not overlap, forming a 2x11 "pseudo-room" that is not an "actual" room. A similar phenomenon can also occur between rooms and tunnels. Both kinds are undesirable.

The current method I've got works by putting special "cue" tags on the "borders" of rooms and tunnels which then provide cues to an A* pathfinding system that is then used to form the tunnels. This method is very powerful, since we can create many different kinds of constraints and even tunnel shapes simply by varying the cost function. But the problem is that the A* part is slow. Though not really noticeable on a modern machine, on some really old stuff it might be a problem (10 seconds to generate a level on an old old old Pentium or 486 thingy, though I don't know if that should matter, and I haven't tested it on any, I'm just guesstimating -- it takes 20 milliseconds to generate an 80x80 level on my few-years-old Core 2 system with optimization turned on with the compiler, and imagining a 486 to be 500 times slower, which may be too high or low, I don't know as I don't have access to one to test with. It's much slower than even Angband's level generator though...). Is that bad? If so, what alternatives may there be, that are faster _and_ also give more diversity?

Another level generation algorithm I've considered is one I call as "KISS" (since it's "simple and stupid" but produces fair results (though not quite what I want)) or "ADOMian" (as it looks like something very similar is probably used in the game ADOM, though without the sources one cannot be totally sure). This method works as follows:

1. Place rooms at randomized positions in a grid dividing up the level. This gives a fairly uniform distribution of rooms. But all room sizes must be constrained to be odd numbers, as must be their coordinates.

2. Connect room edge points with tunnels. All edge points and tunnel corners must have odd-number coordinates. Tunnels can be L-shaped or have zig-zags.

It produces fairly decent results (see ADOM), but to me is not as nice as the A*-based approach in terms of output and also it's ability to produce diversity. Namely, zig-zags must be "bulky" (with length-3 minimum zigzags instead of length-2), which means highly irregular ("cave-like") tunnels may be a problem (though perhaps with those we may not care so much about "pseudo-rooms" and all that anyway).

So what would be a good approach to this problem?
 Is there a third option here which I have not considered?

[Krice]

Is there a third option here which I have not considered?

Let it happen and fix it later with a routine that fills the other side of the double corridor.

[mike3]

You mean something that would convert it to this?

Code: [Select]

                 .
                 .
..................
       .         ...........
       .
       .

?

So then you'd do 3 passes over the level to generate, i.e.:

1. Generate rooms
2. Generate tunnels
3. Clean up level

instead of just 2?

However, there's another wrinkle. Rooms can have parts through which a tunnel can't pass, like corners. What can be done about this? How do we make sure tunnels don't go through them yet everything gets connected?

[Z]

I don't understand why your generator can generate two tunnels which are at distance 1 of each other, but not ones at distance 0 (i.e. overlapping) or negative distance (i.e. crossing)? (If you have problems with tunnels that are going next to rooms, but not ones which go across rooms, why not just tell the corridor generator that all rooms are 1 cell bigger?)

Maybe knowing the whole algorithm would give us some hints about how to optimize the A* part.

If the wrong thing happens rarely, you could detect it and generate again until happy with the results.

[mike3]

I don't understand why your generator can generate two tunnels which are at distance 1 of each other, but not ones at distance 0 (i.e. overlapping) or negative distance (i.e. crossing)? (If you have problems with tunnels that are going next to rooms, but not ones which go across rooms, why not just tell the corridor generator that all rooms are 1 cell bigger?)

Maybe knowing the whole algorithm would give us some hints about how to optimize the A* part.

If the wrong thing happens rarely, you could detect it and generate again until happy with the results.

Tunnels _can_ overlap or cross. What I don't want is the doubling-up or "pseudo room" creation.

Also, I'm wondering, while I'm at this, what is a good target for the speed to be, anyway?

And if you want some more details, the algorithm puts down cues on each wall square of a tunnel or room indicating whether that wall is horizontal, vertical, or a corner/impassable, based on the pattern of neighboring squares. These then serve to obstruct paths going horizontally, vertically, or any direction, respectively, through the given square, and then when we run the pathfinding algorithm, it gives a path that meets the given constraints.

[corremn]

Easy Pezy, it is a weighting issue.  A* terrain weights right? If a tunnel is digging out next to another tunnel then the weights of the existing tunnel cells should be lower than cells that have no tunnel in them.

E.g. weights for dungeon floor should be less that rock.  (also you can increase room walls cell weights so tunnels avoid existing walls, or you can add randomly weights on the fly or for specific cells to make tunnels look a little more organic.

Cheers

I have a video on this at my youtube sight www.youtube.com/user/corremn  A* tunneling algorithm in action.

Check out trollSlayer for a games where this is used.  http://code.google.com/p/trollslayer/

[Krice]

Rooms can have parts through which a tunnel can't pass, like corners. What can be done about this? How do we make sure tunnels don't go through them yet everything gets connected?

Make room corner a special tile protected from tunneling, then check all corners to see if corridor didn't make the connection to room wall and create the missing corridor tiles that go around the corner.

[corremn]

Rooms can have parts through which a tunnel can't pass, like corners. What can be done about this? How do we make sure tunnels don't go through them yet everything gets connected?

Make room corner a special tile protected from tunneling, then check all corners to see if corridor didn't make the connection to room wall and create the missing corridor tiles that go around the corner.

Increase corner weights for A*. Dont allow tunnelling.

Or have a pre map data structure that contains meta data like isCorner, isWall, isFloor, or doNotTunnel. Possibilities are endless.

[mike3]

The current scheme involves marking the walls along rooms and tunnels as horizontal, vertical, or corner, and using that to block or divert tunnels. Interestingly, I found that some of the slowness was in this marking process. The algorithm is somewhat faster now, but I think it'd still take several seconds to generate a level if you were running it on some really old kit.

[Krice]

but I think it'd still take several seconds to generate a level if you were running it on some really old kit.

I think the speed is the last thing you need to worry. Just make it work, then think about optimizing it. There are older computers still in use, but I think it's mainly in Poland.

[mike3]

but I think it'd still take several seconds to generate a level if you were running it on some really old kit.

I think the speed is the last thing you need to worry. Just make it work, then think about optimizing it. There are older computers still in use, but I think it's mainly in Poland.

Right now it works pretty well, just that it's "slow". I found out about the slowness after I got it working.

[corremn]

Is the slowness in debug or release? My tunneling algorithm is painfully slow in debug, but flies in release. Its to do with heavy iterator checking in MSVC.

[mike3]

Is the slowness in debug or release? My tunneling algorithm is painfully slow in debug, but flies in release. Its to do with heavy iterator checking in MSVC.

Just ran two tests with the newest version of the algorithm. By generating 1,000 levels and measuring the time, I find that for levels of size 80x80 tiles, with 27 rooms (6x6 room grid @ 75% room density), I get a per-level generation time of 66 milliseconds/level in "debug" mode (compile with straight "g++" with no options -- yeah, I'm using GCC on GNU/Linux by the way) and 7 milliseconds/level in "release" mode (compiled as "g++" with "-O2 -DNDEBUG" switches). That's good -- since it's too short to see -- but this is a near-modern Core 2 Quad Q6600 system (~3 years old). On some ancient box 500x slower than this, that would give 3.5 seconds to generate a level. Would it be bad press if someone tried this thing out on their ancient 486 (or whatever) junker and found that slowness? Or even on a Pentium I and you see that noticeable hesitation there as it generates the level?

Jamming the settings to the "max" -- 8x6 room grid @ 100% density (=48 rooms), same 80x80 size yields much slower speed: 138 ms/level debug, 15 ms/level release -- that's over 7 seconds on the archaic machine just mentioned. However, usually I don't run it that dense for the game, probably more around the other settings mentioned (6x6 grid @ 75% density for an 80x80 which is the biggest level size I use).

Is a few seconds on archaic junkers bad though? Just paranoid about the press -- love the results from the algorithm in terms of what it generates. The levels are cool.

[Darren Grey]

Anyone who is judgemental about such speed on old machines will likely be illogically judgemental about other aspects of your game too.  Don't worry about it.

[corremn]

Yep, who cares