## 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);``

## 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),
};``````

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!

Continue to the next part.