Back to the index.

Dungeon building blocks

Having a painstakingly handmade room with artfully placed pillars is all well and good, but roguelikes are about procedural generation! How about adding some randomness to the mix?

We’re going to carve rooms and tunnels in underground rock. In this section we’ll build some helper functions which we’ll then use to generate the whole dungeon.

First, a struct that will represent a rectangular room:

/// A rectangle on the map, used to characterise a room.
#[derive(Clone, Copy, Debug)]
struct Rect {
    x1: i32,
    y1: i32,
    x2: i32,
    y2: i32,
}

impl Rect {
    pub fn new(x: i32, y: i32, w: i32, h: i32) -> Self {
        Rect {
            x1: x,
            y1: y,
            x2: x + w,
            y2: y + h,
        }
    }
}

The rectangle stores the coordinates for the top-left and bottom-right points.

This function will take a rect and place it in the map, making sure all the tiles are empty.

fn create_room(room: Rect, map: &mut Map) {
    // go through the tiles in the rectangle and make them passable
    for x in (room.x1 + 1)..room.x2 {
        for y in (room.y1 + 1)..room.y2 {
            map[x as usize][y as usize] = Tile::empty();
        }
    }
}

The +1 business here is a bit subtle: the A..B notation specifies a range that’s inclusive at the beginning but exclusive at the end. For example 1..5 represents numbers 1, 2, 3 and 4 but not 5.

So to go through all the values between x1 and x2 (including both), we’d have to write x1..(x2 + 1). But we want to make sure each room is enclosed in a wall, so we want to go from x1 to x2 exclusive. To do that, we add 1 to the first coordinate and subtract one from the second, ending up with (x1 + 1)..x2. If x1 is 1 and x2 is 5, we would put empty tiles at positions 2, 3 and 4 and leave 1 and 5 solid.

To test it, place two rooms in make_map:

fn make_map() -> Map {
    // fill map with "blocked" tiles
    let mut map = vec![vec![Tile::wall(); MAP_HEIGHT as usize]; MAP_WIDTH as usize];

    // create two rooms
    let room1 = Rect::new(20, 15, 10, 15);
    let room2 = Rect::new(50, 15, 10, 15);
    create_room(room1, &mut map);
    create_room(room2, &mut map);

    map
}

Before testing it out, make the player appear in the centre of the first room:

// place the player inside the first room
let player = Object::new(25, 23, '@', WHITE);

You can walk around the first room, but not reach the second. Let’s add a function to carve a horizontal tunnel:

fn create_h_tunnel(x1: i32, x2: i32, y: i32, map: &mut Map) {
    // horizontal tunnel. `min()` and `max()` are used in case `x1 > x2`
    for x in cmp::min(x1, x2)..(cmp::max(x1, x2) + 1) {
        map[x as usize][y as usize] = Tile::empty();
    }
}

We use min and max to make sure the .. range always starts with the smaller of the numbers — it wouldn’t return produce values otherwise. What it all means that calling create_h_tunnel(1, 5, …​) is equal to create_h_tunnel(5, 1, …​).

The min and max functions come from the std::cmp module, so put it with our other use blocks:

use std::cmp;

And similarly for the vertical tunnels:

fn create_v_tunnel(y1: i32, y2: i32, x: i32, map: &mut Map) {
    // vertical tunnel
    for y in cmp::min(y1, y2)..(cmp::max(y1, y2) + 1) {
        map[x as usize][y as usize] = Tile::empty();
    }
}
We are using Tile::empty to "carve out" the empty tiles in the map. That means we’re replacing the existing tile with a new, empty one instead of just modifying its blocked and block_sight fields. This is easier to read and write, but it wouldn’t work if the tiles already had some fields you care about set. Say if you ran the dungeon generation in layers and an earlier function already set some properties you’d like to keep.

Now we can connect both rooms with a horizontal tunnel. In make_map:

create_h_tunnel(25, 55, 23, &mut map);

Here’s the code for this part.

Dungeon generator

And now, we get to build one of the most integral parts to every roguelike — the dungeon generator. It’s a huge part of the character of your game and it’s what gives it the fabled infinite replayability.

There’s a ton o ways to build your worlds and each may suit a different game. We’ll use a pretty simple algorithm:

First, pick a random location for the first room and carve it. Then pick another location for the second room such that it does not overlap with the first. Connect the two with a tunnel and repeat. This will yield a sequence of connected rooms.

So we need a method to check for room intersections and we’ll add one for getting the centre of a room as well — that’s where the tunnels will start from.

Place these in the impl Rect block:

