Subscribe to:

The Kiwi's TaleWitchBlasterDerelict Blow Stuff Up

Random Dungeons



A couple of years back Joshua Smyth created a blog post explaining the algorithms he used to generate the randomised levels of his browser RPG Caverns of Underkeep.

Special thanks goes to Josh for not only allowing me to repost it here, but for updating the article with new screenshots.

Random Dungeons


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


cou_caveMy 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.

turbulence*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.


cou_castleThe 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!

cou_sewerIn 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 :)




Joined: 05/05/2009

Really like the algorithm you have used here.. I previously have thought about this before... Unfortunately the games you can get from these levels can be boring, not because they are 'predicable' just because there is nothing to do and new emergant (rather than designed) patterns are too far few inbetween.. Although I think randomized levels are a great tool to aid people in development, when they can't think of some underline theme. (Zelda 64's grid based lost forest for example.)

The next step is making the levels somewhat playable on their own.. Maybe a method for adding secrets (don't remove some of those dead-end random walks?) .. Hrm maybe these maps would be excelent Zelda maps. Although the problem with mapping on a 2d plain for a game, is that unless you want Duke Nukem 3d like work around, it is impossible to have a 'building' per say. One thing that has pressed on the back of my mind, is realistic random 'office building' design.. For let's say a sandbox Mirrors Edge. (Something I have been playing with in the back of my mind.)

I wonder however if it would be possible to design the algorithm to apply mathematical patterns underneeth so it would be possible to get an emergent pattern in the over all design.. Think of the Triangle-rule thing that the speaker talked about in the Wolfram Alpha talk...

Earok's picture
Joined: 02/06/2009

Arran, have you played Blow Stuff Up? While the procedural generation involved certainly isn't nearly as impressive as Joshua's, it does have a very rudimentary randomly generated city. The buildings have random heights but the engine is biased to generate skyscrapers near the center of the city and short buildings around the fringes.

It kind of is a sandbox Mirrors Edge as you can run and jump across the building tops while avoiding fire from airborne and ground based foes, except you're supposed to destroy them too ;)

Joined: 05/05/2009

No I haven't although we have previously talked about it. :) The procedural generation I was thinking about was VERY detailed. There is actually a commercial fully fledged city generator that has a lot of architectural detail. (Not the type I want to concentrate on to be honest.) I tried to play with it but it was kind of complex and I never quite got the hang of it. It was involved the Rome building project.

Yeah I have your games in a folder, I need to get around to them. :S Sorry. :S