The definition of “roguelike” is hotly debated but one aspect we can all agree on is that levels must be procedurally generated. That is, rather than fixed, hand-crafted levels, players will explore levels generated according to an algorithm; each playthrough will be unique, and it’s highly unlikely that any other player will ever see the same levels as you.

In this part we’ll implement an algorithm for procedurally generating a dungeon!

By the end of this part, the game will look like this: screenshot-end

This part is loosely based on this part of the python tcod tutorial.

Reference implementation branch for starting point: part-2-end

In this post:

Framework

Rather than generating the dungeon directly into the GameState, it will be more convenient to first populate a 2D array of tiles, and then use the result to initialize the GameState. Grab a crate to help work with 2D arrays using the Coord and Size types we’ve seen in previous parts:

# Cargo.toml
grid_2d = "0.14"

Start by generating a single room and placing the player inside. This starts with a Grid<Option<TerrainTile>>, and sets some of the cells to be Some(...) to add walls, floors, and the player spawn point. As the algorithm may not visit every cell of the grid, the final line of generate_dungeon (grid.map(...)) creates a new grid by unwrapping every cell of the original grid, replacing every None with TerrainTile::Wall.

// terrain.rs

use grid_2d::{Coord, Grid, Size};

#[derive(Clone, Copy, PartialEq, Eq)]
pub enum TerrainTile {
    Player,
    Floor,
    Wall,
}

pub fn generate_dungeon(size: Size) -> Grid<TerrainTile> {
    let mut grid = Grid::new_copy(size, None);
    for coord in Size::new(5, 5).coord_iter_row_major() {
        *grid.get_checked_mut(coord + Coord::new(1, 1)) = Some(TerrainTile::Floor);
    }
    *grid.get_checked_mut(Coord::new(3, 3)) = Some(TerrainTile::Player);
    grid.map(|t| t.unwrap_or(TerrainTile::Wall))
}

Update GameState::populate to spawn entities based on the contents of the a Grid<TerrainTile> returned by terrain::generate_dungeon:

// game.rs

use crate::terrain::{self, TerrainTile};

...

impl GameState {
    ...
    fn populate(&mut self) {
        let terrain = terrain::generate_dungeon(self.screen_size);
        for (coord, terrain_tile) in terrain.enumerate() {
            match terrain_tile {
                TerrainTile::Player => {
                    self.spawn_floor(coord);
                    self.spawn_player(coord);
                }
                TerrainTile::Floor => self.spawn_floor(coord),
                TerrainTile::Wall => {
                    self.spawn_floor(coord);
                    self.spawn_wall(coord);
                }
            }
        }
    }
    ...
}

Add the terrain module to main.rs:

// main.rs

...
mod terrain;
...

Run the game and it will generate this:

screenshot-start

Reference implementation branch: part-3.0

Random Number Generator

Before proceeding with terrain generation, we need a source of randomness in the terrain generator. Add dependencies on rand and rand_isaac:

# Cargo.toml
rand = "0.7"        # basic functionality for random number generators
rand_isaac = "0.2"  # a specific random number generator implementation

Initialize a random number generator and store it in a field of GameState. Pass a reference to the RNG into generate_dungeon.

// game.rs

use rand::SeedableRng;
use rand_isaac::Isaac64Rng;

...

impl GameState {
    ...
    fn populate(&mut self) {
        let terrain = terrain::generate_dungeon(self.screen_size, &mut self.rng);
        ...
    }
    ...
    pub fn new(screen_size: Size) -> Self {
        ...
        let rng = Isaac64Rng::from_entropy();
        let mut game_state = Self {
            ...
            rng,
        };
        ...
    }
    ...
}

Add the corresponding argument to generate_dungeon.

// terrain.rs

use rand::Rng;
...
pub fn generate_dungeon<R: Rng>(size: Size, rng: &mut R) -> Grid<TerrainTile> {
    println!("random int: {}", rng.next_u32());
    ...
}

Run this and it will print out a random number:

random int: 387460914

Reference implementation branch: part-3.1

Rooms

Add rooms in random locations by repeatedly creating rooms with random sizes and positions, but only adding them to the map if they don’t overlap any existing rooms. Here’s the code:

// terrain.rs

...

// A rectangular area of the map
struct Room {
    top_left: Coord,
    size: Size,
}

