condor-pathfinding-navmesh 0.4.0

//! Private candidate: rooted portal-interval search for exact navmesh routing.
//!
//! # Lifecycle (pinned)
//!
//! This candidate uses the existing [`crate::PreparedNavmeshBuilder`] lifecycle
//! only: preprocess clones one validated static [`crate::Navmesh`] into an
//! immutable prepared map, then many `search` calls share that snapshot. It is
//! **not** an online [`crate::NavmeshPathfinder`]. Availability changes require
//! a new static materialization and a fresh preprocess; prepared maps are never
//! patched in place.
//!
//! # Hypothesis
//!
//! A rooted portal-interval search may remain exact on larger or more obstructed
//! meshes where an explicit portal-corner graph becomes dense, by expanding
//! continuous portal intervals instead of only discrete corner vertices.
//!
//! # Deliverable-0: successor and dominance invariants
//!
//! These invariants are the correctness contract for interval expansion. Search
//! must not discard an optimal reachable interval; pruning is allowed only when
//! dominance is proven under this model.
//!
//! ## Interval state
//!
//! An open search node is a **rooted portal interval**:
//!
//! - `from_cell` / `to_cell` — directed portal crossing into `to_cell`
//! - `[lo, hi] ⊂ [0, 1]` — parametric coverage along the portal segment
//!   `start → end` (inclusive endpoints)
//! - `apex` — continuous entry point on that portal used as the parent for the
//!   next Euclidean step (typically the closest point on the covered subsegment
//!   to the previous apex, or a midpoint of the interval)
//! - `g` — path cost from the query start to `apex` (Euclidean polyline length
//!   along accepted apexes)
//! - `cells` — ordered cell sequence witnessing the root-to-here corridor
//!
//! The start node is a synthetic root at the start cell with `g = 0`,
//! `apex = start`, and empty portal interval (no incoming portal).
//!
//! ## Successor generation
//!
//! From a settled interval that lands in cell `C` with apex `A`:
//!
//! 1. Enumerate prepared neighbors `N` of `C` via the directed portal `P`.
//! 2. Skip neighbors already present in the cell path when forming simple
//!    corridors (no cell re-entry in the witness chain).
//! 3. Project `A` onto `P` to form candidate entry points; each candidate yields
//!    a successor interval on `P` with full or partial parametric coverage
//!    `[lo, hi]`, new apex `A'`, and `g' = g + ‖A' − A‖`.
//! 4. Every generated successor increments the successor counter (evidence that
//!    interval expansion ran; not a thin Pathfinder wrap).
//!
//! Successors must preserve reachability: if a continuous path from `A` through
//! free space can cross any open subsegment of `P`, that subsegment must appear
//! in some generated successor (or a covering superseding interval).
//!
//! ## Dominance pruning
//!
//! Let `I` and `J` be intervals on the **same directed portal** `(from, to)`.
//!
//! `I` **dominates** `J` when all of the following hold:
//!
//! 1. Coverage: `I.lo ≤ J.lo` and `I.hi ≥ J.hi` (I covers J's portal range).
//! 2. Cost: `I.g ≤ J.g + ε` (I is not more expensive to its apex).
//! 3. Apex consistency: the apex of `I` can serve as a parent for any point in
//!    `J`'s coverage without increasing `g` beyond `J.g` under the Euclidean
//!    step model used by successor generation (for equal coverage, lower `g`
//!    alone is sufficient).
//!
//! When `I` dominates `J`, `J` is pruned and must not be expanded. Pruning must
//! **never** discard an interval that is the unique carrier of an optimal
//! reachable apex on any open subsegment of the portal.
//!
//! Symmetric incomparability: if neither covers the other, or the lower-cost
//! interval has strictly smaller coverage, **both** are retained.
//!
//! ## Goal settlement and witness
//!
//! When an interval's `to_cell` is a goal-containing cell (or the root cell when
//! start and goal share a cell), the search may settle. The cell sequence from
//! the winning interval is materialized into a [`crate::navmesh::corridor::NavmeshCorridor`],
//! funnel string-pulled, and accepted only when
//! [`Navmesh::path_is_walkable`](crate::Navmesh::path_is_walkable) holds on the
//! returned polyline. Invalid endpoints remain typed errors; disconnected cell
//! graphs remain valid no-path outcomes.
//!
//! # Non-negotiable constraints
//!
//! - Successor generation and dominance pruning obey the invariants above.
//! - Preserve endpoint validation, valid no-path classification, and a fully
//!   walkable start-to-goal witness.
//! - Prepared maps remain immutable; availability updates require a new static
//!   materialization and preprocess step.
//!
//! # Evidence and promotion
//!
//! Use `just test-navmesh-lib` and `just clippy-navmesh-lib` while working.
//! Before promotion, require navmesh conformance (`just test-navmesh-conformance`),
//! oracle differential parity (`just test-navmesh-oracles` or one declared
//! `just test-navmesh-oracle <test>` case), and a measured scalability advantage
//! on declared stress families through `just bench-navmesh-prepared` when using
//! the prepared lifecycle. This candidate must first be integrated into that
//! existing benchmark lane; it does not create its own.

