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

My current project Caverns of Underkeep is a Roguelike, and one of the features of all roguelikes is that they are randomly generated. I’ve currently got two flavors of generation. I’ll briefly explain how they work here, but I really want to write a much longer article as there is a whole bunch of neat stuff - 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:

• 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. 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) randomly place some more circular rooms at these locations.

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!