use crate::config::TerrainConfig;
use crate::error::PcgResult;
use crate::model::geometry::{GridPoint, GridSize};
use crate::model::room::{DoorAnchor, Room};
use crate::model::terrain::{ConnectivitySummary, Grid2D, Terrain, TileKind};
use crate::rng::StableRng;
use super::carve::extract_room_bounds;
use super::strategy::TerrainStrategy;
#[non_exhaustive]
pub struct MazeStrategy;
impl TerrainStrategy for MazeStrategy {
fn name(&self) -> &str {
"maze"
}
fn generate(
&self,
room: &Room,
anchors: &[DoorAnchor],
_config: &TerrainConfig,
rng: &mut StableRng,
) -> PcgResult<Terrain> {
let (bounds, width, height) = extract_room_bounds(room)?;
let mut tiles = Grid2D::new(width, height, TileKind::Wall)?;
let doorway_locals = super::carve::mark_doorways(&mut tiles, anchors, &room.id, bounds.min);
generate_maze_recursive_backtrack(&mut tiles, width, height, rng)?;
connect_doorways_to_maze(&mut tiles, &doorway_locals, width, height);
if doorway_locals.len() >= 2 {
force_connect_doorways(&mut tiles, &doorway_locals, width, height);
}
Ok(Terrain {
room_id: room.id.clone(),
grid_size: GridSize { width, height },
tiles,
reserved_zones: Vec::new(),
connectivity_summary: ConnectivitySummary {
all_doors_connected: false,
walkable_tile_count: 0,
total_tile_count: 0,
connected_region_count: 0,
},
})
}
}
fn generate_maze_recursive_backtrack(
tiles: &mut Grid2D<TileKind>,
width: u32,
height: u32,
rng: &mut StableRng,
) -> PcgResult<()> {
let start_x = if width > 4 { 2 } else { 1 };
let start_y = if height > 4 { 2 } else { 1 };
let mut stack: Vec<GridPoint> = Vec::new();
let mut visited = Grid2D::new(width, height, false)?;
let start = GridPoint {
x: start_x,
y: start_y,
};
tiles.set(start.x, start.y, TileKind::Floor);
visited.set(start.x, start.y, true);
stack.push(start);
while let Some(current) = stack.last().copied() {
let (neighbors, count) = get_unvisited_neighbors(current, &visited, width, height);
if count == 0 {
stack.pop();
continue;
}
let idx = rng.random_range(0, count as i32) as usize;
let next = neighbors[idx];
let wall_x = (current.x + next.x) / 2;
let wall_y = (current.y + next.y) / 2;
tiles.set(wall_x, wall_y, TileKind::Floor);
tiles.set(next.x, next.y, TileKind::Floor);
visited.set(next.x, next.y, true);
stack.push(next);
}
Ok(())
}
fn get_unvisited_neighbors(
point: GridPoint,
visited: &Grid2D<bool>,
width: u32,
height: u32,
) -> ([GridPoint; 4], usize) {
let directions = [(0, 2), (0, -2), (2, 0), (-2, 0)];
let default = GridPoint { x: 0, y: 0 };
let mut neighbors = [default; 4];
let mut count = 0usize;
for (dx, dy) in &directions {
let nx = point.x + dx;
let ny = point.y + dy;
if nx < 1 || ny < 1 || nx >= width as i32 - 1 || ny >= height as i32 - 1 {
continue;
}
if visited.get(nx, ny).copied() == Some(false) {
neighbors[count] = GridPoint { x: nx, y: ny };
count += 1;
}
}
(neighbors, count)
}
fn connect_doorways_to_maze(
tiles: &mut Grid2D<TileKind>,
doorways: &[GridPoint],
width: u32,
height: u32,
) {
use std::collections::VecDeque;
let size = (width * height) as usize;
let mut queue = VecDeque::new();
let mut visited = vec![false; size];
let mut parent: Vec<Option<GridPoint>> = vec![None; size];
for doorway in doorways {
let mut adjacent_floor = false;
for (dx, dy) in &[(1, 0), (-1, 0), (0, 1), (0, -1)] {
let nx = doorway.x + dx;
let ny = doorway.y + dy;
if let Some(tile) = tiles.get(nx, ny).copied() {
if tile == TileKind::Floor || tile == TileKind::Doorway {
adjacent_floor = true;
break;
}
}
}
if adjacent_floor {
continue;
}
queue.clear();
visited.fill(false);
parent.fill(None);
queue.push_back(*doorway);
visited[(doorway.y as u32 * width + doorway.x as u32) as usize] = true;
let mut target = None;
while let Some(current) = queue.pop_front() {
if current != *doorway {
if let Some(tile) = tiles.get(current.x, current.y).copied() {
if tile == TileKind::Floor {
target = Some(current);
break;
}
}
}
for (dx, dy) in &[(1, 0), (-1, 0), (0, 1), (0, -1)] {
let nx = current.x + dx;
let ny = current.y + dy;
if nx < 0 || ny < 0 || nx >= width as i32 || ny >= height as i32 {
continue;
}
if nx < 1 || ny < 1 || nx >= width as i32 - 1 || ny >= height as i32 - 1 {
continue;
}
let ni = (ny as u32 * width + nx as u32) as usize;
if visited[ni] {
continue;
}
visited[ni] = true;
parent[ni] = Some(current);
queue.push_back(GridPoint { x: nx, y: ny });
}
}
if let Some(end) = target {
let mut current = end;
while current != *doorway {
if current.x > 0
&& current.y > 0
&& current.x < width as i32 - 1
&& current.y < height as i32 - 1
&& tiles.get(current.x, current.y).copied() == Some(TileKind::Wall)
{
tiles.set(current.x, current.y, TileKind::Floor);
}
let ci = (current.y as u32 * width + current.x as u32) as usize;
if let Some(prev) = parent[ci] {
current = prev;
} else {
break;
}
}
}
}
}
fn force_connect_doorways(
tiles: &mut Grid2D<TileKind>,
doorways: &[GridPoint],
width: u32,
height: u32,
) {
use std::collections::VecDeque;
if doorways.len() < 2 {
return;
}
let start = doorways[0];
let size = (width * height) as usize;
let mut reachable = vec![false; size];
let mut visited = vec![false; size];
let mut queue = VecDeque::new();
queue.push_back(start);
visited[(start.y as u32 * width + start.x as u32) as usize] = true;
while let Some(current) = queue.pop_front() {
if doorways.contains(¤t) {
reachable[(current.y as u32 * width + current.x as u32) as usize] = true;
}
for (dx, dy) in &[(1, 0), (-1, 0), (0, 1), (0, -1)] {
let nx = current.x + dx;
let ny = current.y + dy;
if nx < 0 || ny < 0 || nx >= width as i32 || ny >= height as i32 {
continue;
}
let ni = (ny as u32 * width + nx as u32) as usize;
if visited[ni] {
continue;
}
if let Some(tile) = tiles.get(nx, ny).copied() {
if super::grid::is_walkable(tile) {
visited[ni] = true;
queue.push_back(GridPoint { x: nx, y: ny });
}
}
}
}
for doorway in doorways.iter().skip(1) {
let di = (doorway.y as u32 * width + doorway.x as u32) as usize;
if reachable[di] {
continue;
}
carve_orthogonal_path(tiles, *doorway, start, width, height);
}
}
fn carve_orthogonal_path(
tiles: &mut Grid2D<TileKind>,
from: GridPoint,
to: GridPoint,
width: u32,
height: u32,
) {
let x_step = if to.x > from.x { 1 } else { -1 };
let mut x = from.x;
while x != to.x {
if x > 0
&& x < width as i32 - 1
&& from.y > 0
&& from.y < height as i32 - 1
&& tiles.get(x, from.y).copied() == Some(TileKind::Wall)
{
tiles.set(x, from.y, TileKind::Floor);
}
x += x_step;
}
let y_step = if to.y > from.y { 1 } else { -1 };
let mut y = from.y;
while y != to.y {
if to.x > 0
&& to.x < width as i32 - 1
&& y > 0
&& y < height as i32 - 1
&& tiles.get(to.x, y).copied() == Some(TileKind::Wall)
{
tiles.set(to.x, y, TileKind::Floor);
}
y += y_step;
}
}