Official development blog

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.

cogmind_map_main

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:

mapgen_tunneler

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!

cogmind_map_tunnelers_even

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…

cogmind_map_tunnelers_padded

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:

cogmand_map_tunnelers_huge

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.

cogmind_map_tunnelers_junctions

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

cogmind_mockup_machines_terminal

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.

cogmand_map_tunnelers_halls

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:

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

This entry was posted in Design, Dev Series: Procedural Maps and tagged , , , . Bookmark the permalink. Trackbacks are closed, but you can post a comment.

8 Comments

  1. Asterne
    Posted July 27, 2014 at 3:30 am | Permalink

    Hey, I’ve been working on a roguelike game of my own lately, and I’m having trouble wrapping my head around this mapping method. Would the pseudocode be something like what I have below?

    1. start miner with parameters
    2. if there’s enough minimum room for a corridor, continue. Else kill the miner
    3. generate random distance to intersection
    4. test if there’s enough room. If so, continue. If not, return to 2.
    5. mine out tunnel
    6. random chance of generating miner for each direction
    -- miners generated with random but guided parameters

    If so, where does the room generation come in?

    • Asterne
      Posted July 27, 2014 at 3:34 am | Permalink

      Or wait, no.

      4 and 5 turns into random with maximum being the room, since it’s checking.

      • Asterne
        Posted July 27, 2014 at 3:34 am | Permalink

        er 3 and 4

    • Kyzrati
      Posted July 27, 2014 at 7:40 pm | Permalink

      Seems like you more or less have the right idea with your pseudocode, the only difference in terms of adding rooms would be that instead of step 6 where you generate random “miners,” some of those miners might instead be “room excavators.” Just remember that the latter is more or less the same thing as a miner, only it digs a room instead of a tunnel--both types of objects can be delayed in their activity so that at any given point during generation you have a lot of idle miners and room excavators sitting around waiting to become active. By the time many become active, they will have nowhere to move and just quit, but any that do have enough space will continue to build tunnels and or rooms.

      • hexe
        Posted April 16, 2019 at 3:57 am | Permalink

        Hi there! Quick (I hope!) question here: I’m not sure what’s the strategy for different tunnelers to create loops, that is to connect parts created by different tunnelers in order to deviate from the “perfect tree” structure typical of BSP algorithms.

        Thanks in advance for your time and keep up the good work, I love your game :)

        • Kyzrati
          Posted April 16, 2019 at 7:46 am | Permalink

          Hi hexe! Yeah that should be pretty easy to accomplish, the trick is essentially allowing tunnelers to join existing tunnelers (or even other rooms) already excavated by other tunnelers.

          Now you don’t want it to let it get completely out of hand and become nothing but a web of connections, so you’ll generally want an adjustable chance of whether or not a tunneler will connect (rather than stop outright, or turn in a different direction). This implies your tunnelers are going to need to look out X cells ahead of their current position to see where they’re going.

          Does that make sense?

          • hexe
            Posted April 16, 2019 at 5:31 pm | Permalink

            absolutely, that’s exactly how I’m planning to implement it.
            Actually the general idea is to compute the distance matrix between each pair of candidate map entities (i.e. rooms, corridors or junctions). And only attemp to connect those which are “close enough”, in order to avoid wasting time trying to connect rooms which are on opposite sides of the map.

            Another unrelated question, while we’re at it: do you use any specific tool for project management, something like todoist or trello or whatever?

            I’m asking because working solo is a bit different than working in a team and using a full project management software like Jira or Asana seems a bit of an overkill.

            As always, thanks for your time and have a great day!

          • Kyzrati
            Posted April 16, 2019 at 6:52 pm | Permalink

            I just use plain old text files! (primarily one huge text file for the TODO) The topic has probably come up on the blog here before, but I’ve written more about that in particular among these FAQs, where it’s probably easier to find what you’re looking for (plus you can read about how other devs manage their own projects).

            Indeed team solutions will generally be overkill for solo projects. I know a bunch of devs who at most use stuff like Trello, but in the end honestly there are almost as many different approaches to management as there are devs, just gotta find what works for your project and situation :)

Post a Comment

Your email is never published nor shared. Only the anti-spam entry is required. See here for the privacy policy.

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>