condor-pathfinding-grid 0.4.0

Grid pathfinding, preprocessing, replanning, and multi-agent algorithms for Condor.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

//! Dynamic-grid [`GridReplanner`] entrypoint: D* Lite surface.
//!
//! [`GridReplanner::initialize`] seeds reusable LPA* state; cell/cost updates take
//! effect on the next [`GridReplanner::replan`]. It returns the standard discrete
//! invalid/found/no-path outcome with per-cell [`traversal_cost`](crate::Grid::traversal_cost)
//! and Manhattan keys. Prefer this public entrypoint for changing integer-cell maps;
//! use [`super::field_d_star::FieldDStar`] only for fractional interpolated requests.
//!
//! # Examples
//!
//! ```
//! use condor_grid::{algorithms::d_star_lite::DStarLite, Grid, GridReplanner, Point, SearchRequest};
//!
//! let mut replanner = DStarLite::default();
//! let grid = Grid::new(3, 3).expect("grid dimensions are valid");
//! let request = SearchRequest::new(Point::new(0, 0), Point::new(2, 2));
//! let initial = replanner.initialize(&grid, request).expect("request is valid");
//! assert!(initial.is_found());
//! ```
use crate::algorithms::lifelong_planning_astar::LifelongPlanningAStar;
use crate::{
    grid::{Grid, GridEditError},
    point::Point,
    replanning::GridReplanner,
    search::{SearchRequest, SearchResult},
};

/// Curated dynamic-grid [`GridReplanner`] (D* Lite product name).
///
/// Implementation reuses [`super::lifelong_planning_astar::LifelongPlanningAStar`]
/// (`g`/`rhs` + priority queue). Cost model: per-cell `traversal_cost` on 4-connected
/// edges with Manhattan keys. Prefer for discrete cell/cost updates between replans.
pub struct DStarLite {
    replanner: LifelongPlanningAStar,
}

impl Default for DStarLite {
    fn default() -> Self {
        Self::new()
    }
}

impl DStarLite {
    /// Creates an uninitialized replanner; call [`GridReplanner::initialize`] before replan.
    #[must_use]
    pub fn new() -> Self {
        Self {
            replanner: LifelongPlanningAStar::new(),
        }
    }
}

impl GridReplanner for DStarLite {
    fn name(&self) -> &'static str {
        "d-star-lite"
    }

    fn initialize(&mut self, grid: &Grid, request: SearchRequest) -> SearchResult {
        self.replanner.initialize(grid, request)
    }

    fn update_cell(&mut self, point: Point, cell: crate::grid::Cell) {
        self.replanner.update_cell(point, cell)
    }

    fn update_cost(&mut self, point: Point, cost: usize) -> Result<(), GridEditError> {
        self.replanner.update_cost(point, cost)
    }

    fn replan(&mut self) -> SearchResult {
        self.replanner.replan()
    }
}