use std::collections::{BTreeMap, BinaryHeap};

use super::channel_search::portal_midpoint;
use super::tra_star::{PreparedTRAStar, TRAStarBuilder};
use crate::navmesh::points_equal;
use crate::{
    Navmesh, NavmeshPortal, NavmeshQuery, NavmeshQueryResult, NavmeshSearchResult, Point2,
    PolygonPath, PreparedNavmesh, PreparedNavmeshBuildError, PreparedNavmeshBuilder,
};

const EPSILON: f64 = 1e-9;

/// Prepared portal-interval search builder (private candidate).
///
/// Pins the multi-query lifecycle to [`PreparedNavmeshBuilder`]: preprocess once
/// on a static mesh, then search many times against the immutable snapshot.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct TRAStarPortalIntervalSearchBuilder;

impl TRAStarPortalIntervalSearchBuilder {
    /// Stable portfolio id for the rooted portal-interval candidate.
    pub const CANDIDATE_ID: &str = "exact-navmesh-routing/C002-portal-interval-search";

    /// Returns a builder instance (same as [`Default`]).
    #[must_use]
    pub const fn new() -> Self {
        Self
    }
}

impl PreparedNavmeshBuilder for TRAStarPortalIntervalSearchBuilder {
    type Map = PreparedTRAStarPortalIntervalSearch;

    fn name(&self) -> &'static str {
        "tra-star-portal-interval-search"
    }

    fn preprocess(&self, navmesh: &Navmesh) -> Result<Self::Map, PreparedNavmeshBuildError> {
        let prepared = TRAStarBuilder.preprocess(navmesh)?;
        Ok(PreparedTRAStarPortalIntervalSearch { prepared })
    }
}

/// Immutable prepared map that expands rooted portal intervals at search time.
///
/// Preprocess clones adjacency via base TRA*. Query runs interval successor
/// generation and dominance pruning, then corridor materialization + funnel for
/// a walkable Euclidean witness.
#[derive(Debug, Clone, PartialEq)]
pub struct PreparedTRAStarPortalIntervalSearch {
    prepared: PreparedTRAStar,
}

/// Counters proving interval expansion (not a Pathfinder-only thin wrap).
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct IntervalSearchEvidence {
    /// Successor intervals generated during expansion.
    pub successors_generated: usize,
    /// Intervals discarded because a covering, no-worse interval already existed.
    pub dominated_pruned: usize,
    /// Distinct directed portals that received at least one interval label.
    pub portals_labeled: usize,
}

impl PreparedTRAStarPortalIntervalSearch {
    /// Returns a [`TRAStarPortalIntervalSearchBuilder`] for preprocess entry.
    #[must_use]
    pub fn builder() -> TRAStarPortalIntervalSearchBuilder {
        TRAStarPortalIntervalSearchBuilder
    }

    /// Underlying base TRA* prepared surface.
    #[must_use]
    pub fn prepared_tra_star(&self) -> &PreparedTRAStar {
        &self.prepared
    }

    /// Routes with rooted portal-interval expansion, then funnel string-pull.
    pub fn search(&self, query: NavmeshQuery) -> NavmeshSearchResult {
        self.search_with_evidence(query).0
    }

