From 6266b64d7c7b0862db2b058021b81e7fb316330e Mon Sep 17 00:00:00 2001 From: alf9310 Date: Sun, 9 Nov 2025 16:43:04 -0500 Subject: dungeon_generation: variables changed from usize to u16 for pos compatability --- dungeon/src/bsp.rs | 127 +++++++++++++++++++++++------------------------------ dungeon/src/map.rs | 2 + 2 files changed, 58 insertions(+), 71 deletions(-) (limited to 'dungeon/src') diff --git a/dungeon/src/bsp.rs b/dungeon/src/bsp.rs index 5800d8d..f996405 100644 --- a/dungeon/src/bsp.rs +++ b/dungeon/src/bsp.rs @@ -1,39 +1,40 @@ //! 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_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)] 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 as u16, cy as u16).unwrap_or(const_pos!(1, 1)) } } @@ -194,29 +195,27 @@ 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) + const_pos!(1, 1) } /// Return a point (x,y) on the border of the room in this node. - fn random_point_in_room(&self, rng: &mut R) -> (usize, usize) { + fn random_point_in_room(&self, rng: &mut R) -> Pos { 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) + Pos::new(rx, ry).unwrap_or(self.rect.center()) } else { // No room: return center of rect self.rect.center() @@ -228,15 +227,15 @@ impl Node { /// `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)>, + 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 (x1, y1) = left.random_point_in_room(rng); - let (x2, y2) = right.random_point_in_room(rng); - corridors.push((x1, y1, x2, y2)); + 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); @@ -247,29 +246,29 @@ impl Node { /// 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; + 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: 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; + 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: usize, y2: usize, x: usize) { +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; + tiles[idx as usize] = Tile::Air; } } @@ -283,7 +282,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. @@ -349,7 +348,9 @@ pub fn generate(seed: u64) -> (Box<[Tile; TILE_COUNT]>, Pos) { 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 { + 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 +368,15 @@ 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 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; - }*/ + // 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 // Return tiles and player_start (tiles_box, player_start) @@ -406,9 +391,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,8 +418,8 @@ 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"), } diff --git a/dungeon/src/map.rs b/dungeon/src/map.rs index eda467c..9e43faf 100644 --- a/dungeon/src/map.rs +++ b/dungeon/src/map.rs @@ -43,6 +43,8 @@ impl Tile { pub fn is_wall(self) -> bool { self == Self::Wall } + + // Index by u16 } impl Default for Tile { fn default() -> Self { -- cgit v1.2.3-freya From ba26fa4eb37e78b6dc47cb7f4e96733375e022fc Mon Sep 17 00:00:00 2001 From: alf9310 Date: Sun, 9 Nov 2025 17:12:15 -0500 Subject: dungeon_generation: added stair generation and fixed room center vs rabdom point recursion --- dungeon/src/bsp.rs | 41 ++++++++++++++++++++++++++++++----------- dungeon/tests/bsp_tests.rs | 14 ++++++++++++++ 2 files changed, 44 insertions(+), 11 deletions(-) (limited to 'dungeon/src') diff --git a/dungeon/src/bsp.rs b/dungeon/src/bsp.rs index f996405..9b288a2 100644 --- a/dungeon/src/bsp.rs +++ b/dungeon/src/bsp.rs @@ -17,7 +17,7 @@ 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: u16, y: u16, @@ -34,13 +34,20 @@ impl Rect { fn center(&self) -> Pos { let cx = self.x + self.w / 2; let cy = self.y + self.h / 2; - Pos::new(cx as u16, cy as u16).unwrap_or(const_pos!(1, 1)) + Pos::new(cx, cy).unwrap_or(const_pos!(1, 1)) + } + + /// Returns a random point in this rectangle. + fn random_point(&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>, // Left child (if not leaf) @@ -207,19 +214,24 @@ impl Node { return right.room_center(); } // Fallback (should not happen) - const_pos!(1, 1) + panic!("No room found in subtree"); } - /// Return a point (x,y) on the border of the room in this node. + /// 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(&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)); - Pos::new(rx, ry).unwrap_or(self.rect.center()) - } 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. @@ -377,6 +389,13 @@ pub fn generate(seed: u64) -> (Box<[Tile; TILE_COUNT]>, Pos) { 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) diff --git a/dungeon/tests/bsp_tests.rs b/dungeon/tests/bsp_tests.rs index 2e3a781..6bd0153 100644 --- a/dungeon/tests/bsp_tests.rs +++ b/dungeon/tests/bsp_tests.rs @@ -3,6 +3,7 @@ mod tests { use dungeon::*; + /// Basic integration test for BSP generation #[test] fn test_bsp_integration() { let seed = 12345u64; @@ -12,4 +13,17 @@ mod tests { 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 seed = 12345u64; + 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 an air tile + let idx = player_start.idx(); + assert_eq!(tiles[idx], map::Tile::Air); + } } -- cgit v1.2.3-freya From 096ff7a891c350da000f18f01ffb4a1f9cde0899 Mon Sep 17 00:00:00 2001 From: alf9310 Date: Sun, 9 Nov 2025 17:37:23 -0500 Subject: dungeon_generation: added Hallway vs Room tiles --- dungeon/src/bsp.rs | 68 ++++++++++++++++++++-------------------------- dungeon/src/map.rs | 15 ++++++---- dungeon/tests/bsp_tests.rs | 22 +++++++++++++-- graphics/src/render.rs | 9 ++++-- 4 files changed, 65 insertions(+), 49 deletions(-) (limited to 'dungeon/src') diff --git a/dungeon/src/bsp.rs b/dungeon/src/bsp.rs index 9b288a2..8b5fa3b 100644 --- a/dungeon/src/bsp.rs +++ b/dungeon/src/bsp.rs @@ -1,6 +1,7 @@ //! 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 @@ -167,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)); } @@ -236,32 +229,33 @@ impl Node { /// 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, - ) { + /// 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 left_point = left.random_point_in_room(rng); - let right_point = right.random_point_in_room(rng); + // Get room centers for left and right children + let left_point = left.room_center(); + let right_point = right.room_center(); 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 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; + tiles[idx as usize] = Tile::Room; } } } @@ -271,16 +265,16 @@ 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; + tiles[idx as usize] = Tile::Hallway; } } -/// Carve a vertical corridor from y1..=y2 at x +/// 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; - tiles[idx as usize] = Tile::Air; + tiles[idx as usize] = Tile::Hallway; } } @@ -356,8 +350,7 @@ 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 (left_point, right_point) in corridors { @@ -440,7 +433,7 @@ mod tests { 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"), } } @@ -461,8 +454,7 @@ 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); + let corridors = node.connect_children(&mut rng); assert!(!corridors.is_empty()); } @@ -470,9 +462,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 9e43faf..5004dd7 100644 --- a/dungeon/src/map.rs +++ b/dungeon/src/map.rs @@ -28,8 +28,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, } @@ -48,7 +50,7 @@ impl Tile { } impl Default for Tile { fn default() -> Self { - Self::Air + Self::Wall } } @@ -213,7 +215,8 @@ impl Floor { let tile = self.get(pos); let char = match tile { Tile::Wall => '#', - Tile::Air => '.', + Tile::Room => '.', + Tile::Hallway => ',', Tile::Stairs => '>', }; output.push(char); @@ -233,7 +236,7 @@ impl Floor { let Some(pos) = Pos::new(x, y) else { continue; }; - if self.get(pos) != Tile::Air { + if self.get(pos) == Tile::Wall { continue; } break pos; @@ -245,7 +248,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 6bd0153..16a8a77 100644 --- a/dungeon/tests/bsp_tests.rs +++ b/dungeon/tests/bsp_tests.rs @@ -22,8 +22,26 @@ mod tests { // Ensure player start is within bounds assert!(player_start.x() < map::MAP_SIZE); assert!(player_start.y() < map::MAP_SIZE); - // Ensure player start is an air tile + // Ensure player start is a room tile let idx = player_start.idx(); - assert_eq!(tiles[idx], map::Tile::Air); + assert_eq!(tiles[idx], map::Tile::Room); + } + + /// Test that BSP-generated floors have at least two rooms + #[test] + fn test_bsp_2_or_more_rooms() { + let seed = 12345u64; + let (tiles, _player_start) = bsp::generate(seed); + // Ensure we have at least two rooms + let mut room_count = 0; + let mut visited = vec![false; tiles.len()]; + for (i, &tile) in tiles.iter().enumerate() { + if tile == map::Tile::Room && !visited[i] { + room_count += 1; + // Mark all connected tiles as visited + visited[i] = true; + } + } + assert!(room_count >= 2); } } diff --git a/graphics/src/render.rs b/graphics/src/render.rs index 0fee7b5..7e9a74b 100644 --- a/graphics/src/render.rs +++ b/graphics/src/render.rs @@ -380,8 +380,10 @@ impl Renderer { let tile = floor.get(pos); let idx = match tile { Tile::Wall => ATLAS_WALL_SIDE, - Tile::Air if (x + y) % 2 == 0 => ATLAS_FLOOR_FULL, - Tile::Air if (x + y) % 2 == 1 => ATLAS_FLOOR_EMPTY, + Tile::Room if (x + y) % 2 == 0 => ATLAS_FLOOR_FULL, + Tile::Room if (x + y) % 2 == 1 => ATLAS_FLOOR_EMPTY, + Tile::Hallway if (x + y) % 2 == 0 => ATLAS_FLOOR_FULL, + Tile::Hallway if (x + y) % 2 == 1 => ATLAS_FLOOR_EMPTY, _ => ATLAS_ERROR, }; rt.draw_atlas( @@ -408,7 +410,8 @@ impl Renderer { let tile = floor.get(pos); let color = match tile { Tile::Wall => Color::DARKGRAY, - Tile::Air => Color::GRAY, + Tile::Room => Color::GRAY, + Tile::Hallway => Color::LIGHTGRAY, Tile::Stairs => Color::WHITE, }; rt.draw_pixel(x.into(), y.into(), color); -- cgit v1.2.3-freya From 0d484d763a243e6b73e13d4968ccf6222b65eeca Mon Sep 17 00:00:00 2001 From: alf9310 Date: Mon, 10 Nov 2025 00:31:56 -0500 Subject: Added many auto-gen test cases for maze connectivity --- dungeon/src/bsp.rs | 18 ++++--- dungeon/tests/bsp_tests.rs | 132 ++++++++++++++++++++++++++++++++++++--------- 2 files changed, 120 insertions(+), 30 deletions(-) (limited to 'dungeon/src') diff --git a/dungeon/src/bsp.rs b/dungeon/src/bsp.rs index 8b5fa3b..aaafa10 100644 --- a/dungeon/src/bsp.rs +++ b/dungeon/src/bsp.rs @@ -228,15 +228,14 @@ impl Node { } /// Connect rooms of child nodes recursively and collect corridors to carve. - /// /// 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) { - // Get room centers for left and right children - let left_point = left.room_center(); - let right_point = right.room_center(); + // 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)); // Recursively connect children @@ -265,6 +264,10 @@ 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; + // Don't carve if it's already a room + if tiles[idx as usize] == Tile::Room { + continue; + } tiles[idx as usize] = Tile::Hallway; } } @@ -274,6 +277,10 @@ 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; + // Don't carve if it's already a room + if tiles[idx as usize] == Tile::Room { + continue; + } tiles[idx as usize] = Tile::Hallway; } } @@ -374,8 +381,6 @@ pub fn generate(seed: u64) -> (Box<[Tile; TILE_COUNT]>, Pos) { } // 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]); @@ -454,6 +459,7 @@ mod tests { let mut node = Node::new(rect); let mut rng = rand::rngs::StdRng::seed_from_u64(12345); node.split(&mut rng); + node.create_room(&mut rng); let corridors = node.connect_children(&mut rng); assert!(!corridors.is_empty()); } diff --git a/dungeon/tests/bsp_tests.rs b/dungeon/tests/bsp_tests.rs index 16a8a77..0a494b8 100644 --- a/dungeon/tests/bsp_tests.rs +++ b/dungeon/tests/bsp_tests.rs @@ -2,46 +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 { + 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 (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); + 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 seed = 12345u64; - 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); + 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 two rooms + /// Test that BSP-generated floors have at least one room tile #[test] fn test_bsp_2_or_more_rooms() { - let seed = 12345u64; - let (tiles, _player_start) = bsp::generate(seed); - // Ensure we have at least two rooms - let mut room_count = 0; + 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); + + // 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 && !visited[i] { - room_count += 1; - // Mark all connected tiles as visited - visited[i] = true; + if tile == map::Tile::Room || tile == map::Tile::Hallway { + assert!(visited[i], "Unreachable air tile at index {i}"); } } - assert!(room_count >= 2); } } -- cgit v1.2.3-freya