This is part three in a series of tutorials on procedural generation with Rust.
- Procedural level generation with Rust
- Drawing tile maps with Rust and Cairo
- Procedural level generation using Binary Space Partitioning in Rust (this one)
- Use prebuilt rooms with Rust macros for more interesting dungeons
This time we're going to add a different algorithm to generate levels, called binary space partition.
The general procedure for binary space partitioning is fairly simple:
- Take an area, known as a
Leafthen split it either horizontally or vertically at a random point. You now have two child leaves. - Repeat this process for each of the two new child leaves.
- Keep repeating for each new child leaf until each area is small enough.
- Once all the leaves can't be split any more, add rooms at random points in each leaf.
- Join rooms in sibling leaves with corridors, then move up to the parent leaf and join one of the rooms to the parent's sibling, and so on until you reach the root leaf.
x
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1 x
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...etc...
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 x x x x 1 x x 1 x x x x 1
1 x x x x 1 x x 1 x x x x 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 x x x 1 x x x x 1 x x 1
1 x x x 1 x x x x 1 x x 1
1 x x x 1 x x x x 1 x x 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 x x x x 1 1 1
1 x x x x 1 x x x 1 x x x1
1 x x x x 1 x x x 1 x x x1
1 1 x x x 1 x x x1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1This process means rooms are spread out more evenly across the entire area of the level when compared with the random room placement algorithm:
Binary space partition
Random room placement
Setup
You'll need the code from last time: you can clone a copy from Github if necessary.
Refactoring
The first step is to move the old level creation code into it's own module so we can switch between the generation algorithms, and create a general Level struct to be used by all types of levels.
Create a new file in src/ called roomscorridors.rs; this will contain a new struct which just holds a level, and several of the level functions will now be part of the RoomsCorridors implementation:
// roomscorridors.rs
use rand::{ Rng, StdRng };
use level::{ Level, Tile };
use room::Room;
// this just holds a Level
pub struct RoomsCorridors {
level: Level
}
impl RoomsCorridors {
// Note that this returns a Level
pub fn new(width: i32, height: i32, hash: &String, rng: &mut StdRng) -> Level {
let level = Level::new(width, height, hash);
let mut map = RoomsCorridors {
level
};
map.place_rooms(rng);
map.place_corridors(rng);
map.level
}
// place_rooms, place_corridors, vert_corridor and horz_corridor are
// almost identical to the implementations in Level
// notice that we're now checking `self.level.width` instead of `self.width`
// and so on
pub fn place_rooms(&mut self, rng: &mut StdRng) {
let max_rooms = 10;
let min_room_width = 4;
let max_room_width = 8;
let min_room_height = 5;
let max_room_height = 12;
for _ in 0..max_rooms {
let mut x = rng.gen_range(0, self.level.width);
let mut y = rng.gen_range(0, self.level.height);
let width = rng.gen_range(min_room_width, max_room_width);
let height = rng.gen_range(min_room_height, max_room_height);
if x + width > self.level.width {
x = self.level.width - width;
}
if y + height > self.level.height {
y = self.level.height - height;
}
let mut collides = false;
let room = Room::new(x, y, width, height);
for other_room in &self.level.rooms {
if room.intersects(&other_room) {
collides = true;
break;
}
}
if !collides {
self.level.add_room(&room);
}
}
}
fn place_corridors(&mut self, rng: &mut StdRng) {
for i in 0..(self.level.rooms.len() - 1) {
let room = self.level.rooms[i];
let other = self.level.rooms[i + 1];
// randomly pick vert or horz
match rng.gen_range(0, 2) {
0 => {
match room.centre.x <= other.centre.x {
true => self.horz_corridor(room.centre.x, other.centre.x, room.centre.y),
false => self.horz_corridor(other.centre.x, room.centre.x, room.centre.y)
}
match room.centre.y <= other.centre.y {
true => self.vert_corridor(room.centre.y, other.centre.y, other.centre.x),
false => self.vert_corridor(other.centre.y, room.centre.y, other.centre.x)
}
}
_ => {
match room.centre.y <= other.centre.y {
true => self.vert_corridor(room.centre.y, other.centre.y, other.centre.x),
false => self.vert_corridor(other.centre.y, room.centre.y, other.centre.x)
}
match room.centre.x <= other.centre.x {
true => self.horz_corridor(room.centre.x, other.centre.x, room.centre.y),
false => self.horz_corridor(other.centre.x, room.centre.x, room.centre.y)
}
}
}
}
}
fn horz_corridor(&mut self, start_x: i32, end_x: i32, y: i32) {
for col in start_x..end_x + 1 {
self.level.board[y as usize][col as usize] = Tile::Walkable;
}
}
fn vert_corridor(&mut self, start_y: i32, end_y: i32, x: i32) {
for row in start_y..end_y + 1 {
self.level.board[row as usize][x as usize] = Tile::Walkable;
}
}
}The RoomsCorridors::new function creates a new level, then places rooms and corridors and returns the level. This is so that when we have lots of different algorithms to choose from, we know that all we need to do is call a new function on them and we'll get a Level back, which we can then draw and serialise as before.
We can also delete the place_rooms, place_corridors, vert_corridor and horz_corridor functions from level.rs, and make add_room public:
use std::fmt;
use serde::{ Serialize, Serializer };
use rand::prelude::*;
use room::Room;
#[derive(Clone)]
pub enum Tile {
Empty,
Walkable
}
impl Serialize for Tile {
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where S: Serializer {
match self {
Tile::Empty => serializer.serialize_i32(0),
Tile::Walkable => serializer.serialize_i32(1)
}
}
}
impl fmt::Display for Tile {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match self {
Tile::Empty => write!(f, "0"),
Tile::Walkable => write!(f, "1")
}
}
}
#[derive(Serialize)]
pub struct Level {
pub width: i32,
pub height: i32,
pub board: Vec<Vec<Tile>,
pub tile_size: i32,
pub rooms: Vec<Room>,
hash: String
}
impl Level {
pub fn new(width: i32, height: i32, hash: &String) -> Self {
let mut board = Vec::new();
for _ in 0..height {
let row = vec![Tile::Empty; width as usize];
board.push(row);
}
Level {
width,
height,
board,
tile_size: 16,
rooms: Vec::new(),
hash: hash.clone()
}
}
// note that this is now public
pub fn add_room(&mut self, room: &Room) {
for row in 0..room.height {
for col in 0..room.width {
let y = (room.y + row) as usize;
let x = (room.x + col) as usize;
self.board[y][x] = Tile::Walkable;
}
}
self.rooms.push(*room);
}
}
impl fmt::Display for Level {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
for row in 0..self.height as usize {
for col in 0..self.width as usize {
write!(f, "{} ", self.board[row][col])?
}
write!(f, "\n")?
}
Ok(())
}
}Finally, update main.rs so that the level we create is a RoomsCorridor rather than Level directly:
extern crate rand;
extern crate sha2;
#[macro_use]
extern crate arrayref;
#[macro_use]
extern crate serde_derive;
extern crate serde;
extern crate serde_json;
extern crate clap;
mod room;
mod level;
mod draw;
// declare the roomscorridors module
mod roomscorridors;
use sha2::{ Sha256, Digest };
use rand::prelude::*;
use rand::distributions::Alphanumeric;
use clap::{ App, Arg };
use draw::{ draw };
// use the roomscorridors module
use roomscorridors::{ RoomsCorridors };
fn create_hash(text: &str) -> String {
let mut hasher = Sha256::default();
hasher.input(text.as_bytes());
format!("{:x}", hasher.result())
}
fn main() {
let matches = App::new("Dungeon")
.version("1.0")
.author("James Baum <@whostolemyhat>")
.arg(Arg::with_name("text")
.short("t")
.long("text")
.takes_value(true)
.help("A string to hash and use as a seed"))
.arg(Arg::with_name("seed")
.short("s")
.long("seed")
.takes_value(true)
.help("An existing seed. Must be 32 characters"))
.get_matches();
let seed: String = match matches.value_of("seed") {
Some(text) => {
if text.chars().count() < 32 {
panic!("Seed must be 32 characters long. Use -t option to create a new seed.")
}
text.to_string()
},
None => {
match matches.value_of("text") {
Some(text) => create_hash(&text),
None => create_hash(&thread_rng().sample_iter(&Alphanumeric).take(32).collect::<String>())
}
}
};
let seed_u8 = array_ref!(seed.as_bytes(), 0, 32);
let mut rng: StdRng = SeedableRng::from_seed(*seed_u8);
// This is now RoomsCorridors::new
let level = RoomsCorridors::new(48, 40, &seed, &mut rng);
// but printing, drawing and serialising still work!
println!("{}", level);
draw(&level, ".", "level").unwrap();
let serialised = serde_json::to_string(&level).unwrap();
println!("{}", serialised);
}Run the project with cargo run and you should see the same output as before:
Compiling dungeon-example v0.1.0
Finished dev [unoptimized + debuginfo] target(s) in 3.19s
Running `target/debug/dungeon-example`
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0
0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0
0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0
0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0
0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 0 0
0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0Binary space partition
Right, with the refactoring done, we can get on with the binary space partition (BSP) algorithm. In a new file, bsp.rs, we need to create a struct which will represent each area of the map - these are usually known as leaves in other implemtations of BSP. Each leaf needs a position within the overall level as well as width and height, and may contain two child leaves since we will split the current leaf in two if it is large enough. The leaf may also have a room - only the end child leaves will have rooms, not the larger parent leaves which contain them. Hopefully that makes sense, anyway onwards! Create bsp.rs:
// bsp.rs
use room::Room;
struct Leaf {
min_size: i32,
x: i32,
y: i32,
width: i32,
height: i32,
left_child: Option<Leaf>,
right_child: Option<Leaf>,
room: Option<Room>
}The left_child, right_child and room attributes are all wrapped in Option since they may or may not be added to each leaf: a leaf will only have child leaves if it is large enough to split, and will only contain a room if it doesn't have any child leaves.
If you try to build the project now, you'll get an error:
This happens because Rust tries to allocate structs on the stack, but since each Leaf can contain another Leaf there's no way for Rust to know how much memory to allocate up-front. Fortunately it's fairly simple to fix this error (and the compiler even gives you tips) - we can wrap each child leaf in a Box which tells Rust to use the heap to allocate child structs. This fixes our problem since the heap doesn't need to know the size of our struct up-front since there isn't a limit on heap size like there is with the stack. Have a read here for more about the stack and heap.
// bsp.rs
use room::Room;
struct Leaf {
min_size: i32,
x: i32,
y: i32,
width: i32,
height: i32,
left_child: Option<Box<Leaf>,
right_child: Option<Box<Leaf>,
room: Option<Room>
}Now the compiler is happier, we can move on to implementing Leaf's methods: we need to be able to create a Leaf and then split it into smaller leaves.
// bsp.rs
use rand::{ Rng, StdRng};
...
impl Leaf {
pub fn new(x: i32, yL i32, width: i32, height: i32, min_size: i32) -> Self {
Leaf {
min_size,
x,
y,
width,
height,
left_child: None,
right_child: None,
room: None
}
}
fn split(&mut self, rng: &mut StdRng) -> bool {
// if width >25% height, split vertically
// if height >25% width, split horz
// otherwise random
// this is the random choice
let mut split_horz = match rng.gen_range(0, 2) {
0 => false,
_ => true
};
// then override with width/height check
if self.width > self.height & (self.width as f32 / self.height as f32) >= 1.25 {
split_horz = false;
} else if self.height > self.width & (self.height as f32 / self.width as f32) >= 1.25 {
split_horz = true;
}
let max = match split_horz {
true => self.height - self.min_size,
false => self.width - self.min_size
};
// the current area is small enough, so stop splitting
if max <= self.min_size {
return false;
}
let split_pos = rng.gen_range(self.min_size, max);
if split_horz {
self.left_child = Some(Box::new(Leaf::new(self.x, self.y, self.width, split_pos, self.min_size)));
self.right_child = Some(Box::new(Leaf::new(self.x, self.y + split_pos, self.width, self.height - split_pos, self.min_size)));
} else {
self.left_child = Some(Box::new(Leaf::new(self.x, self.y, split_pos, self.height, self.min_size)));
self.right_child = Some(Box::new(Leaf::new(self.x + split_pos, self.y, self.width - split_pos, self.height, self.min_size)));
}
true
}
}new is a helper function to make creating leaves a bit easier, while split is the function which will take care of splitting each leaf into child leaves. split will be called recursively, so returns a bool so we can check whether or not to continue splitting the leaf. We also need a function which will start splitting leaves - generate - and a way to check whether the current leaf hasn't already been split, is_leaf.
impl Leaf {
...
fn is_leaf(&self) -> bool {
match self.left_child {
None => match self.right_child {
None => true,
Some(_) => false,
},
Some(_) => false
}
}
fn generate(&mut self, rng: &mut StdRng) {
if self.is_leaf() {
if self.split(rng) {
self.left_child.as_mut().unwrap().generate(rng);
self.right_child.as_mut().unwrap().generate(rng);
}
}
}
}is_leaf checks whether a leaf already has a left or right child; if so, we won't continue splitting it since we will have already visited the leaf to split it in generate. The generate function tries to split the current leaf, and if it was successful, tries to split the new child leaves. When the child leaves are small enough, the splitting will return false and we stop generating leaves.
The next step is to create rooms in our leaves so we actually have something to look at. We need to add a `create_rooms` function to the Leaf:
// bsp.rs
...
impl Leaf {
...
fn create_rooms(&mut self, rng: &mut StdRng, rooms: &mut Vec<Room>) {
if let Some(ref mut room) = self.left_child {
room.as_mut().create_rooms(rng, rooms);
};
if let Some(ref mut room) = self.right_child {
room.as_mut().create_rooms(rng, rooms);
};
let min_room_width = 4;
let min_room_height = 3;
// if last level, add a room
if self.is_leaf() {
let width = rng.gen_range(min_room_width, self.width);
let height = rng.gen_range(min_room_height, self.height);
let x = rng.gen_range(0, self.width - width);
let y = rng.gen_range(0, self.height - height);
self.room = Some(Room::new(x + self.x, y + self.y, width, height));
rooms.push(self.room.unwrap());
}
}
}We check that the current leaf has any children - if so, then we call create_rooms on those leaves; there's also a check to see if the current leaf is in fact the lowest level (ie doesn't have any child leaves). This is because we want the rooms to be added to the smallest leaves, otherwise we could end up placing rooms in the parent leaves which cover large areas and there would have been no point splitting the level in the first place.
We also pass in a vector of rooms into the function - this will be used to update the level with the rooms we create (Note: yep, this is duplicating the rooms so makes the Leaf struct fairly pointless to keep around; don't worry, we'll refactor this in a bit!).
The if let syntax is a nice shorthand for match when the non-matching arm will do nothing. In our case, it's equivalent to
fn create_rooms(&mut self, rng: &mut StdRng, rooms: &mut Vec<Room>) {
match self.left_child {
Some(ref mut room) => room.as_mut().create_rooms(rng, rooms),
_ => ()
};
...which is a bit noisy. This is useful since match patterns are exhaustive in Rust, i.e. you have to have a match for every possible pattern. _ => () is a wildcard match: _ matches everything not already listed, and () is an empty block which does nothing. More on if let on Rust by Example.
Finally, we need a way to actually create the leaves and display the rooms created - add a BspLevel struct which has the same signature as the RoomsCorridors struct:
// bsp.rs
...
pub struct BspLevel {
level: Level
}
impl BspLevel {
pub fn new(width: i32, height: i32, hash: &String, rng: &mut StdRng) -> Level {
let level = Level::new(width, height, hash);
let mut map = BspLevel {
level
};
map.place_rooms(rng);
map.level
}
fn place_rooms(&mut self, rng: &mut StdRng) {
let mut root = Leaf::new(0, 0, self.level.width, self.level.height, 8);
root.generate(rng);
let mut rooms = vec![];
root.create_rooms(rng, &mut rooms);
for room in rooms {
self.level.add_room(&room);
}
}
}This has a new function which creates and returns a level; it also has place_rooms which triggers the binary space partition algorithm, creates rooms in the leaves then updates the level with each room.
And now, update main.rs to call it:
// main.rs
...
use bsp::{ BspLevel };
fn main() {
...
let seed_u8 = array_ref!(seed.as_bytes(), 0, 32);
let mut rng: StdRng = SeedableRng::from_seed(*seed_u8);
// don't call RoomsCorridors
// let level = RoomsCorridors::new(48, 40, &seed, &mut rng);
// instead BspLevel
let level = BspLevel::new(48, 40, &seed, &mut rng);
println!("{}", level);
draw(&level, ".", "level").unwrap();
let serialised = serde_json::to_string(&level).unwrap();
println!("{}", serialised);
}Right, run the programme and you will now see rooms in a level which have been created with the binary space partition algorithm:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1(I've updated the impl Display in level.rs so empty tiles are printed as spaces, so it's clearer what's happening).
Full bsp.rs:
use level::Level;
use room::Room;
use rand::{ Rng, StdRng};
pub struct BspLevel {
level: Level
}
impl BspLevel {
pub fn new(width: i32, height: i32, hash: &String, rng: &mut StdRng) -> Level {
let level = Level::new(width, height, hash);
let mut map = BspLevel {
level
};
map.place_rooms(rng);
map.level
}
fn place_rooms(&mut self, rng: &mut StdRng) {
let mut root = Leaf::new(0, 0, self.level.width, self.level.height, 8);
root.generate(rng);
let mut rooms = vec![];
root.create_rooms(rng, &mut rooms);
for room in rooms {
self.level.add_room(&room);
}
}
}
struct Leaf {
min_size: i32,
x: i32,
y: i32,
width: i32,
height: i32,
left_child: Option<Box<Leaf>,
right_child: Option<Box<Leaf>,
room: Option<Room>
}
impl Leaf {
pub fn new(x: i32, y: i32, width: i32, height: i32, min_size: i32) -> Self {
Leaf {
min_size,
x,
y,
width,
height,
left_child: None,
right_child: None,
room: None
}
}
fn is_leaf(&self) -> bool {
match self.left_child {
None => match self.right_child {
None => true,
Some(_) => false,
},
Some(_) => false
}
}
fn generate(&mut self, rng: &mut StdRng) {
if self.is_leaf() {
if self.split(rng) {
self.left_child.as_mut().unwrap().generate(rng);
self.right_child.as_mut().unwrap().generate(rng);
}
}
}
fn split(&mut self, rng: &mut StdRng) -> bool {
// if width >25% height, split vertically
// if height >25% width, split horz
// otherwise random
// this is the random choice
let mut split_horz = match rng.gen_range(0, 2) {
0 => false,
_ => true
};
// then override with width/height check
if self.width > self.height & (self.width as f32 / self.height as f32) >= 1.25 {
split_horz = false;
} else if self.height > self.width & (self.height as f32 / self.width as f32) >= 1.25 {
split_horz = true;
}
let max = match split_horz {
true => self.height - self.min_size,
false => self.width - self.min_size
};
// the current area is small enough, so stop splitting
if max <= self.min_size {
return false;
}
let split_pos = rng.gen_range(self.min_size, max);
if split_horz {
self.left_child = Some(Box::new(Leaf::new(self.x, self.y, self.width, split_pos, self.min_size)));
self.right_child = Some(Box::new(Leaf::new(self.x, self.y + split_pos, self.width, self.height - split_pos, self.min_size)));
} else {
self.left_child = Some(Box::new(Leaf::new(self.x, self.y, split_pos, self.height, self.min_size)));
self.right_child = Some(Box::new(Leaf::new(self.x + split_pos, self.y, self.width - split_pos, self.height, self.min_size)));
}
true
}
fn create_rooms(&mut self, rng: &mut StdRng, rooms: &mut Vec<Room>) {
if let Some(ref mut room) = self.left_child {
room.as_mut().create_rooms(rng, rooms);
};
if let Some(ref mut room) = self.right_child {
room.as_mut().create_rooms(rng, rooms);
};
let min_room_width = 4;
let min_room_height = 3;
// if last level, add a room
if self.is_leaf() {
let width = rng.gen_range(min_room_width, self.width);
let height = rng.gen_range(min_room_height, self.height);
let x = rng.gen_range(0, self.width - width);
let y = rng.gen_range(0, self.height - height);
self.room = Some(Room::new(x + self.x, y + self.y, width, height));
rooms.push(self.room.unwrap());
}
}
}Add corridors
We now have a lot of rooms, nicely spaced around the level, but we need to connect them with corridors so it's actually usable as a level. To make sure all rooms are connected, we need to work our way through the tree and connect all the pairs of leaves:
- Start at the root leaf
- If the leaf has a left and right child, connect them with a corridor
- Repeat for each left and right child pair of every leaf you check.
This means that all pairs of leaves are connected, not just the ones containing rooms, to ensure that it's possible to get to every room.
x
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1
1 1
1 1 // root
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1
1 1 1
1 1 1
1 x x x x 1 x x x 1 // connect the first pair of leaves
1 1 1
1 1 1
1 1 1 x
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1
1 1 1
1 1 1
1 x x x x 1 x x x 1
1 1 x 1
1 x 1 x 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 x 1 x 1
1 x 1 x 1
1 x 1 1
1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1and so on.
The first thing we need is to add a method to Leaf so we can get a room: this method will check the current leaf and all children until it finds a room. We'll need this to be able to pick start and end points for the corridors:
// bsp.rs
...
impl Leaf {
...
fn get_room(&self) -> Option<Room> {
if self.is_leaf() {
return self.room;
}
let mut left_room: Option<Room> = None;
let mut right_room: Option<Room> = None;
if let Some(ref room) = self.left_child {
left_room = room.get_room();
}
if let Some(ref room) = self.right_child {
right_room = room.get_room();
}
match (left_room, right_room) {
(None, None) => None,
(Some(room), _) => Some(room),
(_, Some(room)) => Some(room),
}
}
}If the current leaf being checked is at the end of a branch (is_leaf is true) then we know it has a room (set in create_rooms) so can return it; otherwise, we check if the leaf has any children and if so check those for a room. The final match statement is the return value for the function (it doesn't have a semi-colon after it) and is checking if there are any rooms at all in the child nodes. get_room returns an Option, so we check if either left_room or right_room has a value, and if either does, return it. _ is Rust syntax which means "I'm ignoring this value", so (Some(room), _) matches a tuple which has a room value in the first position and anything else in the second position.
Next, add functions which create corridors. These don't have to be in the impl Leaf block since they're effectively static functions and don't rely on a single instance of a Leaf.
// bsp.rs
...
impl Leaf {
...
}
// corridors are just very narrow rooms
fn create_corridors(rng: &mut StdRng, left: &mut Box<Leaf>, right: &mut Box<Leaf>, corridors: &mut Vec<Room>) {
if let (Some(left_room), Some(right_room)) = (left.get_room(), right.get_room()) {
// pick point in each room
let left_point = (rng.gen_range(left_room.x, left_room.x + left_room.width), rng.gen_range(left_room.y, left_room.y + left_room.height));
let right_point = (rng.gen_range(right_room.x, right_room.x + right_room.width), rng.gen_range(right_room.y, right_room.y + right_room.height));
match rng.gen_range(0, 2) {
0 => {
match left_point.0 <= right_point.0 {
true => corridors.push(horz_corridor(left_point.0, left_point.1, right_point.0)),
false => corridors.push(horz_corridor(right_point.0, left_point.1, left_point.0))
}
match left_point.1 <= right_point.1 {
true => corridors.push(vert_corridor(right_point.0, left_point.1, right_point.1)),
false => corridors.push(vert_corridor(right_point.0, right_point.1, left_point.1))
}
}
_ => {
match left_point.1 <= right_point.1 {
true => corridors.push(vert_corridor(left_point.0, left_point.1, right_point.1)),
false => corridors.push(vert_corridor(left_point.0, right_point.1, left_point.1))
}
match left_point.0 <= right_point.0 {
true => corridors.push(horz_corridor(left_point.0, right_point.1, right_point.0)),
false => corridors.push(horz_corridor(right_point.0, right_point.1, left_point.0))
}
}
}
};
}
fn horz_corridor(start_x: i32, start_y: i32, end_x: i32) -> Room {
Room::new(start_x, start_y, (end_x - start_x) + 1, 1)
}
fn vert_corridor(start_x: i32, start_y: i32, end_y: i32) -> Room {
Room::new(start_x, start_y, 1, end_y - start_y)
}These functions are very similar to the ones in RoomsCorridors, except instead of updating the level directly, they create new rooms to which are one tile wide to represent corridors, and then update a vector with the corridors.
create_corridors is called from within create_rooms - we're already checking each leaf in there, so just hook in and start creating corridors:
// bsp.rs
...
fn create_rooms(&mut self, rng: &mut StdRng, rooms: &mut Vec<Room>) {
if let Some(ref mut room) = self.left_child {
room.as_mut().create_rooms(rng, rooms);
};
if let Some(ref mut room) = self.right_child {
room.as_mut().create_rooms(rng, rooms);
};
let min_room_width = 4;
let min_room_height = 3;
if self.is_leaf() {
let width = rng.gen_range(min_room_width, self.width);
let height = rng.gen_range(min_room_height, self.height);
let x = rng.gen_range(0, self.width - width);
let y = rng.gen_range(0, self.height - height);
self.room = Some(Room::new(x + self.x, y + self.y, width, height));
rooms.push(self.room.unwrap());
}
// add call to create_corridors
if let (Some(ref mut left), Some(ref mut right)) = (&mut self.left_child, &mut self.right_child) {
create_corridors(rng, left, right, rooms);
};
}
...Now when we run with cargo run, we have corridors joining up each room:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1
1 1
1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1Full bsp.rs so far:
use level::Level;
use room::Room;
use rand::{ Rng, StdRng};
pub struct BspLevel {
level: Level
}
impl BspLevel {
pub fn new(width: i32, height: i32, hash: &String, rng: &mut StdRng) -> Level {
let level = Level::new(width, height, hash);
let mut map = BspLevel {
level
};
map.place_rooms(rng);
map.level
}
fn place_rooms(&mut self, rng: &mut StdRng) {
let mut root = Leaf::new(0, 0, self.level.width, self.level.height, 8);
root.generate(rng);
let mut rooms = vec![];
root.create_rooms(rng, &mut rooms);
for room in rooms {
self.level.add_room(&room);
}
}
}
struct Leaf {
min_size: i32,
x: i32,
y: i32,
width: i32,
height: i32,
left_child: Option<Box<Leaf>,
right_child: Option<Box<Leaf>,
room: Option<Room>
}
impl Leaf {
pub fn new(x: i32, y: i32, width: i32, height: i32, min_size: i32) -> Self {
Leaf {
min_size,
x,
y,
width,
height,
left_child: None,
right_child: None,
room: None
}
}
fn is_leaf(&self) -> bool {
match self.left_child {
None => match self.right_child {
None => true,
Some(_) => false,
},
Some(_) => false
}
}
fn generate(&mut self, rng: &mut StdRng) {
if self.is_leaf() {
if self.split(rng) {
self.left_child.as_mut().unwrap().generate(rng);
self.right_child.as_mut().unwrap().generate(rng);
}
}
}
fn split(&mut self, rng: &mut StdRng) -> bool {
// if width >25% height, split vertically
// if height >25% width, split horz
// otherwise random
// this is the random choice
let mut split_horz = match rng.gen_range(0, 2) {
0 => false,
_ => true
};
// then override with width/height check
if self.width > self.height & (self.width as f32 / self.height as f32) >= 1.25 {
split_horz = false;
} else if self.height > self.width & (self.height as f32 / self.width as f32) >= 1.25 {
split_horz = true;
}
let max = match split_horz {
true => self.height - self.min_size,
false => self.width - self.min_size
};
// the current area is small enough, so stop splitting
if max <= self.min_size {
return false;
}
let split_pos = rng.gen_range(self.min_size, max);
if split_horz {
self.left_child = Some(Box::new(Leaf::new(self.x, self.y, self.width, split_pos, self.min_size)));
self.right_child = Some(Box::new(Leaf::new(self.x, self.y + split_pos, self.width, self.height - split_pos, self.min_size)));
} else {
self.left_child = Some(Box::new(Leaf::new(self.x, self.y, split_pos, self.height, self.min_size)));
self.right_child = Some(Box::new(Leaf::new(self.x + split_pos, self.y, self.width - split_pos, self.height, self.min_size)));
}
true
}
fn create_rooms(&mut self, rng: &mut StdRng, rooms: &mut Vec<Room>) {
if let Some(ref mut room) = self.left_child {
room.as_mut().create_rooms(rng, rooms);
};
if let Some(ref mut room) = self.right_child {
room.as_mut().create_rooms(rng, rooms);
};
let min_room_width = 4;
let min_room_height = 3;
// if last level, add a room
if self.is_leaf() {
let width = rng.gen_range(min_room_width, self.width);
let height = rng.gen_range(min_room_height, self.height);
let x = rng.gen_range(0, self.width - width);
let y = rng.gen_range(0, self.height - height);
self.room = Some(Room::new(x + self.x, y + self.y, width, height));
rooms.push(self.room.unwrap());
}
if let (Some(ref mut left), Some(ref mut right)) = (&mut self.left_child, &mut self.right_child) {
create_corridors(rng, left, right, rooms);
};
}
fn get_room(&self) -> Option<Room> {
if self.is_leaf() {
return self.room;
}
let mut left_room: Option<Room> = None;
let mut right_room: Option<Room> = None;
if let Some(ref room) = self.left_child {
left_room = room.get_room();
}
if let Some(ref room) = self.right_child {
right_room = room.get_room();
}
match (left_room, right_room) {
(None, None) => None,
(Some(room), _) => Some(room),
(_, Some(room)) => Some(room),
}
}
}
// corridors are just very narrow rooms
fn create_corridors(rng: &mut StdRng, left: &mut Box<Leaf>, right: &mut Box<Leaf>, corridors: &mut Vec<Room>) {
if let (Some(left_room), Some(right_room)) = (left.get_room(), right.get_room()) {
// pick point in each room
let left_point = (rng.gen_range(left_room.x, left_room.x + left_room.width), rng.gen_range(left_room.y, left_room.y + left_room.height));
let right_point = (rng.gen_range(right_room.x, right_room.x + right_room.width), rng.gen_range(right_room.y, right_room.y + right_room.height));
match rng.gen_range(0, 2) {
0 => {
match left_point.0 <= right_point.0 {
true => corridors.push(horz_corridor(left_point.0, left_point.1, right_point.0)),
false => corridors.push(horz_corridor(right_point.0, left_point.1, left_point.0))
}
match left_point.1 <= right_point.1 {
true => corridors.push(vert_corridor(right_point.0, left_point.1, right_point.1)),
false => corridors.push(vert_corridor(right_point.0, right_point.1, left_point.1))
}
}
_ => {
match left_point.1 <= right_point.1 {
true => corridors.push(vert_corridor(left_point.0, left_point.1, right_point.1)),
false => corridors.push(vert_corridor(left_point.0, right_point.1, left_point.1))
}
match left_point.0 <= right_point.0 {
true => corridors.push(horz_corridor(left_point.0, right_point.1, right_point.0)),
false => corridors.push(horz_corridor(right_point.0, right_point.1, left_point.0))
}
}
}
};
}
fn horz_corridor(start_x: i32, start_y: i32, end_x: i32) -> Room {
Room::new(start_x, start_y, (end_x - start_x) + 1, 1)
}
fn vert_corridor(start_x: i32, start_y: i32, end_y: i32) -> Room {
Room::new(start_x, start_y, 1, end_y - start_y)
}Refactoring with iterators
As you may have noticed, our tree of leaves holds all the room information, which we then ignore to add to a separate vector of rooms instead. This is a bit silly, so let's change our code so we can iterate over each leaf instead of having a separate vector.
Implementing an iterator for a type is fairly simple in Rust - we just need to add an impl Iterator block with a next function. This means we'll end up with code similar to that in place_rooms at the moment, so we can write something like
for leaf in root {
self.level.add_room(&leaf.get_room());
}To make things simpler for us, we'll also create another structure which organises the child leaves to be iterated over:
// bsp.rs
...
struct LeafIterator<'a> {
current_node: Option<&'a Leaf>,
right_nodes: Vec<&'a Leaf>
}
impl<'a> LeafIterator<'a> {
fn new(root: &'a Leaf) -> LeafIterator<'a> {
let mut iter = LeafIterator {
right_nodes: vec![],
current_node: None
};
iter.add_subtrees(root);
iter
}
// set the current node to the one provided
// and add any child leaves to the node vec
fn add_subtrees(&mut self, node: &'a Leaf) {
if let Some(ref left) = node.left_child {
self.right_nodes.push(&*left);
}
if let Some(ref right) = node.right_child {
self.right_nodes.push(&*right);
}
self.current_node = Some(node);
}
}The LeafIterator struct holds a reference to the current node we're looking at and a vector of all the other leaves in the tree structure. This makes things far simpler when creating an iterator, since we can just move along right_nodes to get the next leaf. In LeafIterator::new, we create a new LeafIterator then call add_subtrees to add the left and right child leaves of the root to the right_nodes vector, which will be used in the iterator.
There are a lot of lifetime annotations in the LeafIterator - the <'a> or &'. These are needed since we're borrowing leaves from the tree we're creating the LeafIterator from, and they tell Rust that the thing we're borrowing won't be destroyed while we're still trying to use the borrowed value. This just means that we'll create a tree structure, then won't delete it while trying to iterate over it, which would cause all kinds of problems. We could have created an iterator which took the values rather than borrowed them, so we wouldn't have to deal with lifetimes. However, this would mean that as soon as we called the iterator, the tree would be used up and we wouldn't be able to use it directly any more - these are known as consuming iterators, as opposed to the non-consuming one we're creating. There are more lifetime examples on Rust by Example.
Next, implement the Iterator trait for the LeafIterator struct:
// bsp.rs
...
impl<'a> Iterator for LeafIterator<'a> {
type Item = &'a Leaf;
fn next(&mut self) -> Option<Self::Item> {
let result = self.current_node.take();
if let Some(rest) = self.right_nodes.pop() {
self.add_subtrees(rest);
}
match result {
Some(leaf) => Some(&*leaf),
None => None
}
}
}Like above, this has lifetime annotations since it'll be using the borrowed values we set in LeafIterator. The type Item = &'a Leaf; line is an associated type and tells the compiler what the iterator returns - in this case a borrowed Leaf, so it also needs a lifetime. The next function reads the current node from the LeafIterator, then checks if there are any more nodes left to iterate through. If so, it then adds the child leaves of the next node to the list of leaves to check by calling add_subtrees. Finally, it returns the current leaf if it exists.
More infomation on iterators on Rust by Example.
Finally, we need to add an iter method to Leaf so we can create a LeafIterator and iterate through the leaves in place_rooms:
// bsp.rs
...
impl BspLevel {
...
fn place_rooms(&mut self, rng: &mut StdRng) {
let mut root = Leaf::new(0, 0, self.level.width, self.level.height, 8);
root.generate(rng);
let mut rooms = vec![];
root.create_rooms(rng, &mut rooms);
for leaf in root.iter() {
if let Some(room) = leaf.get_room() {
self.level.add_room(&room);
}
}
// corridors are still added to the rooms vector
// so we need to check it to draw corridors
for corridor in rooms {
self.level.add_room(&corridor);
}
}
}
...
impl Leaf {
...
fn create_rooms(&mut self, rng: &mut StdRng, rooms: &mut Vec<Room>) {
if let Some(ref mut room) = self.left_child {
room.as_mut().create_rooms(rng, rooms);
};
if let Some(ref mut room) = self.right_child {
room.as_mut().create_rooms(rng, rooms);
};
let min_room_width = 4;
let min_room_height = 3;
// if last level, add a room
if self.is_leaf() {
let width = rng.gen_range(min_room_width, self.width);
let height = rng.gen_range(min_room_height, self.height);
let x = rng.gen_range(0, self.width - width);
let y = rng.gen_range(0, self.height - height);
self.room = Some(Room::new(x + self.x, y + self.y, width, height));
// remove rooms.push()
}
if let (Some(ref mut left), Some(ref mut right)) = (&mut self.left_child, &mut self.right_child) {
create_corridors(rng, left, right, rooms);
};
}
...
fn iter(&self) -> LeafIterator {
LeafIterator::new(&self)
}
}We've stopped adding rooms in create_rooms to the rooms vector created in place_rooms, and are now iterating over the tree structure to get the rooms directly in place_rooms. Run the project again and you should still see the same rooms:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1
1 1
1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1Refactor corridors
So, we haven't got rid of the rooms vector entirely, since corridors are still added to it, and we're now iterating over all the leaves and the corridors separately, which is a bit silly. Let's refactor the Leaf to hold the corridor information, so we'll be able to access it when we iterate over all the leaves in place_rooms.
// bsp.rs
...
struct Leaf {
min_size: i32,
x: i32,
y: i32,
width: i32,
height: i32,
left_child: Option<Box<Leaf>,
right_child: Option<Box<Leaf>,
room: Option<Room>,
corridors: Vec<Room>
}
impl Leaf {
pub fn new(x: i32, y: i32, width: i32, height: i32, min_size: i32) -> Self {
Leaf {
min_size,
x,
y,
width,
height,
left_child: None,
right_child: None,
room: None,
corridors: vec![]
}
}
...
// remove `rooms` from the params
fn create_rooms(&mut self, rng: &mut StdRng) {
if let Some(ref mut room) = self.left_child {
room.as_mut().create_rooms(rng); // remove `rooms`
};
if let Some(ref mut room) = self.right_child {
room.as_mut().create_rooms(rng); // remove `rooms`
};
let min_room_width = 4;
let min_room_height = 3;
// if last level, add a room
if self.is_leaf() {
let width = rng.gen_range(min_room_width, self.width);
let height = rng.gen_range(min_room_height, self.height);
let x = rng.gen_range(0, self.width - width);
let y = rng.gen_range(0, self.height - height);
self.room = Some(Room::new(x + self.x, y + self.y, width, height));
}
if let (Some(ref mut left), Some(ref mut right)) = (&mut self.left_child, &mut self.right_child) {
create_corridors(rng, left, right); // remove `rooms`
};
}
}
...
// remove `corridors` from params
fn create_corridors(rng: &mut StdRng, left: &mut Box<Leaf>, right: &mut Box<Leaf>) {
if let (Some(left_room), Some(right_room)) = (left.get_room(), right.get_room()) {
// pick point in each room
let left_point = (rng.gen_range(left_room.x, left_room.x + left_room.width), rng.gen_range(left_room.y, left_room.y + left_room.height));
let right_point = (rng.gen_range(right_room.x, right_room.x + right_room.width), rng.gen_range(right_room.y, right_room.y + right_room.height));
// instead of pushing to `corridors`, add to `left.corridors`
match rng.gen_range(0, 2) {
0 => {
match left_point.0 <= right_point.0 {
true => left.corridors.push(horz_corridor(left_point.0, left_point.1, right_point.0)),
false => left.corridors.push(horz_corridor(right_point.0, left_point.1, left_point.0))
}
match left_point.1 <= right_point.1 {
true => left.corridors.push(vert_corridor(right_point.0, left_point.1, right_point.1)),
false => left.corridors.push(vert_corridor(right_point.0, right_point.1, left_point.1))
}
}
_ => {
match left_point.1 <= right_point.1 {
true => left.corridors.push(vert_corridor(left_point.0, left_point.1, right_point.1)),
false => left.corridors.push(vert_corridor(left_point.0, right_point.1, left_point.1))
}
match left_point.0 <= right_point.0 {
true => left.corridors.push(horz_corridor(left_point.0, right_point.1, right_point.0)),
false => left.corridors.push(horz_corridor(right_point.0, right_point.1, left_point.0))
}
}
}
};
}and update BspLevel:
// bsp.rs
...
impl BspLevel {
...
fn place_rooms(&mut self, rng: &mut StdRng) {
let mut root = Leaf::new(0, 0, self.level.width, self.level.height, 8);
root.generate(rng);
// don't need a vec any more
// let mut rooms = vec![];
root.create_rooms(rng); // remove `rooms`
for leaf in root.iter() {
// check if the current leaf is the child
// before checking for room
if leaf.is_leaf() {
if let Some(room) = leaf.get_room() {
self.level.add_room(&room);
}
}
// loop over the new corridors attribute
// and add any to the level
for corridor in &leaf.corridors {
self.level.add_room(&corridor);
}
}
// don't need this!
// for corridor in rooms {
// self.level.add_room(&corridor);
// }
}
}In create_corridors, we're now pushing any created corridors into the leaf's corridors vector rather than a stand-alone one created in place_rooms. We're pushing it into the left child of the pair of rooms - it doesn't really matter which child leaf they get added to in our case, since we're looping through every leaf anyway in place_rooms. We've also updated that loop in place_rooms to add any corridors in the leaf to the level, and checking whether the current leaf is the end child before calling get_room, since get_room recursively calls itself. This just saves a few loops: since we're going through every leaf anyway, there's no point trying to get the room in each loop in place_rooms.
Run again with cargo run, and you should still have a working level creator:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1
1 1
1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1Switch between algorithms
The final thing to do is to add a command-line flag so we can easily switch between algorithms. In main.rs, we'll add another argument to the existing ones, this time taking an option from an array, and then use that to switch between algorithms:
// main.rs
...
use roomscorridors::{ RoomsCorridors };
use bsp::{ BspLevel };
...
// enum to match upon
enum Algorithm {
Bsp,
Rooms
}
fn main() {
let matches = App::new("Dungeon")
.version("1.0")
.author("James Baum <@whostolemyhat>")
.arg(Arg::with_name("text")
.short("t")
.long("text")
.takes_value(true)
.help("A string to hash and use as a seed"))
.arg(Arg::with_name("seed")
.short("s")
.long("seed")
.takes_value(true)
.help("An existing seed. Must be 32 characters"))
// add a new flag
.arg(Arg::with_name("algo")
.short("a")
.long("algorithm")
.takes_value(true)
.possible_values(&["rooms", "bsp"])
.default_value("rooms")
.help("The type of procedural algorithm to use"))
.get_matches();
let seed: String = match matches.value_of("seed") {
Some(text) => {
if text.chars().count() < 32 {
panic!("Seed must be 32 characters long. Use -t option to create a new seed.")
}
text.to_string()
},
None => {
match matches.value_of("text") {
Some(text) => create_hash(&text),
None => create_hash(&thread_rng().sample_iter(&Alphanumeric).take(32).collect::<String>())
}
}
};
let seed_u8 = array_ref!(seed.as_bytes(), 0, 32);
let mut rng: StdRng = SeedableRng::from_seed(*seed_u8);
// match on the new flag. since we've specified possible values,
// the wildcard match is unreachable so we don't need to fill it in
let method = match matches.value_of("algo").expect("Default algorithm not set") {
"bsp" => Algorithm::Bsp,
"rooms" => Algorithm::Rooms,
_ => unreachable![] // macro telling the compiler that this branch should never run
};
// you could add more args to alter these too!
let board_width = 48;
let board_height = 40;
// switch between different algorithms
let level = match method {
Algorithm::Rooms => RoomsCorridors::new(board_width, board_height, &seed, &mut rng),
Algorithm::Bsp => BspLevel::new(board_width, board_height, &seed, &mut rng)
};
// output. you could add more flags to control what gets shown
println!("{}", level);
// draw(&level, ".", "level").unwrap();
// let serialised = serde_json::to_string(&level).unwrap();
// println!("{}", serialised);
}Now run with cargo run -- -a bsp or cargo run -- -a rooms to switch between the algorithms! Here's the code for bsp.rs and main.rs - for the entire project, look on Github here under the 'bsp' tag.
// bsp.rs
use level::Level;
use room::Room;
use rand::{ Rng, StdRng};
pub struct BspLevel {
level: Level
}
impl BspLevel {
pub fn new(width: i32, height: i32, hash: &String, rng: &mut StdRng) -> Level {
let level = Level::new(width, height, hash);
let mut map = BspLevel {
level
};
map.place_rooms(rng);
map.level
}
fn place_rooms(&mut self, rng: &mut StdRng) {
let mut root = Leaf::new(0, 0, self.level.width, self.level.height, 8);
root.generate(rng);
root.create_rooms(rng);
for leaf in root.iter() {
if leaf.is_leaf() {
if let Some(room) = leaf.get_room() {
self.level.add_room(&room);
}
}
for corridor in &leaf.corridors {
self.level.add_room(&corridor);
}
}
}
}
struct Leaf {
min_size: i32,
x: i32,
y: i32,
width: i32,
height: i32,
left_child: Option<Box<Leaf>,
right_child: Option<Box<Leaf>,
room: Option<Room>,
corridors: Vec<Room>
}
impl Leaf {
pub fn new(x: i32, y: i32, width: i32, height: i32, min_size: i32) -> Self {
Leaf {
min_size,
x,
y,
width,
height,
left_child: None,
right_child: None,
room: None,
corridors: vec![]
}
}
fn is_leaf(&self) -> bool {
match self.left_child {
None => match self.right_child {
None => true,
Some(_) => false,
},
Some(_) => false
}
}
fn generate(&mut self, rng: &mut StdRng) {
if self.is_leaf() {
if self.split(rng) {
self.left_child.as_mut().unwrap().generate(rng);
self.right_child.as_mut().unwrap().generate(rng);
}
}
}
fn split(&mut self, rng: &mut StdRng) -> bool {
// if width >25% height, split vertically
// if height >25% width, split horz
// otherwise random
// this is the random choice
let mut split_horz = match rng.gen_range(0, 2) {
0 => false,
_ => true
};
// then override with width/height check
if self.width > self.height & (self.width as f32 / self.height as f32) >= 1.25 {
split_horz = false;
} else if self.height > self.width & (self.height as f32 / self.width as f32) >= 1.25 {
split_horz = true;
}
let max = match split_horz {
true => self.height - self.min_size,
false => self.width - self.min_size
};
// the current area is small enough, so stop splitting
if max <= self.min_size {
return false;
}
let split_pos = rng.gen_range(self.min_size, max);
if split_horz {
self.left_child = Some(Box::new(Leaf::new(self.x, self.y, self.width, split_pos, self.min_size)));
self.right_child = Some(Box::new(Leaf::new(self.x, self.y + split_pos, self.width, self.height - split_pos, self.min_size)));
} else {
self.left_child = Some(Box::new(Leaf::new(self.x, self.y, split_pos, self.height, self.min_size)));
self.right_child = Some(Box::new(Leaf::new(self.x + split_pos, self.y, self.width - split_pos, self.height, self.min_size)));
}
true
}
fn create_rooms(&mut self, rng: &mut StdRng) {
if let Some(ref mut room) = self.left_child {
room.as_mut().create_rooms(rng);
};
if let Some(ref mut room) = self.right_child {
room.as_mut().create_rooms(rng);
};
let min_room_width = 4;
let min_room_height = 3;
// if last level, add a room
if self.is_leaf() {
let width = rng.gen_range(min_room_width, self.width);
let height = rng.gen_range(min_room_height, self.height);
let x = rng.gen_range(0, self.width - width);
let y = rng.gen_range(0, self.height - height);
self.room = Some(Room::new(x + self.x, y + self.y, width, height));
}
if let (Some(ref mut left), Some(ref mut right)) = (&mut self.left_child, &mut self.right_child) {
create_corridors(rng, left, right);
};
}
fn get_room(&self) -> Option<Room> {
if self.is_leaf() {
return self.room;
}
let mut left_room: Option<Room> = None;
let mut right_room: Option<Room> = None;
if let Some(ref room) = self.left_child {
left_room = room.get_room();
}
if let Some(ref room) = self.right_child {
right_room = room.get_room();
}
match (left_room, right_room) {
(None, None) => None,
(Some(room), _) => Some(room),
(_, Some(room)) => Some(room),
}
}
fn iter(&self) -> LeafIterator {
LeafIterator::new(&self)
}
}
// corridors are just very narrow rooms
fn create_corridors(rng: &mut StdRng, left: &mut Box<Leaf>, right: &mut Box<Leaf>) {
if let (Some(left_room), Some(right_room)) = (left.get_room(), right.get_room()) {
// pick point in each room
let left_point = (rng.gen_range(left_room.x, left_room.x + left_room.width), rng.gen_range(left_room.y, left_room.y + left_room.height));
let right_point = (rng.gen_range(right_room.x, right_room.x + right_room.width), rng.gen_range(right_room.y, right_room.y + right_room.height));
match rng.gen_range(0, 2) {
0 => {
match left_point.0 <= right_point.0 {
true => left.corridors.push(horz_corridor(left_point.0, left_point.1, right_point.0)),
false => left.corridors.push(horz_corridor(right_point.0, left_point.1, left_point.0))
}
match left_point.1 <= right_point.1 {
true => left.corridors.push(vert_corridor(right_point.0, left_point.1, right_point.1)),
false => left.corridors.push(vert_corridor(right_point.0, right_point.1, left_point.1))
}
}
_ => {
match left_point.1 <= right_point.1 {
true => left.corridors.push(vert_corridor(left_point.0, left_point.1, right_point.1)),
false => left.corridors.push(vert_corridor(left_point.0, right_point.1, left_point.1))
}
match left_point.0 <= right_point.0 {
true => left.corridors.push(horz_corridor(left_point.0, right_point.1, right_point.0)),
false => left.corridors.push(horz_corridor(right_point.0, right_point.1, left_point.0))
}
}
}
};
}
fn horz_corridor(start_x: i32, start_y: i32, end_x: i32) -> Room {
Room::new(start_x, start_y, (end_x - start_x) + 1, 1)
}
fn vert_corridor(start_x: i32, start_y: i32, end_y: i32) -> Room {
Room::new(start_x, start_y, 1, end_y - start_y)
}
struct LeafIterator<'a> {
current_node: Option<&'a Leaf>,
right_nodes: Vec<&'a Leaf>
}
impl<'a> LeafIterator<'a> {
fn new(root: &'a Leaf) -> LeafIterator<'a> {
let mut iter = LeafIterator {
right_nodes: vec![],
current_node: None
};
iter.add_subtrees(root);
iter
}
// set the current node to the one provided
// and add any child leaves to the node vec
fn add_subtrees(&mut self, node: &'a Leaf) {
if let Some(ref left) = node.left_child {
self.right_nodes.push(&*left);
}
if let Some(ref right) = node.right_child {
self.right_nodes.push(&*right);
}
self.current_node = Some(node);
}
}
impl<'a> Iterator for LeafIterator<'a> {
type Item = &'a Leaf;
fn next(&mut self) -> Option<Self::Item> {
let result = self.current_node.take();
if let Some(rest) = self.right_nodes.pop() {
self.add_subtrees(rest);
}
match result {
Some(leaf) => Some(&*leaf),
None => None
}
}
}extern crate rand;
extern crate sha2;
#[macro_use]
extern crate arrayref;
#[macro_use]
extern crate serde_derive;
extern crate serde;
extern crate serde_json;
extern crate clap;
mod room;
mod level;
mod draw;
mod roomscorridors;
mod bsp;
use sha2::{ Sha256, Digest };
use rand::prelude::*;
use rand::distributions::Alphanumeric;
use clap::{ App, Arg };
use draw::{ draw };
use roomscorridors::{ RoomsCorridors };
use bsp::{ BspLevel };
fn create_hash(text: &str) -> String {
let mut hasher = Sha256::default();
hasher.input(text.as_bytes());
format!("{:x}", hasher.result())
}
enum Algorithm {
Bsp,
Rooms
}
fn main() {
let matches = App::new("Dungeon")
.version("1.0")
.author("James Baum <@whostolemyhat>")
.arg(Arg::with_name("text")
.short("t")
.long("text")
.takes_value(true)
.help("A string to hash and use as a seed"))
.arg(Arg::with_name("seed")
.short("s")
.long("seed")
.takes_value(true)
.help("An existing seed. Must be 32 characters"))
.arg(Arg::with_name("algo")
.short("a")
.long("algorithm")
.takes_value(true)
.possible_values(&["rooms", "bsp"])
.default_value("rooms")
.help("The type of procedural algorithm to use"))
.get_matches();
let seed: String = match matches.value_of("seed") {
Some(text) => {
if text.chars().count() < 32 {
panic!("Seed must be 32 characters long. Use -t option to create a new seed.")
}
text.to_string()
},
None => {
match matches.value_of("text") {
Some(text) => create_hash(&text),
None => create_hash(&thread_rng().sample_iter(&Alphanumeric).take(32).collect::<String>())
}
}
};
let seed_u8 = array_ref!(seed.as_bytes(), 0, 32);
let mut rng: StdRng = SeedableRng::from_seed(*seed_u8);
let method = match matches.value_of("algo").expect("Default algorithm not set") {
"bsp" => Algorithm::Bsp,
"rooms" => Algorithm::Rooms,
_ => unreachable![]
};
let board_width = 48;
let board_height = 40;
let level = match method {
Algorithm::Rooms => RoomsCorridors::new(board_width, board_height, &seed, &mut rng),
Algorithm::Bsp => BspLevel::new(board_width, board_height, &seed, &mut rng)
};
println!("{}", level);
// draw(&level, ".", "level").unwrap();
// let serialised = serde_json::to_string(&level).unwrap();
// println!("{}", serialised);
}