8 - Random dungeon generation

Jun 29, 2021 tdd rust srl | Prev | Next | Code

In a typical roguelike, the player is moving through dungeons that are procedurally generated. Sophisticated algorithms will create the playing field and make it look nice. Eventually, we will get there. But since I am a fan of small steps, we start with something simpler: Randomly generate a given number of walls and enemies, and a random starting position for the player.

A failing feature test, again

Since we want to go from the outside in, i.e. we want to start with a feature test, we need to figure out how to get the concept of random dungeon generation into the Game API.

The simplest idea at this point is to add another game “constructor” Game::generate_with, which will take a dungeon generator. Let’s write out a feature test:

#[test]
fn generates_game_using_given_generator() {
    let mut generator = FixedDungeonGenerator::new();
    generator.generate_walls(vec!((0, 0), (1, 0), (2, 0)));
    generator.generate_enemies(vec!((1, 1), (2, 1)));
    generator.generate_player(0, 1);

    let game = Game::generate_with(&generator);
    let mut renderer = RenderingSpy::new(3, 2);
    game.render(&mut renderer);
    renderer.assert_frame(vec![
        "# # #",
        "@ E E"
    ])
}

This looks a lot like our very first feature test, doesn’t it? But this time, all the initial positions will somehow be provided by a generator. For this test, we will use a special generator that accepts a fixed set of things to generate.

Stubbing out the dependencies

To enable injection of different kinds of generators, let’s say Game:generate_with accepts a trait DungeonGenerator:

pub trait DungeonGenerator {
    fn generate(&self) -> Dungeon;
}

impl Game {
    // ...
    pub fn generate_with<T: DungeonGenerator>(generator: &T) -> Self {
        Self { dungeon: generator.generate() }
    }
}

This will set the dungeon property to whatever the generator returns.

To make the test compile, we create an empty FixedDungeonGenerator:

pub struct FixedDungeonGenerator {}

impl FixedDungeonGenerator {
    pub fn new() -> Self { Self {} }

    pub fn generate_walls(&mut self, walls: Vec<CellCoords>) {}

    pub fn generate_enemies(&mut self, walls: Vec<CellCoords>) {}

    pub fn generate_player(&mut self, x: u32, y: u32) {}
}

impl DungeonGenerator for FixedDungeonGenerator {
    fn generate(&self) -> Dungeon { Dungeon::new() }
}

Now the test compiles. And it fails, because we just create an empty dungeon.

Setting that aside for now, we enter the unit testing loop to implement FixedDungeonGenerator:

#[test]
fn generates_given_objects() {
    let mut generator = FixedDungeonGenerator::new();
    generator.generate_walls(vec![(1, 2), (3, 4)]);
    generator.generate_enemies(vec![(5, 6), (7, 8)]);
    generator.generate_player(9, 10);

    let dungeon = generator.generate();
    let objects = dungeon.get_objects();
    assert_eq!(4, objects.len());
    assert!(objects.contains(&((1, 2), Wall)));
    assert!(objects.contains(&((3, 4), Wall)));
    assert!(objects.contains(&((5, 6), Enemy)));
    assert!(objects.contains(&((7, 8), Enemy)));
    assert_eq!((9, 10), dungeon.get_player_position())
}

This test verifies that the generator will generate the dungeon we tell it to generate.
The way the assertions are written prevents accidental dependencies on implementation details.

And so, assuming the obvious implementation of FixedDungeonGenerator, its trait implementation is simply:

impl DungeonGenerator for FixedDungeonGenerator {
    fn generate(&self) -> Dungeon {
        let mut dungeon = Dungeon::new();
        dungeon.add_walls(&self.walls);
        dungeon.add_enemies(&self.enemies);
        dungeon.set_player_position(self.player.0, self.player.1);
        dungeon
    }
}

And with that, the feature test passes as well. The generate_with constructor in place, we are in a position to pass in another kind of generator.

Implementing the random dungeon generator

The first “production” dungeon generator is rather simple: It generates random walls and enemies, as well as a random player position.

The following algorithm is conjured up:
To randomly generate W walls and E enemies in a dungeon of width W and height H:

• Generate all possible positions inside W and H
• Take out W random wall positions and add to dungeon
• Take out E random enemy positions and add to dungeon
• Take out random player position and set it in dungeon

How are we going to test that? Typically, there are two avenues open here: Control the randomness with some kind of stub, or make assertions about the properties of the randomly generated values.
I prefer the latter, because it requires less test helper code, and it keeps the interface complexity down (we don’t have to pass a special random generator).

