condor-pathfinding-grid 0.4.0

//! Online 4-connected grid-search request, result, and [`Pathfinder`] contract.
//!
//! A caller supplies a [`SearchRequest`]; a solver returns [`GridSearchError`] for
//! invalid endpoints or exhausted [`SearchBudget`], or [`SearchOutcome::Found`] /
//! [`SearchOutcome::NoPath`] with [`SearchStats`] for a completed query. Costs and
//! visit counts are algorithm-specific. Prefer [`crate::preprocessed_grid`] for a
//! static build-once/query-many workflow, or [`crate::replanning`] when the grid
//! changes between queries.

use std::{error::Error, fmt};

use crate::{grid::Grid, path::Path, point::Point};

pub use condor_core::{
    BudgetExhausted, BudgetWatch, SearchBudget, SearchOutcome, SearchPathCost, SearchVisitStats,
};

/// Start and goal cell endpoints for a single discrete grid search.
///
/// Walkability is checked at search time via [`validate_request`] / pathfinder code.
/// Optional [`SearchBudget`] caps expansions and/or wall-clock time; default is
/// unlimited.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct SearchRequest {
    /// Inclusive path start cell.
    pub start: Point,
    /// Inclusive path goal cell.
    pub goal: Point,
    /// Optional expansion / wall-clock caps for this query (default unlimited).
    pub budget: SearchBudget,
}

impl SearchRequest {
    /// Pairs start and goal cells with an unlimited budget; walkability is checked at search time.
    #[must_use]
    pub const fn new(start: Point, goal: Point) -> Self {
        Self {
            start,
            goal,
            budget: SearchBudget::UNLIMITED,
        }
    }

    /// Returns a copy of this request with the given budget.
    #[must_use]
    pub const fn with_budget(mut self, budget: SearchBudget) -> Self {
        self.budget = budget;
        self
    }
}

/// Work counters produced by a grid search (algorithm-defined node visits).
///
/// `visited_nodes` is solver-local (cell expansions, jump stops, …); do not treat
/// it as a portable complexity metric across algorithms.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct SearchStats {
    /// Nodes the solver counts as expanded or settled (see algorithm docs).
    pub visited_nodes: usize,
}

/// Failure to execute a grid search request (request validation or hard stop).
///
/// Unreachable but valid endpoints produce [`SearchOutcome::NoPath`], not these variants.
/// Caller [`SearchBudget`] exhaustion is [`Self::BudgetExhausted`] and does **not**
/// prove unreachability.
#[non_exhaustive]
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum GridSearchError {
    /// Start is out of bounds or not walkable.
    InvalidStart { point: Point },
    /// Goal is out of bounds or not walkable.
    InvalidGoal { point: Point },
    /// Caller search budget was exhausted before found/no-path completed.
    BudgetExhausted(BudgetExhausted),
    /// Flow-field path sampling stopped after `max_steps` steps without the goal.
    ///
    /// Not a general [`Pathfinder`] expansion budget API; only
    /// [`crate::flow_field`] sampling emits this variant.
    StepLimitReached { max_steps: usize, reached: Point },
}

impl fmt::Display for GridSearchError {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::InvalidStart { point } => write!(formatter, "invalid start point: {point:?}"),
            Self::InvalidGoal { point } => write!(formatter, "invalid goal point: {point:?}"),
            Self::BudgetExhausted(reason) => write!(formatter, "{reason}"),
            Self::StepLimitReached { max_steps, reached } => write!(
                formatter,
                "search stopped after {max_steps} steps at {reached:?} before reaching the goal"
            ),
        }
    }
}

impl Error for GridSearchError {}

/// Grid search return type: validation error, or found/no-path with stats.
pub type SearchResult = Result<SearchOutcome<Path, SearchStats>, GridSearchError>;

/// Owner-crate helper: wraps a found path into [`SearchResult`] with visit stats.
#[doc(hidden)]
pub const fn found(path: Path, visited_nodes: usize) -> SearchResult {
    Ok(SearchOutcome::found(path, SearchStats { visited_nodes }))
}

/// Owner-crate helper: wraps exhaustive no-path into [`SearchResult`] with visit stats.
#[doc(hidden)]
pub const fn not_found(visited_nodes: usize) -> SearchResult {
    Ok(SearchOutcome::no_path(SearchStats { visited_nodes }))
}

/// Rejects out-of-bounds or blocked start/goal before search (validation `Err`, not no-path).
#[doc(hidden)]
pub fn validate_request(grid: &Grid, request: SearchRequest) -> Result<(), GridSearchError> {
    if !grid.is_walkable(request.start) {
        return Err(GridSearchError::InvalidStart {
            point: request.start,
        });
    }
    if !grid.is_walkable(request.goal) {
        return Err(GridSearchError::InvalidGoal {
            point: request.goal,
        });
    }
    Ok(())
}

impl SearchPathCost for Path {
    type Cost = usize;

    fn path_cost(&self) -> Self::Cost {
        self.cost()
    }
}

impl SearchVisitStats for SearchStats {
    fn visited_nodes(&self) -> usize {
        self.visited_nodes
    }
}

/// Online algorithm entrypoint for static 4-connected grid search.
///
/// Implementations must validate endpoints (walkable start/goal), return
/// [`GridSearchError`] for invalid requests or exhausted [`SearchBudget`], and
/// never panic on in-bounds grids. Unreachable but valid endpoints yield
/// [`SearchOutcome::NoPath`], not an error. Cost models and heuristics are
/// algorithm-defined (unit hop vs `traversal_cost`).
pub trait Pathfinder {
    /// Stable algorithm identifier for benchmarks, logs, and solver portfolios.
    fn name(&self) -> &'static str;

    /// Runs one search on `grid` for `request`.
    ///
    /// Returns `Err` for invalid endpoints or exhausted budgets, `Ok(NoPath)` when
    /// exhaustive search finds no route, and `Ok(Found)` with a non-empty path and
    /// stats when a route is found.
    fn search(&self, grid: &Grid, request: SearchRequest) -> SearchResult;
}

/// Maps a shared budget failure into [`GridSearchError::BudgetExhausted`].
#[doc(hidden)]
pub const fn budget_error(reason: BudgetExhausted) -> GridSearchError {
    GridSearchError::BudgetExhausted(reason)
}