Coding the basic dungeon generator

To create the dungeon we first need to figure out what are the parameters for driving the procedural content.

For this simple algorithm we’ll use:

  • level/map size in tiles because we’ll be using the TileMap node
  • minimum and maximum room sizes for both vertical and horizontal directions
  • the maximum number of possible rooms

Since we’ll create rectangular rooms it sounds like a good use of the Rect2 class. Let’s go over the algorithm conceptually:

  1. Based on the room size parameters (#1).
  2. Create a rectangular room and place it randomly in the allowed level size (#2).
  3. Check for intersections with previous rooms if any (#4-6).
    1. If intersection is confirmed skip the current room.
    2. Else, if the intersection fails then save the current room into the data structure.
  4. If we have more than one room saved create a corridor between the current room and the previous room (#5-9).
  5. Iterate from 1. until the iterator is equal to the maximum allowed number of rooms.

Given that we skip rooms if they intersect with previously placed rooms, we don’t have to generate a random number of rooms to iterate over. Randomly placing them will ensure that the total number of rooms is also random.

Basic dungeon generator algorithm

Preparing the scene

First, create a new Godot project if you haven’t done so. From our Procedural Generation demos project copy the Common folder over to your local project. It contains a tile set resource that we’ll be using through this project. Remember we have to preserve the file structure so copy the entire directory, not olny the files inside of it.

Before moving on you might want to change the default background color to something lighter because our tile set has a dark purple color. You can do so by going to Project > Project Settings… > Rendering > Environment and changing the Default Clear Color option. We’re using the bright cream color from the Pear36 palette: #ffffeb.

Now let’s prepare the scene file. Choose 2D Scene from the Scene docker. Save it as BasicDungeon.tscn.

Prepare new scene

Rename the root node to BasicDungeon node and add the following new nodes:

  • TileMap: rename to Level and follow the instructions in the image below to assign tileset-prototype.tres to the Tile Set property in the Inspector. Also note that we changed Size to Vector2(60, 60).
  • Camera2D: turn on Current in the Inspector docker as it isn’t by default.

That’s all we need to get this rolling. You should have the following now:

Prepared scene

The script

Attach a new script to the BasicDungeon node and define the following variables:

extends Node2D


export var level_size := Vector2(100, 80)
export var rooms_size := Vector2(10, 14)
export var rooms_max := 15

onready var level: TileMap = $Level
onready var camera: Camera2D = $Camera2D

We create level_size, rooms_size and rooms_max as export variables so that we can get easy access to them in the Inspector.

We’ll use rooms_size a bit differently. It’s not the X and Y size of a room, but instead we’ll use rooms_size.x to mean the minimum value of tiles a room can take on either of the axes. And we use rooms_size.y to mean the maximum instead. We’re using a 2D vector to store information about an interval, [rooms_size.x, rooms_size.y] in this case.

Create the _ready() function with the following content:

func _ready() -> void:
    _setup_camera()
    _generate()

We use _setup_camera() to position the camera in the middle of the level, based on level_size. We also calculate a suitable zoom factor:

func _setup_camera() -> void:
    camera.position = level.map_to_world(level_size / 2)
    var z := max(level_size.x, level_size.y) / 8
    camera.zoom = Vector2(z, z)

We place the camera at a position using TileMap.map_to_world() which converts a 2D vector from tile map coordinates to pixel coordinates.

We then calculate the camera zoom factor by dividing the maximum between level_size.x and level_size.y with an arbitrary value that seems to work in this case. Note that Camera2D.zoom > 1 zooms out by that factor since Godot enlarges the camera boundaries by the zoom factor. See the picture below for a visual representation.

Camera zoom explanation

Implementing the algorithm

We can now talk about the algorithm. The first step in deciding what to do is to pick a data structure to hold our information.

Since this is a simple dungeon generator which places rooms and corridors using a TileMap node, we can store Vector2 points into a dictionary as keys representing the location in TileMap coordinates where we’d like to dig. The values aren’t important so we’ll just use null.

We use a dictionary as opposed to an array because operations like inserting elements is much faster and it also prevents adding the same element multiple times.

We’ll go over the algorithm, step by step, starting with the top-level functions and moving to the implementations of the low-level building blocks.

We first clear the TileMap level data with TileMap.clear(). Next we go over the 2D vector data points in a loop, and for each, we set the given cell to use the tile with index 0, which is the only available tile type at our disposal for this project.

func _generate() -> void:
    level.clear()
    for vector in _generate_data():
        level.set_cellv(vector, 0)

_generate_data() is the bulk of the algorithm. This is where we generate the data we’re going to use in the Level node.

func _generate_data() -> Array:
    var rng := RandomNumberGenerator.new()
    rng.randomize()

    var data := {}
    var rooms := []
    for r in range(rooms_max):
        var room := _get_random_room(rng)
        if _intersects(rooms, room):
            continue

        _add_room(data, rooms, room)
        if rooms.size() > 1:
            var room_previous: Rect2 = rooms[-2]
            _add_connection(rng, data, room_previous, room)
    return data.keys()

We divide this function into smaller manageable chunks with descriptive names. This way we understand what the function does without going over the low-level implementation details. This is always a good approach to coding as it allows us keep track of our code even after a long pause.

We first define and initialize necessary variables for our algorithm:

var rng := RandomNumberGenerator.new()
rng.randomize()

var data := {}
var rooms := []

To produce randomly placed rooms we need a random number generator, which we’ll store in the rng variable. We need to use RandomNumberGenerator.randomize() method so that Godot produces different sequences of pseudo-random numbers each time we call the _generate_data() function. Otherwise we’d get the same output every time.

Note that generating pseudo-random numbers isn’t bad because it gives us control over the generated data so we can debug or perhaps recall a specific level. We could for example save the seed value for a specific level and re-generate it when needed instead of saving the level data directly.

We store our TileMap information in the data dictionary.

rooms is an array for keeping track of all the random rooms we generate. We use this data to check for intersections as this algorithm places new rooms only if they don’t intersect with previously placed rooms.

Moving on, we have the main loop body, iterating up to rooms_max.

for r in range(rooms_max):
    var room := _get_random_room(rng)
    if _intersects(rooms, room):
        continue

We first generate a random room with _get_random_room() and if we detect an intersection we skip the rest of the code using the continue statement. What this means is that we won’t place a room on each iteration step so we’ll end up with a random number of rooms up to rooms_max most times.

We complete the loop with:

_add_room(data, rooms, room)
if rooms.size() > 1:
    var room_previous: Rect2 = rooms[-2]
    _add_connection(rng, data, room_previous, room)

Here we first add the room into the data dictionary as well as the rooms arrays. They’re stored in different ways so we need both of these data structures.

We finish up the loop by checking if we have more than one room stored in the rooms array. If so then we add a connection between the currently generated room and the previous room. The previous room is the second to last and we get it using a negative index: rooms[-2]. We’re getting the second to last room because _add_room already adds it in the rooms array. This means that rooms[-1] (the last element in the array) and room are the same object at this point.

This piece of code also reveals that we’re using Rect2 for our underlying room data type. We strive to use as much of the built-in functionality as we can get. Rect2 is beneficial here because it gives us the Rect2.intersects() method which we use in _intersects() function to figure out if rooms overlap.

Now we’re ready to return the data. Since we’re only interested in the keys of the dictionary, we return them as an array rather than the dictionary itself:

return data.keys()

Let’s move on to the implementation of the low-level functions now.

We construct a random Rect2 with _get_random_room():

func _get_random_room(rng: RandomNumberGenerator) -> Rect2:
    var width := rng.randi_range(rooms_size.x, rooms_size.y)
    var height := rng.randi_range(rooms_size.x, rooms_size.y)
    var x := rng.randi_range(0, level_size.x - width - 1)
    var y := rng.randi_range(0, level_size.y - height - 1)
    return Rect2(x, y, width, height)

We’re using the RandomNumberGenerator.randi_range() function to generate a random Rect2 in both position and size.

Note that RandomNumberGenerator.randi_range() is an inclusive function, that is, rng.randi_range(0, 10) returns a number between 0 and 10 inclusive.

In _add_room() we use room to populate both data and rooms variables. We save Vector2 positions in data that comprise the room interior, based on Rect2.position and Rect2.end vectors. Inside the rooms array we store the Rect2 room itself so we can later use it to test if it intersects other rooms.

func _add_room(data: Dictionary, rooms: Array, room: Rect2) -> void:
    rooms.push_back(room)
    for x in range(room.position.x, room.end.x):
        for y in range(room.position.y, room.end.y):
            data[Vector2(x, y)] = null

With _add_connection() we add corridors between two given rooms, starting and ending in the middle of the rooms.

func _add_connection(rng: RandomNumberGenerator, data: Dictionary, room1: Rect2, room2: Rect2) -> void:
    var room_center1 := (room1.position + room1.end) / 2
    var room_center2 := (room2.position + room2.end) / 2
    if rng.randi_range(0, 1) == 0:
        _add_corridor(data, room_center1.x, room_center2.x, room_center1.y, Vector2.AXIS_X)
        _add_corridor(data, room_center1.y, room_center2.y, room_center2.x, Vector2.AXIS_Y)
    else:
        _add_corridor(data, room_center1.y, room_center2.y, room_center1.x, Vector2.AXIS_Y)
        _add_corridor(data, room_center1.x, room_center2.x, room_center2.y, Vector2.AXIS_X)

For this we’ll use _add_corridor() which adds data about corridors horizontally or vertically depending on the last parameter sent to it.

First we calculate the given room1 and room2 center coordinates and with the help of RandomNumberGenerator, we’ll make corridors starting horizontally or vertically with a 50% chance.

To understand how _add_connection() works we’ll look at _add_corridor():

func _add_corridor(data: Dictionary, start: int, end: int, constant: int, axis: int) -> void:
    for t in range(min(start, end), max(start, end) + 1):
        var point := Vector2.ZERO
        match axis:
            Vector2.AXIS_X: point = Vector2(t, constant)
            Vector2.AXIS_Y: point = Vector2(constant, t)
        data[point] = null

This function takes in data as the first parameter, to add information about the corridor as needed. Then we have the corridor start and end coordinates. Depending on axis, we take the variable coordinate to be either on X or Y axis and constant will be on the opposite axis: either Y or X respectively.

We finally add these points to the data dictionary.

We have one last function to cover, the _intersects() function:

func _intersects(rooms: Array, room: Rect2) -> bool:
    var out := false
    for room_other in rooms:
        if room.intersects(room_other):
            out = true
            break
    return out

We use it inside the main loop, in the _generate_data() function to test if the current room we want to place intersects any other room we have already placed. This is a simple matter for us to check, since we rely on the Rect2.intersects() method to do it for us. All we do is iterate over the previously placed rooms and check if they intersect with the current room in which case we assign true to out and break from the loop otherwise we continue with the loop. If there are no intersections detected then out will remain false.

With this last function, we’re done and if you run the project now you’ll get results like in the following image:

Basic dungeon generator sample

References

For reference here is the entire code from BasicDungeon.gd:

extends Node2D


export var level_size := Vector2(100, 80)
export var rooms_size := Vector2(10, 14)
export var rooms_max := 15

onready var level: TileMap = $Level
onready var camera: Camera2D = $Camera2D


func _ready() -> void:
    _setup_camera()
    _generate()


func _setup_camera() -> void:
    camera.position = level.map_to_world(level_size / 2)
    var z := max(level_size.x, level_size.y) / 8
    camera.zoom = Vector2(z, z)


func _generate() -> void:
    level.clear()
    for vector in _generate_data():
        level.set_cellv(vector, 0)


func _generate_data() -> Array:
    var rng := RandomNumberGenerator.new()
    rng.randomize()

    var data := {}
    var rooms := []
    for r in range(rooms_max):
        var room := _get_random_room(rng)
        if _intersects(rooms, room):
            continue

        _add_room(data, rooms, room)
        if rooms.size() > 1:
            var room_previous: Rect2 = rooms[-2]
            _add_connection(rng, data, room_previous, room)
    return data.keys()


func _get_random_room(rng: RandomNumberGenerator) -> Rect2:
    var width := rng.randi_range(rooms_size.x, rooms_size.y)
    var height := rng.randi_range(rooms_size.x, rooms_size.y)
    var x := rng.randi_range(0, level_size.x - width - 1)
    var y := rng.randi_range(0, level_size.y - height - 1)
    return Rect2(x, y, width, height)


func _add_room(data: Dictionary, rooms: Array, room: Rect2) -> void:
    rooms.push_back(room)
    for x in range(room.position.x, room.end.x):
        for y in range(room.position.y, room.end.y):
            data[Vector2(x, y)] = null


func _add_connection(rng: RandomNumberGenerator, data: Dictionary, room1: Rect2, room2: Rect2) -> void:
    var room_center1 := (room1.position + room1.end) / 2
    var room_center2 := (room2.position + room2.end) / 2
    if rng.randi_range(0, 1) == 0:
        _add_corridor(data, room_center1.x, room_center2.x, room_center1.y, Vector2.AXIS_X)
        _add_corridor(data, room_center1.y, room_center2.y, room_center2.x, Vector2.AXIS_Y)
    else:
        _add_corridor(data, room_center1.y, room_center2.y, room_center1.x, Vector2.AXIS_Y)
        _add_corridor(data, room_center1.x, room_center2.x, room_center2.y, Vector2.AXIS_X)


func _add_corridor(data: Dictionary, start: int, end: int, constant: int, axis: int) -> void:
    for t in range(min(start, end), max(start, end) + 1):
        var point := Vector2.ZERO
        match axis:
            Vector2.AXIS_X: point = Vector2(t, constant)
            Vector2.AXIS_Y: point = Vector2(constant, t)
        data[point] = null


func _intersects(rooms: Array, room: Rect2) -> bool:
    var out := false
    for room_other in rooms:
        if room.intersects(room_other):
            out = true
            break
    return out