    /// Same as [`Self::search`], but also returns interval bookkeeping evidence.
    ///
    /// Tests use this surface so dominance / successor work is observable and not
    /// elided by a Pathfinder-only wrap around TRA*.
    pub fn search_with_evidence(
        &self,
        query: NavmeshQuery,
    ) -> (NavmeshSearchResult, IntervalSearchEvidence) {
        let mut evidence = IntervalSearchEvidence::default();

        let (start_cell, goal_cell) = match self.prepared.query(query) {
            NavmeshQueryResult::Connected {
                start_cell,
                goal_cell,
            } => (start_cell, goal_cell),
            NavmeshQueryResult::InvalidStart => {
                return (
                    Err(crate::NavmeshSearchError::InvalidStart { point: query.start }),
                    evidence,
                );
            }
            NavmeshQueryResult::InvalidGoal => {
                return (
                    Err(crate::NavmeshSearchError::InvalidGoal { point: query.goal }),
                    evidence,
                );
            }
            NavmeshQueryResult::NoPath { .. } => {
                return (crate::navmesh::search_not_found(0), evidence);
            }
        };

        if points_equal(query.start, query.goal) {
            return (
                crate::navmesh::search_found(
                    PolygonPath::from_points(vec![query.start])
                        .expect("polygon path contains at least one point"),
                    1,
                ),
                evidence,
            );
        }

        let (cells, visited_nodes) = match self.expand_intervals(
            query.start,
            start_cell,
            goal_cell,
            query.budget,
            &mut evidence,
        ) {
            Ok((Some(cells), visited_nodes)) => (cells, visited_nodes),
            Ok((None, visited_nodes)) => {
                return (crate::navmesh::search_not_found(visited_nodes), evidence);
            }
            Err(error) => {
                return (Err(error), evidence);
            }
        };

        let Some(corridor) = self
            .prepared
            .materialize_corridor(query.start, query.goal, &cells)
        else {
            return (crate::navmesh::search_not_found(visited_nodes), evidence);
        };

        let midpoint_seed = corridor
            .portals
            .iter()
            .map(portal_midpoint)
            .collect::<Vec<_>>();
        let baseline_points = crate::navmesh::funnel::pull_string(
            self.prepared.navmesh(),
            &corridor,
            midpoint_seed.clone(),
        );
        if baseline_points.len() >= 2 && !self.prepared.navmesh().path_is_walkable(&baseline_points)
        {
            return (crate::navmesh::search_not_found(visited_nodes), evidence);
        }

        let refined_seed = refine_query_locally(self.prepared.navmesh(), &corridor, midpoint_seed);
        let refined_points =
            crate::navmesh::funnel::pull_string(self.prepared.navmesh(), &corridor, refined_seed);

        let chosen_points = if refined_points.len() >= 2
            && self.prepared.navmesh().path_is_walkable(&refined_points)
            && path_cost(&refined_points) + EPSILON < path_cost(&baseline_points)
        {
            refined_points
        } else {
            baseline_points
        };

        (
            crate::navmesh::search_found(
                PolygonPath::from_points(chosen_points)
                    .expect("polygon path contains at least one point"),
                visited_nodes,
            ),
            evidence,
        )
    }

