Javascript Demo

If you want to see this in action, you can find a javascript version of the algorithm described in here that runs in your browser over here.

Introduction

Ever since playing my first dungeon crawler (which must have been “Eye of the Beholder” if I remember correct, but there have been a lot of them in my early gaming days) I wanted to do something similar. And in my first years of coding I even started several dungeon crawlers (using Turbo Pascal under DOS), but none of them really took off due to several reasons. So to take a little break from working on Projekt “W” I decided to revise this idea and start working on a random dungeon generator, that’ll maybe at a later point spawn a nice little game (not a huge project though).

And there are basically two ways of creating dungeons for a dungeon crawler (or any other game using something similar to dungeons) :

1. Manually create them using e.g. a 3D modeller or creating your own tools for doing so. This gives you a lot of creative freedom but also means a lot of work and if you want diversity, you need to create a lot of differen dungeons manually.

2. A random dungeon generator that can create an unlimited amount of different dungeons. Although this means that dungeons usually aren’t as “nice” as dungeons created with option 1 it’s the far mor fleixble and interesint way for a programmer to create dungeons. And that’s mainly because it’s a challenge to write a random dungeon generator that outputs useful dungeons. And that’s exactly what I went for, as a random dungeon generator allows for an unlimited amount of different levels without having to create too much content.

So this article is about my “journey” into the realms of random dungeon generation. Since I’m someone that likes to do stuff his own way I decided against using existing generators or diggin through articles that descirbe how to generate random dungeons. Although this resulted in a  “longer-than-expect” timeframe for finishing the random dungeon generator it also resulted in the fact that I wrote a random dungeon generator all by myself, making me kinda proud, which wouldn’t have been the case if I just adapted an existing version from an article.

Note that this is not an article on how to code a random dungeon generator, but more a journal on how I went from zero ideas on how-to-do it to a fully working dungeon generator in the end. If you just want some code or an algorithm for your game then you’re wrong here. But don’t worry, along the road to success I’ll roughly explain the workings behind my generator, so you may even learn something from reading this article.

First try - Doing corridors first

Yes, that’s right. My first idea was not randomly place rooms inside the dungeon, but to rather first place corridors more or less randomly and then to put the rooms “atop” of them. If this would have worked out, then it would have saved me a lot of time. But sadly it didn’t! The idea behind this was to randomly start at the border of the dungeon, start a new corridor there, walk around the map changing direction randomly (after a certain number of steps was taken into the current direction) and to stop randomly after a minimal size for the corridor was reached. Then I would have repeated that until at certain percentage of the dungeon would be covered with corridors. In practice it looked like this :

At first sight this didn’t look to bad. The algorithm for creating the corridors generated pretty results, and if it were only about corridors I would have been fine by now. But after placing the rooms I quickly realized that this idea was going nowhere. I quickly threw together a BSP tre for randomly placing rooms. It worked by splitting the whole dungeon into smaller partitions (like any BSP tree) until splitting was randomly stopped, and also randomly checking if a final partition (one that has no childs, splitting stopped there) should have a room. This method makes for easy room placement without the rooms overlapping. But after implementing that BSP tree I saw that my first assumption was wrong. In the first place I thought when the randomly generated corridors would cover a certain percentage of the dungeon, putting rooms atop of them would give me a nice dungeon with all rooms being reachable. But the results were pretty bad :

Although that roughly looks like a dungeon, the two ones above are actually selected out of a few that looked half-way useful. About 8 out of 10 randomly generated dungeons looked bad or just had rooms that weren’t connected. So this idead wasn’t working out and was complelty scraped.

Second try - Placing rooms first

Step 1 - Placing the rooms using a quadtree

Since the early idea of creating corridors first didn’t work out like I wanted it to, I decided to start from scratch and place rooms first and then connect them. But the first try wasn’t totally useless, as I decided to built on the idea of using some sort of space partitioning for placing rooms. But instead of the BSP tree (which obiously has only two childs in a partition) I opted for a quadtree. Each partition here has four childs, so if I divide a partition I split it horizontal as wall as vertical with the split being randomized in each direction. Splitting will be stopped randomly (to randomize room distribution) or when the size of a partition has reached a lower limit.  Combined this results in a nice seemingly random distribution of non-overlapping rooms.

Step 2 - Connecting the rooms

