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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

//! Grid-domain owner crate for discrete pathfinding substrate.
//!
//! This domain crate owns the map model ([`Grid`]), discrete and any-angle search
//! contracts ([`Pathfinder`], [`AnyAnglePathfinder`]), prepared / preprocessed
//! multi-query maps, flow fields, hierarchical abstracts, MAPF starter surface,
//! and incremental replanning traits. Algorithm implementations live under
//! [`algorithms`]; root re-exports form the curated consumer surface that the
//! public facade (`condor-for-games` / lib `condor`) mirrors for compatibility.
//!
//! **Not** polygonal / navmesh routing — those live in sibling domain crates.
//! This owner crate depends on neutral core contracts, never on the public
//! facade; corpus conformance and capture evidence live in private developer
//! packages.
//!
//! # Choose a grid surface
//!
//! | Need | Start with |
//! | --- | --- |
//! | One static 4-connected query | [`AStar`] via [`Pathfinder`] |
//! | Straight-line paths through a grid | [`AnyAnglePathfinder`] implementations |
//! | Many queries over one static grid | [`PreprocessedGridBuilder`] or a domain-specific prepared builder |
//! | Changing costs or blocked cells | [`GridReplanner`] / [`InterpolatedGridReplanner`] |
//! | Multiple agents | [`MapfStarterPlanner`] |
//!
//! # Example
//!
//! ```
//! use condor_grid::{AStar, Cell, Grid, Pathfinder, Point, SearchRequest};
//!
//! let mut grid = Grid::new(3, 3).expect("grid dimensions are valid");
//! grid.set_cell(Point::new(1, 1), Cell::Blocked)
//!     .expect("point is in bounds");
//! let result = AStar.search(
//!     &grid,
//!     SearchRequest::new(Point::new(0, 0), Point::new(2, 2)),
//! ).expect("request is valid");
//! assert!(result.is_found());
//! ```

#![forbid(unsafe_code)]

/// Grid algorithm implementations (static, prepared, any-angle, replanning families).
pub mod algorithms;
/// Any-angle pathfinder trait and continuous-on-grid request/result contracts.
pub mod any_angle;
/// Same-goal multi-agent flow-field build and query amortization.
pub mod flow_field;
/// Discrete grid storage, cell model, and edit/build errors.
pub mod grid;
/// Hierarchical abstract-grid layers for multi-level search.
pub mod hierarchical;
/// Multi-agent pathfinding starter planner and conflict vocabulary.
pub mod mapf;
/// Discrete path reconstruction and path cost types.
pub mod path;
/// Integer cell coordinates for the discrete grid lane.
pub mod point;
/// Prepared any-angle visibility graphs over static grids.
pub mod prepared_any_angle;
/// Preprocessed static multi-query grid search substrates.
pub mod preprocessed_grid;
/// Incremental grid replanning and interpolated continuous-on-grid routes.
pub mod replanning;
/// Online [`Pathfinder`] trait, search request, budget, and outcome contracts.
pub mod search;

// Private, not-ready MAPF-family candidates beside their mature family.
#[allow(
    dead_code,
    reason = "private candidate retained for normal-family evaluation"
)]
mod mapf_flow_bounds;
#[allow(
    dead_code,
    reason = "private candidate retained for normal-family evaluation"
)]
mod mapf_target_assignment;

pub use algorithms::anya::{Anya, AnyaDiagnostics, AnyaInspection};
pub use algorithms::astar::{AStar, AStarDiagnostics, AStarInspection};
pub use algorithms::bfs::Bfs;
pub use algorithms::bidirectional_bfs::BidirectionalBfs;
pub use algorithms::dijkstra::Dijkstra;
pub use algorithms::hpa_star::{HPAStarBuilder, PreparedHPAStar};
pub use algorithms::jps_plus::{JpsPlusBuilder, PreparedJpsPlus};
pub use algorithms::jump_point_search::{
    JumpPointSearch, JumpPointSearchDiagnostics, JumpPointSearchInspection,
};
pub use algorithms::lazy_theta_star::LazyThetaStar;
pub use algorithms::rectangular_symmetry_reduction::RectangularSymmetryReduction;
pub use algorithms::subgoal_graph::{PreparedSubgoalGraph, SubgoalGraphBuilder};
pub use algorithms::theta_star::ThetaStar;
pub use any_angle::{
    AnyAnglePath, AnyAnglePathBuildError, AnyAnglePathfinder, AnyAngleSearchError,
    AnyAngleSearchRequest, AnyAngleSearchResult, AnyAngleSearchStats, has_line_of_sight,
};
pub use condor_core::Point2;
pub use flow_field::{FlowDirection, FlowFieldBuildError, FlowFieldBuilder, PreparedFlowField};
pub use grid::{Cell, Grid, GridBuildError, GridBuilder, GridEditError, GridStorage};
pub use hierarchical::{
    HierarchicalGridBuildError, HierarchicalGridBuilder, PreparedHierarchicalGrid,
};
pub use mapf::{
    MapfAgent, MapfAgentPath, MapfConflict, MapfObjective, MapfPlan, MapfPlanMetrics, MapfProblem,
    MapfStarterPlanner, MapfStarterPlannerFailure, MapfStarterPlannerOutcome,
    MapfStarterPlannerResult, MapfValidationReport,
};
pub use path::{Path, PathBuildError};
pub use point::Point;
pub use prepared_any_angle::{
    PREPARED_ANY_ANGLE_CSR_U32_INDEX_LIMIT, PREPARED_ANY_ANGLE_DEFAULT_BENCHMARK_NODE_BUDGET,
    PREPARED_ANY_ANGLE_DIRECTED_EDGE_BUDGET, PREPARED_ANY_ANGLE_NODE_BUDGET,
    PREPARED_ANY_ANGLE_RETAINED_BYTES_BUDGET, PreparedAnyAngleBenchmarkAdmission,
    PreparedAnyAngleBuildDiagnostics, PreparedAnyAngleGrid, PreparedAnyAngleGridBuildError,
    PreparedAnyAngleGridBuilder, PreparedAnyAngleQueryDiagnostics,
};
pub use preprocessed_grid::{
    PreparedGridSearch, PreprocessedGridBuildError, PreprocessedGridBuilder,
    PreprocessedGridMetadata, StaticPreparedGrid, StaticPreparedGridBuilder,
};
pub use replanning::{
    GridReplanner, InterpolatedExpectedKind, InterpolatedGridReplanner,
    InterpolatedMovingGoalReplanner, InterpolatedPath, InterpolatedPathBuildError,
    InterpolatedPathOutcome, InterpolatedPathOutcomeKind, InterpolatedPathOutcomeRef,
    InterpolatedQueryResult, InterpolatedSearchError, InterpolatedSearchOutcome,
    InterpolatedSearchRequest, InterpolatedSearchResult, InterpolatedSearchStats,
    InterpolatedTraversalCostModel, best_fallback_interpolated_path,
    best_partial_interpolated_path, interpolated_path_cost, interpolated_segment_cost,
    query_interpolated_grid,
};
pub use search::{
    BudgetExhausted, BudgetWatch, GridSearchError, Pathfinder, SearchBudget, SearchOutcome,
    SearchPathCost, SearchRequest, SearchResult, SearchStats, SearchVisitStats,
};