Bevy roguelike tutorial / devlog part 9 - dungeon generation

2023-05-18

#rust #bevy #gamedev

We have done already a lot of boiler plate code to setup the basic systems in this project. It is time to finally create something more fun and see the effects of our work. In this part we are going to start with procedural generation of the dungeons. (yaaay!)

The final code for this part can be found here: https://github.com/maciekglowka/hike_deck/tree/part_09

General layout

It is no secret that generating roguelike maps mean mostly placing rooms and connecting them with tunnels. That's what we are going to do here as well. However I'd like to also have a little bit of control over the higher level architecture of the dungeon. My aim here is to divide the board into a few distinctly featured parts to encourage player's exploration. I do not plan for the maps to be very complex or large though - just enough to spread places of interest quite apart.

I do not want to dive into very complex algorithms here as well - to keep things manageable (although I think we are going to need more than one blog post on that anyway). We are simply going to split the dungeon into a grid of sub areas, where each area will be a separately generated bunch of rooms. The areas might end up having unique features: Eg. one could be an area with an upgrade to find. Other might be a monster lair, etc. We are probably also going to use separate areas for the entrance and exits (to make sure they're not right next to each other). areas.png

The areas will be placed on an uneven rows/columns grid. (the order of the placement can be seen on the image above) We will make the code flexible enough to adjust the number of the rows, however we'll probably stick with just two for now. The column number will be decided dynamically - based on the areas inserted.

We are going to locate the dungeon generation code in the board module, but as I expect it to grow in the future let's already create an entire directory submodule for that:

src/
├── actions
│   ├── mod.rs
│   ├── models.rs
│   └── systems.rs
├── assets.rs
├── board
│   ├── components.rs
│   ├── dungeon
│   │   ├── mod.rs
│   │   └── room.rs
│   ├── mod.rs
│   └── systems.rs
// cut

As you can see I've already placed two files there: the main mod.rs and an extra one for the rooms. We are going to add some more soon, but for now let's focus on our Room struct:

// board/dungeon/room.rs
use rand::prelude::*;
use std::collections::HashSet;

use crate::vectors::Vector2Int;

pub struct Room {
    pub a: Vector2Int,
    pub b: Vector2Int
}
impl Room {
    pub fn new(a: Vector2Int, b: Vector2Int) -> Self {
        // sort the coordinates so `a` is always the left-bottom
        // and `b` is top-right
        Room {
            a: Vector2Int::new(a.x.min(b.x), a.y.min(b.y)),
            b: Vector2Int::new(a.x.max(b.x), a.y.max(b.y))
        }
    }
    pub fn corners(&self) -> [Vector2Int; 4] {
        [
            Vector2Int::new(self.a.x, self.a.y), Vector2Int::new(self.b.x, self.a.y),
            Vector2Int::new(self.b.x, self.b.y), Vector2Int::new(self.a.x, self.b.y)
        ]
    }
    pub fn random_point(&self) -> Vector2Int {
        let mut rng = thread_rng();
        let x = rng.gen_range(self.a.x..=self.b.x);
        let y = rng.gen_range(self.a.y..=self.b.y);
        Vector2Int::new(x, y)
    }
    pub fn to_tiles(&self) -> HashSet<Vector2Int> {
        (self.a.y..=self.b.y).map(|y| {
            (self.a.x..=self.b.x).map(move |x| {
                Vector2Int::new(x, y)
            })
        })
        .flatten()
        .collect()
    }
}

The room is a simple struct, defined by two corners - the bottom-left a and top-right b. We also include some helper methods, that will become handy very soon.

Also note: we are going to use the rand crate here, so don't forget to add it to your cargo dependencies. The current version I am using in the project is rand = "0.8.5".

Let's define struct for the areas in a similar fashion (add an area.rs file):

// board/dungeon/area.rs
use std::collections::HashSet;

use crate::vectors::Vector2Int;

use super::room::Room;

pub struct Area {
    pub rooms: Vec<Room>,
    pub paths: Vec<Vec<Vector2Int>>
}
impl Area {
    pub fn new() -> Self {
        Area { rooms: Vec::new(), paths: Vec::new() }
    }
    pub fn get_bounds(&self) -> (Vector2Int, Vector2Int) {
        let min_x = self.rooms.iter().map(|r| r.a.x).min().unwrap();
        let max_x = self.rooms.iter().map(|r| r.b.x).max().unwrap();
        let min_y = self.rooms.iter().map(|r| r.a.y).min().unwrap();
        let max_y = self.rooms.iter().map(|r| r.b.y).max().unwrap();
        (Vector2Int::new(min_x, min_y), Vector2Int::new(max_x, max_y))
    }
    pub fn get_size(&self) -> Vector2Int {
        let bounds = self.get_bounds();
        Vector2Int::new(bounds.1.x - bounds.0.x + 1, bounds.1.y - bounds.0.y + 1)
    }
    pub fn shift(&mut self, offset: Vector2Int) {
        // translate the entire area by a given offset
        let bounds = self.get_bounds();
        let d = offset - bounds.0;

        for room in self.rooms.iter_mut() {
            room.a += d;
            room.b += d;
        }
        for path in self.paths.iter_mut() {
            for v in path.iter_mut() {
                *v += d;
            }
        }
    }
    pub fn generate_rooms(&mut self) {
        self.rooms = vec![
            Room::new(Vector2Int::new(0, 0), Vector2Int::new(4, 6)),
            Room::new(Vector2Int::new(10, 2), Vector2Int::new(14, 8))
        ]
    }
    pub fn to_tiles(&self) -> HashSet<Vector2Int> {
        self.rooms.iter()
            .map(|r| r.to_tiles())
            .flatten()
            .chain(
                self.paths.iter().flatten().map(|v| *v)
            )
            .collect()
    }
}

As you can see the definition is slightly more complex. First of all the area will consist of two fields (for now): a vec of rooms and a vec of paths. For the paths we are not going to define a separate struct - a vec of Vector2Ints should be ok for now.

The shift function is going to let us reposition the areas within the dungeon grid. (as each area will be initially generated separately - in it's own space). The generate_rooms method creates two hard-coded rooms for now - it will let us test the layouting before we start with more complex generation. The rest of the methods should be quite self-explanatory, so I will skip their description :)

Now we are ready to finally define the Dungeon itself:

// board/dungeon/mod.rs
use std::collections::HashSet;

use crate::vectors::Vector2Int;

mod area;
mod room;

pub use area::Area;

const AREA_SPACING: i32 = 4;

pub struct Dungeon {
    pub areas: Vec<Area>,
    // the gird contains indexes to the areas vec
    // rows / columns
    grid: Vec<Vec<usize>>
}
impl Dungeon {
    pub fn new(row_count: usize) -> Self {
        let grid = (0..row_count).map(|_| Vec::new()).collect::<Vec<_>>();
        Dungeon { areas: Vec::new(), grid }
    }
    pub fn add_area(&mut self, area: Area) {
        self.areas.push(area);
        let idx = self.areas.len() - 1;
        let row_count = self.grid.len();
        // insert the index to appropriate row vec
        self.grid[idx % row_count].push(idx);
    }
    pub fn generate(&mut self) {
        for area in self.areas.iter_mut() {
            area.generate_rooms();
        }
        self.position_areas();
    }
    pub fn to_tiles(&self) -> HashSet<Vector2Int> {
        self.areas.iter()
            .map(|a| a.to_tiles())
            .flatten()
            .collect()
    }
    fn position_areas(&mut self) {
        let column_count = self.grid[0].len();

        // calculate grid dimensions based on contained areas
        let column_widths = (0..column_count).map(|i| 
            self.grid.iter().map(|r| match r.get(i) {
                None => 0,
                Some(a) => self.areas[i].get_size().x
            }).max().unwrap() + AREA_SPACING
        )
        .collect::<Vec<_>>();
        let row_heights = self.grid.iter()
            .map(|r| 
                r.iter().map(|i| 
                    self.areas[*i].get_size().y
                ).max().unwrap() + AREA_SPACING
            )
            .collect::<Vec<_>>();

        // calculate the offset amounts per each grid position
        let column_shifts = (0..column_widths.len())
            .map(|i| column_widths[..i].iter().sum())
            .collect::<Vec<i32>>();
        let row_shifts = (0..row_heights.len())
            .map(|i| row_heights[..i].iter().sum())
            .collect::<Vec<i32>>();

        // reposition the areas
        for (y, row) in self.grid.iter().enumerate() {
            for (x, idx) in row.iter().enumerate() {
                let offset = Vector2Int::new(column_shifts[x], row_shifts[y]);
                self.areas[*idx].shift(offset);
            }
        }
    }
}

That's a lot of code again! And not all of it is very readable (oops!). Let's try to break it down a bit.

Our Dungeon struct is going to hold quite naturally a vec of Areas. Apart from that we are going to keep a field defining our grid. It is a vec (rows) of vecs (columns) containing indexes to the areas field. (we do not use references to make it easier for us to work with Rust's borrow checker ;) We are going to update the struct each time we insert a new area to the dungeon, so everything is properly synced. Please notice that because we chose an ordering system as on the image above, the first row will always be the longest one - so we can calculate the column count from it's length.

The position_areas method uses lots of iterators and might not be the clearest to read. It is not very complex tough. At first, for each row and column we look for the area with the largest dimension. Then we calculate offsets per each grid x, y position. Finally, we can shift the areas using that info.

The to_tiles method allows us to convert the dungeon struct into our board tiles easily. It's based on analogous methods in the room and area structs.

Now we can go back to our spawn_map system (from the very first tutorial part) and use the dungeon generator there:

// board/systems.rs
use bevy::prelude::*;
use std::collections::HashMap;

use super::CurrentBoard;
use super::dungeon::{Area, Dungeon};
use super::components::{Position, Tile};

pub fn spawn_map(
    mut commands: Commands,
    mut current: ResMut<CurrentBoard>
) {
    let mut dungeon = Dungeon::new(2);
    for _ in 0..4 {
        dungeon.add_area(Area::new())
    }
    dungeon.generate();

    current.tiles = HashMap::new();
    for v in dungeon.to_tiles() {
        let tile = commands.spawn((
                Position { v },
                Tile
            ))
            .id();
        current.tiles.insert(v, tile);
    }
}

For the testing purposes we have inserted 4 separate areas to the dungeon. If you run the game now you should already be able to see the some rooms generated. initial_rooms.png

Tunnels

Now that we have some very basic rooms set up, we can try to connect them with tunnels. There are two very basic ways of generating corridors that come to my mind:

We are going to implement both to see how they can be easily used interchangeably to add some variation to our dungeons.

Let's start by creating a new tunneler.rs file:

// board/dungeon/tunneler.rs
use rand::{
    distributions::WeightedIndex,
    prelude::*
};

use crate::vectors::Vector2Int;

pub trait Tunneler {
    fn connect(&self, a: Vector2Int, b: Vector2Int) -> Vec<Vector2Int>;
}

pub struct LShapeTunneler;
impl Tunneler for LShapeTunneler {
    // connects two points by forming an L shaped connection
    // initial direction (hor / ver) is the one whith the biggest coordinate difference
    fn connect(&self, a: Vector2Int, b: Vector2Int) -> Vec<Vector2Int> {
        let d = b - a;
        let (hor_y, ver_x) = match d.x > d.y {
            true => (a.y, b.x),
            false => (b.y, a.x)
        };

        let hor = (a.x.min(b.x)..=a.x.max(b.x))
            .map(|x| Vector2Int::new(x, hor_y))
            .collect::<Vec<_>>();
        let ver = (a.y.min(b.y)..=a.y.max(b.y))
            .map(|y| Vector2Int::new(ver_x, y))
            .collect::<Vec<_>>();
        [ver, hor].concat()
    }
}

pub struct RandomTunneler;
impl Tunneler for RandomTunneler {
    // connects two points by taking a random direction (hor / ver) towards the target
    // choice chance is determined by a current coordinate difference
    // (it is most likely to pick a dir with the biggest diff)
    fn connect(&self, a: Vector2Int, b: Vector2Int) -> Vec<Vector2Int> {
        let mut cur = a;
        let mut path = Vec::new();
        let mut rng = thread_rng();
    
        while cur != b {
            path.push(cur);
            // 0 is horizontal, 1 is vertical
            let dirs = vec![b.x - cur.x, b.y - cur.y];
            // build weights
            let dist = WeightedIndex::new(dirs.iter().map(|d| d.abs())).unwrap();
            // pick a dir idx (0 or 1)
            let dir_idx = dist.sample(&mut rng);
            // create a normalized step vector in a single direction
            let dv = match dir_idx {
                0 => Vector2Int::new(dirs[0] / dirs[0].abs(), 0),
                1 => Vector2Int::new(0, dirs[1] / dirs[1].abs()),
                _ => panic!()
            };
            cur += dv;
        }
        path
    }
}

As a first thing - we define a trait for our tunnelers, so they can share a common interface.

Then we create the two implementations mentioned above. The L-shaped tunneler creates just two sections, a horizontal and a vertical one. First one being the longest one.

The random tunneler with each step makes a decision about a direction to take. Based on a weighted random function. If we are further away on the x-axis from the target, we are more likely to pick the horizontal direction. Also we only walk towards our target. Eg. if we have to move 5 tiles right and 3 down, we can only draw positive x values and negative ys.

Let's now include the tunneler object in our Area struct (so each area can have a different character):

pub struct Area {
    pub rooms: Vec<Room>,
    pub paths: Vec<Vec<Vector2Int>>,
    pub tunneler: Box<dyn Tunneler>
}
impl Area {
    pub fn new(tunneler: Box<dyn Tunneler>) -> Self {
        Area { rooms: Vec::new(), paths: Vec::new(), tunneler }
    }
// cut

Let's also change the dungeon generator code in the spawn_map system to use both tunneler algorithms, so we can test them:

let mut dungeon = Dungeon::new(2);
    for idx in 0..4 {
        let tun = match idx % 2 {
            0 => Box::new(tunneler::LShapeTunneler) as Box<dyn tunneler::Tunneler>,
            _ => Box::new(tunneler::RandomTunneler) as Box<dyn tunneler::Tunneler>
        };
        dungeon.add_area(Area::new(tun))
    }
    dungeon.generate();

Now let's use our tunnelers to internally connect rooms in the areas:

// in board/dungeon/area.rs
impl Area {
    // cut
    pub fn join_rooms(&self, a: &Room, b: &Room) -> Vec<Vector2Int> {
        self.tunneler.connect(a.random_point(), b.random_point())
    }
    pub fn generate_rooms(&mut self) {
        self.rooms = vec![
            Room::new(Vector2Int::new(0, 0), Vector2Int::new(4, 6)),
            Room::new(Vector2Int::new(10, 2), Vector2Int::new(14, 8))
        ];
        self.paths = vec![self.join_rooms(&self.rooms[0], &self.rooms[1])];
    }
// cut

We can now run the game and check if our connections are working, but before we do that let's change temporarily the camera to see the entire map:

pub fn setup(mut commands: Commands) {
    let mut camera = Camera2dBundle::default();
    // temporary ;)
    camera.projection.scale = 2.;
    camera.transform.translation = Vec3::new(
        20. * TILE_SIZE,
        10. * TILE_SIZE,
        camera.transform.translation.z
    );
    commands.spawn(camera);
}

tunnels.png

Joining dungeon areas

There is one last thing that we are going to tackle in this part. We will use our tunnelers to connect the separated dungeon areas. We will do so by finding a closest pair of rooms between the areas we want to connect. And then we will create a tunnel joining them (just as above).

Our method for finding the correct room pair is going to be rather crude and will take into account only rooms' corners. (so it might happen that in reality there is a closer pair based on edge to edge or edge to corner distance).

I know it's a lot of nested iterators, but it gets the job done :)

// in board/dungeon/area.rs

impl Area {
    // cut
    fn find_closest_room_pair<'a>(&'a self, other: &'a Area) -> (&'a Room, &'a Room) {
        // find closest room pair between two areas
        // based on corner distances only
        let mut pairs = Vec::new();
        for ra in self.rooms.iter() {
            for rb in other.rooms.iter() {
                // find min corner dist
                let d= ra.corners().iter()
                    .map(|ca| rb.corners().iter()
                        .map(|cb| ca.manhattan(*cb))
                        .collect::<Vec<_>>()
                    )
                    .flatten()
                    .min()
                    .unwrap();
                pairs.push((d, ra, rb));
            }
        }
        // sort by corner dist
        pairs.sort_by(|a, b| a.0.cmp(&b.0));
        (pairs[0].1, pairs[0].2)
    }
    pub fn join_area(&self, other: &Area) -> Vec<Vector2Int> {
        let rooms = self.find_closest_room_pair(other);
        self.join_rooms(rooms.0, rooms.1)
    }
// cut

Having that, we can create simple method in the Dungeon struct that will iterate through the area grid and connect neighbouring locations:

// in board/dungeon/mod.rs

impl Dungeon {
    // cut
    pub fn generate(&mut self) {
        for area in self.areas.iter_mut() {
            area.generate_rooms();
        }
        self.position_areas();
        self.connect_areas();
    }
    // cut
    fn connect_areas(&mut self) {
        // connect areas based on their grid location
        let mut pairs = Vec::new();
        for (y, row) in self.grid.iter().enumerate() {
            for (x, idx) in row.iter().enumerate() {
                if x != 0 {
                    // join to area at x - 1
                    pairs.push((idx, row[x-1]));
                };
                if y != 0 {
                    // join to area at y - 1
                    pairs.push((idx, self.grid[y-1][x]));
                };
            }
        }
        for pair in pairs {
            let path = self.areas[*pair.0].join_area(&self.areas[pair.1]);
            self.areas[*pair.0].paths.push(path);
        }
    }
}

We simply just connect non-zero indexed areas to their left or bottom neighbours - that's it. Now if you run the game you should finally see the entire map connected :)

Next time we are going to randomize the room generation to finally have some nicer looking maps. joined_areas.png