Map Generation

As the player descends the dungeon, the game procedurally generates new levels that are unique to the game seed and dungeon depth. Levels are created in two phases: laying out the map and placing interesting things in it like monsters and items. This chapter is about map layout: deciding where rooms and corridors should appear, then drawing them out with wall and floor tiles.

Map Data

Before diving into the logic, it helps to be familiar with how the map is represented in terms of data. The main data structure involved is the Map struct that can be found in the src/map.rs file. The relevant parts of it are reproduced below:

pub struct Map {
    pub depth: i32,
    pub width: i32,
    pub height: i32,
    tiles: Vec<Tile>,
    pub rooms: Vec<Rect>,
    // ...
}

The depth field is the dungeon depth of the map; this is 1 for the first level. The width and height fields hold the dimensions of the map in terms of tiles. The tiles field contains the tiles themselves, stored in row-major order, i.e. store a full row of tiles, then the next row, then the next and so on. The Tile enum is defined higher up in the src/map.rs file:

pub enum Tile {
    Floor,
    Wall,
    DownStairs,
}

The final relevant field of the Map struct is the rooms field. This is a list of Rect structs, one for each room:

pub struct Rect {
    pub x1: i32,
    pub y1: i32,
    pub x2: i32,
    pub y2: i32,
}

Here, (x1, y1) is the top-left corner of the room, while (x2, y2) is the bottom-right corner. Even though rooms are drawn out as wall and floor tiles, the game needs to keep track of room positions like this in order to place other things in the level such as monsters and items later on, hence this list.

A single Map struct is allocated and added as unique data at game launch in the main function in the src/main.rs file, like so:

world.add_unique(Map::new(80, 50));

Every time a new level is needed, this Map struct is cleared and reused. There's no special reason for this except that it just happens to be the easiest way to do this for how unique game data is handled. Since this map is initialized here to be 80 tiles wide and 50 tiles high, all maps in the game share these dimensions.

When Levels are Generated

Levels are generated by calling the map::generate_rooms_and_corridors function, which happens in two places:

  1. When starting a new game in the new_game_setup function in the src/modes/title.rs file.
  2. When the player descends a dungeon level in the player_do_descend function in the src/player.rs file.

Rooms and Corridors

Map generation takes place in the map::generate_rooms_and_corridors function in the src/map.rs file. As the name suggests, its job is to draw rooms and corridors in terms of map tiles, and produce a list of rooms for later use.

The very first thing this function does is fill the map with wall tiles.

Rooms and corridors are placed randomly about the map, so a random number generator is created for this purpose. This is seeded with the game seed and the dungeon depth for the map as described in the Randomness chapter, so each map is effectively unique across game seeds and dungeon depths.

Placing Rooms

Rooms are placed onto the map as follows:

  1. Make a rectangle with a random width and height.
  2. Pick a random position on the map.
  3. If the rectangle doesn't intersect any existing room, draw floor tiles and add it to the room list.

This process is repeated thirty times, so the code looks like this:

for _ in 0..30 {
    let w: i32 = rng.gen_range(6i32..15i32);
    let h: i32 = rng.gen_range(6i32..11i32);
    let x: i32 = rng.gen_range(1i32..map.width - w - 1);
    let y: i32 = rng.gen_range(1i32..map.height - h - 1);
    let new_room = Rect::new(x, y, w, h);

    if !map.rooms.iter().any(|r| new_room.intersects(r, 1)) {
        map.set_rect(&new_room, Tile::Floor);
        map.rooms.push(new_room);
    }
}

This typically results in about a dozen rooms per level.

Rooms look better when they're surrounded by wall tiles, so the x and y values are chosen to avoid placing the room flush with the edges of the map.

The new_room.intersects(r, 1) part checks if new_room intersects with a room r that cycles through all of the existing rooms. The Rect::intersects function higher up in the src/map.rs file takes a margin argument that's set to 1 tile here, so the new_room is 'inflated' by one tile in all directions when checking to avoid placing it flush against another room.

Connecting Rooms with Corridors