pub fn center(&self) -> (i32, i32) {
    let center_x = (self.x1 + self.x2) / 2;
    let center_y = (self.y1 + self.y2) / 2;
    (center_x, center_y)
}

pub fn intersects_with(&self, other: &Rect) -> bool {
    // returns true if this rectangle intersects with another one
    (self.x1 <= other.x2)
        && (self.x2 >= other.x1)
        && (self.y1 <= other.y2)
        && (self.y2 >= other.y1)
}

Now add some constants for the allowed room sizes and the maximum number of rooms:

//parameters for dungeon generator
const ROOM_MAX_SIZE: i32 = 10;
const ROOM_MIN_SIZE: i32 = 6;
const MAX_ROOMS: i32 = 30;

For generating random numbers we’re going to use the rand crate instead of libtcod’s random number generator, because the former has been designed for Rust and has more functionality.

To enable it, open Cargo.toml and add this in your [dependencies] section:

rand = "0.3.9"

And put this on top of your source file:

use rand::Rng;

With that out of the way, let’s actually implement the algorithm in make_map. Remove the previous code that created the example rooms and tunnel and instead make a loop that goes through the maximum number of rooms, assigning random coordinates and size to each one as we go.

let mut rooms = vec![];

for _ in 0..MAX_ROOMS {
    // random width and height
    let w = rand::thread_rng().gen_range(ROOM_MIN_SIZE, ROOM_MAX_SIZE + 1);
    let h = rand::thread_rng().gen_range(ROOM_MIN_SIZE, ROOM_MAX_SIZE + 1);
    // random position without going out of the boundaries of the map
    let x = rand::thread_rng().gen_range(0, MAP_WIDTH - w);
    let y = rand::thread_rng().gen_range(0, MAP_HEIGHT - h);
}

Next we’ll store all the created rooms in the rooms vec and use it to check for intersections with any new room we create.

let new_room = Rect::new(x, y, w, h);

// run through the other rooms and see if they intersect with this one
let failed = rooms
    .iter()
    .any(|other_room| new_room.intersects_with(other_room));

The iter method returns an iterator — a value we can query for each item in the vector. Iterators are really handy in Rust because they have a bunch of useful methods one might want to do on a collection already defined.

The any method runs the code in the parentheses (which is a closure) for every item in the rooms vec. As soon as it encounters false, it will abort.

Now we know whether the room is valid. If it is, we can carve it with create_room! We’ll also handle a special case: the player will start at the centre of the first room.

We will pass the player into make_map and set its position there.

fn make_map(player: &mut Object) -> Map {
    // ...

    for _ in 0..MAX_ROOMS {
        // ...

        if !failed {
            // this means there are no intersections, so this room is valid

            // "paint" it to the map's tiles
            create_room(new_room, &mut map);

            // center coordinates of the new room, will be useful later
            let (new_x, new_y) = new_room.center();

            if rooms.is_empty() {
                // this is the first room, where the player starts at
                player.x = new_x;
                player.y = new_y;
            }
        }
    }

    map
}

And in main get the starting position from make_map and use it to set player’s initial coordinates:

// create object representing the player
let player = Object::new(0, 0, '@', WHITE);

let game = Game {
    // generate map (at this point it's not drawn to the screen)
    map: make_map(&mut objects[0]),
};

Now let’s get back to our dungeon generator and make sure we add tunnels between the rooms.

For every room except the first one we connect it to the previous one. Now, sometimes we can’t connect them with a straight line (horizontal or vertical) but we need two tunnels.

We could start with a horizontal tunnel to reach the same level as the new room and then connect it with a vertical one or we can do the opposite: start with a vertical tunnel and finish with a horizontal one.

Both approaches are valid so we’ll choose between them randomly.

if rooms.is_empty() {
    // this is the first room, where the player starts at
    // ...
} else {
    // all rooms after the first:
    // connect it to the previous room with a tunnel

    // center coordinates of the previous room
    let (prev_x, prev_y) = rooms[rooms.len() - 1].center();

    // toss a coin (random bool value -- either true or false)
    if rand::random() {
        // first move horizontally, then vertically
        create_h_tunnel(prev_x, new_x, prev_y, &mut map);
        create_v_tunnel(prev_y, new_y, new_x, &mut map);
    } else {
        // first move vertically, then horizontally
        create_v_tunnel(prev_y, new_y, prev_x, &mut map);
        create_h_tunnel(prev_x, new_x, new_y, &mut map);
    }
}

// finally, append the new room to the list
rooms.push(new_room);

And there we have it! A procedural dungeon generator!

Here’s the complete code so far.

Continue to the next part.