condor_grid/grid/

reachability.rs

//! Optional connected-component index for walkable cells on a [`Grid`].
//!
//! [`Grid::index_reachability`] builds it with the same 4-connected neighborhood as
//! online search, letting solvers reject a valid but disconnected pair before their
//! own work begins. It is an optimization only: rebuild it after a walkability edit,
//! or omit it when queries are too sparse to justify preprocessing.

use std::collections::VecDeque;

use super::Grid;
use crate::Point;

/// Maps each walkable cell to a 4-connected component id for cheap reachability.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct GridReachabilityIndex {
    width: usize,
    height: usize,
    components: Vec<Option<u32>>,
    component_count: u32,
}

impl GridReachabilityIndex {
    /// Flood-fills walkable cells into 4-connected components (same neighbor model as search).
    ///
    /// Snapshot of `grid` at call time; rebuild after walkability edits. Blocked cells
    /// receive no component id.
    #[must_use]
    pub fn from_grid(grid: &Grid) -> Self {
        let width = grid.width();
        let height = grid.height();
        let mut components = vec![None; width * height];
        let mut component_count = 0;

        for y in 0..height {
            for x in 0..width {
                let point = Point::new(x, y);
                let index = grid.index_of(point).unwrap();

                if grid.is_walkable(point) && components[index].is_none() {
                    let component_id = component_count;
                    component_count += 1;

                    let mut queue = VecDeque::new();
                    queue.push_back(point);
                    components[index] = Some(component_id);

                    while let Some(current) = queue.pop_front() {
                        for neighbor in grid.neighbors4(current) {
                            let neighbor_index = grid.index_of(neighbor).unwrap();
                            if components[neighbor_index].is_none() {
                                components[neighbor_index] = Some(component_id);
                                queue.push_back(neighbor);
                            }
                        }
                    }
                }
            }
        }

        Self {
            width,
            height,
            components,
            component_count,
        }
    }

    /// Returns the component id for a walkable in-bounds cell; blocked and OOB cells return `None`.
    #[must_use]
    pub fn component_id(&self, point: Point) -> Option<u32> {
        if point.x >= self.width || point.y >= self.height {
            return None;
        }
        let index = (point.y * self.width) + point.x;
        self.components[index]
    }

    /// Whether `start` and `goal` share a walkable 4-connected component.
    ///
    /// Returns `false` if either point is blocked, out of bounds, or the pair
    /// lies in different components. A walkable cell is reachable from itself.
    #[must_use]
    pub fn is_reachable(&self, start: Point, goal: Point) -> bool {
        let start_comp = self.component_id(start);
        let goal_comp = self.component_id(goal);

        match (start_comp, goal_comp) {
            (Some(s), Some(g)) => s == g,
            _ => false,
        }
    }

    /// Number of distinct walkable components in the indexed grid.
    #[must_use]
    pub fn component_count(&self) -> u32 {
        self.component_count
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{
        AStar, Bfs, BidirectionalBfs, Cell, Dijkstra, JumpPointSearch, Pathfinder,
        RectangularSymmetryReduction, SearchRequest,
    };

    #[test]
    fn open_field_has_one_component() {
        let grid = Grid::new(10, 10).expect("grid dimensions are valid");
        let index = GridReachabilityIndex::from_grid(&grid);
        assert_eq!(index.component_count(), 1);
        assert!(index.is_reachable(Point::new(0, 0), Point::new(9, 9)));
    }

    #[test]
    fn blocked_wall_splits_components() {
        let mut grid = Grid::new(10, 10).expect("grid dimensions are valid");
        for y in 0..10 {
            grid.set_cell(Point::new(5, y), Cell::Blocked)
                .expect("valid grid edit");
        }
        let index = GridReachabilityIndex::from_grid(&grid);
        assert_eq!(index.component_count(), 2);
        assert!(!index.is_reachable(Point::new(0, 0), Point::new(9, 9)));
        assert!(index.is_reachable(Point::new(0, 0), Point::new(4, 9)));
        assert!(index.is_reachable(Point::new(6, 0), Point::new(9, 9)));
    }

    #[test]
    fn blocked_cells_have_no_component() {
        let mut grid = Grid::new(10, 10).expect("grid dimensions are valid");
        grid.set_cell(Point::new(5, 5), Cell::Blocked)
            .expect("valid grid edit");
        let index = GridReachabilityIndex::from_grid(&grid);
        assert_eq!(index.component_id(Point::new(5, 5)), None);
    }

    #[test]
    fn out_of_bounds_points_have_no_component() {
        let grid = Grid::new(4, 4).expect("grid dimensions are valid");
        let index = GridReachabilityIndex::from_grid(&grid);
        assert_eq!(index.component_id(Point::new(4, 0)), None);
        assert_eq!(index.component_id(Point::new(0, 4)), None);
    }

    #[test]
    fn pathfinders_short_circuit_on_disconnected_islands() {
        let mut grid = Grid::new(10, 10).expect("grid dimensions are valid");
        for y in 0..10 {
            grid.set_cell(Point::new(5, y), Cell::Blocked)
                .expect("wall cell should be valid");
        }
        grid.index_reachability();

        let request = SearchRequest::new(Point::new(0, 0), Point::new(9, 9));
        let algorithms: Vec<Box<dyn Pathfinder>> = vec![
            Box::new(Bfs),
            Box::new(AStar),
            Box::new(BidirectionalBfs),
            Box::new(Dijkstra),
            Box::new(JumpPointSearch),
            Box::new(RectangularSymmetryReduction),
        ];

        for algorithm in algorithms {
            let result = algorithm
                .search(&grid, request)
                .expect("test request should be valid");
            assert!(
                !result.is_found(),
                "Algorithm {} should not find a path",
                algorithm.name()
            );
            assert_eq!(
                result.stats().visited_nodes,
                0,
                "Algorithm {} should have 0 visited nodes due to short-circuit",
                algorithm.name()
            );
        }
    }

    #[test]
    fn pathfinders_work_normally_when_no_index_present() {
        let mut grid = Grid::new(3, 3).expect("grid dimensions are valid");
        for x in 0..3 {
            grid.set_cell(Point::new(x, 1), Cell::Blocked)
                .expect("wall cell should be valid");
        }

        let request = SearchRequest::new(Point::new(0, 0), Point::new(2, 2));
        let result = AStar
            .search(&grid, request)
            .expect("test request should be valid");

        assert!(!result.is_found());
        assert!(result.stats().visited_nodes > 0);
    }
}