Watabou’s Cave Generator is one in a series of RPG-ready map generators that Watabou has created over the years. All his work oozes style, but the cave generator was always the one I found most mysterious.

I discovered that the entire thing was exported with extremely readable javascript, so naturally I started to poke and prod. Let’s go over how it works.

We’ll focus on how this map is generated for version 2.0.2:

Getting started

The main thing to initialize are tags. These are randomly picked, but can also be set by the user.

Tags control the later generation steps. Sometimes they switch between different algorithms, but more commonly they act as presets for numeric parameters. I’ll refer to tags like this when they are referenced. Some tags are mutually exclusive – e.g. only one of small / medium / large can be chosen.

Some other global parameters are randomly chosen at the start, such as chamber size and connectedness preference for area growth. This gives each dungeon a more consistent feel across the map.

Like all procedural generators, there is a seed parameter that controls all sources of randomness. This enables permalinks for maps by storing the seed.

The hidden grid

It’s not obvious, but in fact everything in the generator is done on a hex grid. Let’s see the final output again, this time with all the graphical details turned off – no wobbly lines, no random rocks, no water, no superimposed square gridlines.

Now you can see the actual specifics of the map. But how is the layout actually achieved?

Grid To Mesh

After creating the hex grid, it is immediately converted into a data structure called a Doubly connected edge list, which is essentially a fancy way of representing a mesh of polygons and their neighbours. Everything in the generator operates on this mesh data structure – it’s not tied to hexes at all. I was able to hack in square grids without much difficulty, the author just didn’t find a use for this feature.

Seed Growth

The majority of the map is generated with an algorithm called seed growth¹. It picks a random starting location and then adds adjacent cells at random until a predetermined size has been met. This is then repeated to give several areas. Areas are not permitted to touch each other.

Most of the details of the generation are determined by tags:

The number of areas is 9-19 for a large map, 3-8 for a medium and 2-3 for a small. If no tags are present has a 1 in 20 chance of picking 2 or 20, otherwise it uses a random formula.

The size of each area is also a random function. For hub generations, there is one area of size 60-79, and other areas of size 8-13. For chamber, a random chamber size is chosen between 11-14, and then each area is randomly offset from that by 0-2. And for burrow, it uses formula 10 + 80 * pow((rand() + rand() + rand()) / 3, 3) which gives rooms around size 23, but occasionally much larger.

When choosing which cell to add to the area, they are weighted differently according to various algorithms. By default, it weights each cell as pow(c, gamma) where c is the number of adjacent cells already in the area, and gamma is a random variable indicating the preference for connection. High gamma tends to cause rounder areas with fewer jutting pieces. cavities fixes the gamma of 6, while coral uses a negative gamma so each area prefers narrow tendrils. chaotic prefers cells with 2 connections.

Building doorways

Now its time to connect up all the areas. First, the algorithm identifies all cells that border two elements.

The possible area-pairs are then culled. For tree, a simple depth first search ensures each area is only reachable a single way (no loops). For connected, if it finds 3 areas all adjacent, it disconnects one pair. Otherwise, all pairs are kept.

For each pair, a single door cell is randomly chosen from amongst the possibilities and added to the map.

Building Corridors

Some areas are randomly chosen to shrink to corridors. It prefers areas with a large number of doors for the area, and some tags, particularly burrows, greatly increase the chances.

To shrink an area, points are repeatedly removed, and flood-fill is used to ensure that the doors are all still connected, which I describe more in Chiseled Paths Revisited.

At this point, exits are chosen too, which are randomly selected from eligible border cells. Cells further from the center get higher weights. The exact number of exits can be controlled with tags sealed, entrance, passage, junction.

Water

The water is simply an independent Perlin noise, which is compared against a threshold. It’s more obvious in v2.1.0, where you can play with a slider.

Rough outlines

The hexagonal nature of the walls is hidden via several steps:

• Every edge is subdivided
• The outline is smoothed (“bumpiness”)
• Vertices in corridors are moved towards the face center.
• The points are randomly offset (“irregularity”)
• Two more iterations of subdivision and randomness (“roughness”)
• The boundary is converted to curves with Chaikin’s Algorithm (not shown in gif)

Cosmetics

Some random small polygons are dropped on the map to make stones and rubble. Dyson hatching is applied near the boundary.

Title

The title of each map is generated using a Tracery script. Many features contribute to the choices – “demonic” names are more likely for certain tags, and the presence of water increases the chance of damp names like “Bog”.

The top-level rule gives you an idea of what it’s like:

	"name" : [
		"#compound_noun# #noun#",
		"#adj# #noun#",
		"0.2?-#noun# of #fantasy#",
		"!LARGE&0.2?-#person#'s #noun#",
		"!SMALL&0.1?-#noun# of #epic_noun#"],

Glade Mode

Glade mode re-purposes the entire generator for making forest clearings. The main differences are the trees randomly drawn along the border, and the name generator switches to a different script. I love how you can switch it on and see the same map completely re-interpreted.

Summary

Oleg’s generator illustrates a common maxim in procedural generation. Great results don’t come from applying a super advanced algorithm, but rather by combining several simple rules effectively, and with an eye to the look and style you are aiming for.

In my opinion, Some of the rules used here, notably seed growth, and path chiseling offer a nice balance of simplicity to useful results and are generally underappreciated as techniques.

1. We’ve seen “seed growth” before in my Binding of Isaac article. But there’s no widely known name for this technique that I’m aware of. ↩︎