Mapgen: Tunneling Algorithm

Cogmind’s main dungeon maps are excavated by “tunnelers” that dig corridors and rooms, much in the way a dungeon architect would build a home for their master’s minions. An empty map is seeded by one or more tunnelers, and they travel around that map opening up all the areas that will become occupiable space, e.g. corridors, doors, rooms, halls.

I like tunneling algorithms because with the right parameters they can create fairly realistic environment.

Behold an underground complex ruled by robots!

Inspiration

First I must give credit where it is due. Tunneling algorithms didn’t interest me before because when used in expansive dungeons they tend to produce boring repetitive layouts. Then a few years ago I came across this project, which introduced me to the key concept that tunnelers can change their own parameters as they move (there’s a good overview of the idea on that site). The result is a more varied dungeon environment, especially across larger maps like those Cogmind uses.

That particular algorithm has some oddities--what’s with all the useless and redundant corridors? Why doesn’t it ever produce even-width corridors?* I suppose many of its drawbacks never came to the forefront because the creator never applied it to an actual game:

Looks cool, but not very realistic.

*I suspect this has to do with symmetrical tunnelers being easier to work with in code. While I’ve written my own algorithm to handle arbitrary widths, because tunnels logically tend to shrink and grow two cells at a time, even-width corridors eventually become odd-width corridors anyway after shrinking to 1-cell wide then growing again!

A dungeon excavated by a single even-width tunneler (begins top center) eventually creates more odd-width corridors (blue) after its initial run of even-width corridors (orange).

I may not bother using even-width corridors since they are more likely to produce off-center connections that don’t look quite as nice. I do like 2-width corridors from a gameplay point of view since they are narrow yet still leave enough room to maneuver around other units, but 3-width corridors are probably better as a standard for a game like Cogmind in which battles are most commonly fought from a distance--there needs to be enough room to set up a decent firing line.

In any case, over the years I’ve been working on my own algorithm based on the same principle: that tunnelers creating the dungeon can evolve over time to “mix things up.”

Parameters

There is a wide variety of parameters to control for tunneler behavior: Width, direction, speed, chance to turn, chance to create rooms, size and shape of rooms to create, how much space to leave between self and other dungeon objects, when to quit…

Example: Increased padding between both corridors and rooms might be desirable if you don’t want it to be too easy for the player to blow their way into another room/pathway. In my case I keep padding low because what good is destructible terrain if you can’t use it to your advantage to make situations more dynamic? (But look out, because a very determined enemy may come blasting through a wall, too!)

Anyone familiar with procedural map generation will know that the same algorithm can produce significantly different results by tweaking its parameters. Later I’ll be showing more features used in conjunction with this algorithm to make it even more dynamic, but this is essentially all we need for the core game.

Size

Many maps in Cogmind are going to be even larger than in the 7DRL, and include more open spaces. The main dungeon used to be 100×100 per map, which will be increasing to up to 200×200 for the largest maps. That’s four times as large:

The largest likely map. Layout/style is still very WIP, but the algorithm is 90% complete--still some cleanup to do to reduce overall jaggedness. (click for full size)

Why larger maps? Well, first of all Cogmind always needed the space since combat is mostly ranged--you are generally fighting enemies an average of 15 or more cells away. Maps are growing even larger mostly to accommodate changes in game content.

The world will be larger with more places to visit, so we need to spread out the main maps such that area transitions aren’t too frequent. Battles might be bigger depending on your play style; who knows, raising a small robot army is likely to start a little war? In short there’s more you can do now, and we need more space to do it in.

There’s also a greater emphasis on intelligence gathering. Aside from sensor-type parts seen in the 7DRL, you’ll be able to learn about the map via terminals. Larger maps will encourage players to take advantage of these sources of information when possible. This should make the stealth route more feasible since you have more means of learning about the layout and enemy movements, but the map isn’t small enough that this knowledge will make success too easy.

On a more fundamental level, many areas of the map that would have been empty in the 7DRL will now be occupied by machines, so less of the map space is actually as “occupiable” as it appears. The current stage of map generation is only interested in connectivity, flow, and open vs. closed space; we’ll get around to placing objects later.

Composition

As stated earlier (and you can see above), the new maps have a fair number of wide corridors and open areas.

The 7DRL contained a much higher ratio of corridors and places to hide, making it seem easier to hide than it actually was--the enemy could track you down without much difficulty, or even head you off at a shortcut because after all they know the dungeon better than you do!

Opening up the map forces you to think a bit more before attracting attention, since in doing so you may end up committed to a confrontation until it’s resolved.

Layout

During the generation process tunnelers are responsible for laying the paths that take the player from an entrance to an exit, of which there are usually several with a guaranteed amount of space between them. How tunnelers move and what they decide to do pretty much determines what most of the map will look like.

When possible most tunnelers try to dig out rooms along their edges. These serve as places to hide/wait or find parts. They may also contain machines, which are sometimes just for atmosphere, or not. Rooms with multiple doors are usually an intersection of sorts, giving access to areas other than their primary corridor.

Tunnelers also sometimes build junctions when turning or changing width. These aren’t purely aesthetic enhancements--junctions can contain terminals from which operator class bots supervise local activity.

Those junctions located along main corridors will almost certainly have terminal access.

The idea of having some terminals located at corridor junctions was seen in the very first mockup, as above.

Tunnelers also spill into and contribute to larger areas called “halls.” If you’re trying to stay undetected you’ll want to think twice about traveling through halls, since a passing patrol or scout is more likely to spot you.

Halls will usually contain larger machines to further subdivide them and provide obstacles behind which to hide.

We’ll be taking another look at tunneler-generated maps in later posts on other map-related topics.

This is the second in a five-part series on procedural maps:

• Part 1: Procedural Map Generation
• Part 3: Cellular Automata
• Part 4: Dungeon Metrics
• Part 5: Dungeon Prefabs
  

Update 190306: There’s also an additional article now which covers procedural layouts as they related to level design in Cogmind.