Merge branch 'dungeon_generation' into 'main'

Dungeon Generation

See merge request psr2251/project/DungeonCrawl!2

3 files changed, 275 insertions, 119 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);
diff --git a/dungeon/src/map.rs b/dungeon/src/map.rs
index 8d9a391..7d79f7f 100644
--- a/dungeon/src/map.rs
+++ b/dungeon/src/map.rs
@@ -29,8 +29,10 @@ pub const TILE_COUNT: usize = MAP_SIZE_USIZE * MAP_SIZE_USIZE;
 pub enum Tile {
 	/// `Wall` represents an impassible wall
 	Wall,
-	/// `Air` represents empty walkable space
-	Air,
+	/// `Room` represents empty walkable space for a rectangular room
+	Room,
+	/// `Hallway` represents empty walkable space for a hallway
+	Hallway,
 	/// `Stairs` represents stairs to another floor
 	Stairs,
 }
@@ -51,10 +53,12 @@ impl Tile {
 	pub const fn is_walkable(self) -> bool {
 		matches!(self, Self::Air)
 	}
+
+	// Index by u16
 }
 impl Default for Tile {
 	fn default() -> Self {
-		Self::Air
+		Self::Wall
 	}
 }
 impl Display for Tile {
@@ -207,6 +211,40 @@ impl Floor {
 		*hash
 	}
 
+	/// Display the floor as a string for debugging
+	///
+	/// # Examples
+	/// ```no_run
+	/// use dungeon::Floor;
+	/// let floor = Floor::generate();
+	/// println!("{}", floor.display());
+	/// ```
+	#[must_use]
+	pub fn display(&self) -> String {
+		let mut output = String::new();
+		for pos in Pos::values() {
+			// If it's the player start, show 'P'
+			if self.player_start == pos {
+				output.push('P');
+				continue;
+			}
+			// Otherwise, show the tile character
+			let tile = self.get(pos);
+			let char = match tile {
+				Tile::Wall => '#',
+				Tile::Room => '.',
+				Tile::Hallway => ',',
+				Tile::Stairs => '>',
+			};
+			output.push(char);
+			// Newline at the end of each row
+			if pos.xy().0 == MAP_SIZE - 1 {
+				output.push('\n');
+			}
+		}
+		output
+	}
+
 	/// Returns a random open (no wall) position
 	pub fn random_pos(&mut self) -> Pos {
 		loop {
@@ -227,7 +265,7 @@ impl Default for Floor {
 	/// Returns a floor with a single set of walls on the map border
 	fn default() -> Self {
 		let player_start = const_pos!(1, 1);
-		let mut tiles = Box::new([Tile::Air; TILE_COUNT]);
+		let mut tiles = Box::new([Tile::Room; TILE_COUNT]);
 		let seed = 0u64;
 
 		for pos in Pos::values() {
diff --git a/dungeon/tests/bsp_tests.rs b/dungeon/tests/bsp_tests.rs
index 2e3a781..0a494b8 100644
--- a/dungeon/tests/bsp_tests.rs
+++ b/dungeon/tests/bsp_tests.rs
@@ -2,14 +2,130 @@
 #[cfg(test)]
 mod tests {
 	use dungeon::*;
+	use pos::Pos;
+	use rand::{Rng, SeedableRng};
 
+	/// Generate a set of test seeds for reproducibility with a seeded RNG
+	fn generate_test_seeds(seed: u64) -> Vec<u64> {
+		let mut rng = rand::rngs::StdRng::seed_from_u64(seed);
+		// Generate 100 random u64 seeds
+		(0..100).map(|_| rng.random_range(0..u64::MAX)).collect()
+	}
+
+	/// Basic integration test for BSP generation
 	#[test]
 	fn test_bsp_integration() {
-		let seed = 12345u64;
+		let test_seeds = generate_test_seeds(123456);
+		for seed in test_seeds {
+			let (tiles, player_start) = bsp::generate(seed);
+			// Basic integration test: ensure we get valid data
+			assert!(!tiles.is_empty());
+			assert!(player_start.x() < map::MAP_SIZE);
+			assert!(player_start.y() < map::MAP_SIZE);
+		}
+	}
+
+	/// Test that BSP-generated floors have a valid player start
+	#[test]
+	fn test_bsp_player_start() {
+		let test_seeds = generate_test_seeds(654321);
+		for seed in test_seeds {
+			let (tiles, player_start) = bsp::generate(seed);
+			// Ensure player start is within bounds
+			assert!(player_start.x() < map::MAP_SIZE);
+			assert!(player_start.y() < map::MAP_SIZE);
+			// Ensure player start is a room tile
+			let idx = player_start.idx();
+			assert_eq!(tiles[idx], map::Tile::Room);
+		}
+	}
+
+	/// Test that BSP-generated floors have at least one room tile
+	#[test]
+	fn test_bsp_2_or_more_rooms() {
+		let test_seeds = generate_test_seeds(111222);
+		for seed in test_seeds {
+			let (tiles, _player_start) = bsp::generate(seed);
+			// Ensure we have at least one room tile
+			let room_count = tiles
+				.iter()
+				.filter(|&&tile| tile == map::Tile::Room)
+				.count();
+			assert!(
+				room_count >= 1,
+				"Expected at least one room tile, found {room_count}"
+			);
+		}
+	}
+
+	/// Test that BSP-generated floors have walls on the borders
+	#[test]
+	fn test_bsp_walls_on_borders() {
+		let test_seeds = generate_test_seeds(777888);
+		for seed in test_seeds {
+			let (tiles, _player_start) = bsp::generate(seed);
+			// Go through all tiles, and ensure border tiles are walls
+			for x in 0..map::MAP_SIZE {
+				for y in 0..map::MAP_SIZE {
+					let pos = Pos::new(x, y).unwrap_or(const_pos!(1, 1));
+					if pos.is_border() {
+						let idx = pos.idx();
+						assert_eq!(
+							tiles[idx],
+							map::Tile::Wall,
+							"Expected wall at border position {pos:?}"
+						);
+					}
+				}
+			}
+		}
+	}
+
+	// Test that BSP-generated floors are reproducible with the same seed
+	#[test]
+	fn test_bsp_reproducibility() {
+		let test_seeds = generate_test_seeds(111111);
+		for seed in test_seeds {
+			let (tiles1, player_start1) = bsp::generate(seed);
+			let (tiles2, player_start2) = bsp::generate(seed);
+			assert_eq!(tiles1, tiles2, "Tiles differ for same seed {seed}");
+			assert_eq!(
+				player_start1, player_start2,
+				"Player starts differ for same seed {seed}"
+			);
+		}
+	}
+
+	// Test that all `air` tiles (`Tile::Room` and `Tile::Hallway`) are reachable from the player start
+	#[test]
+	fn test_bsp_all_air_tiles_reachable() {
+		let test_seeds = generate_test_seeds(333444);
+		for seed in test_seeds {
+			check_air_tiles_reachable(seed);
+		}
+	}
+
+	// Helper function to check that all air tiles are reachable from player start
+	fn check_air_tiles_reachable(seed: u64) {
 		let (tiles, player_start) = bsp::generate(seed);
-		// Basic integration test: ensure we get valid data
-		assert!(!tiles.is_empty());
-		assert!(player_start.x() < map::MAP_SIZE);
-		assert!(player_start.y() < map::MAP_SIZE);
+
+		// BFS to find all reachable air tiles
+		let mut visited = vec![false; tiles.len()];
+		let mut queue = vec![player_start];
+		visited[player_start.idx()] = true;
+		while let Some(pos) = queue.pop() {
+			for neighbor in pos.neighbors() {
+				let idx = neighbor.idx();
+				if !visited[idx] && tiles[idx] != map::Tile::Wall {
+					visited[idx] = true;
+					queue.push(neighbor);
+				}
+			}
+		}
+		for (i, &tile) in tiles.iter().enumerate() {
+			if tile == map::Tile::Room || tile == map::Tile::Hallway {
+				assert!(visited[i], "Unreachable air tile at index {i}");
+			}
+		}
 	}
 }