Once the rooms have been placed they need to be connected in a way that guarantees that all of the rooms can be reached. Rooms are connected with corridors as follows:

  1. Add the first room to a connected list and the rest to a disconnected list.
  2. While the disconnected list still has rooms:
    • Pick the disconnected room that is closest to a room in the connected list.
    • Join those rooms with a corridor drawn out of floor tiles.
    • Move the room from the disconnected list to the connected list.

Once every room is in the connected list, they can all be reached via corridors. The code itself looks like this:

let mut connected: Vec<usize> = Vec::new();
let mut disconnected: Vec<usize> = Vec::new();

// Consider the first room as the start of connectedness.
connected.push(0);

// All other rooms start disconnected.
for i in 1..map.rooms.len() {
    disconnected.push(i);
}

// Connect all the disconnected rooms to the connected rooms based on closeness.
while !disconnected.is_empty() {
    // Find the closest match between connected and disconnected.
    let (closest_connected, closest_disconnected) = connected
        .iter()
        .enumerate()
        .flat_map(|c| std::iter::repeat(c).zip(disconnected.iter().enumerate()))
        .min_by_key(|&((_, &croom), (_, &droom))| {
            let ccenter = map.rooms[croom].center();
            let dcenter = map.rooms[droom].center();
            (ccenter.0 - dcenter.0).abs() + (ccenter.1 - dcenter.1).abs()
        })
        .map(|((ci, _), (di, _))| (ci, di))
        .unwrap();

    // Connect the closest connected and disconnected rooms together.
    connect_rooms(
        &mut map,
        connected[closest_connected],
        disconnected[closest_disconnected],
        rng.gen::<bool>(),
    );

    // Transfer newly-connected room index from disconnected to connected.
    connected.push(disconnected.remove(closest_disconnected));
}

The connected and disconnected lists above store indices into the map's rooms list.

The code for finding the closest disconnected room to a connected room can be a bit tricky to read. The connected/iter/enumerate/flat_map lines create an iterator that pairs up each connected room index with a disconnected room index. For example, if connected contains [0, 1] and disconnected contains [2, 3, 4], this iterator produces these pairs in order:

  • (0, 2)
  • (0, 3)
  • (0, 4)
  • (1, 2)
  • (1, 3)
  • (1, 4)

The min_by_key code block calculates the approximate corridor length between the center tiles of the connected and disconnected rooms and returns the pair that would need the shortest corridor to connect. In the example above, if the (1, 3) pair had the shortest estimated corridor length, connected room 1 and disconnected room 3 would be joined with a corridor, and 3 would be moved from the disconnected list to the connected list.

The task of drawing a corridor out of floor tiles is done by connect_rooms:

let connect_rooms = |map: &mut UniqueViewMut<Map>, r1: usize, r2: usize, h_then_v: bool| {
    let (r1x, r1y) = map.rooms[r1].center();
    let (r2x, r2y) = map.rooms[r2].center();
    if h_then_v {
        map.set_hline(r2x, r1x, r2y, Tile::Floor);
        map.set_vline(r2y, r1y, r1x, Tile::Floor);
    } else {
        map.set_vline(r2y, r1y, r2x, Tile::Floor);
        map.set_hline(r2x, r1x, r1y, Tile::Floor);
    }
};

The h_then_v argument is a flag to draw horizontal floor tiles, then vertical floor tiles; this is decided with a random coin flip by the map generation random number generator. Corridors can freely overlap rooms and each other.

Savvy readers may notice that joining rooms with corridors this way is like using Prim's algorithm for finding the minimum spanning tree of a graph, i.e. the least cost edges to join every node. A tree of a graph contains no loops, so what we have so far is a map with a lot of dead end rooms, which in gameplay terms means a lot of backtracking that we don't want. To reduce the number of dead ends and backtracking needed, several extra pairs of rooms are picked at random and joined with corridors as well.

Finishing Touches

If the player hasn't descended deep enough into the dungeon, a downstairs tile is placed in the center of the last room in the room list. If they have, the coordinates of that same tile is passed back to the calling code so that the victory item can be placed there instead.

With the map tiles drawn out and the room list prepared, the map is ready to be populated with things like monsters and items.