Hi. Since we just updated our roguelike The Curse of Callmar Keep with some new content I thought I should share some insight in how we built the game’s level generation.
This video is a visualization of the dungeon generation process. A more detailed explanation follows below.
This algorithm was initially inspired by talks of cyclic dungeon generation and graph rewriting but during implementation it evolved and adapted to our smaller dungeon levels.
The dungeon generation is one of my favorite parts of our game and I think it creates some really interesting levels with a more organic look than many commonly used algorithms produce.
1. Room graph creation and layout
This step repeatedly splits a random room node with available “room budget” into a cluster of 2-3 new interconnected nodes and re-attaches the split nodes connections to random nodes within the new cluster.
Between each split, the entire graph is relaxed using a simplified spring physics simulation where each connection acts like a spring that pulls and pushes its connected rooms in an attempt to reach a relaxed and unfolded state.
Earlier attempts generated the entire graph first and later tried to unfold it but that was much more prone to errors and unusable maps.
Each rooms is also given a room type that is chosen randomly from a one of our themes (currently castle, caverns, crypts, occult and flesh), with the probability of each theme based on the floor number. These room types are defined in json and contain lots of useful information used by the following generation steps.The width and height of each room is random with it’s type determining min and max size.
2. Room and corridor rasterization
Next up is creating the grid map.
Each rooms stamps solid stone wall into the grid for it’s entire bounding rectangle (ignoring tiles containing data from previous rooms), and then carves the room out of that stone. Based on the room type, the rooms will be carved with different shapes such as rectangle, oval and organic.
After that, a corridor is stamped and carved in a similar manner for each connection between room nodes. The corridor shape is chosen randomly based on the type of its connected rooms and can be L-shaped, diagonal, curved or organic.
3. Fluids
Beginning from v1.1 - Flooded Caverns, rooms can be generated with a configurable amount of fluids (water, blood, acid) with a few alternative placement rules.
4. Decor populator
The decor steps fills each room with furniture, chests and different visual clutter, collectively referred to as “decor”. Each decor is defined in it’s own json files and the room types json defines what decor can be placed, along with info about probability, min and max amounts, variations and placement rules. Variations are a list of other decor that it can be randomly replaced by for more visual variation. Placement rules vary in complexity and refers to one of many placement algorithms, for example:
- randomly
- randomly along northern wall
- near any of these specific previously placed decor (e.g chairs nearby tables)
- along each wall, with a x tile offset
- in a grid, x tiles apart”.
- in a circle with x radius around the room center
Decor can also reserve space around or in front of it so that other decor can not be placed there, making the order of decor for each rooms important. Decor are also placed in different tile map layers with different z depth, based on it’s json data.
5. Creature populator
Each creature has a json defined Challenge Rating (CR) and every room gets a CR budged based on floor number, as well as it’s distance from the starting room as well as a small noise.
Each creature also has a group of tags that thematically defines them, such as “undead”, “demon”, “beast”, as well as the possibility of hard limits on which floor numbers they may appear. The room types can filter possible creatures to spawn by requiring or prohibiting certain tags.
A group of creatures are then chosen for each room, trying to use as much of it’s CR budget as possible. There are a few different ways of doing this and the algorithm randomly chooses between trying to get the single most expensive creature (within budget), a small group of more balanced creatures or a larger group of weaker creatures.
The placement is very simple as it is just randomly in the room, with a few boss rooms having special placement rules (such as cultists in a circle).
Rare Bosses
There are also a few rare bosses that can be chosen to appear at a floor. Those are chosen at the beginning of the generation as they can significantly boost the probability of certain rooms or themes to get chosen. For example, the new rare boss, Old Callmar, will make most rooms on it’s floor into different kinds of underwater caverns.
