path: root/src/lib.rs

#[macro_use]
extern crate stdweb;

use rand::{Rng, SeedableRng};

pub mod canvas;

type RoomId = u32;

#[derive(Debug)]
pub enum Error {
    OutOfBounds,
    MaximumIterations,
    NonEmpty,
    InvalidRoomId,
}


pub mod Direction {
    pub const UP: u8 = 1 << 0;
    pub const RIGHT: u8 = 1 << 1;
    pub const DOWN: u8 = 1 << 2;
    pub const LEFT: u8 = 1 << 3;

    #[derive(Debug)]
    pub enum Error {
        Underflow,
        Overflow,
    }

    pub fn opposite(dir: u8) -> u8 {
        match dir {
            UP => DOWN,
            RIGHT => LEFT,
            DOWN => UP,
            LEFT => RIGHT,
            _ => unreachable!()
        }
    }

    pub fn step_towards(dir: u8, point: (u32, u32)) -> Result<(u32, u32), Error> {
        let p = match dir { 
            UP => if point.1 > 0 { (point.0, point.1 - 1) } else { return Err(Error::Underflow) },
            RIGHT => (point.0 + 1, point.1),
            DOWN =>  (point.0, point.1 + 1),
            LEFT => if point.0 > 0 { (point.0 - 1, point.1) } else { return Err(Error::Underflow) },
            _ => unreachable!()

        };
        Ok(p)
    }
            
}

pub struct RoomDescription {
    width: u32,
    height: u32,
    data: Vec<u32>,
}

pub trait Region<T> {
    fn width(&self) -> u32;
    fn height(&self) -> u32;
    fn set(&mut self, x: u32, y: u32, value: T) -> Result<(), Error>;
    fn get(&self, x: u32, y: u32) -> Result<&T, Error>;
    fn get_mut(&mut self, x: u32, y: u32) -> Result<&mut T,  Error>;
}

pub struct VecRegion<T> {
    inner: Vec<T>,
    width: u32,
    height: u32,
}

impl<T> Region<T> for VecRegion<T> {
    fn width(&self) -> u32 {
        self.width
    }

    fn height(&self) -> u32 {
        self.height
    }

    fn set(&mut self, x: u32, y: u32, value: T) -> Result<(), Error> {
        if x >= self.width || y >= self.height {
            return Err(Error::OutOfBounds);
        }

        self.inner[(y * self.width + x) as usize] = value;
        Ok(())
    }

    fn get(&self, x: u32, y:u32) -> Result<&T, Error> {
        if x >= self.width || y >= self.height {
            return Err(Error::OutOfBounds);
        }

        Ok(&self.inner[(y * self.width + x) as usize])
    }

    fn get_mut(&mut self, x: u32, y: u32) -> Result<&mut T,  Error> {
        if x >= self.width || y >= self.height {
            return Err(Error::OutOfBounds);
        }

        Ok(&mut self.inner[(y * self.width + x) as usize])
    }
}

impl<T: Default> Region<T> {
    pub fn new_with(width: u32, height: u32) -> VecRegion<T> {
        let size = (width * height) as usize;
        let mut inner = Vec::with_capacity(size);
        inner.resize_with(size, T::default);
        VecRegion {
            inner,
            width,
            height,
        }
    }
}


const TILE_IS_PATH: u8 = 0x4;

#[derive(Clone, Debug)]
pub struct Tile {
    owner: Owner,
    flags: u8,
    connections: u8,
}

#[derive(Clone)]
pub struct TileTemplate {
    pub connections: u8
}

#[derive(Eq, PartialEq, Clone, Debug, Copy)]
enum Owner {
    Room(RoomId),
    Tunnel(u32),
}

impl TileTemplate {
    fn into_tile(&self, room: RoomId) -> Tile {
        Tile {
            connections: self.connections,
            owner: Owner::Room(room),
            flags: 0,
        }
    }
}

//type Level = Region<Option<Tile>>;
type RoomTemplate = Region<Option<TileTemplate>>;

struct Room {
    x: u32,
    y: u32,
    width: u32,
    height: u32,
}

pub struct Level {
    region: Box<dyn Region<Option<Tile>>>,
    rooms: Vec<Room>,
    tunnels: u32,
}

impl Level {
    pub fn new(region: Box<dyn Region<Option<Tile>>>) -> Level {
        Level {
            region: region,
            rooms: Vec::new(),
            tunnels: 0
        }
    }
}