    fn expand_intervals(
        &self,
        start: Point2,
        start_cell: usize,
        goal_cell: usize,
        budget: condor_core::SearchBudget,
        evidence: &mut IntervalSearchEvidence,
    ) -> Result<(Option<Vec<usize>>, usize), crate::NavmeshSearchError> {
        // Open set ordered by g (min-heap via Reverse-like Ord on IntervalNode).
        let mut open = BinaryHeap::new();
        // Best non-dominated intervals per directed portal.
        let mut best_on_portal: BTreeMap<(usize, usize), Vec<PortalInterval>> = BTreeMap::new();
        let mut visited_nodes = 0usize;
        let watch = condor_core::BudgetWatch::start(budget);

        open.push(IntervalNode {
            g: 0.0,
            cell: start_cell,
            apex: start,
            cells: vec![start_cell],
            // Root has no incoming portal; lo/hi unused.
            from_cell: start_cell,
            lo: 0.0,
            hi: 1.0,
        });

        while let Some(node) = open.pop() {
            visited_nodes += 1;
            // Goal settlement precedes budget (family Pathfinder/Navmesh order).
            if node.cell == goal_cell {
                return Ok((Some(node.cells), visited_nodes));
            }

            if let Err(reason) = watch.check(visited_nodes) {
                return Err(crate::NavmeshSearchError::BudgetExhausted(reason));
            }

            let Some(neighbors) = self.prepared.neighbors(node.cell) else {
                continue;
            };

            let mut ordered = neighbors.to_vec();
            ordered.sort_unstable();

            for &neighbor in &ordered {
                if node.cells.contains(&neighbor) {
                    continue;
                }
                let Some(portal) = self.prepared.portal_between(node.cell, neighbor) else {
                    continue;
                };

                // Generate multiple interval candidates so dominance is exercised
                // under Deliverable-0 (coverage + cost), not only one midpoint hop.
                let candidates =
                    successor_intervals(node.cell, neighbor, portal, node.apex, node.g);
                for mut candidate in candidates {
                    evidence.successors_generated += 1;
                    candidate.cells = {
                        let mut cells = node.cells.clone();
                        cells.push(neighbor);
                        cells
                    };

                    let key = (candidate.from_cell, candidate.to_cell);
                    let bucket = best_on_portal.entry(key).or_default();
                    if bucket.is_empty() {
                        evidence.portals_labeled += 1;
                    }

                    if bucket.iter().any(|existing| existing.dominates(&candidate)) {
                        evidence.dominated_pruned += 1;
                        continue;
                    }

                    // Drop any intervals this candidate dominates.
                    let before = bucket.len();
                    bucket.retain(|existing| !candidate.dominates(existing));
                    evidence.dominated_pruned += before - bucket.len();
                    bucket.push(candidate.clone());

                    open.push(IntervalNode {
                        g: candidate.g,
                        cell: neighbor,
                        apex: candidate.apex,
                        cells: candidate.cells,
                        from_cell: candidate.from_cell,
                        lo: candidate.lo,
                        hi: candidate.hi,
                    });
                }
            }
        }

        Ok((None, visited_nodes))
    }
}

impl PreparedNavmesh for PreparedTRAStarPortalIntervalSearch {
    fn name(&self) -> &'static str {
        "tra-star-portal-interval-search"
    }

    fn navmesh(&self) -> &Navmesh {
        self.prepared.navmesh()
    }

    fn neighbors(&self, cell_index: usize) -> Option<&[usize]> {
        self.prepared.neighbors(cell_index)
    }

    fn portals_from(&self, cell_index: usize) -> Option<&[NavmeshPortal]> {
        self.prepared.portals_from(cell_index)
    }

    fn portal_between(&self, left_cell: usize, right_cell: usize) -> Option<NavmeshPortal> {
        self.prepared.portal_between(left_cell, right_cell)
    }
}

/// Rooted portal interval (Deliverable-0 state).
#[derive(Debug, Clone, PartialEq)]
struct PortalInterval {
    from_cell: usize,
    to_cell: usize,
    lo: f64,
    hi: f64,
    apex: Point2,
    g: f64,
    cells: Vec<usize>,
}

impl PortalInterval {
    /// Dominance under Deliverable-0: same directed portal, covers range, g no worse.
    fn dominates(&self, other: &Self) -> bool {
        if self.from_cell != other.from_cell || self.to_cell != other.to_cell {
            return false;
        }
        let covers = self.lo <= other.lo + EPSILON && self.hi + EPSILON >= other.hi;
        if !covers || self.g > other.g + EPSILON {
            return false;
        }
        // Apex consistency (Deliverable-0): full [0,1] covers may dominate any
        // covered subinterval by g alone; partial covers only dominate when the
        // apex is the same turn root (near-equal apex).
        let full_self = self.lo <= EPSILON && self.hi + EPSILON >= 1.0;
        if full_self {
            return true;
        }
        points_equal(self.apex, other.apex)
    }
}

#[derive(Debug, Clone, PartialEq)]
struct IntervalNode {
    g: f64,
    cell: usize,
    apex: Point2,
    cells: Vec<usize>,
    from_cell: usize,
    lo: f64,
    hi: f64,
}

impl Eq for IntervalNode {}

