condor_grid/

preprocessed_grid.rs

//! Algorithm-neutral build-once/query-many contracts for static grid search.
//!
//! A [`PreprocessedGridBuilder`] snapshots a [`Grid`] into a [`PreparedGridSearch`];
//! repeated [`SearchRequest`]s use the usual invalid/found/no-path [`SearchResult`]
//! without re-binding mutable map state. Rebuild after any map edit. The
//! [`StaticPreparedGridBuilder`] is the pass-through A* baseline; JPS+, subgoal, and
//! hierarchical implementations supply their own cost-model constraints. Prefer an
//! online [`crate::Pathfinder`] for a one-shot or changing grid.

use crate::{
    AStar, Grid, HierarchicalGridBuildError, Pathfinder, Point,
    search::{SearchRequest, SearchResult},
};

/// Preprocesses a static grid into a queryable prepared map.
///
/// Prep may be a cheap clone ([`StaticPreparedGridBuilder`]) or an expensive
/// index build. Failures are typed via [`PreprocessedGridBuildError`].
pub trait PreprocessedGridBuilder {
    /// Prepared map type this builder produces.
    type Map: PreparedGridSearch;

    /// Stable builder identity for reports and portfolios.
    fn name(&self) -> &'static str;

    /// Snapshot `grid` into a prepared search structure.
    ///
    /// # Errors
    ///
    /// Returns [`PreprocessedGridBuildError`] when the grid violates the
    /// algorithm's cost or geometry assumptions.
    fn preprocess(&self, grid: &Grid) -> Result<Self::Map, PreprocessedGridBuildError>;
}

/// Prepared static grid that answers repeated point-to-point search requests.
///
/// Holds (or views) immutable walkability / cost data from preprocess. Query
/// cost models follow the concrete algorithm named in metadata
/// (for example A* on 4-way grids with per-cell `traversal_cost`).
pub trait PreparedGridSearch {
    /// Stable map identity (usually the builder name).
    fn name(&self) -> &'static str;

    /// Grid snapshot used for walkability and costs.
    fn grid(&self) -> &Grid;

    /// Build-time summary of shape, walkability counts, and cost model labels.
    fn metadata(&self) -> &PreprocessedGridMetadata;

    /// Point-to-point search on the prepared snapshot.
    fn search(&self, request: SearchRequest) -> SearchResult;
}

/// Build-time summary of grid shape, walkability, and movement model.
///
/// Recorded once at preprocess for catalogs and multi-query reports; not updated
/// by individual searches.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct PreprocessedGridMetadata {
    /// Builder that produced the map.
    pub builder_name: &'static str,
    /// Online or abstract algorithm used at query time.
    pub query_algorithm: &'static str,
    pub width: usize,
    pub height: usize,
    pub cell_count: usize,
    pub walkable_cell_count: usize,
    pub blocked_cell_count: usize,
    /// Movement neighborhood label (starter maps use `"4-way"`).
    pub movement_model: &'static str,
    /// `"uniform"` when every walkable cell has `traversal_cost == 1`, else `"weighted"`.
    pub cost_model: &'static str,
}

/// Error returned when static grid preprocessing fails.
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
#[non_exhaustive]
pub enum PreprocessedGridBuildError {
    /// Hierarchical / HPA*-style prep nested under the preprocessed-grid surface.
    #[error(transparent)]
    Hierarchical(#[from] HierarchicalGridBuildError),
    /// Algorithm requires unit costs on every walkable cell.
    #[error("{algorithm} requires uniform traversal cost 1; cell {point:?} has cost {cost}")]
    NonUniformCost {
        algorithm: &'static str,
        point: Point,
        cost: usize,
    },
}

/// Pass-through builder that clones the grid and delegates queries to [`AStar`].
///
/// Establishes the preprocess/query API without abstract indexing. Useful as a
/// baseline for multi-query amortization measurements against heavier builders.
#[derive(Debug, Clone, Copy, Default)]
pub struct StaticPreparedGridBuilder;

impl StaticPreparedGridBuilder {
    /// Constructs the default pass-through builder.
    #[must_use]
    pub const fn new() -> Self {
        Self
    }
}

impl PreprocessedGridBuilder for StaticPreparedGridBuilder {
    type Map = StaticPreparedGrid;

    fn name(&self) -> &'static str {
        "static-prepared-grid"
    }

    fn preprocess(&self, grid: &Grid) -> Result<Self::Map, PreprocessedGridBuildError> {
        Ok(StaticPreparedGrid {
            grid: grid.clone(),
            metadata: metadata_for_grid(grid, self.name(), AStar.name()),
        })
    }
}

/// Immutable grid snapshot with metadata for repeated online search.
///
/// Each [`PreparedGridSearch::search`] runs [`AStar`] on the owned clone. No
/// shared open set or cache is retained between queries.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct StaticPreparedGrid {
    grid: Grid,
    metadata: PreprocessedGridMetadata,
}

