summaryrefslogtreecommitdiff
path: root/src/lib.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib.rs')
-rw-r--r--src/lib.rs590
1 files changed, 590 insertions, 0 deletions
diff --git a/src/lib.rs b/src/lib.rs
new file mode 100644
index 0000000..54d5fa3
--- /dev/null
+++ b/src/lib.rs
@@ -0,0 +1,590 @@
+#[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)
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-06 15:54:28 +0000