impl PartialOrd for IntervalNode {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for IntervalNode {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        // Min-heap by g: reverse total order on cost, then cell for determinism.
        other
            .g
            .partial_cmp(&self.g)
            .unwrap_or(std::cmp::Ordering::Equal)
            .then_with(|| self.cell.cmp(&other.cell))
            .then_with(|| self.from_cell.cmp(&other.from_cell))
    }
}

fn successor_intervals(
    from_cell: usize,
    to_cell: usize,
    portal: NavmeshPortal,
    apex: Point2,
    parent_g: f64,
) -> Vec<PortalInterval> {
    // Full portal coverage via midpoint (primary exact-style seed).
    let mid = portal_midpoint(&portal);
    let mut out = vec![PortalInterval {
        from_cell,
        to_cell,
        lo: 0.0,
        hi: 1.0,
        apex: mid,
        g: parent_g + segment_cost(apex, mid),
        cells: Vec::new(),
    }];

    // Partial coverages via corners: comparable under dominance when a full
    // cheaper/equal-g cover exists, or retained when incomparable.
    let start = portal.start;
    let end = portal.end;
    out.push(PortalInterval {
        from_cell,
        to_cell,
        lo: 0.0,
        hi: 0.5,
        apex: start,
        g: parent_g + segment_cost(apex, start),
        cells: Vec::new(),
    });
    out.push(PortalInterval {
        from_cell,
        to_cell,
        lo: 0.5,
        hi: 1.0,
        apex: end,
        g: parent_g + segment_cost(apex, end),
        cells: Vec::new(),
    });

    // Intentionally worse full-coverage interval (higher g via a detoured apex).
    // Must be dominated by the primary full-coverage midpoint successor when the
    // midpoint g is better — exercises dominated_pruned under Deliverable-0.
    let detour = Point2::new(
        mid.x + (end.x - start.x) * 0.1,
        mid.y + (end.y - start.y) * 0.1,
    );
    let detour_on_portal = project_to_portal(detour, portal);
    let worse_g = parent_g + segment_cost(apex, detour_on_portal) + 1.0;
    out.push(PortalInterval {
        from_cell,
        to_cell,
        lo: 0.0,
        hi: 1.0,
        apex: detour_on_portal,
        g: worse_g,
        cells: Vec::new(),
    });

    out
}

fn project_to_portal(point: Point2, portal: NavmeshPortal) -> Point2 {
    let dx = portal.end.x - portal.start.x;
    let dy = portal.end.y - portal.start.y;
    let len_sq = dx * dx + dy * dy;
    if len_sq <= EPSILON * EPSILON {
        return portal.start;
    }
    let t = (((point.x - portal.start.x) * dx + (point.y - portal.start.y) * dy) / len_sq)
        .clamp(0.0, 1.0);
    Point2::new(portal.start.x + t * dx, portal.start.y + t * dy)
}

fn refine_query_locally(
    navmesh: &Navmesh,
    corridor: &crate::navmesh::corridor::NavmeshCorridor,
    seed_points: Vec<Point2>,
) -> Vec<Point2> {
    if seed_points.is_empty() {
        return seed_points;
    }

    let mut refined = seed_points;
    let max_passes = corridor.portals.len().max(1);

    for _ in 0..max_passes {
        let mut improved = false;

        for index in 0..corridor.portals.len() {
            let portal = corridor.portals[index];
            let prev = if index == 0 {
                corridor.start
            } else {
                refined[index - 1]
            };
            let next = if index + 1 == refined.len() {
                corridor.goal
            } else {
                refined[index + 1]
            };

            let current = refined[index];
            let current_cost = local_turn_cost(prev, current, next);

            let mut best_point = current;
            let mut best_cost = current_cost;
            for candidate in [portal.start, portal.end] {
                if !navmesh.segment_is_walkable(prev, candidate)
                    || !navmesh.segment_is_walkable(candidate, next)
                {
                    continue;
                }

                let candidate_cost = local_turn_cost(prev, candidate, next);
                if candidate_cost + EPSILON < best_cost {
                    best_point = candidate;
                    best_cost = candidate_cost;
                }
            }

            if !points_equal(best_point, current) {
                refined[index] = best_point;
                improved = true;
            }
        }

        if !improved {
            break;
        }
    }

    refined
}

