# condor
[](https://crates.io/crates/condor-for-games)
[](https://github.com/bnomei/condor/actions/workflows/ci.yml)
[](https://codspeed.io/bnomei/condor?utm_source=badge)
[](https://crates.io/crates/condor-for-games)
[](https://github.com/bnomei/condor/blob/main/LICENSE)
[](https://discordapp.com/users/bnomei)
[](https://www.buymeacoffee.com/bnomei)
Condor is a Rust pathfinding library for comparing multiple algorithm families
across grid maps, weighted grids, exact polygonal scenes, and deterministic
navmeshes.
It currently exposes public APIs for:
- grid search through the `Pathfinder` trait
- static grid preprocessing through `PreprocessedGridBuilder`
- exact polygonal search through the `PolygonPathfinder` trait
- exact navmesh search through the `NavmeshPathfinder` trait
- repeated-query polygonal preprocessing through `ContinuousShortestPathMap`
The published `condor-for-games` package is the curated consumer facade. Its
Rust library name is `condor` (same idea as `cargo add condor-for-games --rename condor`).
The `core`, `geometry`, `grid`, and `navmesh` workspace crates own the
implementations. Root examples intentionally use the facade exactly as
downstream callers do.
## Current Algorithms
### Grid (`Pathfinder`)
- `Bfs`: unweighted baseline
- `AStar`: heuristic grid search
- `BidirectionalBfs`: two-frontier unweighted search
- `Dijkstra`: weighted-grid baseline
- `JumpPointSearch`: 4-way jump-point search
- `RectangularSymmetryReduction`: 4-way room/corridor specialist
### Preprocessed Static Grid (`PreprocessedGridBuilder`)
- `StaticPreparedGridBuilder`: build-once/query-many contract proof that owns a
grid snapshot and delegates queries to A*
### Exact Polygonal Scenes (`PolygonPathfinder`)
- `VisibilityGraph`: exact sparse-scene baseline
- `TopologicalFractureSearch`: exact continuous polygonal competitor
### Repeated-Query Polygonal
- `ContinuousShortestPathMap`: preprocess once, then answer many goals from the
same source
### Navmesh Routing (`NavmeshPathfinder` / `PreparedNavmeshBuilder`)
- `Polyanya`: exact online navmesh baseline on the current deterministic
substrate
- `ChannelSearch`: static corridor-search navmesh competitor
- `TAStar`: tactical online navmesh route search
- `TRAStarBuilder`: prepared TRA* routing and the current recommended navmesh
entrypoint
### Dynamic Navmesh Availability
- `DynamicNavmeshState`: bounded cell and portal availability updates over an
existing navmesh, with materialized static snapshots for raw query and
prepared rebuild
## Using The Library
The public API is split by problem model. Grid, polygonal, and navmesh
algorithms do not share one universal trait.
### Add Condor
The Cargo package is `condor-for-games`; its Rust library is `condor`. Add it
with a rename so application code imports `condor::{...}`:
```bash
cargo add condor-for-games --rename condor
```
Or in `Cargo.toml` for a grid-only surface:
```toml
[dependencies]
condor = { package = "condor-for-games", version = "0.4.0", default-features = false, features = ["grid"] }
```
Then import the curated public API from `condor`:
```rust
use condor::{AStar, Grid, Pathfinder};
```
Omit the feature settings when you want the default complete public surface.
Application code should depend on the facade as `condor`, not directly on
implementation crates such as `condor-pathfinding-grid`.
### How the workspace is organized
`condor` is the public facade. Grid, continuous geometry, and navmesh runtime
implementations live in their owner crates behind that facade; their types are
re-exported without becoming separate consumer APIs. Private support packages
own correctness corpora (`condor-harness`), benchmark/capture evidence
(`condor-bench`), and the read-only developer catalog (`condor-lab`).
This keeps application imports stable while keeping fixtures and generated
evidence out of the published API. Contributor ownership, package-edge rules,
and validation routes are in [CONTRIBUTING.md](CONTRIBUTING.md).
### Search budgets
Online pathfinders accept an optional [`SearchBudget`](https://docs.rs/condor-for-games) on
each request/query (`SearchRequest`, `AnyAngleSearchRequest`, `PolygonSearchRequest`,
`NavmeshQuery`). Default is unlimited. When a budget is exhausted the solver returns a
domain `Err(…BudgetExhausted…)` — that is a hard stop, **not** a proof of unreachability
(`Ok(NoPath)`). Hosts that embed Condor on untrusted maps should still set map-size limits
outside the library; prepared any-angle preprocess budgets remain separate fail-closed
build caps (`PREPARED_ANY_ANGLE_*`).
```rust
use condor::{AStar, Grid, Pathfinder, Point, SearchBudget, SearchRequest};
use std::time::Duration;
let grid = Grid::new(32, 32).expect("grid dimensions are valid");
let request = SearchRequest::new(Point::new(0, 0), Point::new(31, 31))
.with_budget(
SearchBudget::max_expansions(64)
.with_max_duration(Duration::from_millis(5)),
);
let _ = AStar.search(&grid, request);
```
### Grid Example
```rust
use condor::{AStar, Cell, Grid, Pathfinder, Point, SearchRequest};
let mut grid = Grid::new(8, 8).expect("grid dimensions are valid");
for point in [Point::new(3, 2), Point::new(3, 3), Point::new(3, 4)] {
grid.set_cell(point, Cell::Blocked)
.expect("point is in bounds");
}
let pathfinder = AStar;
let result = pathfinder.search(
&grid,
SearchRequest::new(Point::new(0, 0), Point::new(7, 7)),
).expect("request endpoints are valid");
assert!(result.is_found());
println!("visited nodes: {}", result.stats().visited_nodes);
println!("path cost: {:?}", result.cost());
```
For compact literal maps, `grid!` delegates to the same validated row parser as
`Grid::try_from_rows`:
```rust
let grid = condor::grid![
".....",
"..#..",
".3...",
].expect("grid literal is valid");
```
### Preprocessed Grid Example
This is a preprocess/query API for repeated static-grid requests. The starter
baseline records build metadata separately from query `SearchStats` and does
not claim acceleration. `HPAStarBuilder` is also exposed through the same
neutral contract as the first concrete prepared-grid consumer.
```rust
use condor::{
Grid, Point, PreparedGridSearch, PreprocessedGridBuilder, SearchRequest,
StaticPreparedGrid,
};
let grid = Grid::new(8, 8).expect("grid dimensions are valid");
let prepared = StaticPreparedGrid::builder()
.preprocess(&grid)
.expect("grid should preprocess");
let result = prepared
.search(SearchRequest::new(Point::new(0, 0), Point::new(7, 7)))
.expect("request endpoints are valid");
assert!(result.is_found());
assert_eq!(prepared.metadata().builder_name, "static-prepared-grid");
```
Run `cargo run -p condor-bench --example capture_preprocessed_grid_report` to emit
`target/condor/reports/static-prepared-grid-foundation-v0.json`. The
report labels the pass-through baseline and HPA* consumer lanes separately.
For weighted grids, use the same API and set traversal costs on open cells:
```rust
use condor::{Dijkstra, Grid, Pathfinder, Point, SearchRequest};
let mut grid = Grid::new(4, 4).expect("grid dimensions are valid");
grid
.set_traversal_cost(Point::new(1, 0), 5)
.expect("traversal cost is positive");
grid
.set_traversal_cost(Point::new(1, 1), 5)
.expect("traversal cost is positive");
let result = Dijkstra.search(
&grid,
SearchRequest::new(Point::new(0, 0), Point::new(3, 3)),
).expect("request endpoints are valid");
assert!(result.is_found());
```
### Exact Polygonal Example
```rust
use condor::{PolygonPathfinder, VisibilityGraph, polygonal::load_polygon_scene_pack};
fn main() -> Result<(), Box<dyn std::error::Error>> {
let pack = load_polygon_scene_pack()?;
let fixture = &pack.scenes[0];
let pathfinder = VisibilityGraph;
let result = pathfinder.search(&fixture.scene, fixture.request)?;
assert!(result.is_found());
println!("polygon cost: {:?}", result.cost());
Ok(())
}
```
### Repeated-Query Polygonal Example
This is a preprocess/query API, not another `PolygonPathfinder`.
```rust
use condor::{
ContinuousShortestPathMap, PolygonShortestPathMap, PolygonShortestPathMapBuilder,
polygonal::load_polygon_scene_pack,
};
fn main() -> Result<(), Box<dyn std::error::Error>> {
let pack = load_polygon_scene_pack()?;
let fixture = &pack.scenes[0];
let map = ContinuousShortestPathMap.preprocess(&fixture.scene, fixture.request.start)?;
let result = map.query(fixture.request.goal)?;
assert!(result.is_found());
Ok(())
}
```
### Exact Navmesh Example
```rust
use condor::{
Navmesh, NavmeshCell, NavmeshPortal, NavmeshQuery, PreparedNavmeshBuilder, Point2,
TRAStarBuilder,
};
fn main() -> Result<(), Box<dyn std::error::Error>> {
let navmesh = Navmesh::new(
vec![
NavmeshCell::new("left", vec![
Point2::new(0.0, 0.0), Point2::new(2.0, 0.0),
Point2::new(2.0, 2.0), Point2::new(0.0, 2.0),
]),
NavmeshCell::new("right", vec![
Point2::new(2.0, 0.0), Point2::new(4.0, 0.0),
Point2::new(4.0, 2.0), Point2::new(2.0, 2.0),
]),
],
vec![NavmeshPortal {
left_cell: 0, right_cell: 1,
start: Point2::new(2.0, 0.0), end: Point2::new(2.0, 2.0),
}],
);
navmesh.validate()?;
let query = NavmeshQuery::new(Point2::new(0.5, 1.0), Point2::new(3.5, 1.0));
let prepared = TRAStarBuilder.preprocess(&navmesh)?;
let result = prepared.search(query)?;
assert!(result.is_found());
println!("navmesh cost: {:?}", result.cost());
Ok(())
}
```
### Dynamic Navmesh Update Example
Dynamic navmesh updates are availability changes over the current cells and
portals. They invalidate prepared data; rebuild from the materialized snapshot
before issuing a prepared query.
```rust
use condor::{
DynamicNavmeshState, DynamicNavmeshUpdate, DynamicPreparedNavmeshQuery, Navmesh,
NavmeshCell, NavmeshPortal, NavmeshQuery, Point2, StaticPreparedNavmeshBuilder,
};
fn main() -> Result<(), Box<dyn std::error::Error>> {
let navmesh = Navmesh::new(
vec![
NavmeshCell::new("left", vec![
Point2::new(0.0, 0.0), Point2::new(2.0, 0.0),
Point2::new(2.0, 2.0), Point2::new(0.0, 2.0),
]),
NavmeshCell::new("right", vec![
Point2::new(2.0, 0.0), Point2::new(4.0, 0.0),
Point2::new(4.0, 2.0), Point2::new(2.0, 2.0),
]),
],
vec![NavmeshPortal {
left_cell: 0, right_cell: 1,
start: Point2::new(2.0, 0.0), end: Point2::new(2.0, 2.0),
}],
);
let mut state = DynamicNavmeshState::new(navmesh)?;
let result = DynamicPreparedNavmeshQuery::run(
&mut state,
[DynamicNavmeshUpdate::set_portal_enabled("left", "right", false)],
NavmeshQuery::new(Point2::new(0.5, 1.0), Point2::new(3.5, 1.0)),
&StaticPreparedNavmeshBuilder,
)?;
assert!(result.metadata.prepared_stale_after_updates);
assert!(!state.prepared_stale());
Ok(())
}
```
The checked-in corpus and per-step capture route are developer tools: use
`condor_harness::navmesh` for fixture-backed conformance and
`cargo run -p condor-bench --example capture_dynamic_navmesh_report` for
update, invalidation, raw-query, rebuild-status, and rebuilt-prepared evidence.
This lane is rebuild-only for bounded cell and portal availability updates; it
does not claim incremental prepared repair, tactical routing, local steering,
or mesh generation.
## Public API Entry Points
The following curated map names the literal crate-root algorithm imports that
matter and the module-owned support surfaces around them. These groups are the
preferred external entrypoints for their stated problem models:
### Primary entrypoints by problem model
- **Grid and dynamic-grid pathfinding:** `Grid`, `Point`, `SearchRequest`, `Pathfinder`, `AStar`, `Dijkstra`, `Bfs`, `BidirectionalBfs`, `JumpPointSearch`, `RectangularSymmetryReduction`, `GridReplanner`, and `DStarLite`.
- **Preprocessed static grids:** `PreprocessedGridBuilder`, `PreparedGridSearch`, and `StaticPreparedGridBuilder`.
- **MAPF validation foundation:** `MapfProblem`, `MapfPlan`, `MapfConflict`, `MapfPlanMetrics`, and `load_mapf_fixture_pack`.
- **Any-angle grid paths:** `AnyAnglePathfinder`, `ThetaStar`, `LazyThetaStar`, and `Anya`.
- **Polygonal scenes:** `Point2`, `PolygonScene`, `PolygonSearchRequest`, `PolygonPathfinder`, `VisibilityGraph`, and `ContinuousShortestPathMap`.
- **Navmesh routing:** `Navmesh`, `NavmeshQuery`, `NavmeshPathfinder`, `PreparedNavmeshBuilder`, and `TRAStarBuilder`.
- **Recommendation facade:** `SolverPortfolio`, `SolverUseCase`, `SolverPortfolioRecommendation`, `SolverSurface`, `SolverRecommendationStatus`, `SolverPortfolio::recommend`, and `SolverPortfolio::catalog`.
### Supporting recommendation, discovery, and capture surfaces
- [`examples/solver_selection.rs`](examples/solver_selection.rs) shows how to choose a curated entrypoint.
- `condor_bench::consumer_surface_index::ConsumerSurfaceIndex::catalog` indexes the recommendation, guide, catalog, and export packets.
- `condor_bench::replanning_capture_catalog::InterpolatedReplanningCaptureCatalog::catalog` catalogs the current interpolated foundation and FieldDStar trace packs.
- `condor_bench::public_surface_audit::PublicSurfaceAudit::catalog` publishes the audit baseline that anchors this curation.
## Best Current Picks
- For static unweighted grids, use `AStar`.
- For weighted grids, use `Dijkstra`.
- For dynamic grid replanning, use `DStarLite`.
- For any-angle grid paths, use `Anya`.
- For exact polygonal scenes, use `VisibilityGraph`.
- For repeated polygonal queries from one fixed source, use
`ContinuousShortestPathMap`.
- For exact navmesh routing, use `TRAStarBuilder`.
- For dynamic navmesh availability changes, use `DynamicNavmeshState` and
rebuild prepared data from its materialized snapshot after each update.
- For interpolated dynamic replanning, watch `FieldDStar`; that lane is active
but still expanding.
If you want one bounded API for these current picks instead of hand-maintaining
the mapping in your application, use `SolverPortfolio::recommend(...)`.
```rust
use condor::{SolverPortfolio, SolverUseCase};
let recommendation = SolverPortfolio::recommend(SolverUseCase::ExactNavmeshRouting);
assert_eq!(
recommendation.solver_surface().public_entrypoint(),
"TRAStarBuilder"
);
assert_eq!(
recommendation.solver_surface().integration_surface(),
"PreparedNavmeshBuilder"
);
```
The canonical recommendation-to-usage bridge is the runnable example
[`examples/solver_selection.rs`](examples/solver_selection.rs).
The developer-side `ConsumerSurfaceIndex` and
`InterpolatedReplanningCaptureCatalog` types provide discovery over the current
solver-portfolio, fixed-goal, moving-goal, partial-path, and fallback capture
surfaces.
The nine focused caller-owned examples live under
[`examples/`](examples/README.md): grid and weighted search, preprocessed and
any-angle grids, polygonal and fixed-source polygonal queries, prepared and
dynamic navmeshes, and solver selection.
For transparency about the current benchmark/report coverage, run
[`cargo run -p condor-bench --example capture_benchmark_scorecard`](dev/condor-bench/examples/capture_benchmark_scorecard.rs)
to emit `target/condor/catalogs/benchmark-scorecard-v0.json`.
### Story packs (S0–S3 lab corpus)
Condor-owned multi-query **story families** explain when algorithms look strong
or weak. They are lab evidence, not Moving AI publication parity.
| S0 | Story family contract + catalog | `condor_bench::story_family_catalog` |
| S1 | Grid multi-query lab (120 scenarios) | `dev/condor-harness/fixtures/grid/story/` |
| S2 | Weighted + any-angle lab | `dev/condor-harness/fixtures/grid/` |
| S3 | Continuous / TFS stress depth | `dev/condor-harness/fixtures/polygonal/` |
```sh
just test-story
cargo run -p condor-bench --example capture_story_family_catalog
cargo run -p condor-bench --example seed_story_reports
cargo run -p condor-bench --example capture_benchmark_report -- story-grid-lab astar
cargo run -p condor-bench --example capture_benchmark_report -- story-weighted-lab dijkstra
```
Seeded story reports use synthetic Criterion slopes for harness wiring; path
costs and expansion stats come from live solvers. `StoryFamilyCatalog` owns the
thesis, counter-algorithm, provenance, CI policy, and fail-if fields.
For a grouped progress view with stable row ids, evidence kinds, explicit gap
rows, and community-atlas provenance pointers, run
[`cargo run -p condor-bench --example capture_benchmark_progress_tracker`](dev/condor-bench/examples/capture_benchmark_progress_tracker.rs)
to emit `target/condor/catalogs/benchmark-progress-tracker-v0.json`. The tracker
artifact is a versioned JSON object with rows sorted by stable `row_id`,
structured `evidence` pointers. These generated outputs are local developer
evidence and are not part of crate package contents.
MAPF foundation fixtures
------------------------
The first multi-agent pathfinding surface is a foundation plus a bounded starter
baseline. It models agents, static 4-way grids, time-stepped plans, wait and
cardinal movement, vertex conflicts, edge-swap conflicts, makespan, and
sum-of-costs metrics. `MapfStarterPlanner` adds a deterministic fixed-order
reservation-table baseline with an explicit finite horizon; it is not complete,
optimal, benchmark-comparable MAPF solving, CBS/ICBS/ECBS, lifelong assignment,
or local avoidance. The Condor-owned fixtures live in
[`dev/condor-harness/fixtures/grid/mapf-conformance.toml`](dev/condor-harness/fixtures/grid/mapf-conformance.toml), and
the JSON capture example, which labels validation-only and planner-owned rows
separately:
```sh
cargo run -p condor-bench --example capture_mapf_report
```
For explicit readiness guidance, run
[`cargo run -p condor-bench --example capture_stability_matrix`](dev/condor-bench/examples/capture_stability_matrix.rs)
to export `target/condor/catalogs/stability-matrix-v0.json`. The matrix clarifies
which surfaces are stable defaults, which remain watch-only, and which serve
as supporting discovery assets.
Before declaring a release, follow [CONTRIBUTING.md](CONTRIBUTING.md) and run
[`cargo run -p condor-bench --example capture_release_readiness`](dev/condor-bench/examples/capture_release_readiness.rs)
to regenerate `target/condor/catalogs/release-readiness-v0.json`. That doc and
artifact keep the manual pre-release checklist explicit without claiming the
crate is already published.
Dependency and security update expectations also live in
[CONTRIBUTING.md](CONTRIBUTING.md). The repository keeps this gate
intentionally narrow around RustSec advisories.
If you need the full current recommendation matrix for tooling, docs, or other
consumer-facing surfaces, use `SolverPortfolio::catalog()`.
## Benchmarks And Reports
Criterion is split into independent binaries so one evidence lane does not
compile or execute every benchmark family. Select the narrowest owner:
| `grid_core` | uniform, weighted, atlas, community grids | `just bench-grid-core` |
| `grid_lab` | story-grid scenarios; stress is opt-in | `just bench-grid-lab` |
| `continuous_core` | ordinary polygonal routing | `just bench-continuous-core` |
| `continuous_stress` | polygonal stress scenarios | `just bench-continuous-stress` |
| `navmesh_direct` / `navmesh_prepared` | direct and prepared navmesh work | `just bench-navmesh-direct` / `just bench-navmesh-prepared` |
| `any_angle` / `any_angle_promotion` | standard and promotion-corpus any-angle runs | `just bench-any-angle` / `just bench-any-angle-promotion` |
For compile-only coverage, use `just bench-compile-one <lane>`; the full suite is
reserved for CI with `just bench-compile-all`.
The report capture tool at
[`dev/condor-bench/examples/capture_benchmark_report.rs`](dev/condor-bench/examples/capture_benchmark_report.rs)
currently supports:
- `uniform`
- `weighted`
- `community-derived`
- `continuous`
- `atlas`
- `navmesh`
- `any-angle`
Repeated fixed-source polygonal query evidence is captured separately through
[`dev/condor-bench/examples/capture_continuous_shortest_path_map_report.rs`](dev/condor-bench/examples/capture_continuous_shortest_path_map_report.rs).
That report records `ContinuousShortestPathMap` preprocessing and repeated query
results against the polygon scene pack without claiming Criterion-backed
benchmark coverage for that lane yet.
## Derived Community Atlas
Condor now also exposes a local derived community atlas for internal algorithm
improvement work. It stages Condor-owned benchmark families informed by Moving
AI and Iron Harvest, but it does not claim official benchmark parity with those
upstream suites.
Use:
- `condor_bench::community_benchmark_atlas::CommunityBenchmarkAtlas::families()`
- `condor_bench::community_benchmark_atlas::CommunityBenchmarkAtlas::scenario_index()`
The canonical machine-readable export can be regenerated with
[`dev/condor-bench/examples/capture_community_benchmark_atlas.rs`](dev/condor-bench/examples/capture_community_benchmark_atlas.rs).
## Condor Lab TUI
Condor includes a read-only terminal lab for repeated inspection of the current
solver picks, consumer surfaces, benchmark coverage, benchmark progress,
stability rows, and community atlas families and scenarios.
Run the full-screen TUI:
```sh
cargo run -p condor-lab --bin condor-lab
```
Run the deterministic noninteractive summary:
```sh
cargo run -p condor-lab --bin condor-lab -- --summary
```
Run help:
```sh
cargo run -p condor-lab --bin condor-lab -- --help
```
The TUI exposes section-specific details, including available documentation
paths, example commands, benchmark artifacts, capture targets, explicit
`covered`, `capture-only`, `gap`, `stable`, `watch-only`, and `supporting`
statuses, and atlas provenance notes. It does not execute benchmarks, mutate
artifacts, download datasets, claim upstream benchmark parity, or perform
graphical playback.
## Useful Commands
- Fast focused test: `just test-fast <target>`
- Full non-ignored tests plus doctests: `just test-full`
- Exact oracle differential (explicit, serial): `just test-oracle <test-name>`
- Story stress evidence (explicit, serial): `just test-story-stress`
- `cargo fmt --all`
- `cargo clippy --all-targets --all-features -- -D warnings`
- `cargo audit --deny warnings`
- Filtered benchmark evidence: `just bench-any-angle-promotion -- <Criterion args>`
- Compile one benchmark lane only: `just bench-compile-one any_angle_promotion`
- `cargo run -p condor-bench --example capture_benchmark_report -- uniform bfs`
- `cargo run -p condor-bench --example capture_benchmark_report -- community-derived astar`
- `cargo run -p condor-bench --example capture_benchmark_report -- atlas astar`
- `cargo run -p condor-bench --example capture_continuous_shortest_path_map_report`
- `cargo run -p condor-bench --example capture_benchmark_progress_tracker`
- `cargo run -p condor-bench --example capture_community_benchmark_atlas`
- `cargo run -p condor-bench --example inspect_astar_rooms -- community-derived mai-rts-frontier-96x64`
- `cargo run -p condor-bench --example capture_benchmark_report -- navmesh polyanya`
- `cargo run -p condor-bench --example capture_dynamic_navmesh_report`
- `cargo run -p condor-bench --example capture_preprocessed_grid_report`
- `cargo run -p condor-lab --bin condor-lab`
- `cargo run -p condor-lab --bin condor-lab -- --summary`
## Roadmap
Condor's next wave is less about adding one more narrow variant and more about
making the library broader, easier to inspect, and stronger on shared
benchmarks.
- [ ] Broaden the benchmark atlas with further derived families informed by
community datasets such as Moving AI and cross-representation sets like
Iron Harvest.
- [x] Add `condor-lab`, a read-only terminal workspace for browsing solver
picks, consumer surfaces, benchmark coverage, stability rows, and atlas
metadata.
- [ ] Extend prepared static-grid solver evidence beyond the current neutral
baseline and HPA* consumer to families such as subgoal and database-backed
approaches.
- [x] Add starter multi-agent pathfinding planning on top of the MAPF
validation foundation.
- [ ] Add dynamic and tactical navmesh routing, including update-aware mesh
handling and replanning.
- [x] Add a public benchmark tracker that makes progress, gaps, and standings
easier to inspect than raw artifacts alone.