condor_grid/
search.rs

1//! Online 4-connected grid-search request, result, and [`Pathfinder`] contract.
2//!
3//! A caller supplies a [`SearchRequest`]; a solver returns [`GridSearchError`] for
4//! invalid endpoints or exhausted [`SearchBudget`], or [`SearchOutcome::Found`] /
5//! [`SearchOutcome::NoPath`] with [`SearchStats`] for a completed query. Costs and
6//! visit counts are algorithm-specific. Prefer [`crate::preprocessed_grid`] for a
7//! static build-once/query-many workflow, or [`crate::replanning`] when the grid
8//! changes between queries.
9
10use std::{error::Error, fmt};
11
12use crate::{grid::Grid, path::Path, point::Point};
13
14pub use condor_core::{
15    BudgetExhausted, BudgetWatch, SearchBudget, SearchOutcome, SearchPathCost, SearchVisitStats,
16};
17
18/// Start and goal cell endpoints for a single discrete grid search.
19///
20/// Walkability is checked at search time via [`validate_request`] / pathfinder code.
21/// Optional [`SearchBudget`] caps expansions and/or wall-clock time; default is
22/// unlimited.
23#[derive(Debug, Clone, Copy, PartialEq, Eq)]
24pub struct SearchRequest {
25    /// Inclusive path start cell.
26    pub start: Point,
27    /// Inclusive path goal cell.
28    pub goal: Point,
29    /// Optional expansion / wall-clock caps for this query (default unlimited).
30    pub budget: SearchBudget,
31}
32
33impl SearchRequest {
34    /// Pairs start and goal cells with an unlimited budget; walkability is checked at search time.
35    #[must_use]
36    pub const fn new(start: Point, goal: Point) -> Self {
37        Self {
38            start,
39            goal,
40            budget: SearchBudget::UNLIMITED,
41        }
42    }
43
44    /// Returns a copy of this request with the given budget.
45    #[must_use]
46    pub const fn with_budget(mut self, budget: SearchBudget) -> Self {
47        self.budget = budget;
48        self
49    }
50}
51
52/// Work counters produced by a grid search (algorithm-defined node visits).
53///
54/// `visited_nodes` is solver-local (cell expansions, jump stops, …); do not treat
55/// it as a portable complexity metric across algorithms.
56#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
57pub struct SearchStats {
58    /// Nodes the solver counts as expanded or settled (see algorithm docs).
59    pub visited_nodes: usize,
60}
61
62/// Failure to execute a grid search request (request validation or hard stop).
63///
64/// Unreachable but valid endpoints produce [`SearchOutcome::NoPath`], not these variants.
65/// Caller [`SearchBudget`] exhaustion is [`Self::BudgetExhausted`] and does **not**
66/// prove unreachability.
67#[non_exhaustive]
68#[derive(Debug, Clone, Copy, PartialEq, Eq)]
69pub enum GridSearchError {
70    /// Start is out of bounds or not walkable.
71    InvalidStart { point: Point },
72    /// Goal is out of bounds or not walkable.
73    InvalidGoal { point: Point },
74    /// Caller search budget was exhausted before found/no-path completed.
75    BudgetExhausted(BudgetExhausted),
76    /// Flow-field path sampling stopped after `max_steps` steps without the goal.
77    ///
78    /// Not a general [`Pathfinder`] expansion budget API; only
79    /// [`crate::flow_field`] sampling emits this variant.
80    StepLimitReached { max_steps: usize, reached: Point },
81}
82
83impl fmt::Display for GridSearchError {
84    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
85        match self {
86            Self::InvalidStart { point } => write!(formatter, "invalid start point: {point:?}"),
87            Self::InvalidGoal { point } => write!(formatter, "invalid goal point: {point:?}"),
88            Self::BudgetExhausted(reason) => write!(formatter, "{reason}"),
89            Self::StepLimitReached { max_steps, reached } => write!(
90                formatter,
91                "search stopped after {max_steps} steps at {reached:?} before reaching the goal"
92            ),
93        }
94    }
95}
96
97impl Error for GridSearchError {}
98
99/// Grid search return type: validation error, or found/no-path with stats.
100pub type SearchResult = Result<SearchOutcome<Path, SearchStats>, GridSearchError>;
101
102/// Owner-crate helper: wraps a found path into [`SearchResult`] with visit stats.
103#[doc(hidden)]
104pub const fn found(path: Path, visited_nodes: usize) -> SearchResult {
105    Ok(SearchOutcome::found(path, SearchStats { visited_nodes }))
106}
107
108/// Owner-crate helper: wraps exhaustive no-path into [`SearchResult`] with visit stats.
109#[doc(hidden)]
110pub const fn not_found(visited_nodes: usize) -> SearchResult {
111    Ok(SearchOutcome::no_path(SearchStats { visited_nodes }))
112}
113
114/// Rejects out-of-bounds or blocked start/goal before search (validation `Err`, not no-path).
115#[doc(hidden)]
116pub fn validate_request(grid: &Grid, request: SearchRequest) -> Result<(), GridSearchError> {
117    if !grid.is_walkable(request.start) {
118        return Err(GridSearchError::InvalidStart {
119            point: request.start,
120        });
121    }
122    if !grid.is_walkable(request.goal) {
123        return Err(GridSearchError::InvalidGoal {
124            point: request.goal,
125        });
126    }
127    Ok(())
128}
129
130impl SearchPathCost for Path {
131    type Cost = usize;
132
133    fn path_cost(&self) -> Self::Cost {
134        self.cost()
135    }
136}
137
138impl SearchVisitStats for SearchStats {
139    fn visited_nodes(&self) -> usize {
140        self.visited_nodes
141    }
142}
143
144/// Online algorithm entrypoint for static 4-connected grid search.
145///
146/// Implementations must validate endpoints (walkable start/goal), return
147/// [`GridSearchError`] for invalid requests or exhausted [`SearchBudget`], and
148/// never panic on in-bounds grids. Unreachable but valid endpoints yield
149/// [`SearchOutcome::NoPath`], not an error. Cost models and heuristics are
150/// algorithm-defined (unit hop vs `traversal_cost`).
151pub trait Pathfinder {
152    /// Stable algorithm identifier for benchmarks, logs, and solver portfolios.
153    fn name(&self) -> &'static str;
154
155    /// Runs one search on `grid` for `request`.
156    ///
157    /// Returns `Err` for invalid endpoints or exhausted budgets, `Ok(NoPath)` when
158    /// exhaustive search finds no route, and `Ok(Found)` with a non-empty path and
159    /// stats when a route is found.
160    fn search(&self, grid: &Grid, request: SearchRequest) -> SearchResult;
161}
162
163/// Maps a shared budget failure into [`GridSearchError::BudgetExhausted`].
164#[doc(hidden)]
165pub const fn budget_error(reason: BudgetExhausted) -> GridSearchError {
166    GridSearchError::BudgetExhausted(reason)
167}
condor_grid/search.rs

condor_grid/
search.rs