pub fn place_template(level: &mut Level, template: &RoomTemplate, x: u32, y: u32) -> Result<RoomId, Error> {
    let region = &mut level.region;
    let width = region.width();
    let height = region.height();

    if x >= width || x + template.width() > width || y >= height || y + template.height() > height {
        return Err(Error::OutOfBounds);
    }

    for row in 0..template.height() {
        for column in 0..template.width() {
            if region.get(column + x, row + y)?.is_some() {
                return Err(Error::NonEmpty);
            }
        }
    }

    let room = Room {
        x,
        y,
        width: template.width(),
        height: template.height(),
    };
    let room_id = level.rooms.len() as u32;
    level.rooms.push(room);

    for row in 0..template.height() {
        for column in 0..template.width() {
            region.set(column + x, row + y,
                       template.get(column, row)?.clone().map(|t| t.into_tile(room_id)))?;
        }
    }

    Ok(room_id)
}

fn tunnel<R: Rng + ?Sized>(level: &mut Level, from: (u32, u32), to: (u32, u32), owner: Owner, rng: &mut R) -> Result<(), Error> {

    let mut from = from;
    let mut connected = false;

    while !connected {

        let diff: (i64, i64) = (from.0 as i64 - to.0 as i64, from.1 as i64 - to.1 as i64);
        let abs_diff = (i64::abs(diff.0), i64::abs(diff.1));
        let mut direction = if abs_diff.1 < abs_diff.0 {
            if diff.0 < 0 { Direction::RIGHT } else { Direction::LEFT }
        } else {
            if diff.1 < 0 { Direction::DOWN } else { Direction::UP }
        };

        let mut steps = match direction {
            Direction::RIGHT | Direction::LEFT => rng.gen_range(0, abs_diff.0) + 1,
            Direction::UP | Direction::DOWN => rng.gen_range(0, abs_diff.1) + 1,
            _ => 1
        };

        while steps > 0 {
            let connection = direction; 
            let opposite = Direction::opposite(connection);
            let tile = level.region.get_mut(from.0, from.1)?;
            if let Some(tile) = tile {
                tile.connections = tile.connections | connection;
            } else {
                level.region.set(from.0, from.1, Some(Tile { owner: owner, flags: TILE_IS_PATH, connections: direction}));
            }

            from = Direction::step_towards(direction, from).unwrap();

            let tile = level.region.get_mut(from.0, from.1)?;
            match tile {
                Some(tile) => {
                    if tile.owner != owner {
                        tile.connections = tile.connections | opposite;
                        connected = true;
                        break;
                    }
                },
                None => {
                    level.region.set(from.0, from.1, Some(Tile { owner: owner, flags: TILE_IS_PATH, connections: opposite}));
                }
            }
            steps = steps - 1;
        }
    }
    Ok(())
}

pub fn connect_rooms<R: Rng + ?Sized>(level: &mut Level, from_id: RoomId, to_id: RoomId, rng: &mut R) -> Result<(), Error> {

    let mut candidates = Vec::new();
    let from = level.rooms.get(from_id as usize).ok_or(Error::InvalidRoomId)?;
    let from_center = (from.x + (from.width / 2), from.y + (from.height / 2));

    let to = level.rooms.get(to_id as usize).ok_or(Error::InvalidRoomId)?;
    let to_center = (to.x + (to.width / 2), to.y + (to.height / 2));

    let diff: (i32, i32) = (from_center.0 as i32 - to_center.0 as i32, from_center.1 as i32 - to_center.1 as i32);
    let abs_diff = (i32::abs(diff.0), i32::abs(diff.1));

    let direction =  if abs_diff.1 < abs_diff.0 {
        if -1 < diff.0 { Direction::LEFT } else { Direction::RIGHT }
    } else {
        if diff.1 < 0 { Direction::DOWN } else { Direction::UP }
    };

    /*Find a suitable starting location*/
    match direction {
        Direction::UP => {
            while candidates.len() < 1 {
                let mut y = from.y;
                for x in from.x..(from.x + from.width) {
                    if let Some(tile) = level.region.get(x, y)? {
                        candidates.push((x, y));
                    }
                }
                y = y + 1;
            }
        },
        Direction::RIGHT => {
            while candidates.len() < 1 {
                let mut x = from.x + from.width - 1;
                for y in from.y..(from.y + from.height) {
                    if let Some(tile) = level.region.get(x, y)? {
                        candidates.push((x, y));
                    }
                }
                x = x - 1;
            }
        },
        Direction::DOWN => {
            while candidates.len() < 1 {
                let mut y = from.y + from.height - 1;
                for x in from.x..(from.x + from.width) {
                    if let Some(tile) = level.region.get(x, y)? {
                        candidates.push((x, y));
                    }
                }
                y = y - 1;
            }
        },
        Direction::LEFT => {
            while candidates.len() < 1 {
                let mut x = from.x;
                for y in from.y..(from.y + from.height) {
                    if let Some(tile) = level.region.get(x, y)? {
                        candidates.push((x, y));
                    }
                }
                x = x + 1;
            }
        },
        _ => unreachable!()
    }

    let pos = candidates[rng.gen_range(0, candidates.len())];
    tunnel(level, pos, to_center, Owner::Room(from_id), rng)
}

