I’ve been working on algorithms for randomly generating dungeons.

My project Caverns of Underkeep is a Roguelike, and one of the features of all roguelikes is that they have randomly generated dungeons. there are two flavors of random dungeon generation in Caverns of Underkeep and I’ll explain how they work in this article – Surprisingly the simplest algorithms can often produce the best results.

Here is a screenshot from a typical Cave map

The way this type of dungeon is generated is as follows:

• Start with a completely unwalkable surface, then draw some randomly sized circles in random places – These circles are going to be water areas.
• Perform a couple of random walks from the centre of the map, if we fall off the side of the map stop walking.
• Locate tiles that are dead ends. (Any tile that has only one walkable tile as a neighbour) At these dead ends place a circular style room. Use a basic turbulence* algorithm to alter the shape of the room.
• Locate a few other tiles that are part of a corridor – And not part of a room (To do this just work out how many unwalkable tiles are in the area immediately surrounding the tile you selected – If the number is greater than 2, then the tile must be part of a room and not part of a corridor) and randomly place some more circular rooms at these locations.

*A basic turbulence algorithm for drawing a shape is if say – You are going to draw a rectangle, then draw it as normal but determine randomly if you are going to draw N more rectangles with slight x and y offsets to give a more interesting shape to your rooms. See the image below for an example.

The second type of map is a Citadel – A typical screenshot is bellow.

This algorithm is pretty much the exact opposite of the one above.

• Instead of starting with some random walks, I divide the map into 10×10 sections. Doing this gives it that more deliberate man made look to it.
• Determine if I want to place a room here – If I do, note it’s location in a big list of rooms.
• Draw a random rectangular room (with turbulence)
• Once all the rooms have been drawn, consult my list of rooms. For each room draw a corridor between that room and the nearest room. Once a corridor has been drawn from a room, remove it from the list of candidates for nearest neighbour (otherwise we could get stuck in an infinite loop)

Both algorithms are guaranteed to be completely connected – Which is a really important thing to have in a roguelike. There’s nothing worse than not being able to complete the game because of the random generator – Bad computer, no biscuit!

In Caverns of Underkeep I also take a hybrid approach to generate the sewer levels. Basically I combine the two algorithms to produce another style of dungeon – See if you can work this one out for yourself