condor_grid/algorithms/
d_star_lite.rs

1//! Dynamic-grid [`GridReplanner`] entrypoint: D* Lite surface.
2//!
3//! [`GridReplanner::initialize`] seeds reusable LPA* state; cell/cost updates take
4//! effect on the next [`GridReplanner::replan`]. It returns the standard discrete
5//! invalid/found/no-path outcome with per-cell [`traversal_cost`](crate::Grid::traversal_cost)
6//! and Manhattan keys. Prefer this public entrypoint for changing integer-cell maps;
7//! use [`super::field_d_star::FieldDStar`] only for fractional interpolated requests.
8//!
9//! # Examples
10//!
11//! ```
12//! use condor_grid::{algorithms::d_star_lite::DStarLite, Grid, GridReplanner, Point, SearchRequest};
13//!
14//! let mut replanner = DStarLite::default();
15//! let grid = Grid::new(3, 3).expect("grid dimensions are valid");
16//! let request = SearchRequest::new(Point::new(0, 0), Point::new(2, 2));
17//! let initial = replanner.initialize(&grid, request).expect("request is valid");
18//! assert!(initial.is_found());
19//! ```
20use crate::algorithms::lifelong_planning_astar::LifelongPlanningAStar;
21use crate::{
22    grid::{Grid, GridEditError},
23    point::Point,
24    replanning::GridReplanner,
25    search::{SearchRequest, SearchResult},
26};
27
28/// Curated dynamic-grid [`GridReplanner`] (D* Lite product name).
29///
30/// Implementation reuses [`super::lifelong_planning_astar::LifelongPlanningAStar`]
31/// (`g`/`rhs` + priority queue). Cost model: per-cell `traversal_cost` on 4-connected
32/// edges with Manhattan keys. Prefer for discrete cell/cost updates between replans.
33pub struct DStarLite {
34    replanner: LifelongPlanningAStar,
35}
36
37impl Default for DStarLite {
38    fn default() -> Self {
39        Self::new()
40    }
41}
42
43impl DStarLite {
44    /// Creates an uninitialized replanner; call [`GridReplanner::initialize`] before replan.
45    #[must_use]
46    pub fn new() -> Self {
47        Self {
48            replanner: LifelongPlanningAStar::new(),
49        }
50    }
51}
52
53impl GridReplanner for DStarLite {
54    fn name(&self) -> &'static str {
55        "d-star-lite"
56    }
57
58    fn initialize(&mut self, grid: &Grid, request: SearchRequest) -> SearchResult {
59        self.replanner.initialize(grid, request)
60    }
61
62    fn update_cell(&mut self, point: Point, cell: crate::grid::Cell) {
63        self.replanner.update_cell(point, cell)
64    }
65
66    fn update_cost(&mut self, point: Point, cost: usize) -> Result<(), GridEditError> {
67        self.replanner.update_cost(point, cost)
68    }
69
70    fn replan(&mut self) -> SearchResult {
71        self.replanner.replan()
72    }
73}
condor_grid/algorithms/d_star_lite.rs

condor_grid/algorithms/
d_star_lite.rs