pub fn create_deadend<R: Rng + ?Sized>(level: &mut Level, rng: &mut R) -> Result<(), Error>  {
    let mut attempts = 0;
    loop {
        let x = rng.gen_range(0, level.region.width() - 3);
        let y = rng.gen_range(0, level.region.height() - 3);
        let mut empty = true;

        for i in 0..3 {
            for j in 0..3 {
                let tile = level.region.get(x + j, y + i)?;
                if tile.is_some() {
                    empty = false;
                    break;
                }
            }
        }
        attempts = attempts + 1;
        if attempts > 128 {break;}

        if empty {
            let owner = Owner::Tunnel(level.tunnels);
            let rnd_index = rng.gen_range(0, level.rooms.len());
            let room = &mut level.rooms[rnd_index];
            let room_center: (u32, u32) = ((room.x + (room.width/2)), (room.y  + (room.height/2)));
            let res = tunnel(level, (x,y), room_center, owner , rng);
            level.tunnels += 1;
            return res;
        }

    }
    Ok(())
}

fn empty_neighbours(level: &Level, x: u32, y:u32, options: &mut [u8; 4], neighbours: &mut usize) {
    let region = &level.region;
    if y > 0 && region.get(x, y - 1).unwrap().is_none() {
        options[*neighbours] = Direction::UP;
        *neighbours += 1;
    }

    if x + 1  < region.width() && region.get(x + 1, y).unwrap().is_none() {
        options[*neighbours] = Direction::RIGHT;
        *neighbours += 1;
    }

    if y + 1 < region.height() && region.get(x, y + 1).unwrap().is_none() {
        options[*neighbours] = Direction::DOWN;
        *neighbours += 1;
    }

    if x > 0 && region.get(x - 1, y).unwrap().is_none() {
        options[*neighbours] = Direction::LEFT;
        *neighbours += 1;
    }
}

pub fn tunnel_branches<R: Rng + ?Sized>(level: &mut Level, rng: &mut R) -> Result<(), Error> {
    let mut iterations = 0;
    const max_iterations: u32 = 128;

    let mut neighbours = 0;
    let mut options = [0;  4];
    let mut x = 0;
    let mut y = 0;

    let owner = Owner::Tunnel(level.tunnels);
    level.tunnels += 1;
    
    while neighbours <= 0 && iterations < max_iterations {
        neighbours = 0;
        x = rng.gen_range(0, level.region.width() - 4) + 2;
        y = rng.gen_range(0, level.region.height() - 4) + 2;

        if let Some(tile) = level.region.get(x, y)? {
            if tile.flags & TILE_IS_PATH != 0 {
                empty_neighbours(level, x, y, &mut options, &mut neighbours);
            }
        }
        iterations = iterations + 1;
    }

    if neighbours <= 0 {
        return Err(Error::NonEmpty);
    }

    let direction = options[rng.gen_range(0, neighbours)];
    if let Some(tile) = level.region.get_mut(x, y)? {
        tile.connections |= direction;
    };

    let mut pos = (x, y);
    pos = Direction::step_towards(direction, pos).unwrap();
    level.region.set(pos.0, pos.1, Some(Tile { owner: owner, flags: TILE_IS_PATH, connections: Direction::opposite(direction)}));
    let mut iterations = rng.gen_range(0, 2);

    while iterations >= 0 {
        neighbours = 0;
        empty_neighbours(level, pos.0, pos.1, &mut options, &mut neighbours);

        if neighbours <= 0 {
            return Ok(());
        }

        let direction = options[rng.gen_range(0, neighbours)];
        let mut length = rng.gen_range(0, 2) + 1;
        while length > 0 {
            let old_pos = pos.clone();
            let m_pos = Direction::step_towards(direction, pos); 
            if let Err(_) = m_pos {
                break;
            } else {
                pos = m_pos.unwrap();
            }

            match level.region.get(pos.0, pos.1) {
                Ok(tile) => {
                    if tile.is_none() {
                        level.region.set(pos.0, pos.1, Some(Tile { owner: owner, flags: TILE_IS_PATH, connections: Direction::opposite(direction)}));
                        if let Some(tile) = level.region.get_mut(old_pos.0, old_pos.1)? {
                            tile.connections |= direction;
                        }
                    }
                },
                Err(_) => {
                    pos = old_pos;
                    length = 0;
                }
            }
            length += -1;
        }
        iterations += -1;
    }

    Ok(())
}

