Procedural Cavern Generation

We're adding a bunch of new features to our engine right now to prepare for instanced dungeons and zones. Our task for the week was to replace the level design team with robots and implement procedural cavern generation. Here's a play-by-play of the cavern creation process, which makes some pretty interesting maps. The method is pretty straight forward, and can be used for any Roguelike or dungeon crawler. Our 3D client needs some enhancements, so we'll be using the text-based version for screenshots.

The method used is based on an algorithm described by a Roguebasin article here:

Step One: Placing Random Walls

Starting with a totally open map, the first step is to randomly change a percentage of the walkable tiles (.) into walls (spaces). The density of these wall tiles will affect the shape of the cavern in the next step. We want to create a circular cavern rather than a square one, so the amount of wall tiles rises steadily from the center out towards the edge. In our example map to the right, we have a 20% fill rate, which should create an open, spacious cavern.

Density map

Step Two: Smoothing Things Out

Our map looks ugly right now, so we use a fancy cellular automation algorithm to smooth it out. For each tile, a count of walls is performed in a 3x3 box. If there are 5 or more walls, it becomes a wall tile. If not, it's a walkable space.

Another check is performed to remove really open spaces - if there are no walls in a 5x5 area of a tile, the tile becomes a wall. The box size can be expanded to allow for more spacious caverns.

First pass

The first pass already looks much, much better. Performing the same transformation a few more times will smooth the map out even further. To the right, the map has run through five passes, which looks smooth enough for our final result. Notice that a lot more open space has been filled.

For a variety of ruggedness between maps, some caverns run fewer or more passes.

Fifth pass

Step Three: Adding Variety

The map shape is pretty good, but it's still pretty boring overall. Let's add a variety of different terrain types to spice things up. In our example map, we're going to place some rough terrain (%) and forests (#). This is done by placing 16 to 64 % and # tiles randomly, then spreading them out until they fill a certain percentage of their usable space. Each map has anywhere from 2-15% of its walking space occupied by these terrain types.

Rough/forest

Next, we place some pools of water or lava using the same algorithm. This is an easy map that's close to the surface so we're only using water, but as we go deeper into the earth, lava pools will start to form. The amount of water varies drastically from map to map - anywhere from 0% to 33%.

Water pools

Step Four: Making it Playable

Our map looks interesting now, but it has one fatal flaw: the water has divided most of our walkable area and left several regions unreachable by foot. Our characters can't walk on water (or lava), so adding pools will often make huge sections of the map inaccessible. There are also some pockets of space completely surrounded by rock. To fix all this, we cut away every walkable region but the largest one, as shown to the right.

Every tile reachable by foot

Although all of our map is now reachable by foot, this is obviously a tiny portion of our original map, and it's totally unacceptable! So, let's take a few steps back to the terrain/water placement phase to shrink pool sizes and change their locations. We'll repeat this process until we have at least 75% of our original map. After a few tries, we finally end up with something usable. The regions cut make the map more unique as an added bonus.

Less water, more reachable

Step Five: Final Touches

Our map is now fully playable, and every location is reachable by foot. This means we can randomly place treasure, monsters, exits, traps, etc. without fear that players will never reach them. But first, let's make some cosmetic changes. In the image on the right, pools of water surrounded by rock have been scrapped, leaving us with a clean map, totally free of any useless regions.

Scrapped useless water

Finally, we can add a border to our map to make it prettier. Each wall tile checks the 8 adjacent tiles to see what character it should use. This is done with a simple table lookup. Once our borders are placed, the map is finished! Here's the final map in full view:

ProcDungeon9.jpg

More Examples

ProcMontage.jpg

-- Simon (Synival)


Harmonia
Harmonia Game Engine
Copyright © Baroque Creations 2014
All Rights Reserved