23.
Oct
2011

Dungeon Generation explained

4

In this post I’ll try and explain the dungeon generation that we are currently using in our dungeon crawler (WIP title: Awaken). It’s taken us a little bit of time to get to the place where we are somewhat happy. There will still be lots of improvements done until the final release, but in the meantime we can get some pretty decent looking dungeons.

To give you an idea of what kind of dungeons we are currently getting, here’s an image that shows variously sized dungeons generated out of the game:



Each level consists of various sectors and “key rooms”. The grey rooms on the picture indicate “key rooms”. We use these rooms to create a certain linearity into the dungeons. All key rooms are generated by hand and with that we can ensure the player goes through certain “key” locations in the game. This also keeps the dungeon approachable to a degree, as you always have certain recognisable key points if you get lost. Besides that, we leave it up to the player how much he wants to explore..

Each sector is split up via a simple BSP algorithm:

– Pick a random direction, either horizontal or vertical
– Pick a random position along the x or y axis
– Split the sector into two sub-sectors
– Repeat until desired room-size is reached

The picture above is what a sector looks like after it’s been split up into bsp nodes. The next step is to fill all these nodes with rooms. Because I wanted maximum flexibility I created an abstract concept, the “room generator” that spits out rooms following specified rules. For example the default room generator will only create rectangular rooms using up as much space as possible within the node. I’m planning on adding various generators on top that’ll create round-ish rooms, etc. This makes it possible to create extremely diverse dungeons, even though we’re only using one type of generator.

Once all the nodes have been filled with rooms we need to connect all of them. That’s fairly easy, you just traverse back up the bsp tree and connect neighbouring nodes. This way you’ll always end up with a completely connected sector.

From there the only thing left to do is connect the individual sectors with the key rooms and we’re done.

After that the dungeon gets “decorated”. This includes placing items all over (incl. doors, etc.). Depending on the interest I might post some stuff on that as well.

If you want to do some more reading up on dungeon creation here are some resources I’ve found useful and learned from:

http://roguebasin.roguelikedevelopment.org/index.php/Basic_BSP_Dungeon_generation
http://pixelenvy.ca/wa/ca_cave.html
http://roguebasin.roguelikedevelopment.org/index.php/…
http://doryen.eptalys.net/articles/

I hope someone will find this information useful!

4 comments on “Dungeon Generation explained

Leave a Reply

Your email address will not be published. Required fields are marked *


*