condor

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::{...}:

cargo add condor-for-games --rename condor

Or in Cargo.toml for a grid-only surface:

[dependencies]
condor = { package = "condor-for-games", version = "0.4.0", default-features = false, features = ["grid"] }

Then import the curated public API from condor:

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.

Search budgets

Online pathfinders accept an optional SearchBudget 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_*).

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

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:

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.

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:

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

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.

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

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.

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 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(...).

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. 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/: 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 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.

Wave	Pack / focus	Durable owner
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/

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 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, and the JSON capture example, which labels validation-only and planner-owned rows separately:

cargo run -p condor-bench --example capture_mapf_report

For explicit readiness guidance, run cargo run -p condor-bench --example capture_stability_matrix 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 and run cargo run -p condor-bench --example capture_release_readiness 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. 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:

Lane	Scope	Command
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 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. 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.

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:

cargo run -p condor-lab --bin condor-lab

Run the deterministic noninteractive summary:

cargo run -p condor-lab --bin condor-lab -- --summary

Run help:

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.
• 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.
• 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.
• Add a public benchmark tracker that makes progress, gaps, and standings easier to inspect than raw artifacts alone.