pub fn pretty_print(level: &Level) {

    let region = &level.region;

    for x in 0..region.width() { print!(" _"); }
    println!("");

    for y in 0..region.height() {
        for x in 0..region.width() {
            if  x == 0 { print!("|");}
            let tile = region.get(x, y).unwrap();
            match tile {
                Some(tile) => {
                    if tile.connections & Direction::DOWN == 0 { print!("_") } else { print!(" ") }
                    if tile.connections & Direction::RIGHT == 0 { print!("|") } else { print!(" ") }
                },
                None => print!("_|"),
            }
        }
        println!("");
    }
}

pub fn create_templates() -> Vec<VecRegion<Option<TileTemplate>>> {

    let mut template:VecRegion<Option<TileTemplate>> = Region::new_with(3, 3);
    use Direction::{UP, DOWN, LEFT, RIGHT};
    template.set(0, 0, Some(TileTemplate { connections: RIGHT | DOWN}));
    template.set(1, 0, Some(TileTemplate { connections: RIGHT | DOWN | LEFT}));
    template.set(2, 0, Some(TileTemplate { connections: DOWN | LEFT}));

    template.set(0, 1, Some(TileTemplate { connections: UP | RIGHT | DOWN}));
    template.set(1, 1, Some(TileTemplate { connections: UP | RIGHT | DOWN | LEFT}));
    template.set(2, 1, Some(TileTemplate { connections: UP | DOWN | LEFT}));

    template.set(0, 2, Some(TileTemplate { connections: UP | RIGHT}));
    template.set(1, 2, Some(TileTemplate { connections: UP | RIGHT | LEFT}));
    template.set(2, 2, Some(TileTemplate { connections: UP | LEFT}));

    vec!(template)
}

pub fn random_dungeon<R: Rng + ?Sized>(templates: &Vec<VecRegion<Option<TileTemplate>>>, mut rng: &mut R) -> Result<Level, Error> {
    let mut region: VecRegion<Option<Tile>> = Region::new_with(15, 15);
    let mut level = Level {
        rooms: Vec::new(),
        region: Box::new(region),
        tunnels: 0,
    };

    let mut attempts = 20;
    let first = loop {
        let template = &templates[0];
        let x = rng.gen_range(0, level.region.width() - 2) + 1;
        let y = rng.gen_range(0, level.region.height() - 2) + 1;
        let res = place_template(&mut level, template, x, y);
        if  attempts <= 0 && res.is_err() { panic!() }
        if res.is_ok() { break res.unwrap() }
        attempts += -1;
    };

    let mut attempts = 20;
    let second = loop {
        let template = &templates[0];
        let x = rng.gen_range(0, level.region.width() - 2) + 1;
        let y = rng.gen_range(0, level.region.height() - 2) + 1;
        let res = place_template(&mut level, template, x, y);
        if  attempts <= 0 && res.is_err() { return Err(Error::MaximumIterations); }
        if res.is_ok() { break res.unwrap() }
        attempts += -1;
    };

    connect_rooms(&mut level, first, second, &mut rng)?;
    let mut additional_rooms = rng.gen_range(0, 3) + 4;

    while additional_rooms >= 0 {
        let mut attempts = 20;
        let room_id = loop {
            let template = &templates[0];
            let x = rng.gen_range(0, level.region.width() - 2) + 1;
            let y = rng.gen_range(0, level.region.height() - 2) + 1;
            let res = place_template(&mut level, template, x, y);
            if  attempts <= 0 && res.is_err() { return Err(Error::MaximumIterations); }
            if res.is_ok() { break res.unwrap() }
            attempts += -1;
        };
        let to_room = (level.rooms.len() - 1) as u32;
        connect_rooms(&mut level, room_id, rng.gen_range(0, to_room), &mut rng)?;
        additional_rooms += -1;
    }

    let mut connections = rng.gen_range(0, 3) + 1;
    while connections > 0 {
        let upper = level.rooms.len();
        let mut from = 0;
        let mut to = 0;
        while to == from {
            from = rng.gen_range(0, upper);
            to = rng.gen_range(0, upper);
        }
        connect_rooms(&mut level, from as u32, to as u32, &mut rng)?;
        connections += -1;
    }

    let mut deadends = rng.gen_range(0, 3) + 1;
    while deadends > 0 {
        create_deadend(&mut level, &mut rng)?;
        deadends += -1;
    }

    tunnel_branches(&mut level, &mut rng)?;
    tunnel_branches(&mut level, &mut rng)?;
    tunnel_branches(&mut level, &mut rng)?;

    Ok(level)
}