1 files changed, 112 insertions, 110 deletions

diff --git a/dungeon/src/bsp.rs b/dungeon/src/bsp.rs
index 5800d8d..aaafa10 100644
--- a/dungeon/src/bsp.rs
+++ b/dungeon/src/bsp.rs
@@ -1,45 +1,54 @@
 //! 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 core::panic;
+use rand::prelude::IndexedRandom;
 use rand::{Rng, SeedableRng};
 use std::cmp; // for min/max
 
-use crate::map::{MAP_SIZE_USIZE, TILE_COUNT, Tile};
+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: usize = 8;
+const MIN_LEAF_SIZE: u16 = 8;
 /// `MIN_ROOM_SIZE` is the minimum room size (w/h).
-const MIN_ROOM_SIZE: usize = 3;
+const MIN_ROOM_SIZE: u16 = 3;
 /// `MAX_ROOM_SIZE` is the maximum room size (w/h).
-const MAX_ROOM_SIZE: usize = 12;
+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)]
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
 struct Rect {
-	x: usize,
-	y: usize,
-	w: usize,
-	h: usize,
+	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: usize, y: usize, w: usize, h: usize) -> Self {
+	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.
-	fn center(&self) -> (usize, usize) {
+	/// 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;
-		(cx, cy)
+		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)]
+#[derive(Debug, Clone, PartialEq, Eq)]
 struct Node {
 	rect: Rect,               // Area this node covers
 	left: Option<Box<Node>>,  // Left child (if not leaf)
@@ -159,21 +168,13 @@ impl Node {
 		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
+		// Define a valid range for room position, leaving at least 1 tile 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)
-		};
+		// Choose room position randomly within valid range
+		let rx = rng.random_range(x_range);
+		let ry = rng.random_range(y_range);
 
 		self.room = Some(Rect::new(rx, ry, room_w, room_h));
 	}
@@ -194,82 +195,93 @@ impl Node {
 
 	/// 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)> {
+	fn room_center(&self) -> Pos {
+		// Base case: if this node has a room, return its center
 		if let Some(room) = &self.room {
-			return Some(room.center());
+			return room.center();
 		}
-		if let Some(left) = &self.left
-			&& let Some(center) = left.room_center()
-		{
-			return Some(center);
+		if let Some(left) = &self.left {
+			return left.room_center();
 		}
-		if let Some(right) = &self.right
-			&& let Some(center) = right.room_center()
-		{
-			return Some(center);
+		if let Some(right) = &self.right {
+			return right.room_center();
 		}
-		None
+		// Fallback (should not happen)
+		panic!("No room found in subtree");
 	}
 
-	/// 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) {
+	/// 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 {
-			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()
+			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<(usize, usize, usize, usize)>,
-		rng: &mut rand::rngs::StdRng,
-	) {
+	/// returns corridors: output vector of (Pos, Pos) pairs to connect
+	fn connect_children(&self, rng: &mut rand::rngs::StdRng) -> Vec<(Pos, Pos)> {
+		let mut corridors = Vec::new();
+
 		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));
+			// Get a random point in each child's room
+			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);
+			// Recursively connect children
+			let mut left_corridors = left.connect_children(rng);
+			let mut right_corridors = right.connect_children(rng);
+			corridors.append(&mut left_corridors);
+			corridors.append(&mut right_corridors);
 		}
-		// leaf: nothing to connect!
+
+		corridors
 	}
 }
 
-/// Carve a room rectangle into the map (tile array) by setting tiles inside to Air.
+/// Carve a room rectangle into the map (tile array) by setting tiles inside to Room.
 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;
+	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::Room;
 		}
 	}
 }
 
 /// 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) {
+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_USIZE;
-		tiles[idx] = Tile::Air;
+		let idx = x + y * MAP_SIZE;
+		// Don't carve if it's already a room
+		if tiles[idx as usize] == Tile::Room {
+			continue;
+		}
+		tiles[idx as usize] = Tile::Hallway;
 	}
 }
 
-/// Carve a vertical corridor from y1..=y2 at x
-fn carve_v_corridor(tiles: &mut [Tile; TILE_COUNT], y1: usize, y2: usize, x: usize) {
+/// Carve a vertical corridor from y1..=y2 at x (inclusive)
+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_USIZE;
-		tiles[idx] = Tile::Air;
+		let idx = x + y * MAP_SIZE;
+		// Don't carve if it's already a room
+		if tiles[idx as usize] == Tile::Room {
+			continue;
+		}
+		tiles[idx as usize] = Tile::Hallway;
 	}
 }
 
@@ -283,7 +295,7 @@ pub fn generate(seed: u64) -> (Box<[Tile; TILE_COUNT]>, Pos) {
 
 	// 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 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.
@@ -345,11 +357,12 @@ pub fn generate(seed: u64) -> (Box<[Tile; TILE_COUNT]>, Pos) {
 	}
 
 	// Collect corridors (pairs of centers) by connecting children bottom-up
-	let mut corridors = Vec::new();
-	root.connect_children(&mut corridors, &mut rng);
+	let corridors = root.connect_children(&mut rng);
 
 	// Carve corridors. For each corridor (x1,y1,x2,y2), carve straight or L-shape.
-	for (x1, y1, x2, y2) in corridors {
+	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);
@@ -367,31 +380,20 @@ pub fn generate(seed: u64) -> (Box<[Tile; TILE_COUNT]>, Pos) {
 		}
 	}
 
-	// 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 player start randomly in the center of one of the rooms (leaf nodes)
+	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();
 
-	// 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;
-		}
+	// 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]);
 	}
-	// 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;
-	}*/
+	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)
@@ -406,9 +408,9 @@ mod tests {
 	#[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);
+		let center = rect.center();
+		assert_eq!(center.xy().0, 4);
+		assert_eq!(center.xy().1, 4);
 	}
 
 	#[test]
@@ -433,10 +435,10 @@ mod tests {
 			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);
+				assert!(room.x + room.w < MAP_SIZE);
+				assert!(room.y + room.h < MAP_SIZE);
 			}
-			None => panic!("Room should be created"),
+			None => self::panic!("Room should exist"),
 		}
 	}
 
@@ -457,8 +459,8 @@ mod tests {
 		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);
+		node.create_room(&mut rng);
+		let corridors = node.connect_children(&mut rng);
 		assert!(!corridors.is_empty());
 	}
 
@@ -466,9 +468,9 @@ mod tests {
 	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 tiles contain some Room tiles
+		let room_count = tiles.iter().filter(|&&t| t == Tile::Room).count();
+		assert!(room_count > 0);
 		// Check that player_start is within bounds
 		assert!(player_start.xy().0 < MAP_SIZE);
 		assert!(player_start.xy().1 < MAP_SIZE);