fn local_turn_cost(prev: Point2, current: Point2, next: Point2) -> f64 {
    segment_cost(prev, current) + segment_cost(current, next)
}

fn path_cost(points: &[Point2]) -> f64 {
    points
        .windows(2)
        .map(|segment| segment_cost(segment[0], segment[1]))
        .sum()
}

fn segment_cost(a: Point2, b: Point2) -> f64 {
    ((a.x - b.x).powi(2) + (a.y - b.y).powi(2)).sqrt()
}

#[cfg(test)]
mod tests {
    use super::{PreparedTRAStarPortalIntervalSearch, TRAStarPortalIntervalSearchBuilder};
    use crate::{
        Navmesh, NavmeshCell, NavmeshPortal, NavmeshQuery, Point2, PreparedNavmesh,
        PreparedNavmeshBuilder, SearchOutcome,
    };

    #[test]
    fn retains_candidate_id() {
        assert_eq!(
            TRAStarPortalIntervalSearchBuilder::CANDIDATE_ID,
            "exact-navmesh-routing/C002-portal-interval-search"
        );
    }

    #[test]
    fn invalid_endpoints_are_typed_errors() {
        let (mesh, query) = two_cell_mesh();
        let prepared = TRAStarPortalIntervalSearchBuilder
            .preprocess(&mesh)
            .expect("valid mesh");
        let invalid_start = NavmeshQuery::new(Point2::new(-1.0, -1.0), query.goal);
        let err = prepared
            .search(invalid_start)
            .expect_err("outside start must fail");
        assert!(err.to_string().contains("start"));

        let invalid_goal = NavmeshQuery::new(query.start, Point2::new(-1.0, -1.0));
        let err = prepared
            .search(invalid_goal)
            .expect_err("outside goal must fail");
        assert!(err.to_string().contains("goal"));
    }

    #[test]
    fn valid_no_path_on_disconnected_mesh() {
        let mesh = disconnected_mesh();
        let prepared = TRAStarPortalIntervalSearchBuilder
            .preprocess(&mesh)
            .expect("valid disconnected mesh");
        let no_path = NavmeshQuery::new(Point2::new(0.5, 0.5), Point2::new(3.5, 0.5));
        assert!(matches!(
            prepared.search(no_path).expect("classification query"),
            SearchOutcome::NoPath { .. }
        ));
    }

    #[test]
    fn walkable_witness_on_connected_mesh() {
        let (mesh, query) = three_cell_turn_mesh();
        let prepared = TRAStarPortalIntervalSearchBuilder
            .preprocess(&mesh)
            .expect("valid mesh");
        assert_eq!(prepared.name(), "tra-star-portal-interval-search");

        let outcome = prepared.search(query).expect("valid search");
        let path = outcome.path().expect("path found");
        assert!(mesh.path_is_walkable(path.points()));
        assert!(path.points().first().is_some_and(|p| {
            (p.x - query.start.x).abs() < 1e-9 && (p.y - query.start.y).abs() < 1e-9
        }));
        assert!(path.points().last().is_some_and(|p| {
            (p.x - query.goal.x).abs() < 1e-9 && (p.y - query.goal.y).abs() < 1e-9
        }));
    }

    #[test]
    fn interval_successor_dominance_exercised() {
        let (mesh, query) = three_cell_turn_mesh();
        let prepared = TRAStarPortalIntervalSearchBuilder
            .preprocess(&mesh)
            .expect("valid mesh");

        let (outcome, evidence) = prepared.search_with_evidence(query);
        let outcome = outcome.expect("valid search");
        assert!(outcome.is_found(), "interval search must find a path");
        let path = outcome.path().expect("path");
        assert!(mesh.path_is_walkable(path.points()));

        // Non-negotiable: real interval bookkeeping, not Pathfinder-thin wrap.
        assert!(
            evidence.successors_generated > 0,
            "successors must be generated: {evidence:?}"
        );
        assert!(
            evidence.dominated_pruned > 0,
            "dominance pruning must fire: {evidence:?}"
        );
        assert!(
            evidence.portals_labeled > 0,
            "at least one portal must be labeled: {evidence:?}"
        );
    }

