condor_grid/
hierarchical.rs

1//! Hierarchical build-once/query-many contracts for cluster abstraction and refinement.
2//!
3//! A [`HierarchicalGridBuilder`] snapshots a static grid into an abstract map; its
4//! [`PreparedHierarchicalGrid`] answers repeated [`SearchRequest`]s with the normal
5//! [`SearchResult`] contract. [`crate::HPAStarBuilder`] is the current implementation
6//! and requires uniform traversal cost. Prefer [`crate::preprocessed_grid`] for
7//! algorithm-neutral prepared maps that do not require hierarchical abstraction.
8
9use crate::{
10    grid::Grid,
11    point::Point,
12    search::{SearchRequest, SearchResult},
13};
14
15/// Preprocesses a static grid into a hierarchical search structure.
16///
17/// Implementations define how the grid is clustered and which abstract graph is
18/// stored. Prep cost is paid once; query cost depends on cluster size and abstract
19/// connectivity, not on re-scanning the full grid for every request.
20pub trait HierarchicalGridBuilder {
21    /// Immutable hierarchical map produced by this builder.
22    type Map: PreparedHierarchicalGrid;
23
24    /// Stable builder identity for reports and portfolios.
25    fn name(&self) -> &'static str;
26
27    /// Snapshot `grid` into a prepared hierarchical map.
28    ///
29    /// # Errors
30    ///
31    /// Returns [`HierarchicalGridBuildError`] when cluster parameters are invalid
32    /// or the grid violates the builder's cost model (for example non-uniform
33    /// `traversal_cost` for HPA*).
34    fn preprocess(&self, grid: &Grid) -> Result<Self::Map, HierarchicalGridBuildError>;
35}
36
37/// Immutable hierarchical map that answers point-to-point grid searches.
38///
39/// Search uses the builder's abstract graph plus local refinement; the owned
40/// grid snapshot (when present) is not mutated across queries.
41pub trait PreparedHierarchicalGrid {
42    /// Stable map identity (usually the builder name).
43    fn name(&self) -> &'static str;
44
45    /// Point-to-point search on the prepared hierarchical structure.
46    ///
47    /// Returns the same [`SearchResult`] shape as online grid pathfinders
48    /// (validation errors, found path, or no-path with stats).
49    fn search(&self, request: SearchRequest) -> SearchResult;
50}
51
52/// Hierarchical preprocess failed (cluster size or non-uniform costs).
53#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
54#[non_exhaustive]
55pub enum HierarchicalGridBuildError {
56    /// Cluster width/height must be positive for HPA*-style builders.
57    #[error("HPA* cluster size must be greater than zero")]
58    InvalidClusterSize,
59    /// Hierarchical abstracts currently require unit `traversal_cost` on every walkable cell.
60    #[error("HPA* supports only uniform-cost grids; cell {point:?} has traversal cost {cost}")]
61    NonUniformCost { point: Point, cost: usize },
62}
condor_grid/hierarchical.rs

condor_grid/
hierarchical.rs