So now that all rooms are in place and none of them overlap it’s time to connect them using corridors. This part is pretty easy. Start at the “lowest” partitions of the quadtree (all partitions that have no childs, I collect them using an array and just loop through it) and then for each of them create a connection to their neighbours and their parent. Generating the corridor then is done be moving from the center of one room to the center of the other room. After that call the connecting procedure for the parent partition to traverse to the top of the quadtree. Sounds easy, and also is pretty easy. Here are the first results of this (in the first shot the quadtree partitions are colored) :

Step 3 - Placing walls

This one is eaven easier than creating the corridors. Each cell has an array containing 4 booleans with each value representing a wall in one of the four directions (north, south, east, west). Now I only needed to loop through all the cells in the dungeon and see if that cell isn’t empty. Then I just see where this cell has it’s neighbours and place a well if there is no neighbour (or the border of that dungeon) in that given direction.

Step 4 - Placing doors

At first I thought this would be as easy as the two steps before, but it actually caused me several headaches until I finally got it working, mainly because the easiest solution was the last I could come up with. Initially I thought it would be sufficent to just check if a cell containing a corridor (each cell in my appliaction has a boolean value that is true when the cell is a corridor) has a neighbour that is not empty and not a corridor. But somehow that didn’t work until I remembered that I did the rooms atop of the corridor, so the there were still cells within some rooms flagged as corridors (bright green indicates a cell flagged as a corridor)  :

Fixing this was no problem. I just had to loop through all nodes of the quadtree, see if that node has a room and then see if one of the cells within that room was flagged as a corridor and then set this to false. After implementing that the dungeon looked like this :

Still not perfect, and my initial idea of placing doors (neighbour cell of a corridor is inside a room) still would not work. Just take a look at the left part and see the long corridor in the horizontal center. It “touches” several rooms and with my initial idea I would produce a lot of doors along that shared border. So next thing I had to to was to implement a function that checks if a corridor is running along the border of a room and then incorporate that border into the room by expanding the room itself over that corridor. Although it sounds pretty complicated, the solution to this is pretty easy. Again I loop through all nodes containing a room and then for each border (south, north, west, east) I walk along that border and check if that border has at least two adjacent corridor cells next to it (the adjacent is very important, just checking for two corridor cells would also expand the room if there were two separated corridors leading to that room). If that’s the case I expand the room in that border’s direction. This way I can easily eliminate all the corridors that run alongside a room.

So after doing all that cleanup, removing corridors inside rooms and expanding rooms to remove corridors alongside room borders it’s now safe to use the easy way for placing the doors : Loop through all cells, and if a cell is a corridor and one of it’s neighbours is not a corridor and not empty, place a door in that direction. And to see if it really works I decided to do a bigger random dungeon (128x128 instead of 64x64 in the previous screencaps), and yes, it seems that door placing now works perfectly :

Step5 - Adding randomness

Although the dungeon already looks nice it’s still missing some randmoness. Up until now I’ve been placing a room in each ending partition of the quadtree, and though the partitions are randomly sized (to a certain degree) it doesn’t look very random at all. But with a very simple trick we can add a lot of randomness for our final product. So each time an end partition is reached I only place a room inside when a random value is thrown (the value can be adjusted, making for much more randomness). This way not all ending partitions will contain a room and therefore not all cells will be connected using corridors. This adds a lot to the randomness of the dungeon as you can see :

No connection checks?

Right now you may ask yourself wethere there’s a need for somehow checking if all the rooms can be reached. But with the method I use it’s not. Due to the fact that I’m using a quadtree connecting all rooms from the bottom node up to the topmost node each room will be accessible by at least one corridor. To see if that really works I quickly added an A* search into the dungeon generation and in all of my randomly generated dungeons each room was accessible. But wait, don’t remove A*. It’s very useful for other things, e.g. if you want to have doors that need keys. This way you can make sure that a key can be reached without having to open the door that you actually need the key for, and even better, A* can also be used for AI movement in your randomly generated dungeon.

Conclusion

So that’s it. It’s not finished, and I already have a nice idea for making a dungeon crawler that is pretty much unique, but I don’t know if I’m ever going to start working on it. But other than that there is still some stuff do with my random dungeon generator (more randomness I guess) and a lot of room for improvement. But this was more than just coding a random dungeon generator, as with most projects I do I don’t gain any new kowledge, but with this one it was different. It was something I never had done and I did it from scratch. So even if it won’t make it into the game it’s something I enjoyed and something I learned.

And to finish off this small article here is a huge screencap of a big dungeon that is 1024x1024 cells big :