use std::collections::VecDeque;
use crate::model::geometry::GridPoint;
use crate::model::terrain::{ConnectivitySummary, Grid2D, TileKind};
use super::grid::{collect_walkable_points, is_walkable};
pub fn summarize_connectivity(grid: &Grid2D<TileKind>) -> ConnectivitySummary {
let walkable_points = collect_walkable_points(grid);
let total_tile_count = grid.width * grid.height;
let walkable_tile_count = walkable_points.len() as u32;
let mut visited = vec![false; (grid.width * grid.height) as usize];
let mut connected_region_count = 0u32;
for start in &walkable_points {
let idx = grid_idx(*start, grid.width);
if visited[idx] {
continue;
}
connected_region_count += 1;
flood_fill(*start, grid, &mut visited);
}
ConnectivitySummary {
all_doors_connected: connected_region_count <= 1,
walkable_tile_count,
total_tile_count,
connected_region_count,
}
}
fn flood_fill(start: GridPoint, grid: &Grid2D<TileKind>, visited: &mut [bool]) {
let w = grid.width;
let mut queue = VecDeque::from([start]);
while let Some(current) = queue.pop_front() {
let ci = grid_idx(current, w);
if visited[ci] {
continue;
}
visited[ci] = true;
for neighbor in neighbors(current) {
if neighbor.x < 0
|| neighbor.y < 0
|| neighbor.x as u32 >= grid.width
|| neighbor.y as u32 >= grid.height
{
continue;
}
let ni = grid_idx(neighbor, w);
if visited[ni] {
continue;
}
if grid
.get(neighbor.x, neighbor.y)
.copied()
.is_some_and(is_walkable)
{
queue.push_back(neighbor);
}
}
}
}
fn neighbors(point: GridPoint) -> [GridPoint; 4] {
[
GridPoint {
x: point.x + 1,
y: point.y,
},
GridPoint {
x: point.x - 1,
y: point.y,
},
GridPoint {
x: point.x,
y: point.y + 1,
},
GridPoint {
x: point.x,
y: point.y - 1,
},
]
}
pub(crate) fn connect_all_doorways(grid: &mut Grid2D<TileKind>, doorways: &[GridPoint]) {
if doorways.len() <= 1 {
return;
}
let w = grid.width as i32;
let h = grid.height as i32;
if w < 3 || h < 3 {
return;
}
let first = doorways[0];
let target = inward_neighbor(first, w, h);
carve_floor(grid, target, w, h);
let mut reachable = vec![false; (grid.width * grid.height) as usize];
flood_fill(first, grid, &mut reachable);
for &door in &doorways[1..] {
let di = grid_idx(door, grid.width);
if reachable[di] {
continue;
}
let entry = inward_neighbor(door, w, h);
carve_floor(grid, entry, w, h);
carve_orthogonal_interior(grid, entry, target, w, h);
flood_fill(entry, grid, &mut reachable);
}
}
#[inline]
fn grid_idx(p: GridPoint, w: u32) -> usize {
(p.y as u32 * w + p.x as u32) as usize
}
fn inward_neighbor(door: GridPoint, w: i32, h: i32) -> GridPoint {
if door.x == 0 {
GridPoint { x: 1, y: door.y }
} else if door.x == w - 1 {
GridPoint {
x: w - 2,
y: door.y,
}
} else if door.y == 0 {
GridPoint { x: door.x, y: 1 }
} else if door.y == h - 1 {
GridPoint {
x: door.x,
y: h - 2,
}
} else {
door
}
}
fn carve_floor(grid: &mut Grid2D<TileKind>, p: GridPoint, w: i32, h: i32) {
if p.x <= 0 || p.y <= 0 || p.x >= w - 1 || p.y >= h - 1 {
return; }
if grid.get(p.x, p.y).copied() == Some(TileKind::Doorway) {
return; }
grid.set(p.x, p.y, TileKind::Floor);
}
fn carve_orthogonal_interior(
grid: &mut Grid2D<TileKind>,
from: GridPoint,
to: GridPoint,
w: i32,
h: i32,
) {
let mut x = from.x;
while x != to.x {
carve_floor(grid, GridPoint { x, y: from.y }, w, h);
x += if to.x > from.x { 1 } else { -1 };
}
let mut y = from.y;
while y != to.y {
carve_floor(grid, GridPoint { x: to.x, y }, w, h);
y += if to.y > from.y { 1 } else { -1 };
}
carve_floor(grid, to, w, h);
}