diff options
Diffstat (limited to 'dungeon/src/bsp.rs')
| -rw-r--r-- | dungeon/src/bsp.rs | 475 |
1 files changed, 475 insertions, 0 deletions
diff --git a/dungeon/src/bsp.rs b/dungeon/src/bsp.rs new file mode 100644 index 0000000..be0f282 --- /dev/null +++ b/dungeon/src/bsp.rs @@ -0,0 +1,475 @@ +//! The `bsp` module implements a Binary-Space Partitioning based dungeon generator. +//! Produces a tile array and a player start position for a given seed. + +use rand::{Rng, SeedableRng}; +use std::cmp; // for min/max + +use crate::map::{MAP_SIZE_USIZE, TILE_COUNT, Tile}; +use crate::{const_pos, pos::Pos}; + +/// `MIN_LEAF_SIZE` is the minimum width/height for a leaf to be considered "splittable". +const MIN_LEAF_SIZE: usize = 8; +/// `MIN_ROOM_SIZE` is the minimum room size (w/h). +const MIN_ROOM_SIZE: usize = 3; +/// `MAX_ROOM_SIZE` is the maximum room size (w/h). +const MAX_ROOM_SIZE: usize = 12; + +/// The `Rect` type represents a rectangle inside the map (x,y,width,height). +/// (x,y) is the top-left corner. +#[derive(Debug, Clone, Copy)] +pub(crate) struct Rect { + x: usize, + y: usize, + w: usize, + h: usize, +} +// since this is all "internal", you likely have to use unit tests and not doctests +impl Rect { + fn new(x: usize, y: usize, w: usize, h: usize) -> Self { + Self { x, y, w, h } + } + + /// Returns the center point (cx, cy) of the rectangle. + fn center(&self) -> (usize, usize) { + let cx = self.x + self.w / 2; + let cy = self.y + self.h / 2; + (cx, cy) + } +} + +/// The `Node` type represents a node in the BSP tree. +/// Has optional left and right children, and an optional room rectangle. +#[derive(Debug)] +pub(crate) struct Node { + rect: Rect, // Area this node covers + left: Option<Box<Node>>, // Left child (if not leaf) + right: Option<Box<Node>>, // Right child (if not leaf) + room: Option<Rect>, // Room created in this node (if leaf) +} + +impl Node { + fn new(rect: Rect) -> Self { + Self { + rect, + left: None, + right: None, + room: None, + } + } + + /// Try to split the node. Returns true if split happened. + /// Splitting is done either horizontally or vertically, + /// depending on the dimensions of the node. + fn split<R: Rng>(&mut self, rng: &mut R) -> bool { + // Already split + if self.left.is_some() || self.right.is_some() { + return false; + } + + // Determine if we can split + let can_split_h = self.rect.h >= (MIN_LEAF_SIZE * 2); + let can_split_v = self.rect.w >= (MIN_LEAF_SIZE * 2); + + if !can_split_h && !can_split_v { + return false; + } + + // Choose orientation: prefer the longer side + let split_h = if self.rect.w > self.rect.h { + false + } else if self.rect.h > self.rect.w { + true + } else { + rng.random_bool(0.5) + }; + + // Choose split coordinate with margin so each side can contain a room + if split_h { + // horizontal split => choose y + // avoid too close to borders of rect + let min = cmp::max( + self.rect.y + MIN_ROOM_SIZE + 1, + self.rect.y + MIN_LEAF_SIZE + 1, + ); + let max = cmp::min( + self.rect.y + self.rect.h - MIN_ROOM_SIZE - 1, + self.rect.y + self.rect.h - MIN_LEAF_SIZE - 1, + ); + if max <= min { + return false; + } + // Add some heterogeneity: choose random position between min..max + let split_y = rng.random_range(min..=max); + let top_h = split_y - self.rect.y; + let bottom_h = self.rect.h - top_h; + if top_h < MIN_LEAF_SIZE || bottom_h < MIN_LEAF_SIZE { + return false; + } + + let top = Rect::new(self.rect.x, self.rect.y, self.rect.w, top_h); + let bottom = Rect::new(self.rect.x, split_y, self.rect.w, bottom_h); + self.left = Some(Box::new(Self::new(top))); + self.right = Some(Box::new(Self::new(bottom))); + } else { + // vertical split => choose x + let min = cmp::max( + self.rect.x + MIN_ROOM_SIZE + 1, + self.rect.x + MIN_LEAF_SIZE + 1, + ); + let max = cmp::min( + self.rect.x + self.rect.w - MIN_ROOM_SIZE - 1, + self.rect.x + self.rect.w - MIN_LEAF_SIZE - 1, + ); + if max <= min { + return false; + } + let split_x = rng.random_range(min..=max); + let left_w = split_x - self.rect.x; + let right_w = self.rect.w - left_w; + if left_w < MIN_LEAF_SIZE || right_w < MIN_LEAF_SIZE { + return false; + } + + let left_rect = Rect::new(self.rect.x, self.rect.y, left_w, self.rect.h); + let right_rect = Rect::new(split_x, self.rect.y, right_w, self.rect.h); + self.left = Some(Box::new(Self::new(left_rect))); + self.right = Some(Box::new(Self::new(right_rect))); + } + true + } + + /// Create a room inside this node (called for leaves). + /// Room size and position chosen randomly. + fn create_room<R: Rng>(&mut self, rng: &mut R) { + if self.left.is_some() || self.right.is_some() { + // This is not a leaf + if let Some(left) = &mut self.left { + left.create_room(rng); + } + if let Some(right) = &mut self.right { + right.create_room(rng); + } + return; + } + + // Leaf: choose room size + // Ensure room fits inside rect with at least 1 tile border to walls + let max_w = (self.rect.w - 2).max(MIN_ROOM_SIZE); + let max_h = (self.rect.h - 2).max(MIN_ROOM_SIZE); + let room_w = rng.random_range(MIN_ROOM_SIZE..=max_w.min(MAX_ROOM_SIZE)); + let room_h = rng.random_range(MIN_ROOM_SIZE..=max_h.min(MAX_ROOM_SIZE)); + + // Choose position inside rect, leaving at least 1 tile to the border + let x_range = (self.rect.x + 1)..=(self.rect.x + self.rect.w - 1 - room_w); + let y_range = (self.rect.y + 1)..=(self.rect.y + self.rect.h - 1 - room_h); + + // The ranges should be valid; if not, fallback to center + let rx = if x_range.is_empty() { + self.rect.x + (self.rect.w.saturating_sub(room_w)) / 2 + } else { + rng.random_range(x_range) + }; + let ry = if y_range.is_empty() { + self.rect.y + (self.rect.h.saturating_sub(room_h)) / 2 + } else { + rng.random_range(y_range) + }; + + self.room = Some(Rect::new(rx, ry, room_w, room_h)); + } + + /// Return a vector of references to all leaf nodes (in-order). + fn collect_leaves<'a>(&'a self, out: &mut Vec<&'a Self>) { + if self.left.is_none() && self.right.is_none() { + out.push(self); + return; + } + if let Some(left) = &self.left { + left.collect_leaves(out); + } + if let Some(right) = &self.right { + right.collect_leaves(out); + } + } + + /// Return the "room center" for this subtree: if node has a room, return its center, + /// else try left then right. + fn room_center(&self) -> Option<(usize, usize)> { + if let Some(room) = &self.room { + return Some(room.center()); + } + if let Some(left) = &self.left + && let Some(center) = left.room_center() + { + return Some(center); + } + if let Some(right) = &self.right + && let Some(center) = right.room_center() + { + return Some(center); + } + None + } + + /// Return a point (x,y) on the border of the room in this node. + fn random_point_in_room<R: Rng>(&self, rng: &mut R) -> (usize, usize) { + if let Some(room) = &self.room { + let rx = rng.random_range(room.x..(room.x + room.w)); + let ry = rng.random_range(room.y..(room.y + room.h)); + (rx, ry) + } else { + // No room: return center of rect + self.rect.center() + } + } + + /// Connect rooms of child nodes recursively and collect corridors to carve. + /// + /// `corridors` is appended with pairs of points (x1,y1,x2,y2) describing corridors to carve. + fn connect_children( + &self, + corridors: &mut Vec<(usize, usize, usize, usize)>, + rng: &mut rand::rngs::StdRng, + ) { + if let (Some(left), Some(right)) = (&self.left, &self.right) { + // Connect a room (or corridor endpoint) from left subtree to right subtree + // Select a random point from each side + let (x1, y1) = left.random_point_in_room(rng); + let (x2, y2) = right.random_point_in_room(rng); + corridors.push((x1, y1, x2, y2)); + + left.connect_children(corridors, rng); + right.connect_children(corridors, rng); + } + // leaf: nothing to connect! + } +} + +/// Carve a room rectangle into the map (tile array) by setting tiles inside to Air. +fn carve_room(tiles: &mut [Tile; TILE_COUNT], room: &Rect) { + for yy in room.y..(room.y + room.h) { + for xx in room.x..(room.x + room.w) { + let idx = xx + yy * MAP_SIZE_USIZE; + tiles[idx] = Tile::Air; + } + } +} + +/// Carve a horizontal corridor from x1..=x2 at y (inclusive) +fn carve_h_corridor(tiles: &mut [Tile; TILE_COUNT], x1: usize, x2: usize, y: usize) { + let (sx, ex) = if x1 <= x2 { (x1, x2) } else { (x2, x1) }; + for x in sx..=ex { + let idx = x + y * MAP_SIZE_USIZE; + tiles[idx] = Tile::Air; + } +} + +/// Carve a vertical corridor from y1..=y2 at x +fn carve_v_corridor(tiles: &mut [Tile; TILE_COUNT], y1: usize, y2: usize, x: usize) { + let (sy, ey) = if y1 <= y2 { (y1, y2) } else { (y2, y1) }; + for y in sy..=ey { + let idx = x + y * MAP_SIZE_USIZE; + tiles[idx] = Tile::Air; + } +} + +/// Top-level generator function for the dungeon using BSP. +/// Returns (tiles, player_start). +pub fn generate(seed: u64) -> (Box<[Tile; TILE_COUNT]>, Pos) { + let mut rng = rand::rngs::StdRng::seed_from_u64(seed); + + // Initialize all tiles to walls + let mut tiles_box: Box<[Tile; TILE_COUNT]> = Box::new([Tile::Wall; TILE_COUNT]); + + // Rooms and coorridors will be carved as `Air` into the tile array. + // Build root rect (whole map) + let root_rect = Rect::new(0, 0, MAP_SIZE_USIZE, MAP_SIZE_USIZE); + let mut root = Node::new(root_rect); + + // Repeatedly try splitting nodes to produce the tree. + // Collect leaves and try to split them until no splits happen or we reach a cap. + // Number of splits proportional to map size to avoid infinite loops. + let max_attempts = 2000usize; + let mut attempts = 0usize; + while attempts < max_attempts { + attempts += 1; + + // Collect mutable references to current leaves + let mut leaves = vec![]; + { + // Collect leaves with a stack + let mut stack = vec![&mut root]; + while let Some(node) = stack.pop() { + if node.left.is_none() && node.right.is_none() { + leaves.push(node as *mut Node); + } else { + if let Some(left) = &mut node.left { + stack.push(left); + } + if let Some(right) = &mut node.right { + stack.push(right); + } + } + } + } + + let mut splitted_any = false; + + // Try splitting each leaf in order + for &node_ptr in leaves.iter() { + // Pointers obtained from boxed root remain valid while root lives + // TODO: Store nodes in smart pointers to avoid unsafe? + let node = unsafe { &mut *node_ptr }; + // Attempt to split if possible + if node.split(&mut rng) { + splitted_any = true; + } + } + + // If no splits happened, we're done + if !splitted_any { + break; + } + } + + // Create rooms in all leaves + root.create_room(&mut rng); + + // Carve all rooms into the tile array + let mut leaves = vec![]; + root.collect_leaves(&mut leaves); + for leaf in leaves.iter() { + if let Some(room) = &leaf.room { + carve_room(&mut tiles_box, room); + } + } + + // Collect corridors (pairs of centers) by connecting children bottom-up + let mut corridors = Vec::new(); + root.connect_children(&mut corridors, &mut rng); + + // Carve corridors. For each corridor (x1,y1,x2,y2), carve straight or L-shape. + for (x1, y1, x2, y2) in corridors { + // If aligned horizontally or vertically, carve straight + if x1 == x2 { + carve_v_corridor(&mut tiles_box, y1, y2, x1); + } else if y1 == y2 { + carve_h_corridor(&mut tiles_box, x1, x2, y1); + } else { + // Choose whether to go horizontal then vertical or vertical then horizontal + if rng.random_bool(0.5) { + carve_h_corridor(&mut tiles_box, x1, x2, y1); + carve_v_corridor(&mut tiles_box, y1, y2, x2); + } else { + carve_v_corridor(&mut tiles_box, y1, y2, x1); + carve_h_corridor(&mut tiles_box, x1, x2, y2); + } + } + } + + // Choose player start randomly in the center of one of the rooms + // TODO: Better Pos creation + #[expect(clippy::cast_possible_truncation)] + let player_start = root + .room_center() + .map(|(cx, cy)| Pos::new(cx as u16, cy as u16).unwrap_or(const_pos!(1, 1))) + .unwrap_or(const_pos!(1, 1)); + + // Choose random location among air tiles + /* + let mut player_start = Pos::new_unchecked(1, 1); + let mut found = false; + for pos in Pos::values() { + if tiles_box[pos.idx()] == Tile::Air { + player_start = pos; + found = true; + break; + } + } + // If we didn't find any air (extremely unlikely), put start at (1,1) and carve it + if !found { + player_start = Pos::new_unchecked(1, 1); + let idx = player_start.idx(); + tiles_box[idx] = Tile::Air; + }*/ + + // Return tiles and player_start + (tiles_box, player_start) +} + +/// Tests +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_rect_center() { + let rect = Rect::new(2, 2, 4, 4); + let (cx, cy) = rect.center(); + assert_eq!(cx, 4); + assert_eq!(cy, 4); + } + + #[test] + fn test_node_split() { + let rect = Rect::new(0, 0, 20, 20); + let mut node = Node::new(rect); + let mut rng = rand::rngs::StdRng::seed_from_u64(12345); + let splitted = node.split(&mut rng); + assert!(splitted); + assert!(node.left.is_some()); + assert!(node.right.is_some()); + } + + #[test] + fn test_node_create_room() { + let rect = Rect::new(0, 0, 20, 20); + let mut node = Node::new(rect); + let mut rng = rand::rngs::StdRng::seed_from_u64(12345); + node.create_room(&mut rng); + assert!(node.room.is_some()); + match &node.room { + Some(room) => { + assert!(room.w >= MIN_ROOM_SIZE && room.h >= MIN_ROOM_SIZE); + assert!(room.x >= 1 && room.y >= 1); + assert!(room.x + room.w < MAP_SIZE_USIZE); + assert!(room.y + room.h < MAP_SIZE_USIZE); + } + None => panic!("Room should be created"), + } + } + + #[test] + fn test_node_collect_leaves() { + let rect = Rect::new(0, 0, 20, 20); + let mut node = Node::new(rect); + let mut rng = rand::rngs::StdRng::seed_from_u64(12345); + node.split(&mut rng); + let mut leaves = Vec::new(); + node.collect_leaves(&mut leaves); + assert!(!leaves.is_empty()); + } + + #[test] + fn test_node_connect_children() { + let rect = Rect::new(0, 0, 20, 20); + let mut node = Node::new(rect); + let mut rng = rand::rngs::StdRng::seed_from_u64(12345); + node.split(&mut rng); + let mut corridors = Vec::new(); + node.connect_children(&mut corridors, &mut rng); + assert!(!corridors.is_empty()); + } + + #[test] + fn test_generate() { + let seed = 12345u64; + let (tiles, player_start) = generate(seed); + // Check that tiles contain some Air tiles + let air_count = tiles.iter().filter(|&&t| t == Tile::Air).count(); + assert!(air_count > 0); + // Check that player_start is within bounds + assert!(player_start.xy().0 < MAP_SIZE_USIZE as u16); + assert!(player_start.xy().1 < MAP_SIZE_USIZE as u16); + } +} |