Cell Constraint Dungeon Generation
The way Diablo 2 did it for almost all of the dungeons in the game
Why?
There are a bunch of other generator types out there: wave function collapse, cellular automata, room & hallway - but all of those make it hard to author a particular look. With a room-based cell structure each room is a hand-crafted scene, with optional random variety internal to the cell.
The primary advantage to the following approach is that the cells can be rotated and attached to each other, and they’ll always fit together - no need to mess with door alignment. The glaring disadvantage is that it’s difficult to design the spaces to make it less obvious that it’s a large grid; though not impossible.
Goals
Let’s take a step back and examine some goals for this dungeon generator before we look at any implementation details:
- The generator should allow loops:
- The generator should not force loops:
- The generator should place known important special rooms:
- The generator should have a minimum size:
- The generator should have a hard-maximum size:
<Imagine a stupendously large dungeon, with an X> - The generator should aim for a target size:
- The generator should not leave empty connections:
Examples
Catacombs Level 2
Maggot Lair Level 1
By adjusting the size of the cells, and playing around with the flow of the player’s path within each cell, you can make vastly different and interesting dungeons using the same basic layout generation algorithm.
So let’s get into the higher level concepts of the solution one at a time, as we dive deeper into the actual generation algorithm.
Rooms
We keep our layout generator separate from our actual rendering system, so that we can use the same layout in multiple different places. We might render a 3D dungeon with scenes, we might render a minimap, or we might render debug visuals. As such, there are only five possible rooms in this layout system:
- North Entrance, Leaf rooms
- North and South Entrances, Straight rooms
- North and East Entrances, Turn rooms
- North, East, and South Entrances, T-Junction rooms
- NEWS entrances, Cross junction rooms
It’s important to note that an entrance doesn’t necessarily mean a door. If you take a closer look at the catacombs example above, an entrance is actually two parallel hallways that end at the edge of the cell. The actual doors are doodads on the interior of the cell.
We’ll also keep track of special rooms for later, like start rooms, treasure rooms, end rooms, waypoint rooms, quest rooms, whatever - but fundamentally they’re just named rooms, and they still follow the same core structure.
We can, however, choose if special rooms are allowed to be rotated. In Diablo 2, they cannot be. The end room for the tower cellar, for example, is always facing 90 degrees to the left of the start room’s orientation, allowing players to always follow a consistent direction when navigating the dungeon, despite it being largely randomly generated.
Cell Constraints
To make sure we always have valid dungeon layouts, the current layout’s empty cells need metadata about neighboring cells to inform the kind of room that can be placed on that cell. Any time we place a room, we need to update that room’s neighboring empty cells with new metadata. In particular, we need to know which directions are considered blocked, and which directions must have an entrance:
You don’t have to store the metadata on these empty cells as an object, but doing so helps a lot with figuring out which cells still need attention later in the algorithm.
Later, when placing a room on a cell that has constraints (a cell will always have at least one constraint except for the seed room) we can rotate our candidate room until it satisfies all of the constraints:
Or, a candidate room might not satisfy all of the constraints even if rotated in all directions. For example, a straight room with two entrances would never satisfy the constraints on the above cell, but we can’t know until we try it and reject the candidacy.
Testing Candidacy
Before we place a room on an empty cell, we need to gather potential candidates for the placement, shuffle them, and then pick one at a time until it works.
How we choose which rooms to add to the candidacy list depends on where we are in the dungeon generation process.
- If the dungeon is still smaller than what we need, then we check the required entrance count, and choose rooms with more entrances than what the cell requires. This means we’ll grow the dungeon by adding more rooms to it.
- If the dungeon has crossed the target size, we instead want to grab rooms that have exactly the number of entrances required by the cell. This means we’re effectively just capping off the open entrances and wrapping it up.
- We may only drop a small number of rooms during the finish-up phase, or we could have quite a few rooms left to place to finish up. There’s a lot of variance during this phase.
- During this wrap up phase, we also add the special rooms into the mix, so that they more likely show up at the edges of the dungeon
Once we have that list of candidate rooms, we can perform the following:
- For each candidate room
- For each orientation
- If it works, place the room
- If no orientation works, discard the room and get a new one from the list
- For each orientation
- If there are no rooms left, put this particular cell back into the back of the queue and we’ll get to it later. This can happen for large dungeons if the generator is still in growth mode, but the cell requires an exact placement.
Placing Rooms
Inserting a room into our layout requires us to record which room candidate was chosen, its special details (if any), and the orientation it was placed with.
When we place a room, we need to also mark neighboring empty cells with the additional metadata about blocked and required entrances. This is also a good place to make sure that any empty cells with required rooms are added to a queue for us to visit later.
Dungeon Validation
Once the required room queue is exhausted, we have a closed up dungeon layout - and we just need to perform a few last-minute checks against it to be sure it will work for our game world.
- We should ensure that all required special rooms that were in the list have been added to the layout.
- We should ensure that the dungeon is not too small.
- More rules for your game here - maybe that there aren’t too many straights in a row?
If the validation fails here, just toss out the whole dungeon and try again. Set a sensible bail-out limit, and keep track of failure counts. If your dungeons are failing too often, adjust the build parameters to ensure you get a higher success rate.
Parameterization
There’s actually quite a bit of opportunity in this generator for parameterization.
Depth first or Breadth first
When placing rooms, adding new cells to the front or back of the queue has a huge impact on the shape of the resulting dungeon.
Adding the cells-to-visit at the back of the list creates clustered, fat dungeon layouts:
Putting them at the front of the list creates longer dungeons with lots of side rooms well suited for caves and jails:
Both is good, too
By adding a weighted random choice between the two, you can sort of curl the dungeons up onto themselves a bit and get a good half-way:
Room orientations
The starting orientations and directions chosen to rotate the cells when testing for placement can also have a significant impact on the shape of the resulting dungeon. By always starting north and rotating clockwise, you end up with dungeons that curl to the right. Reversing that you get dungeons that curl to the left. Adding parameters to weigh the choice between left and right rotations, as well as starting room orientations can give you more flexibility in overall dungeon shape. This one is harder to visualize.
Split weights
When sampling the candidate room list, you can add weights for which rooms are chosen during the growth phase. You can weigh more on the side of fewer splits, or on the side of more splits to create more narrow passageways, or wider self-looping systems. You could even ban the usage of cross rooms except when the constraints require it.
There’s probably plenty of ways to make this do more varied layouts than I’m thinking of here, definitely experiment with it.
Rendering your dungeon
Once you have a layout from this system, you can really do anything you want when it comes to rendering it. You can position rooms in 3D space with relative ease, you can render it to a 2D map like I did above by placing sprites with rotations for each room.
You can add a lot of variety by creating multiple different room layouts for each room template type and choosing randomly, or semi-randomly, when assembling the final result from the layout data:
Important Gotcha!
One very important thing to note though is the rotation directions! In Godot, 2D images rotate clockwise with positive rotations. In 3D, if you use X and Z as your ground plane, positive Y rotations result in counter-clockwise rotations. You have to pick one in your layout generator and then compensate when reading the data back, or your rooms won’t connect properly!
- TestSubject06
The Code
@tool
extends Node
class_name DungeonLayoutGenerator
signal generation_complete(grid: Dictionary[Vector2i, RefCounted], extents: Rect2i);
enum Direction { NORTH, EAST, SOUTH, WEST };
func get_opposite_direction(direction: Direction) -> Direction:
match direction:
Direction.NORTH: return Direction.SOUTH;
Direction.SOUTH: return Direction.NORTH;
Direction.EAST: return Direction.WEST;
Direction.WEST: return Direction.EAST;
return direction;
# TODO: This could probably be done a lot better.
func rotate_direction(direction: Direction, rotation_degrees: int) -> Direction:
# rotation_degrees should be 0, 90, 180, or 270.
# We rotate clockwise in 90° steps.
var rotations: int = rotation_degrees / 90;
var new_direction: Direction = direction;
for i in range(rotations):
match new_direction:
Direction.NORTH: new_direction = Direction.WEST;
Direction.EAST: new_direction = Direction.NORTH;
Direction.SOUTH: new_direction = Direction.EAST;
Direction.WEST: new_direction = Direction.SOUTH;
return new_direction;
func direction_to_vector(direction: Direction) -> Vector2i:
match direction:
Direction.NORTH: return Vector2i(0, -1);
Direction.EAST: return Vector2i(1, 0);
Direction.SOUTH: return Vector2i(0, 1);
Direction.WEST: return Vector2i(-1, 0);
return Vector2i.ZERO;
# A simple room "template" that has a name and a set of door directions in its base orientation.
class RoomTemplate:
var name: String = "";
var doors: Array[Direction] = []; # each door is one of the Direction enum values
func _init(_name: String, _doors: Array[Direction]) -> void:
name = _name;
doors = _doors;
# A placed room stores which template was chosen and the rotation (in degrees) applied.
# These will be returned to the generate dungeon caller.
class PlacedRoom:
var template: RoomTemplate;
var rotation: int = 0;
func _init(_template: RoomTemplate, _rotation: int) -> void:
template = _template;
rotation = _rotation;
# Constraints for a grid cell. 'required' is a list of door directions that must be present
# in the room placed here (because an adjacent room is connecting), while 'blocked' lists directions that must not be present.
class CellConstraint:
var required: Array[Direction] = [];
var blocked: Array[Direction] = [];
func _init() -> void:
required = [];
blocked = [];
# Dictionary mapping grid cell positions (Vector2i) to a placed room.
# This allows for sparse mapping of dungeon rooms - there are no empty rooms in this structure
# as the dictionary only contains placed rooms. Consumers can get the keys to get the positions
# of the rooms in layout-space.
# e.g. grid[Vector2i(2,1)] = PlacedRoom
var grid: Dictionary[Vector2i, PlacedRoom] = {};
# Dictionary mapping grid cell positions (Vector2) to constraints. Again, sparse structure mapping
# a position in layout-space to a set of cell constraints. While we're laying out, we don't know the height and
# width of the dungeon, and don't want to constrain to imaginary edges.
# e.g. constraints[Vector2(2,2)] = CellConstraint
var constraints: Dictionary[Vector2i, CellConstraint] = {};
# Since we keep the layout separate from any rendering, we only have 5 possible room templates.
var room_templates: Array[RoomTemplate] = [
RoomTemplate.new("1Door", [Direction.NORTH]),
RoomTemplate.new("2Door_NS", [Direction.NORTH, Direction.SOUTH]),
RoomTemplate.new("2Door_NE", [Direction.NORTH, Direction.EAST]),
RoomTemplate.new("3Door_NES", [Direction.NORTH, Direction.EAST, Direction.SOUTH]),
RoomTemplate.new("4Door", [Direction.NORTH, Direction.EAST, Direction.SOUTH, Direction.WEST])
];
# We'll visit these one a a time to place new rooms.
var necessary_cells: Array[Vector2i] = [];
# Parameters
var soft_max_rooms := 4;
var hard_max_rooms := 15;
var hard_min_rooms := 6;
# Tracking
var num_rooms := 0;
func generate_layout(start_type: String, soft_max: int, hard_max: int, hard_min: int):
var success := false;
var attempts := 0;
while !success && attempts < 20:
print("Generating level. Attempt: ", attempts);
necessary_cells = [];
grid = {};
constraints = {};
soft_max_rooms = soft_max;
hard_max_rooms = hard_max;
hard_min_rooms = hard_min;
num_rooms = 0;
# Start by placing an initial room at (0, 0).
var start_room: RoomTemplate;
match(start_type):
"Start_N":
start_room = RoomTemplate.new("Start_N", [Direction.NORTH]);
"Start_NE":
start_room = RoomTemplate.new("Start_NE", [Direction.NORTH, Direction.EAST]);
"Start_NS":
start_room = RoomTemplate.new("Start_NS", [Direction.NORTH, Direction.SOUTH]);
"Start_NES":
start_room = RoomTemplate.new("Start_NES", [Direction.NORTH, Direction.EAST, Direction.SOUTH]);
"Start_NESW":
start_room = RoomTemplate.new("Start_NESW", [Direction.NORTH, Direction.EAST, Direction.SOUTH, Direction.WEST]);
place_room(Vector2i(0, 0), start_room, 0);
update_constraints_for_room(Vector2i(0, 0));
success = generate_dungeon();
attempts += 1;
# For debugging, print out the final grid.
print("Generated a layout with: ", num_rooms, " rooms.");
# Very helpful to know the rectangular extents of the final dungeon.
var extents := Rect2i();
var min: = Vector2i(0,0);
var max: = Vector2i(0,0);
for key in (grid.keys() as Array[Vector2i]):
var room: PlacedRoom = grid[key];
if(key.x < min.x):
min.x = key.x;
if(key.y < min.y):
min.y = key.y;
if(key.x > max.x):
max.x = key.x;
if(key.y > max.y):
max.y = key.y;
print("Room at ", key, ": ", room.template.name, " rotated: ", room.rotation);
extents = Rect2i(min, max - min);
# Include the edges
extents.size.x += 1;
extents.size.y += 1;
print("Emitting complete signal...");
generation_complete.emit(grid, extents);
func _ready():
randomize();
func generate_dungeon() -> bool:
# While there are cells with constraints that are not filled, try to fill them.
while necessary_cells.size() > 0:
var cell: Vector2i = necessary_cells.pop_front() as Vector2i;
# Skip cells that already have a room. This should never happen.
if grid.has(cell):
continue;
var cell_constraint: CellConstraint = constraints[cell];
# Choose a candidate room template based on a random roll.
var candidate_templates: Array[RoomTemplate] = [];
for rt in room_templates:
# Grow mode, pick rooms bigger than the required number of doors
if(num_rooms < soft_max_rooms && (rt.doors.size() > cell_constraint.required.size() || rt.doors.size() == 4)):
candidate_templates.append(rt)
# Finish up mode, pick rooms that perfectly satisfy
# TODO: Consider special rooms here, like stairs, treasure rooms, boss chambers
elif num_rooms >= soft_max_rooms && rt.doors.size() == cell_constraint.required.size():
candidate_templates.append(rt)
if candidate_templates.size() == 0:
# No candidate can satisfy the constraint; cell will remain empty.
continue;
# TODO: Add parameterized weight for more or less doors, or certain room types here.
var chosen_template := candidate_templates[randi() % candidate_templates.size()];
while(candidate_templates.size() > 0):
# Try to place the room with one of the 90° rotations.
if try_place_room(cell, chosen_template, cell_constraint):
# If placement succeeds, update neighbor cell constraints from this new room.
update_constraints_for_room(cell);
break;
else:
candidate_templates.erase(chosen_template);
if(candidate_templates.size() == 0):
print("ALL OPTIONS EXHAUSTED AT: ", cell);
print("WILL TRY AGAIN LATER...");
necessary_cells.push_back(cell);
else:
chosen_template = candidate_templates[randi() % candidate_templates.size()];
# Dungeon generation failed - too big. Throw it out and start over.
if num_rooms > hard_max_rooms:
return false;
# TODO: If there are any important rooms left unplaced - fail.
# Dungeon generation failed - too small. Throw it out and start over.
if num_rooms < hard_min_rooms:
return false;
# Everything finished up - dungeon generation success!
return true;
func try_place_room(cell: Vector2i, room_template: RoomTemplate, cell_constraint: CellConstraint) -> bool:
# Try each rotation: 0, 90, 180, and 270 degrees.
var rotations: Array[int] = [0, 90, 180, 270];
if( randi() % 2 == 0 ):
rotations.reverse();
for rotation in rotations:
var rotated_doors: Array[Direction] = [];
for door in room_template.doors:
rotated_doors.append( rotate_direction(door, rotation) )
# Check that every required door is present in the rotated configuration.
var valid := true;
for req in cell_constraint.required:
if(!rotated_doors.has(req)):
valid = false;
break;
# Also, ensure that none of the blocked directions are present.
for block in cell_constraint.blocked:
if(rotated_doors.has(block)):
valid = false;
break;
if valid:
place_room(cell, room_template, rotation);
return true;
return false;
func place_room(cell: Vector2i, room_template: RoomTemplate, rotation: int) -> void:
# Place the room into the grid.
grid[cell] = PlacedRoom.new(room_template, rotation);
# Once a room is placed, remove any constraints for that cell.
constraints.erase(cell);
num_rooms += 1;
func update_constraints_for_room(cell: Vector2i) -> void:
# For the room at 'cell', update the constraints on its four neighboring cells.
if !(grid.has(cell)):
return;
var placed: PlacedRoom = grid[cell];
# Determine the rotated door configuration.
var rotated_doors: Array[Direction] = [];
for door in placed.template.doors:
rotated_doors.append( rotate_direction(door, placed.rotation) );
# For each of the four directions:
var directions: Array[Direction] = [Direction.NORTH, Direction.EAST, Direction.SOUTH, Direction.WEST];
for direction in directions:
var neighbor: Vector2i = cell + direction_to_vector(direction);
var opp: Direction = get_opposite_direction(direction);
# Get or create a CellConstraint for the neighbor.
var cell_constraint: CellConstraint;
if constraints.has(neighbor):
cell_constraint = constraints[neighbor];
else:
cell_constraint = CellConstraint.new();
constraints[neighbor] = cell_constraint;
# If this room has a door in the direction, then the neighbor MUST eventually have a door facing 'opp'.
if(rotated_doors.has(direction)):
if(!cell_constraint.required.has(opp)):
cell_constraint.required.append(opp);
if(!necessary_cells.has(neighbor)):
if( randi() % 4 <= 2 ):
necessary_cells.push_front(neighbor);
else:
necessary_cells.push_back(neighbor);
else:
# If there is no door here, we add a "blocked" constraint so that a later room cannot have a door on that side.
if(!cell_constraint.blocked.has(opp)):
cell_constraint.blocked.append(opp);