Building the Java Crypt: A Dungeon Building Algorithm
If you’ve ever played rogue-likes, or other similar games, you’ve most likely encountered some amount of procedural generation. Often, this takes the form of randomly generated levels, or may extend to other aspects of the game like random monsters, items, quests, or more. This is done to improve replayability in a genre that tends to include permadeath along with high levels of difficulty.
There’s arguably as many ways to write a procedural map generation algorithm as there as developers writing them. This is just one algorithm that I happen to like, and find to be a good basis for expanding upon! In particular, this is very similar to the algorithm I used to build the dungeon in Rogue Janitor. I’ve put a version of it onto a CodePen here.
The overall algorithm I used can be summarized as follows:
While the map hasn’t been filled to the desired amount yet:
Randomly choose a room size and type.
Find a random location.
Check if the room will fit.
If it fits:
Draw the room and add it to the list of rooms.
Add connections from the new room to one or more other rooms.
Run some a function to add doors.Choose a room to be the start point and add an up staircase there.Find the room furthest from the start point and add a down staircase there.For every room in the list of rooms:
Add items/monsters/other content as desired!
As always the devil is in the details. For choosing where to add the first room, a random location within the boundaries of the map is chosen. For every subsequent room, it tries to shift the location slightly. If the location ends up outside of the map boundaries, the location finder is reset to some other completely randomized location. In the model above, this approach of taking small steps isn’t strictly necessary, and the map end up entirely filled regardless of how it’s done; but on much larger maps, or if the map data is stored in such a manner that it doesn’t have a hard boundary and could extend indefinitely, small steps give less absurd results.
Connecting the rooms together is another part that takes some thought. I like to choose the nearest preexisting rooms, and connect the new room to one or more of them. You can have a hallway carving “digger” walk from the centre of the starting room to the desired destination. For an artificial seeming dungeon, you can have the digger walk to match the X coordinate first, and then walk down to match it’s Y coordinate as well. To add slightly more variety you can add some slight wiggles along the way, to make bendier corridors. One approach that could give better results than what I’ve done is to use a variant of whatever pathfinding algorithm your game is using to march your digger to the desired room while avoiding other rooms, or perhaps towards the nearest open space.
Adding doors is the component I often struggle with; I’ve never been 100% happy with the results. The approach I chose though is to check every tile in the map, and then look at it’s neighbours. If it has two walls on opposing orthogonal sides (i.e. straight up and down, or left and right) and is within a room, it is probably an entrance to the room, and a good place to add a door. Some rooms will have overlapping hallways, leading to double width entrances that won’t get doors with this approach. I don’t mind this so much; I like that visual effect of some rooms opening up into cavernous hallways between them. You can use a more complicated hallway carving algorithm that avoids that problem if you prefer!
There’s a lot of ways to decide where the start and end location should be. I like to choose a random start point, and then choose the furthest room from that point to be the end, to both give some variety to where the player starts and also force the player to traverse as much of the map as possible. I also think it’s a good idea to add goodies and treasure to a majority of rooms, if not all of them, to reward exploration and encourage the player to do more of it.
Monsters can be more randomized. In this case, there’s a probability of each room having a monster, with the exceptions that the start room will never have a monster and the end room will always have a monster, without exception. My reasons being, getting devoured by a dragon the moment you hit go isn’t very fun. Meanwhile, I want the player to have to fight to get to the next level; the exit should always have a guard! This approach tends to leave the hallways pretty empty though. You could have alternative approaches to adding monsters; say, having a target number of monsters for the level and adding them completely randomly throughout the map. An approach I find fun is to have the monsters wander around, as opposed to being tied to their initial location; they might ambush the player, rather than the other way around.
While this algorithm is relative basic, you can expand it quite a bit. One approach is to add a variety of room types. For the toy model above, every room is rectangular, but the power of this model is that you can do whatever you want for the rooms! All you need is:
- A function to check if the room will fit
- A function to draw the room.
For example, if you instead wanted to draw a circular room, you could check a circular region, and then draw that circular region. If you want to make a cavern, generated using a cellular automata approach or a digger, you can check a rectangular region and then run that cave generator within that region. A really easy way to add flavour to a particular dungeon may be to change what room generator you’re using for an entire dungeon; the underlying algorithm is the same, you simply swap out how your rooms are built, or their relative probabilities.
Another way to add variety might be to meld it with another dungeon generator, or with other larger map features. For example, you could write some code to generate a cave level, or a river or chasm, and then run this algorithm around that to fill in the rest of the space (though you would need to figure out how to adapt the corridor carving code to connect to the larger features). You would then have interesting levels with recognizable terrain features, plus some extra rooms built around it.
Dungeon generators for games are a lot of fun to code. I love taking a skeleton like this and then building upon it to give each game it’s own flavour. I hope you’ll play around with my example here, think of your own ways to further expand upon it, and make some cool stuff with it!