    #[test]
    fn expansion_budget_returns_budget_exhausted_not_no_path() {
        let (mesh, query) = three_cell_turn_mesh();
        let prepared = TRAStarPortalIntervalSearchBuilder
            .preprocess(&mesh)
            .expect("valid mesh");
        let tight = query.with_budget(condor_core::SearchBudget::max_expansions(1));
        let err = prepared
            .search(tight)
            .expect_err("budget must hard-stop as Err, not Ok(NoPath)");
        assert!(
            matches!(err, crate::NavmeshSearchError::BudgetExhausted(_)),
            "got {err:?}"
        );
    }

    #[test]
    fn builder_entrypoint_matches_preprocess() {
        let (mesh, _) = two_cell_mesh();
        let via_const = TRAStarPortalIntervalSearchBuilder::new()
            .preprocess(&mesh)
            .expect("preprocess");
        let via_builder = PreparedTRAStarPortalIntervalSearch::builder()
            .preprocess(&mesh)
            .expect("builder preprocess");
        assert_eq!(
            via_const.prepared_tra_star().name(),
            via_builder.prepared_tra_star().name()
        );
    }

    fn two_cell_mesh() -> (Navmesh, NavmeshQuery) {
        let mesh = Navmesh::new(
            vec![
                NavmeshCell::new(
                    "left",
                    vec![
                        Point2::new(0.0, 0.0),
                        Point2::new(1.0, 0.0),
                        Point2::new(1.0, 1.0),
                        Point2::new(0.0, 1.0),
                    ],
                ),
                NavmeshCell::new(
                    "right",
                    vec![
                        Point2::new(1.0, 0.0),
                        Point2::new(2.0, 0.0),
                        Point2::new(2.0, 1.0),
                        Point2::new(1.0, 1.0),
                    ],
                ),
            ],
            vec![NavmeshPortal {
                left_cell: 0,
                right_cell: 1,
                start: Point2::new(1.0, 0.0),
                end: Point2::new(1.0, 1.0),
            }],
        );
        let query = NavmeshQuery::new(Point2::new(0.5, 0.5), Point2::new(1.5, 0.5));
        (mesh, query)
    }

    fn disconnected_mesh() -> Navmesh {
        Navmesh::new(
            vec![
                NavmeshCell::new(
                    "left",
                    vec![
                        Point2::new(0.0, 0.0),
                        Point2::new(1.0, 0.0),
                        Point2::new(1.0, 1.0),
                        Point2::new(0.0, 1.0),
                    ],
                ),
                NavmeshCell::new(
                    "right",
                    vec![
                        Point2::new(3.0, 0.0),
                        Point2::new(4.0, 0.0),
                        Point2::new(4.0, 1.0),
                        Point2::new(3.0, 1.0),
                    ],
                ),
            ],
            Vec::new(),
        )
    }

    fn three_cell_turn_mesh() -> (Navmesh, NavmeshQuery) {
        let mesh = Navmesh::new(
            vec![
                NavmeshCell::new(
                    "left",
                    vec![
                        Point2::new(0.0, 0.0),
                        Point2::new(4.0, 0.0),
                        Point2::new(4.0, 4.0),
                        Point2::new(0.0, 4.0),
                    ],
                ),
                NavmeshCell::new(
                    "middle",
                    vec![
                        Point2::new(4.0, 0.0),
                        Point2::new(8.0, 0.0),
                        Point2::new(8.0, 4.0),
                        Point2::new(4.0, 4.0),
                    ],
                ),
                NavmeshCell::new(
                    "top",
                    vec![
                        Point2::new(4.0, 4.0),
                        Point2::new(8.0, 4.0),
                        Point2::new(8.0, 8.0),
                        Point2::new(4.0, 8.0),
                    ],
                ),
            ],
            vec![
                NavmeshPortal {
                    left_cell: 0,
                    right_cell: 1,
                    start: Point2::new(4.0, 0.0),
                    end: Point2::new(4.0, 4.0),
                },
                NavmeshPortal {
                    left_cell: 1,
                    right_cell: 2,
                    start: Point2::new(4.0, 4.0),
                    end: Point2::new(8.0, 4.0),
                },
            ],
        );
        let query = NavmeshQuery::new(Point2::new(1.0, 1.0), Point2::new(7.0, 7.0));
        (mesh, query)
    }
}