Procedurally Generating Dungeon Geomorph Tiles in Godot

---

---

There are many ways to create procedural dungeon layouts. Binary Space Partitioning (BSP), Cellular automata, Random Room placement to name a few.

I have been experimenting with the idea of procedurally generating dungeon geomorphs which can then be placed together like puzzle pieces to form a dungeon. This idea is often used in physical table top dungeon games or RPGs.

A full set of corners, intersections and dead ends need to be created to form a full geomorph tile set. A total of 16 tiles. While these can be created as 2 dimensional arrays it quickly becomes tedious when creating very large tiles.

My strategy is to first procedurally create tile border templates. These represent areas where a wall must be placed. I also create a path template, this one represents where a wall must not be placed.

These two templates ensure that there will be no passages leading into oblivion, or walls that block the path through the dungeon.

Once these are created, the remaining blocks can be procedurally filled without causing unusable tiles.

Creating the wall template

I am using Godot and GdScript but the idea can be used in any language or game engine.

A custom Godot resource is used to represent each tile. The properties width and height are exported to the editor.

@export var width := 6
@export var height := 6
@export var bitmask := 15

A property called bitmask is also exported. I wont go into detail regarding bitmasks in this post (maybe later), but at a high level each number from 0 through to 15 represents one of the tiles in the geomorph set. If the bitmask is set to 1 the resulting binary is 0001 that means there is no wall at the top. If bitmask is set to 2 with a binary of 0010 that means there is no wall to the left. Bitmask 3 which in binary is 0011, means that there is no wall to the top or to the left.

If you are interested in reading more about bitmasks and tiles I recommend this post

Now that the size of the tile and its bitmask are set, we can start to generate the border. The tile and its border are represented as a 2 dimensional array of 1 and 0. 1 means wall 0 means no wall

To start create a function that generates a border on all sides:

func create_mask_0_array() -> Array[Array]:
    var matrix : Array[Array] = []
    for y in range(height):
        var row := []
        for x in range(width):
            var value = 0
            if y == 0 or y == height-1:
                value = 1 
            if x == 0 or x == width-1:
                value = 1
            row.append(value)
        matrix.append(row)
    return matrix

The result should be as follows:

[1, 1, 1, 1, 1, 1]
[1, 0, 0, 0, 0, 1]
[1, 0, 0, 0, 0, 1]
[1, 0, 0, 0, 0, 1]
[1, 0, 0, 0, 0, 1]
[1, 1, 1, 1, 1, 1]

Now loop through this two dimensional array, and depending on what bitmask is set, clear the appropriate walls:

func create_section_border() -> Array[Array]:
    var matrix: Array[Array] = create_mask_0_array()

    for y in range(height):
        for x in range(width):
            var value := 1
            # -Z boundary (NORTH) the 1 bit is set (0001)
            if y == 0 and x > 0 and x < width-1 and bitmask & 1:
                matrix[y][x] = 0
            # +Z boundary (SOUTH) the 8 bit is set (1000)
            if y == height-1 and x > 0 and x < width-1 and bitmask & 8:
                matrix[y][x] = 0
            # -X boundary (WEST) the 2 bit is set (0010)
            if x == 0 and y > 0 and y < height-1 and bitmask & 2:
                matrix[y][x] = 0
            # +X boundary (EAST) the 4 bit is set (0100)
            if x == width-1 and y > 0 and y < height-1 and bitmask & 4:
                matrix[y][x] = 0

    return matrix

The result is as follows when the bitmask is set to 5

[1, 0, 0, 0, 0, 1]
[1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[1, 1, 1, 1, 1, 1]

And we have a border template.

Creating the path template

Similar to how the border template is created, a path template can be created. This time the value is set to 1 if is in the centre based on the bitmask. This one is a bit more complicated as the width and height of the tile needs to be checked. If it is an odd number only a single width path is cleared. But if the width or height is even a double width path needs to be created in order to keep it centre aligned.

func create_path_mask() -> Array[Array]:
    #generate a matrix with all values set to 0
    var matrix : Array[Array] = []
    for y in range(height):
        var row := []
        for x in range(width):
            row.append(val)
        matrix.append(row)

    for y in range(height):
        for x in range(width):
            if width % 2 == 0: # evens add double center
                if bitmask & 1 and x == width / 2 and y <= height / 2:
                    matrix[y][x-1] = 1
                    matrix[y][x] = 1
                if bitmask & 2 and y == height / 2 and x <= width / 2:
                    matrix[y-1][x] = 1
                    matrix[y][x] = 1
                if bitmask & 4 and y == height / 2 and x >= width / 2 and x < width:
                    matrix[y-1][x] = 1
                    matrix[y][x] = 1
                if bitmask & 8 and x == width / 2 and y >= height / 2 and y < height:
                    matrix[y][x-1] = 1
                    matrix[y][x] = 1
            else: # odd add single center
                if bitmask & 1 and x == ceil(width / 2) and y <= ceil(height / 2):
                    matrix[y][x] = 1
                if bitmask & 2 and y == ceil(height / 2) and x <= ceil(width / 2):
                    matrix[y][x] = 1
                if bitmask & 4 and y == ceil(height / 2) and x >= ceil(width / 2) and x < width:
                    matrix[y][x] = 1
                if bitmask & 8 and x == ceil(width / 2) and y >= ceil(height / 2) and y < height:
                    matrix[y][x] = 1
    return  matrix

If the bitmask is 5, the result will be the following, note how because there is a width and height of 6. The path has a width of 2:

[0, 0, 1, 1, 0, 0]
[0, 0, 1, 1, 0, 0]
[0, 0, 1, 1, 1, 1]
[0, 0, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]

Randomly filling the geomorph tile

Now that the walls and non blocking areas are defined, the fun bit begins! Procedurally filling in the rest of the geomorph tile with an algorithm (or multiple) of choice. Below is a simple example using random placement.

func random_build() -> Array[Array]:
      # create the walls and mask of non block-able areas
    var build_mask = create_path_mask()
    var base = create_section_border()

    var placed = 0
    var rng = RandomNumberGenerator.new()

    # only fill in a maximum quarter of the geomorph
    var max_placements = width * height / 4

    # Just in case we create an infinite loop!
    var emergency_stop = max_placements * 5
    var current_iter = 0
    while placed < max_placements:
        if current_iter >= emergency_stop:
            break
        current_iter += 1

        # find a random place to put a wall
        var y = rng.randi_range(0, base.size()-1)
        var x = rng.randi_range(0, base[0].size()-1)

        # this space must be a wall!
        if base[y][x] == 1: continue

        # this space must be a path
        if build_mask[y][x] == 1: 
            base[y][x] = 0
            continue

        base[y][x] = 1
        placed += 1
    return  base

And a procedural geomorph tile is born!

[1, 1, 0, 0, 1, 1]
[1, 1, 0, 0, 1, 0]
[1, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[1, 1, 1, 0, 1, 0]
[1, 1, 1, 1, 1, 1]

Here is an example putting multiple geomorphs together to create a world map

---