impl StaticPreparedGrid {
    /// Convenience constructor for the matching pass-through builder.
    #[must_use]
    pub fn builder() -> StaticPreparedGridBuilder {
        StaticPreparedGridBuilder
    }
}

impl PreparedGridSearch for StaticPreparedGrid {
    fn name(&self) -> &'static str {
        self.metadata.builder_name
    }

    fn grid(&self) -> &Grid {
        &self.grid
    }

    fn metadata(&self) -> &PreprocessedGridMetadata {
        &self.metadata
    }

    fn search(&self, request: SearchRequest) -> SearchResult {
        AStar.search(&self.grid, request)
    }
}

/// Snapshots shape, walkability counts, and cost-model labels for a prepared map.
///
/// Walkable cells are counted by presence of `traversal_cost`; cost model is
/// `"uniform"` only when every walkable cell has unit cost, else `"weighted"`.
/// Movement model is always `"4-way"` for this owner crate.
pub(crate) fn metadata_for_grid(
    grid: &Grid,
    builder_name: &'static str,
    query_algorithm: &'static str,
) -> PreprocessedGridMetadata {
    let mut walkable_cell_count = 0usize;
    let mut weighted = false;

    for y in 0..grid.height() {
        for x in 0..grid.width() {
            let point = Point::new(x, y);
            if let Some(cost) = grid.traversal_cost(point) {
                walkable_cell_count += 1;
                weighted |= cost != 1;
            }
        }
    }

    let cell_count = grid.cell_count();
    PreprocessedGridMetadata {
        builder_name,
        query_algorithm,
        width: grid.width(),
        height: grid.height(),
        cell_count,
        walkable_cell_count,
        blocked_cell_count: cell_count - walkable_cell_count,
        movement_model: "4-way",
        cost_model: if weighted { "weighted" } else { "uniform" },
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{Cell, Pathfinder};

    #[test]
    fn static_prepared_grid_records_build_metadata_separately_from_query_stats() {
        let mut grid = Grid::new(4, 3).expect("grid dimensions are valid");
        grid.set_cell(Point::new(1, 1), Cell::Blocked)
            .expect("fixture point is in bounds");
        grid.set_traversal_cost(Point::new(2, 0), 3)
            .expect("traversal cost is positive");

        let prepared = StaticPreparedGrid::builder()
            .preprocess(&grid)
            .expect("static grid should preprocess");
        let metadata = *prepared.metadata();

        assert_eq!(metadata.builder_name, "static-prepared-grid");
        assert_eq!(metadata.query_algorithm, "astar");
        assert_eq!(metadata.width, 4);
        assert_eq!(metadata.height, 3);
        assert_eq!(metadata.cell_count, 12);
        assert_eq!(metadata.walkable_cell_count, 11);
        assert_eq!(metadata.blocked_cell_count, 1);
        assert_eq!(metadata.movement_model, "4-way");
        assert_eq!(metadata.cost_model, "weighted");

        let result = prepared
            .search(SearchRequest::new(Point::new(0, 0), Point::new(3, 2)))
            .expect("request is valid");
        assert!(result.is_found());
        assert_eq!(*prepared.metadata(), metadata);
        assert!(result.visited_nodes() > 0);
        assert!(result.cost().is_some());
    }

    #[test]
    fn static_prepared_grid_queries_an_immutable_snapshot() {
        let mut grid = Grid::new(5, 1).expect("grid dimensions are valid");
        let request = SearchRequest::new(Point::new(0, 0), Point::new(4, 0));
        let prepared = StaticPreparedGrid::builder()
            .preprocess(&grid)
            .expect("static grid should preprocess");

        grid.set_cell(Point::new(2, 0), Cell::Blocked)
            .expect("fixture point is in bounds");

        let prepared_result = prepared.search(request).expect("request is valid");
        let changed_online_result = AStar.search(&grid, request).expect("request is valid");

        assert!(prepared_result.is_found());
        assert_eq!(prepared_result.cost(), Some(4));
        assert!(!changed_online_result.is_found());
    }

    #[test]
    fn static_prepared_grid_matches_astar_on_a_uniform_obstacle_course() {
        let mut grid = Grid::new(5, 3).expect("grid dimensions are valid");
        grid.set_cell(Point::new(2, 0), Cell::Blocked)
            .expect("fixture point is in bounds");
        grid.set_cell(Point::new(2, 2), Cell::Blocked)
            .expect("fixture point is in bounds");
        let request = SearchRequest::new(Point::new(0, 1), Point::new(4, 1));

        let prepared = StaticPreparedGrid::builder()
            .preprocess(&grid)
            .expect("static grid should preprocess");
        let prepared_result = prepared.search(request).expect("request is valid");
        let astar_result = AStar.search(&grid, request).expect("request is valid");

        assert_eq!(prepared_result, astar_result);
        assert!(
            prepared_result
                .path()
                .is_some_and(|path| prepared.grid().path_is_walkable(path.steps()))
        );
    }
}