The first RandomDungeonGenerator test looks like this, including necessary helper functions:

#[test]
fn generates_distinct_walls_and_enemies() {
    let generator = RandomDungeonGenerator::new(10, 20, 3, 2);
    let dungeon = generator.generate();
    let walls = get_distinct_objects_of_type(Wall, &dungeon);
    let enemies = get_distinct_objects_of_type(Enemy, &dungeon);
    let all_coords = get_distinct_coords(&dungeon);
    assert_eq!(walls.len(), 3);
    assert_eq!(enemies.len(), 2);
    assert_eq!(all_coords.len(), walls.len() + enemies.len());
}

fn get_distinct_objects_of_type(object_type: ObjectType, dungeon: &Dungeon) -> HashSet<DungeonObject> {
    dungeon.get_objects()
        .iter()
        .filter_map(|(pos, ty)| {
            if *ty == object_type { Some((*pos, *ty)) } else { None }
        })
        .collect()
}

fn get_distinct_coords(dungeon: &Dungeon) -> HashSet<DungeonCoords> {
    dungeon.get_objects()
        .iter()
        .map(|(pos, _)| { *pos })
        .collect()
}

That is quite an eyefull, right? It’s true. When doing this kind of testing, the test code tends to be a lot more complex, which makes me a bit uncomfortable.
Nevertheless, this test will generate a dungeon and it will assert that all generated walls and enemies have distinct coordinates, and that there is no overlap between wall and enemy positions. The trick is to convert lists of coordinates into sets, and asserting that the length does not change - duplicates would not be in the set.
But this is only one test case, right? Is that enough? It was enough for me at the time. It’s trivial to wrap this in a loop or use a framework to produce many test cases with different sets of inputs.

Another thing we want to assert is that two subsequent calls of generate return different dungeons:

#[test]
fn generates_different_dungeons() {
    let generator = RandomDungeonGenerator::new(10, 20, 3, 2);
    let dungeon1 = generator.generate();
    let dungeon2 = generator.generate();

    assert_ne!(get_distinct_objects_of_type(Wall, &dungeon1), 
               get_distinct_objects_of_type(Wall, &dungeon2));

    assert_ne!(get_distinct_objects_of_type(Enemy, &dungeon1), 
               get_distinct_objects_of_type(Enemy, &dungeon2));

    assert_ne!(dungeon1.get_player_position(), dungeon2.get_player_position());
}

Again, a very narrow test case. What about three calls? N calls? Maybe later.

Lastly, let’s make sure that the player does not spawn inside a wall or an enemy:

#[test]
fn generates_player_position_distinct_from_objects() {
    let generator = RandomDungeonGenerator::new(10, 20, 3, 2);
    let dungeon = generator.generate();
    let all_coords = get_distinct_coords(&dungeon);
    let player_position = dungeon.get_player_position();
    assert!(!all_coords.contains(&player_position))

}

I think the tests are more interesting than the implementation in this case, but you can have a look here:

• random_dungeon_generator.rs
• random_dungeon_generator_test.rs

Back to main

Finally, we plug the new generator into the production code. The change is minimal:

fn main() -> std::io::Result<()> {
    let generator = RandomDungeonGenerator::new(GAME_WIDTH, GAME_HEIGHT, 30, 10);
    let mut game = Game::generate_with(&generator);
    let mut renderer = TerminalRenderer::new(GAME_WIDTH, GAME_HEIGHT);
    let mut input = TerminalInput::new();
    let mut term = Term::buffered_stdout();
    while !input.quit_game() {
        game.render(&mut renderer);
        renderer.flush(&mut term);
        input.on_key(term.read_key()?);
        game.tick(&input);
        term.clear_last_lines(GAME_HEIGHT - 1)?;
    }
    term.clear_to_end_of_screen()
}

- [X] Player collision with walls
- [X] Player collision with enemies (no combat)
- [X] Randomly generated walls

Parting words

Alright, here is what the judges have to say:

• RandomDungeonGenerator API is clunky, a constructor with 4 paramters. And those insufficent test cases!
  That generator is really just a stepping stone to greater things (we hope). The tests are sufficient insofar as I am confident enough that the code does what it needs to do. If that changes, there will be more tests.

• What about Game::new? And the now duplicated API for adding walls and enemies, and the player?
  That’s fine, we can clean that up later. It’s techincal dept with no interest. It does not accumulate.

And that’s Version 0 shipped! The next thing to think about will be combat.