impl Room {
    // Returns a randomly sized room at a random position within `bounds`
    fn choose<R: Rng>(bounds: Size, rng: &mut R) -> Self {
        let width = rng.gen_range(5, 11);
        let height = rng.gen_range(5, 9);
        let size = Size::new(width, height);
        let top_left_bounds = bounds - size;
        let left = rng.gen_range(0, top_left_bounds.width());
        let top = rng.gen_range(0, top_left_bounds.height());
        let top_left = Coord::new(left as i32, top as i32);
        Self { top_left, size }
    }

    // Returns a coord at the centre of the room, rounding down
    fn centre(&self) -> Coord {
        self.top_left + self.size.to_coord().unwrap() / 2
    }

    // Returns an iterator over all the coordinates in the room in row major order
    fn coords<'a>(&'a self) -> impl 'a + Iterator<Item = Coord> {
        self.size
            .coord_iter_row_major()
            .map(move |coord| self.top_left + coord)
    }

    // Returns true if and only if each cell of `grid` overlapping this room is `None`
    fn only_intersects_empty(&self, grid: &Grid<Option<TerrainTile>>) -> bool {
        self.coords().all(|coord| grid.get_checked(coord).is_none())
    }

    // Updates `grid`, setting each cell overlapping this room to `Some(TerrainTile::Floor)`.
    // The top and left sides of the room are set to `Some(TerrainTile::Wall)` instead.
    // This prevents a pair of rooms being placed immediately adjacent to one another.
    fn carve_out(&self, grid: &mut Grid<Option<TerrainTile>>) {
        for coord in self.coords() {
            let cell = grid.get_checked_mut(coord);
            if coord.x == self.top_left.x || coord.y == self.top_left.y {
                *cell = Some(TerrainTile::Wall);
            } else {
                *cell = Some(TerrainTile::Floor);
            }
        }
    }
}

pub fn generate_dungeon<R: Rng>(size: Size, rng: &mut R) -> Grid<TerrainTile> {
    let mut grid = Grid::new_copy(size, None);
    let mut player_coord = None;

    // Attempt to add a room a constant number of times
    const NUM_ATTEMPTS: usize = 100;
    for _ in 0..NUM_ATTEMPTS {
        // Make a random room
        let room = Room::choose(size, rng);

        // Carve out the room unless it overlaps with an existing room
        if room.only_intersects_empty(&grid) {
            room.carve_out(&mut grid);
            if player_coord.is_none() {
                player_coord = Some(room.centre());
            }
        }
    }

    // Start the player in the centre of the first room
    *grid.get_checked_mut(player_coord.unwrap()) = Some(TerrainTile::Player);
    grid.map(|t| t.unwrap_or(TerrainTile::Wall))
}

Here’s an example map produced by this algorithm:

screenshot-rooms

Reference implementation branch: part-3.2

Corridors

To add corridors between rooms, keep track of the centre of every room that gets placed, and then after all the rooms are placed, carve out corridors connecting every adjacent pair of room centres.

// terrain.rs

...

// Carve out an L-shaped corridor between a pair of coordinates
fn carve_corridor(start: Coord, end: Coord, grid: &mut Grid<Option<TerrainTile>>) {
    for i in start.x.min(end.x)..=start.x.max(end.x) {
        *grid.get_checked_mut(Coord { x: i, ..start }) = Some(TerrainTile::Floor);
    }
    for i in start.y.min(end.y)..start.y.max(end.y) {
        *grid.get_checked_mut(Coord { y: i, ..end }) = Some(TerrainTile::Floor);
    }
}

pub fn generate_dungeon<R: Rng>(size: Size, rng: &mut R) -> Grid<TerrainTile> {
    let mut grid = Grid::new_copy(size, None);
    let mut room_centres = Vec::new();

    // Attempt to add a room a constant number of times
    const NUM_ATTEMPTS: usize = 100;
    for _ in 0..NUM_ATTEMPTS {
        // Make a random room
        let room = Room::choose(size, rng);

        // Carve out the room unless it overlaps with an existing room
        if room.only_intersects_empty(&grid) {
            room.carve_out(&mut grid);

            // Build up a list of room centres
            let room_centre = room.centre();
            room_centres.push(room_centre);
        }
    }

    // Add corridors connecting every adjacent pair of room centres
    for window in room_centres.windows(2) {
        carve_corridor(window[0], window[1], &mut grid);
    }

    // Start the player in the centre of the first room
    *grid.get_checked_mut(room_centres[0]) = Some(TerrainTile::Player);
    grid.map(|t| t.unwrap_or(TerrainTile::Wall))
}

After this change, the dungeon generator will produce fully-connected dungeons made up of rooms and corridors.

screenshot-end

Reference implementation branch: part-3.3