path: root/dungeon/src/bsp.rs

//! 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::prelude::IndexedRandom;
use rand::{Rng, SeedableRng};
use std::cmp; // for min/max

use crate::map::{MAP_SIZE, 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: u16 = 8;
/// `MIN_ROOM_SIZE` is the minimum room size (w/h).
const MIN_ROOM_SIZE: u16 = 3;
/// `MAX_ROOM_SIZE` is the maximum room size (w/h).
const MAX_ROOM_SIZE: u16 = 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, PartialEq, Eq)]
struct Rect {
	x: u16,
	y: u16,
	w: u16,
	h: u16,
}
// since this is all "internal", you likely have to use unit tests and not doctests
impl Rect {
	fn new(x: u16, y: u16, w: u16, h: u16) -> Self {
		Self { x, y, w, h }
	}

	/// Returns the center point (cx, cy) of the rectangle as a Pos.
	fn center(&self) -> Pos {
		let cx = self.x + self.w / 2;
		let cy = self.y + self.h / 2;
		Pos::new(cx, cy).unwrap_or(const_pos!(1, 1))
	}

	/// Returns a random point in this rectangle.
	fn random_point<R: Rng>(&self, rng: &mut R) -> Pos {
		let rx = rng.random_range(self.x..(self.x + self.w));
		let ry = rng.random_range(self.y..(self.y + self.h));
		Pos::new(rx, ry).unwrap_or(self.center())
	}
}

/// The `Node` type represents a node in the BSP tree.
/// Has optional left and right children, and an optional room rectangle.
#[derive(Debug, Clone, PartialEq, Eq)]
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) -> Pos {
		// Base case: if this node has a room, return its center
		if let Some(room) = &self.room {
			return room.center();
		}
		if let Some(left) = &self.left {
			return left.room_center();
		}
		if let Some(right) = &self.right {
			return right.room_center();
		}
		// Fallback (should not happen)
		panic!("No room found in subtree");
	}

	/// Return a random point for a room in this subtree:
	/// if node has a room, return a randiom point in it, else try left then right.
	fn random_point_in_room<R: Rng>(&self, rng: &mut R) -> Pos {
		// Base case: if this node has a room, return a random point in it
		if let Some(room) = &self.room {
			return room.random_point(rng);
		}
		if let Some(left) = &self.left {
			return left.random_point_in_room(rng);
		}
		if let Some(right) = &self.right {
			return right.random_point_in_room(rng);
		}
		// Fallback (should not happen)
		panic!("No room found in subtree");
	}

	/// 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<(Pos, Pos)>,
		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 left_point = left.random_point_in_room(rng);
			let right_point = right.random_point_in_room(rng);
			corridors.push((left_point, right_point));

			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 y in room.y..(room.y + room.h) {
		for x in room.x..(room.x + room.w) {
			let idx = x + y * MAP_SIZE;
			tiles[idx as usize] = Tile::Air;
		}
	}
}

/// Carve a horizontal corridor from x1..=x2 at y (inclusive)
fn carve_h_corridor(tiles: &mut [Tile; TILE_COUNT], x1: u16, x2: u16, y: u16) {
	let (sx, ex) = if x1 <= x2 { (x1, x2) } else { (x2, x1) };
	for x in sx..=ex {
		let idx = x + y * MAP_SIZE;
		tiles[idx as usize] = Tile::Air;
	}
}

/// Carve a vertical corridor from y1..=y2 at x
fn carve_v_corridor(tiles: &mut [Tile; TILE_COUNT], y1: u16, y2: u16, x: u16) {
	let (sy, ey) = if y1 <= y2 { (y1, y2) } else { (y2, y1) };
	for y in sy..=ey {
		let idx = x + y * MAP_SIZE;
		tiles[idx as usize] = 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, MAP_SIZE);
	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 (left_point, right_point) in corridors {
		let (x1, y1) = (left_point.xy().0, left_point.xy().1);
		let (x2, y2) = (right_point.xy().0, right_point.xy().1);
		// 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 (leaf nodes)

	// Choose a random leaf node (room) for the player start
	let mut leaves = vec![];
	root.collect_leaves(&mut leaves);
	let player_room = leaves.choose(&mut rng).unwrap_or(&leaves[0]);
	let player_start = player_room.room_center();

	// Set one tile to Stairs (exit) in a random room different from player start
	let mut exit_room = player_room;
	while exit_room == player_room {
		exit_room = leaves.choose(&mut rng).unwrap_or(&leaves[0]);
	}
	let exit_pos = exit_room.room_center();
	let exit_idx = exit_pos.xy().0 + exit_pos.xy().1 * MAP_SIZE;
	tiles_box[exit_idx as usize] = Tile::Stairs;

	// Return tiles and player_start
	(tiles_box, player_start)
}

/// BSP Unit Tests
#[cfg(test)]
mod tests {
	use super::*;
	use crate::map::MAP_SIZE;

	#[test]
	fn test_rect_center() {
		let rect = Rect::new(2, 2, 4, 4);
		let center = rect.center();
		assert_eq!(center.xy().0, 4);
		assert_eq!(center.xy().1, 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);
				assert!(room.y + room.h < MAP_SIZE);
			}
			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);
		assert!(player_start.xy().1 < MAP_SIZE);
	}
}