condor_navmesh/navmesh/

mod.rs

//! Deterministic convex-cell navmesh substrate: geometry, walkability, and availability.
//!
//! This module owns the **mesh contract** that solvers and adapters consume. It
//! does **not** implement online routing algorithms—those live under
//! [`crate::algorithms`] (and optional [`crate::polyanya`]) and call into a
//! validated [`Navmesh`] (or a prepared/dynamic snapshot derived from it).
//! Continuous polygonal free-space types remain in the geometry crate; this
//! module is the navmesh-specific cell/portal graph and walkability layer on top.
//!
//! # Lifecycle
//!
//! 1. **Build / validate** — assemble [`NavmeshCell`]s and [`NavmeshPortal`]s, then
//!    [`Navmesh::validate`]. Invalid geometry fails closed before any query.
//! 2. **Locate** — map continuous points into cell indices with [`Navmesh::locate_point`] /
//!    [`Navmesh::locate_cells`] (shared by connectivity checks and pathfinders).
//! 3. **Query connectivity or route** — [`Navmesh::query`] answers cell-graph reachability
//!    without a geometric path; [`NavmeshPathfinder`]s produce polylines via corridor + funnel.
//! 4. **Prepared snapshots** — [`PreparedNavmeshBuilder`] clones a static mesh and indexes
//!    adjacency for repeated neighbor/portal lookup ([`prepared`]); TRA* builders layer on this.
//! 5. **Dynamic availability** — [`DynamicNavmeshState`] overlays cell/portal enable flags.
//!    Each update sets [`DynamicNavmeshState::prepared_stale`]; consumers
//!    [`DynamicNavmeshState::materialize`] a static snapshot and rebuild prepared data
//!    (for example via [`DynamicPreparedNavmeshQuery::run`]). No in-place prepared repair.
//!
//! # Submodules
//!
//! - [`adapter`] — fan-triangulate cells for the external Polyanya mesh API (`polyanya` feature)
//! - [`corridor`] — ordered portal chain along a known cell sequence
//! - [`funnel`] — string-pull a seed polyline inside a corridor
//! - [`prepared`] — build-once / query-many adjacency contracts

use std::{
    borrow::Borrow,
    collections::{BTreeMap, BTreeSet, VecDeque},
};

/// Fan-triangulate cells for the external Polyanya mesh API (`polyanya` feature).
#[cfg(feature = "polyanya")]
pub mod adapter;
/// Ordered portal chain construction along a known cell sequence.
pub mod corridor;
/// String-pull a seed polyline inside a corridor.
pub mod funnel;
/// Build-once / query-many adjacency contracts for static navmesh snapshots.
pub mod prepared;

use condor_core::{Point2, SearchOutcome, SearchVisitStats};
use condor_geometry::continuous::PolygonPath;
pub use prepared::{
    PreparedNavmesh, PreparedNavmeshBuildError, PreparedNavmeshBuilder, StaticPreparedNavmesh,
    StaticPreparedNavmeshBuilder,
};

/// Static navmesh cell or portal validation failure.
///
/// Raised by [`NavmeshCell::validate`] and [`Navmesh::validate`] when geometry or
/// indexing violates the convex-cell / portal-boundary contract. Build and prepare
/// paths fail closed on these errors rather than searching an inconsistent mesh.
#[derive(Debug, Clone, PartialEq, thiserror::Error)]
#[non_exhaustive]
pub enum NavmeshValidationError {
    /// Cell id is empty or whitespace-only.
    #[error("navmesh cell id must not be empty")]
    EmptyCellId,
    /// Cell polygon has fewer than three vertices.
    #[error("navmesh cell '{cell_id}' needs at least three vertices (found {actual})")]
    TooFewCellVertices {
        /// Offending cell id.
        cell_id: String,
        /// Observed vertex count.
        actual: usize,
    },
    /// Cell polygon has near-zero signed area.
    #[error("navmesh cell '{cell_id}' must have non-zero area")]
    DegenerateCell {
        /// Offending cell id.
        cell_id: String,
    },
    /// Cell polygon fails the convexity check.
    #[error("navmesh cell '{cell_id}' must be convex")]
    NonConvexCell {
        /// Offending cell id.
        cell_id: String,
    },
    /// Two cells share the same non-empty `cell_id`.
    #[error("duplicate navmesh cell id '{cell_id}'")]
    DuplicateCellId {
        /// Duplicated cell id.
        cell_id: String,
    },
    /// Portal indexes a cell outside the mesh cell list.
    #[error("navmesh portal {portal_index} references missing cell {cell_index}")]
    MissingPortalCell {
        /// Portal index in the mesh portal list.
        portal_index: usize,
        /// Out-of-range cell index referenced by the portal.
        cell_index: usize,
    },
    /// Portal's left and right cell indices are equal.
    #[error("navmesh portal {portal_index} must connect two different cells")]
    SelfPortal {
        /// Portal index in the mesh portal list.
        portal_index: usize,
    },
    /// Portal start and end coincide (zero-length segment).
    #[error("navmesh portal {portal_index} endpoints must span a non-zero segment")]
    DegeneratePortal {
        /// Portal index in the mesh portal list.
        portal_index: usize,
    },
    /// Portal segment is not on the named cell's boundary.
    #[error("navmesh portal {portal_index} is not on the boundary of cell '{cell_id}'")]
    PortalOutsideCellBoundary {
        /// Portal index in the mesh portal list.
        portal_index: usize,
        /// Cell id whose boundary does not contain the portal segment.
        cell_id: String,
    },
}

/// Failure while applying or materializing dynamic navmesh availability.
///
/// Covers empty bases, invalid base meshes, updates that reference unknown cell or
/// portal ids, and prepared rebuild failures after materialization.
#[derive(Debug, thiserror::Error)]
#[non_exhaustive]
pub enum DynamicNavmeshError {
    /// Base mesh had no cells when constructing dynamic state.
    #[error("dynamic navmesh base must contain at least one cell")]
    EmptyBase,
    /// Base mesh failed [`Navmesh::validate`] during construction or materialize.
    #[error(transparent)]
    InvalidNavmesh(#[from] NavmeshValidationError),
    /// An update referenced a `cell_id` absent from the base mesh.
    #[error("dynamic navmesh update references missing cell '{cell_id}'")]
    MissingCell {
        /// Unknown cell id from the update.
        cell_id: String,
    },
    /// An update referenced a portal whose cell-id pair is not on the base mesh.
    #[error(
        "dynamic navmesh update references missing portal '{left_cell_id}'<->'{right_cell_id}'"
    )]
    MissingPortal {
        /// One cell id of the missing portal pair.
        left_cell_id: String,
        /// Other cell id of the missing portal pair.
        right_cell_id: String,
    },
    /// Prepared rebuild after materialization failed validation or preprocess.
    #[error("failed to rebuild prepared navmesh: {source}")]
    PreparedRebuild {
        /// Underlying prepared-build failure.
        #[source]
        source: PreparedNavmeshBuildError,
    },
}
const EPSILON: f64 = 1e-9;
const ENDPOINT_PROBE_PARAMETER: f64 = 1e-6;

/// One convex walkable polygon in a navmesh, keyed by a stable `cell_id`.
///
/// Cell ids are the durable identity used by dynamic availability updates; portal
/// endpoints must lie on the cell boundary. Construction does not validate—call
/// [`Self::validate`] (or [`Navmesh::validate`]) before search.
#[derive(Debug, Clone, PartialEq)]
pub struct NavmeshCell {
    cell_id: String,
    vertices: Vec<Point2>,
}

impl NavmeshCell {
    /// Creates an unvalidated cell; geometry and id contracts are checked by [`Self::validate`].
    #[must_use]
    pub fn new(cell_id: impl Into<String>, vertices: Vec<Point2>) -> Self {
        Self {
            cell_id: cell_id.into(),
            vertices,
        }
    }

    /// Stable string identity for this cell within a mesh.
    #[must_use]
    pub fn cell_id(&self) -> &str {
        &self.cell_id
    }

    /// Convex polygon ring in world coordinates (CCW or CW; validation checks area).
    #[must_use]
    pub fn vertices(&self) -> &[Point2] {
        &self.vertices
    }

    /// Checks non-empty id, at least three vertices, non-zero area, and convexity.
    ///
    /// # Errors
    ///
    /// Returns [`NavmeshValidationError`] when the cell id or polygon geometry
    /// violates the navmesh contract.
    pub fn validate(&self) -> Result<(), NavmeshValidationError> {
        if self.cell_id.trim().is_empty() {
            return Err(NavmeshValidationError::EmptyCellId);
        }

        if self.vertices.len() < 3 {
            return Err(NavmeshValidationError::TooFewCellVertices {
                cell_id: self.cell_id.clone(),
                actual: self.vertices.len(),
            });
        }

        if is_degenerate_polygon(&self.vertices) {
            return Err(NavmeshValidationError::DegenerateCell {
                cell_id: self.cell_id.clone(),
            });
        }

        if !is_convex_polygon(&self.vertices) {
            return Err(NavmeshValidationError::NonConvexCell {
                cell_id: self.cell_id.clone(),
            });
        }

        Ok(())
    }

    /// Inclusive membership: interior points and boundary edges (including vertices) count.
    #[must_use]
    pub fn contains_point_inclusive(&self, point: Point2) -> bool {
        if polygon_edges(&self.vertices).any(|(start, end)| point_on_segment(point, start, end)) {
            return true;
        }

        let mut reference_sign = 0.0_f64;
        for (start, end) in polygon_edges(&self.vertices) {
            let sign = orientation(start, end, point);
            if sign.abs() <= EPSILON {
                continue;
            }

            if reference_sign.abs() <= EPSILON {
                reference_sign = sign;
                continue;
            }

            if sign.signum() != reference_sign.signum() {
                return false;
            }
        }

        true
    }

    /// Whether both endpoints of a portal segment lie on a single cell boundary edge.
    #[must_use]
    pub fn has_boundary_segment(&self, start: Point2, end: Point2) -> bool {
        polygon_edges(&self.vertices).any(|(edge_start, edge_end)| {
            point_on_segment(start, edge_start, edge_end)
                && point_on_segment(end, edge_start, edge_end)
        })
    }
}

/// Adjacency segment between two cells; endpoints must lie on both cell boundaries.
///
/// Cell indices refer into the owning [`Navmesh`]'s cell list. Direction is not
/// semantic—either endpoint order may appear—but both sides must share the segment.
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct NavmeshPortal {
    /// Index of one adjacent cell in the owning [`Navmesh`] cell list.
    pub left_cell: usize,
    /// Index of the other adjacent cell (must differ from [`Self::left_cell`]).
    pub right_cell: usize,
    /// First endpoint of the shared boundary segment (world coordinates).
    pub start: Point2,
    /// Second endpoint of the shared boundary segment (world coordinates).
    pub end: Point2,
}

/// Graph of convex cells and portal segments for connectivity and walkability.
///
/// Construction does not validate. Treat a mesh as authoritative only after
/// [`Self::validate`] (or after materialization from a valid [`DynamicNavmeshState`]).
/// Solvers and prepared builders clone this snapshot; they do not mutate it in place.
#[derive(Debug, Clone, PartialEq)]
pub struct Navmesh {
    cells: Vec<NavmeshCell>,
    portals: Vec<NavmeshPortal>,
}

impl Navmesh {
    /// Creates an unvalidated mesh; call [`Self::validate`] before search or preprocess.
    #[must_use]
    pub fn new(cells: Vec<NavmeshCell>, portals: Vec<NavmeshPortal>) -> Self {
        Self { cells, portals }
    }

    /// Convex cells that define walkable free space.
    #[must_use]
    pub fn cells(&self) -> &[NavmeshCell] {
        &self.cells
    }

    /// Shared boundary portals linking adjacent cells.
    #[must_use]
    pub fn portals(&self) -> &[NavmeshPortal] {
        &self.portals
    }

    /// Validates every cell and every portal's indices, non-degeneracy, and boundary endpoints.
    ///
    /// # Errors
    ///
    /// Returns [`NavmeshValidationError`] when a cell is invalid, cell ids are
    /// duplicated, or a portal violates its endpoint contract.
    pub fn validate(&self) -> Result<(), NavmeshValidationError> {
        let mut cell_ids = BTreeMap::new();
        for (index, cell) in self.cells.iter().enumerate() {
            cell.validate()?;
            if cell_ids.insert(cell.cell_id(), index).is_some() {
                return Err(NavmeshValidationError::DuplicateCellId {
                    cell_id: cell.cell_id().to_owned(),
                });
            }
        }

        for (portal_index, portal) in self.portals.iter().enumerate() {
            if portal.left_cell >= self.cells.len() || portal.right_cell >= self.cells.len() {
                let cell_index = if portal.left_cell >= self.cells.len() {
                    portal.left_cell
                } else {
                    portal.right_cell
                };
                return Err(NavmeshValidationError::MissingPortalCell {
                    portal_index,
                    cell_index,
                });
            }
            if portal.left_cell == portal.right_cell {
                return Err(NavmeshValidationError::SelfPortal { portal_index });
            }
            if points_equal(portal.start, portal.end) {
                return Err(NavmeshValidationError::DegeneratePortal { portal_index });
            }

            let left = &self.cells[portal.left_cell];
            let right = &self.cells[portal.right_cell];
            if !left.has_boundary_segment(portal.start, portal.end) {
                return Err(NavmeshValidationError::PortalOutsideCellBoundary {
                    portal_index,
                    cell_id: left.cell_id().to_owned(),
                });
            }
            if !right.has_boundary_segment(portal.start, portal.end) {
                return Err(NavmeshValidationError::PortalOutsideCellBoundary {
                    portal_index,
                    cell_id: right.cell_id().to_owned(),
                });
            }
        }

        Ok(())
    }

    /// Index of the first cell that contains `point` under inclusive membership, if any.
    ///
    /// When a point lies on a shared boundary, the lowest-index containing cell wins.
    /// Prefer [`Self::locate_cells`] when multi-membership matters (connectivity BFS).
    #[must_use]
    pub fn locate_point(&self, point: Point2) -> Option<usize> {
        self.locate_cells(point).into_iter().next()
    }

    /// All cell indices whose polygons contain `point` (inclusive boundary).
    ///
    /// Order follows cell list order. Overlapping or boundary-sharing cells all appear.
    #[must_use]
    pub fn locate_cells(&self, point: Point2) -> Vec<usize> {
        self.cells
            .iter()
            .enumerate()
            .filter_map(|(index, cell)| cell.contains_point_inclusive(point).then_some(index))
            .collect()
    }

    /// Cell indices reachable in one portal hop from `cell_index` (unsorted, portal order).
    ///
    /// Out-of-range indices yield an empty list. Duplicate portals to the same neighbor
    /// produce duplicate entries.
    #[must_use]
    pub fn neighbors(&self, cell_index: usize) -> Vec<usize> {
        self.portals
            .iter()
            .filter_map(|portal| {
                if portal.left_cell == cell_index {
                    Some(portal.right_cell)
                } else if portal.right_cell == cell_index {
                    Some(portal.left_cell)
                } else {
                    None
                }
            })
            .collect()
    }

    /// Portals incident to `cell_index`, in mesh portal order.
    #[must_use]
    pub fn portals_from(&self, cell_index: usize) -> Vec<&NavmeshPortal> {
        self.portals
            .iter()
            .filter(|portal| portal.left_cell == cell_index || portal.right_cell == cell_index)
            .collect()
    }

    /// Cell-graph connectivity between query endpoints (no geometric path).
    ///
    /// Locates every cell covering start and goal. If either endpoint lies outside all
    /// cells, returns [`NavmeshQueryResult::InvalidStart`] or
    /// [`NavmeshQueryResult::InvalidGoal`]. Otherwise BFS over portals from the full start
    /// cell set; when any goal cell is reachable, returns
    /// [`NavmeshQueryResult::Connected`] with the source start cell and hit goal cell.
    /// Multi-cell endpoints use the first located cell only for the reported
    /// `NoPath` indices when disconnected.
    #[must_use]
    pub fn query(&self, query: NavmeshQuery) -> NavmeshQueryResult {
        // First located cell wins when start/goal overlap multiple polygons.
        let start_cells = self.locate_cells(query.start);
        let Some(&start_cell) = start_cells.first() else {
            return NavmeshQueryResult::InvalidStart;
        };
        let goal_cells = self.locate_cells(query.goal);
        let Some(&goal_cell) = goal_cells.first() else {
            return NavmeshQueryResult::InvalidGoal;
        };

        if let Some((start_cell, goal_cell)) = self.connected_cell_pair(&start_cells, &goal_cells) {
            NavmeshQueryResult::Connected {
                start_cell,
                goal_cell,
            }
        } else {
            NavmeshQueryResult::NoPath {
                start_cell,
                goal_cell,
            }
        }
    }

    fn connected_cell_pair(
        &self,
        start_cells: &[usize],
        goal_cells: &[usize],
    ) -> Option<(usize, usize)> {
        let goal_set: BTreeSet<usize> = goal_cells.iter().copied().collect();
        let mut seen = vec![false; self.cells.len()];
        let mut frontier = VecDeque::new();

        for &start_cell in start_cells {
            if start_cell >= seen.len() || seen[start_cell] {
                continue;
            }
            if goal_set.contains(&start_cell) {
                return Some((start_cell, start_cell));
            }
            seen[start_cell] = true;
            frontier.push_back((start_cell, start_cell));
        }

        while let Some((cell_index, source_start_cell)) = frontier.pop_front() {
            for neighbor in self.neighbors(cell_index) {
                if neighbor >= seen.len() || seen[neighbor] {
                    continue;
                }
                if goal_set.contains(&neighbor) {
                    return Some((source_start_cell, neighbor));
                }
                seen[neighbor] = true;
                frontier.push_back((neighbor, source_start_cell));
            }
        }

        None
    }

    /// Whether `point` lies in at least one cell (inclusive boundary).
    #[must_use]
    pub fn is_walkable(&self, point: Point2) -> bool {
        !self.locate_cells(point).is_empty()
    }

    /// Whether the open segment from `start` to `end` stays on walkable cells.
    ///
    /// Endpoints must be walkable. The check samples cell-edge intersections along the
    /// segment and requires each open sub-interval to lie inside some cell; when adjacent
    /// intervals occupy disjoint cell sets, a portal must cover the transition point.
    /// Used by funnel string-pull and path validation—not a free-space raycast.
    #[must_use]
    pub fn segment_is_walkable(&self, start: Point2, end: Point2) -> bool {
        if !self.is_walkable(start) || !self.is_walkable(end) {
            return false;
        }

        let mut parameters = vec![0.0, 1.0];
        for cell in &self.cells {
            for (edge_start, edge_end) in polygon_edges(cell.vertices()) {
                parameters.extend(segment_intersection_parameters(
                    start, end, edge_start, edge_end,
                ));
            }
        }

        sort_and_dedup_parameters(&mut parameters);

        for parameter in &parameters {
            let point = interpolate_segment(start, end, *parameter);
            if !self.is_walkable(point) {
                return false;
            }
        }

        let mut interval_cells = Vec::new();
        for interval in parameters.windows(2) {
            let start_parameter = interval[0];
            let end_parameter = interval[1];
            if end_parameter - start_parameter <= EPSILON {
                continue;
            }

            let midpoint = interpolate_segment(start, end, (start_parameter + end_parameter) / 2.0);
            let cells = self.locate_cells(midpoint);
            if cells.is_empty() {
                return false;
            }
            interval_cells.push(cells);
        }

        for (index, boundary_parameter) in parameters
            .iter()
            .copied()
            .enumerate()
            .skip(1)
            .take(interval_cells.len().saturating_sub(1))
        {
            let left_cells = &interval_cells[index - 1];
            let right_cells = &interval_cells[index];
            if shares_any_cell(left_cells, right_cells) {
                continue;
            }

            let boundary_point = interpolate_segment(start, end, boundary_parameter);
            if !self.portal_transition_allowed(left_cells, right_cells, boundary_point) {
                return false;
            }
        }

        true
    }

    /// Whether every consecutive segment of `path` is walkable and vertices admit portal transitions.
    ///
    /// Empty paths are not walkable. A single point is walkable iff it lies in some cell.
    /// At interior vertices, incoming and outgoing probes must share a cell or cross a portal.
    #[must_use]
    pub fn path_is_walkable(&self, path: &[Point2]) -> bool {
        match path {
            [] => return false,
            [point] => return self.locate_point(*point).is_some(),
            _ => {}
        }

        for pair in path.windows(2) {
            if !self.segment_is_walkable(pair[0], pair[1]) {
                return false;
            }
        }

        for index in 1..(path.len() - 1) {
            let incoming_cells = self.endpoint_probe_cells(path[index - 1], path[index], true);
            let outgoing_cells = self.endpoint_probe_cells(path[index], path[index + 1], false);
            if shares_any_cell(&incoming_cells, &outgoing_cells) {
                continue;
            }

            if !self.portal_transition_allowed(&incoming_cells, &outgoing_cells, path[index]) {
                return false;
            }
        }

        true
    }

    fn endpoint_probe_cells(&self, start: Point2, end: Point2, near_end: bool) -> Vec<usize> {
        let parameter = if near_end {
            1.0 - ENDPOINT_PROBE_PARAMETER
        } else {
            ENDPOINT_PROBE_PARAMETER
        };
        self.locate_cells(interpolate_segment(start, end, parameter))
    }

    fn portal_transition_allowed(
        &self,
        left_cells: &[usize],
        right_cells: &[usize],
        boundary_point: Point2,
    ) -> bool {
        self.portals.iter().any(|portal| {
            let connects_left_to_right =
                left_cells.contains(&portal.left_cell) && right_cells.contains(&portal.right_cell);
            let connects_right_to_left =
                left_cells.contains(&portal.right_cell) && right_cells.contains(&portal.left_cell);

            (connects_left_to_right || connects_right_to_left)
                && point_on_segment(boundary_point, portal.start, portal.end)
        })
    }
}

/// Start/goal endpoints for connectivity checks and route search.
///
/// Points are continuous world coordinates; cell membership is resolved by the mesh.
/// Optional [`condor_core::SearchBudget`] caps expansions and/or wall-clock time for
/// pathfinders; connectivity-only [`Navmesh::query`] ignores the budget.
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct NavmeshQuery {
    /// Continuous start endpoint; must locate in at least one walkable cell.
    pub start: Point2,
    /// Continuous goal endpoint; must locate in at least one walkable cell.
    pub goal: Point2,
    /// Optional expansion / wall-clock caps for route search (default unlimited).
    pub budget: condor_core::SearchBudget,
}

impl NavmeshQuery {
    /// Pairs start and goal world points with an unlimited budget; cell membership is resolved at query time.
    #[must_use]
    pub const fn new(start: Point2, goal: Point2) -> Self {
        Self {
            start,
            goal,
            budget: condor_core::SearchBudget::UNLIMITED,
        }
    }

    /// Returns a copy of this query with the given budget.
    #[must_use]
    pub const fn with_budget(mut self, budget: condor_core::SearchBudget) -> Self {
        self.budget = budget;
        self
    }
}

/// Connectivity outcome for a start/goal pair (no geometric path polyline).
///
/// Distinct from [`NavmeshSearchResult`]: this answers only whether the cell graph
/// links the endpoints. Pathfinders use it as a precheck before corridor search.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum NavmeshQueryResult {
    /// Portal-connected cells cover start and goal; indices are the BFS-chosen pair.
    Connected {
        /// Source start cell chosen by multi-source connectivity BFS.
        start_cell: usize,
        /// Goal cell reached first by the connectivity BFS.
        goal_cell: usize,
    },
    /// Both endpoints locate, but no portal path joins their cell sets.
    NoPath {
        /// First located start cell (report index when disconnected).
        start_cell: usize,
        /// First located goal cell (report index when disconnected).
        goal_cell: usize,
    },
    /// Start lies outside every cell.
    InvalidStart,
    /// Goal lies outside every cell (start was valid).
    InvalidGoal,
}

impl NavmeshQueryResult {
    /// Whether the outcome is [`Self::Connected`].
    #[must_use]
    pub fn is_connected(self) -> bool {
        matches!(self, Self::Connected { .. })
    }
}

/// Geometric navmesh route; same continuous polyline type as polygonal free-space paths.
///
/// Euclidean cost and walkable-witness vertices live on [`PolygonPath`]; navmesh
/// solvers produce this after corridor + funnel (or external adapt + funnel).
pub type NavmeshPath = PolygonPath;

/// Work counters for a navmesh route search.
///
/// `visited_nodes` is algorithm-defined (typically expanded cells in corridor BFS;
/// Polyanya reports triangle/polygon expansions from the external path).
#[derive(Debug, Clone, Copy, Default, PartialEq)]
pub struct NavmeshSearchStats {
    /// Algorithm-defined expansion / visit count for this route search.
    pub visited_nodes: usize,
}

/// Failure to validate or prepare a navmesh route search request.
///
/// Endpoint errors mean the point is off-mesh. Adapter errors mean a backend could
/// not build its intermediate representation (for example Polyanya triangulation).
/// [`Self::BudgetExhausted`] means a caller budget hard-stopped the search without
/// proving unreachability—distinct from [`SearchOutcome::NoPath`].
#[derive(Debug, Clone, Copy, PartialEq, thiserror::Error)]
#[non_exhaustive]
pub enum NavmeshSearchError {
    /// Start does not locate in any walkable cell.
    #[error("invalid navmesh start: {point:?}")]
    InvalidStart {
        /// Off-mesh start that was rejected.
        point: Point2,
    },
    /// Goal does not locate in any walkable cell (start was valid).
    #[error("invalid navmesh goal: {point:?}")]
    InvalidGoal {
        /// Off-mesh goal that was rejected.
        point: Point2,
    },
    /// Caller [`condor_core::SearchBudget`] exhausted before found/no-path completed.
    #[error(transparent)]
    BudgetExhausted(#[from] condor_core::BudgetExhausted),
    /// Feature-gated Polyanya mesh adaptation or bake failed.
    #[cfg(feature = "polyanya")]
    #[error("failed to adapt navmesh for Polyanya: {source}")]
    PolyanyaMeshAdapter {
        /// Underlying adapter / triangulation failure.
        #[from]
        #[source]
        source: adapter::PolyanyaMeshAdapterError,
    },
}

/// Navmesh route return type: validation / budget `Err`, or found/no-path with stats.
///
/// `Ok(Found)` carries a walkable polyline witness; `Ok(NoPath)` is exhaustive
/// unreachability (or a solver-local dead end after precheck). `Err` is not a
/// no-path proof.
pub type NavmeshSearchResult =
    Result<SearchOutcome<NavmeshPath, NavmeshSearchStats>, NavmeshSearchError>;

/// Builds `Ok(Found)` with a walkable polyline witness and expansion stats.
pub(crate) const fn search_found(path: NavmeshPath, visited_nodes: usize) -> NavmeshSearchResult {
    Ok(SearchOutcome::found(
        path,
        NavmeshSearchStats { visited_nodes },
    ))
}

/// Builds `Ok(NoPath)` after connectivity precheck or exhaustive local search.
pub(crate) const fn search_not_found(visited_nodes: usize) -> NavmeshSearchResult {
    Ok(SearchOutcome::no_path(NavmeshSearchStats { visited_nodes }))
}

impl SearchVisitStats for NavmeshSearchStats {
    fn visited_nodes(&self) -> usize {
        self.visited_nodes
    }
}

/// Canonical undirected portal identity for dynamic enable/disable updates.
///
/// Cell ids are sorted so `(A,B)` and `(B,A)` map to the same key regardless of
/// the order written in an update or fixture.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
pub struct DynamicNavmeshPortalKey {
    left_cell_id: String,
    right_cell_id: String,
}

impl DynamicNavmeshPortalKey {
    /// Builds a order-normalized key from the two cell ids a portal connects.
    #[must_use]
    pub fn new(left_cell_id: impl Into<String>, right_cell_id: impl Into<String>) -> Self {
        let left_cell_id = left_cell_id.into();
        let right_cell_id = right_cell_id.into();
        if left_cell_id <= right_cell_id {
            Self {
                left_cell_id,
                right_cell_id,
            }
        } else {
            Self {
                left_cell_id: right_cell_id,
                right_cell_id: left_cell_id,
            }
        }
    }

    /// Canonical left cell id for this undirected portal key.
    #[must_use]
    pub fn left_cell_id(&self) -> &str {
        &self.left_cell_id
    }

    /// Canonical right cell id for this undirected portal key.
    #[must_use]
    pub fn right_cell_id(&self) -> &str {
        &self.right_cell_id
    }
}

/// Single availability mutation applied to a [`DynamicNavmeshState`].
///
/// Cell and portal identities use stable string ids from the base mesh—not cell
/// indices—so updates remain valid across materializations that reindex survivors.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum DynamicNavmeshUpdate {
    /// Enable or disable a whole cell by `cell_id`.
    SetCellEnabled {
        /// Stable base-mesh cell id (not a materialization index).
        cell_id: String,
        /// `true` enables the cell; `false` subtracts it from materializations.
        enabled: bool,
    },
    /// Enable or disable the portal between two cell ids (order-insensitive).
    SetPortalEnabled {
        /// One cell id of the undirected portal.
        left_cell_id: String,
        /// Other cell id of the undirected portal.
        right_cell_id: String,
        /// `true` enables the portal; `false` removes it from materializations.
        enabled: bool,
    },
}

impl DynamicNavmeshUpdate {
    /// Disables (`enabled = false`) or re-enables a cell in the availability overlay.
    #[must_use]
    pub fn set_cell_enabled(cell_id: impl Into<String>, enabled: bool) -> Self {
        Self::SetCellEnabled {
            cell_id: cell_id.into(),
            enabled,
        }
    }

    /// Disables or re-enables the undirected portal between two cell ids.
    #[must_use]
    pub fn set_portal_enabled(
        left_cell_id: impl Into<String>,
        right_cell_id: impl Into<String>,
        enabled: bool,
    ) -> Self {
        Self::SetPortalEnabled {
            left_cell_id: left_cell_id.into(),
            right_cell_id: right_cell_id.into(),
            enabled,
        }
    }
}

/// Mutable availability overlay on a validated base [`Navmesh`].
///
/// The base geometry is immutable. Disabled cells and portals form a subtractive
/// overlay: [`Self::materialize`] emits a static [`Navmesh`] containing only enabled
/// cells and portals (with remapped indices). This is **not** mesh carving or
/// in-place prepared repair.
///
/// # Prepared staleness
///
/// Every successful [`Self::apply_update`] sets [`Self::prepared_stale`]. Callers that
/// hold a [`PreparedNavmesh`] built from a prior snapshot must discard it and rebuild
/// from a fresh materialization. Staleness clears only when a rebuild-backed helper
/// (for example [`DynamicPreparedNavmeshQuery::run`]) marks the state rebuilt—not
/// merely from calling [`Self::materialize`].
#[derive(Debug, Clone, PartialEq)]
pub struct DynamicNavmeshState {
    base: Navmesh,
    disabled_cells: BTreeSet<String>,
    disabled_portals: BTreeSet<DynamicNavmeshPortalKey>,
    prepared_stale: bool,
}

impl DynamicNavmeshState {
    /// Validates `base` (non-empty, passes [`Navmesh::validate`]) with all cells/portals enabled.
    ///
    /// # Errors
    ///
    /// Returns [`DynamicNavmeshError`] when the base is empty or invalid.
    pub fn new(base: Navmesh) -> Result<Self, DynamicNavmeshError> {
        if base.cells().is_empty() {
            return Err(DynamicNavmeshError::EmptyBase);
        }
        base.validate()?;
        Ok(Self {
            base,
            disabled_cells: BTreeSet::new(),
            disabled_portals: BTreeSet::new(),
            prepared_stale: false,
        })
    }

    /// Like [`Self::new`], then seeds the disabled cell and portal sets without marking stale.
    ///
    /// Use for fixture restore and cold start. Subsequent [`Self::apply_update`] calls still
    /// mark prepared data stale as usual.
    ///
    /// # Errors
    ///
    /// Returns [`DynamicNavmeshError`] when the base is invalid or a disabled id is unknown.
    pub fn with_disabled_availability(
        base: Navmesh,
        disabled_cells: impl IntoIterator<Item = String>,
        disabled_portals: impl IntoIterator<Item = DynamicNavmeshPortalKey>,
    ) -> Result<Self, DynamicNavmeshError> {
        let mut state = Self::new(base)?;
        for cell_id in disabled_cells {
            state.ensure_cell_exists(&cell_id)?;
            state.disabled_cells.insert(cell_id);
        }
        for portal in disabled_portals {
            state.ensure_portal_exists(&portal)?;
            state.disabled_portals.insert(portal);
        }
        Ok(state)
    }

    /// Immutable base geometry (full cell/portal set, ignoring availability).
    #[must_use]
    pub fn base(&self) -> &Navmesh {
        &self.base
    }

    /// Stable cell ids currently excluded from materialization.
    #[must_use]
    pub fn disabled_cells(&self) -> &BTreeSet<String> {
        &self.disabled_cells
    }

    /// Portal keys currently excluded from materialization.
    #[must_use]
    pub fn disabled_portals(&self) -> &BTreeSet<DynamicNavmeshPortalKey> {
        &self.disabled_portals
    }

    /// Whether any availability change has not yet been followed by a prepared rebuild.
    ///
    /// When `true`, any prepared snapshot derived before the last update must not be trusted.
    #[must_use]
    pub fn prepared_stale(&self) -> bool {
        self.prepared_stale
    }

    fn mark_prepared_rebuilt(&mut self) {
        self.prepared_stale = false;
    }

    /// Applies one cell or portal availability change and marks prepared data stale.
    ///
    /// Disabling a cell drops it from the next materialization. Disabling a portal drops
    /// connectivity between the two cell ids while leaving both cells present when enabled.
    ///
    /// # Errors
    ///
    /// Returns [`DynamicNavmeshError`] when an update references an unknown cell
    /// or portal.
    pub fn apply_update(
        &mut self,
        update: &DynamicNavmeshUpdate,
    ) -> Result<(), DynamicNavmeshError> {
        match update {
            DynamicNavmeshUpdate::SetCellEnabled { cell_id, enabled } => {
                self.ensure_cell_exists(cell_id)?;
                if *enabled {
                    self.disabled_cells.remove(cell_id);
                } else {
                    self.disabled_cells.insert(cell_id.clone());
                }
            }
            DynamicNavmeshUpdate::SetPortalEnabled {
                left_cell_id,
                right_cell_id,
                enabled,
            } => {
                let portal = DynamicNavmeshPortalKey::new(left_cell_id, right_cell_id);
                self.ensure_portal_exists(&portal)?;
                if *enabled {
                    self.disabled_portals.remove(&portal);
                } else {
                    self.disabled_portals.insert(portal);
                }
            }
        }

        self.prepared_stale = true;
        Ok(())
    }

    /// Builds a static [`Navmesh`] snapshot of currently enabled cells and portals.
    ///
    /// Survivor cells keep their geometry and stable `cell_id`s but receive new dense
    /// indices. Portals between two surviving enabled cells are remapped; portals that
    /// touch a disabled cell or sit in the disabled-portal set are dropped. Does **not**
    /// clear [`Self::prepared_stale`]—callers must rebuild prepared structures separately.
    /// If every cell is disabled, the snapshot is empty and queries return
    /// [`NavmeshQueryResult::InvalidStart`].
    ///
    /// # Errors
    ///
    /// Returns [`DynamicNavmeshError`] if the enabled subset does not form a
    /// valid navmesh.
    pub fn materialize(&self) -> Result<Navmesh, DynamicNavmeshError> {
        let mut source_to_materialized = BTreeMap::new();
        let mut cells = Vec::new();
        for (source_index, cell) in self.base.cells().iter().enumerate() {
            if self.disabled_cells.contains(cell.cell_id()) {
                continue;
            }

            let materialized_index = cells.len();
            source_to_materialized.insert(source_index, materialized_index);
            cells.push(cell.clone());
        }

        let portals = self
            .base
            .portals()
            .iter()
            .filter_map(|portal| {
                let left = &self.base.cells()[portal.left_cell];
                let right = &self.base.cells()[portal.right_cell];
                let portal_key = DynamicNavmeshPortalKey::new(left.cell_id(), right.cell_id());
                let left_cell = *source_to_materialized.get(&portal.left_cell)?;
                let right_cell = *source_to_materialized.get(&portal.right_cell)?;
                (!self.disabled_portals.contains(&portal_key)).then_some(NavmeshPortal {
                    left_cell,
                    right_cell,
                    start: portal.start,
                    end: portal.end,
                })
            })
            .collect::<Vec<_>>();

        let navmesh = Navmesh::new(cells, portals);
        navmesh.validate()?;
        Ok(navmesh)
    }

    fn ensure_cell_exists(&self, cell_id: &str) -> Result<(), DynamicNavmeshError> {
        if self
            .base
            .cells()
            .iter()
            .any(|cell| cell.cell_id() == cell_id)
        {
            Ok(())
        } else {
            Err(DynamicNavmeshError::MissingCell {
                cell_id: cell_id.to_owned(),
            })
        }
    }

    fn ensure_portal_exists(
        &self,
        portal: &DynamicNavmeshPortalKey,
    ) -> Result<(), DynamicNavmeshError> {
        if self.base.portals().iter().any(|candidate| {
            let left = &self.base.cells()[candidate.left_cell];
            let right = &self.base.cells()[candidate.right_cell];
            DynamicNavmeshPortalKey::new(left.cell_id(), right.cell_id()) == *portal
        }) {
            Ok(())
        } else {
            Err(DynamicNavmeshError::MissingPortal {
                left_cell_id: portal.left_cell_id().to_owned(),
                right_cell_id: portal.right_cell_id().to_owned(),
            })
        }
    }
}

/// How a dynamic prepared query restored a fresh prepared snapshot.
///
/// V0 always discards prior prepared data and rebuilds from the materialized
/// snapshot—there is no incremental patch path.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum DynamicPreparedNavmeshRebuildStatus {
    /// Prepared map was rebuilt from [`DynamicNavmeshState::materialize`] output.
    RebuiltFromMaterializedSnapshot,
}

impl DynamicPreparedNavmeshRebuildStatus {
    /// Stable string token for reports and fixtures.
    #[must_use]
    pub const fn as_str(self) -> &'static str {
        match self {
            Self::RebuiltFromMaterializedSnapshot => "rebuilt-from-materialized-snapshot",
        }
    }
}

/// Staleness and rebuild bookkeeping from one dynamic prepared query run.
///
/// Captures whether prepared data was already stale, how many updates ran, and
/// that a full rebuild from the materialized snapshot completed (V0 has no
/// incremental patch path).
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct DynamicPreparedNavmeshQueryMetadata {
    /// [`PreparedNavmeshBuilder::name`] used for the rebuild.
    pub builder_name: &'static str,
    /// Number of [`DynamicNavmeshUpdate`]s applied in this run.
    pub applied_update_count: usize,
    /// [`DynamicNavmeshState::prepared_stale`] before any update in this run.
    pub prepared_stale_before_updates: bool,
    /// Stale flag after updates (true when any update applied or already stale).
    pub prepared_stale_after_updates: bool,
    /// Stale flag after rebuild; expected `false` on success.
    pub prepared_stale_after_rebuild: bool,
    /// Cell count in the materialization used for rebuild.
    pub materialized_cell_count: usize,
    /// Portal count in the materialization used for rebuild.
    pub materialized_portal_count: usize,
    /// How prepared data was restored (V0: always full rebuild).
    pub rebuild_status: DynamicPreparedNavmeshRebuildStatus,
}

/// Materialized navmesh, rebuilt prepared map, and raw vs rebuilt query outcomes.
///
/// `raw_result` is [`Navmesh::query`] on the materialization; `rebuilt_prepared_result`
/// is the same query on the freshly prepared map (parity check for rebuild correctness).
#[derive(Debug, Clone, PartialEq)]
pub struct DynamicPreparedNavmeshQueryResult<M> {
    /// Static mesh snapshot after applying availability updates.
    pub materialized_navmesh: Navmesh,
    /// Prepared map rebuilt from [`Self::materialized_navmesh`].
    pub prepared_navmesh: M,
    /// Connectivity result from the raw materialization (no prepared index).
    pub raw_result: NavmeshQueryResult,
    /// Connectivity result from the freshly prepared map (parity with raw).
    pub rebuilt_prepared_result: NavmeshQueryResult,
    /// Staleness / rebuild bookkeeping for this run.
    pub metadata: DynamicPreparedNavmeshQueryMetadata,
}

/// Applies dynamic updates, materializes, rebuilds prepared data, and runs connectivity.
///
/// Canonical lifecycle helper for the dynamic availability lane: ordered updates →
/// materialize → [`PreparedNavmeshBuilder::preprocess`] → query both raw and prepared →
/// clear [`DynamicNavmeshState::prepared_stale`].
#[derive(Debug, Clone, Copy, Default)]
pub struct DynamicPreparedNavmeshQuery;

impl DynamicPreparedNavmeshQuery {
    /// Applies `updates` in order, materializes, rebuilds via `builder`, and queries both.
    ///
    /// On success, marks `state` as no longer prepared-stale. Does not mutate the base
    /// mesh geometry—only the availability overlay and staleness flag.
    ///
    /// # Errors
    ///
    /// Returns [`DynamicNavmeshError`] when an update is invalid, materialization fails,
    /// or prepared preprocess fails.
    pub fn run<B, U>(
        state: &mut DynamicNavmeshState,
        updates: impl IntoIterator<Item = U>,
        query: NavmeshQuery,
        builder: &B,
    ) -> Result<DynamicPreparedNavmeshQueryResult<B::Map>, DynamicNavmeshError>
    where
        B: PreparedNavmeshBuilder,
        U: Borrow<DynamicNavmeshUpdate>,
    {
        let prepared_stale_before_updates = state.prepared_stale();
        let mut applied_update_count = 0;
        for update in updates {
            state.apply_update(update.borrow())?;
            applied_update_count += 1;
        }
        let prepared_stale_after_updates = state.prepared_stale();

        let materialized_navmesh = state.materialize()?;
        let raw_result = materialized_navmesh.query(query);
        let prepared_navmesh = builder
            .preprocess(&materialized_navmesh)
            .map_err(|source| DynamicNavmeshError::PreparedRebuild { source })?;
        let rebuilt_prepared_result = prepared_navmesh.query(query);
        state.mark_prepared_rebuilt();

        let metadata = DynamicPreparedNavmeshQueryMetadata {
            builder_name: builder.name(),
            applied_update_count,
            prepared_stale_before_updates,
            prepared_stale_after_updates,
            prepared_stale_after_rebuild: state.prepared_stale(),
            materialized_cell_count: materialized_navmesh.cells().len(),
            materialized_portal_count: materialized_navmesh.portals().len(),
            rebuild_status: DynamicPreparedNavmeshRebuildStatus::RebuiltFromMaterializedSnapshot,
        };

        Ok(DynamicPreparedNavmeshQueryResult {
            materialized_navmesh,
            prepared_navmesh,
            raw_result,
            rebuilt_prepared_result,
            metadata,
        })
    }
}

/// Online route search over a validated **static** [`Navmesh`] snapshot.
///
/// Implementations (channel search, TA*, optional Polyanya) own the algorithm but
/// share this module's mesh, walkability, and query contracts. They do not apply
/// dynamic availability—callers [`DynamicNavmeshState::materialize`] first when
/// needed. Prepared multi-query TRA* maps implement
/// [`PreparedNavmesh`] + a local `search` instead of this trait.
pub trait NavmeshPathfinder {
    /// Stable algorithm name for reports and benchmark ids.
    fn name(&self) -> &'static str;

    /// Searches for a continuous polyline between the query endpoints.
    ///
    /// Successful computation returns [`Ok`] with found or no-path
    /// [`SearchOutcome`]; invalid endpoints, exhausted [`condor_core::SearchBudget`],
    /// and backend prep failures return [`NavmeshSearchError`]. Disconnected graphs
    /// are no-path, not `Err`.
    ///
    /// # Errors
    ///
    /// Returns [`NavmeshSearchError`] when an endpoint is invalid, the caller budget
    /// is exhausted, or an implementation cannot prepare the navmesh for its search
    /// backend.
    fn search(&self, navmesh: &Navmesh, query: NavmeshQuery) -> NavmeshSearchResult;
}

fn polygon_edges(vertices: &[Point2]) -> impl Iterator<Item = (Point2, Point2)> + '_ {
    vertices
        .iter()
        .copied()
        .zip(vertices.iter().copied().cycle().skip(1))
        .take(vertices.len())
}

fn sort_and_dedup_parameters(parameters: &mut Vec<f64>) {
    parameters.sort_by(f64::total_cmp);
    parameters.dedup_by(|left, right| (*left - *right).abs() <= EPSILON);
}

fn interpolate_segment(start: Point2, end: Point2, parameter: f64) -> Point2 {
    Point2::new(
        start.x + ((end.x - start.x) * parameter),
        start.y + ((end.y - start.y) * parameter),
    )
}

fn segment_intersection_parameters(
    a_start: Point2,
    a_end: Point2,
    b_start: Point2,
    b_end: Point2,
) -> Vec<f64> {
    let mut parameters = Vec::with_capacity(2);
    for point in [a_start, a_end, b_start, b_end] {
        if point_on_segment(point, a_start, a_end) && point_on_segment(point, b_start, b_end) {
            parameters.push(segment_parameter(point, a_start, a_end));
        }
    }

    if !parameters.is_empty() {
        sort_and_dedup_parameters(&mut parameters);
        return parameters;
    }

    if let Some(parameter) = proper_intersection_parameter(a_start, a_end, b_start, b_end) {
        parameters.push(parameter);
    }

    parameters
}

fn segment_parameter(point: Point2, start: Point2, end: Point2) -> f64 {
    let dx = end.x - start.x;
    let dy = end.y - start.y;
    if dx.abs() >= dy.abs() && dx.abs() > EPSILON {
        ((point.x - start.x) / dx).clamp(0.0, 1.0)
    } else if dy.abs() > EPSILON {
        ((point.y - start.y) / dy).clamp(0.0, 1.0)
    } else {
        0.0
    }
}

fn proper_intersection_parameter(
    a_start: Point2,
    a_end: Point2,
    b_start: Point2,
    b_end: Point2,
) -> Option<f64> {
    let o1 = orientation(a_start, a_end, b_start);
    let o2 = orientation(a_start, a_end, b_end);
    let o3 = orientation(b_start, b_end, a_start);
    let o4 = orientation(b_start, b_end, a_end);

    let properly_crosses = (o1 > EPSILON && o2 < -EPSILON || o1 < -EPSILON && o2 > EPSILON)
        && (o3 > EPSILON && o4 < -EPSILON || o3 < -EPSILON && o4 > EPSILON);
    if !properly_crosses {
        return None;
    }

    let a_dx = a_end.x - a_start.x;
    let a_dy = a_end.y - a_start.y;
    let b_dx = b_end.x - b_start.x;
    let b_dy = b_end.y - b_start.y;
    let denominator = cross(a_dx, a_dy, b_dx, b_dy);
    if denominator.abs() <= EPSILON {
        return None;
    }

    let offset_x = b_start.x - a_start.x;
    let offset_y = b_start.y - a_start.y;
    Some((cross(offset_x, offset_y, b_dx, b_dy) / denominator).clamp(0.0, 1.0))
}

fn point_on_segment(point: Point2, start: Point2, end: Point2) -> bool {
    orientation(start, end, point).abs() <= EPSILON
        && point.x >= start.x.min(end.x) - EPSILON
        && point.x <= start.x.max(end.x) + EPSILON
        && point.y >= start.y.min(end.y) - EPSILON
        && point.y <= start.y.max(end.y) + EPSILON
}

fn orientation(start: Point2, end: Point2, point: Point2) -> f64 {
    ((end.x - start.x) * (point.y - start.y)) - ((end.y - start.y) * (point.x - start.x))
}

fn cross(left_x: f64, left_y: f64, right_x: f64, right_y: f64) -> f64 {
    (left_x * right_y) - (left_y * right_x)
}

fn is_degenerate_polygon(vertices: &[Point2]) -> bool {
    signed_area(vertices).abs() <= EPSILON
}

fn signed_area(vertices: &[Point2]) -> f64 {
    polygon_edges(vertices)
        .map(|(left, right)| (left.x * right.y) - (right.x * left.y))
        .sum::<f64>()
        / 2.0
}

fn is_convex_polygon(vertices: &[Point2]) -> bool {
    let mut reference_sign = 0.0_f64;
    for index in 0..vertices.len() {
        let a = vertices[index];
        let b = vertices[(index + 1) % vertices.len()];
        let c = vertices[(index + 2) % vertices.len()];
        let turn = orientation(a, b, c);
        if turn.abs() <= EPSILON {
            continue;
        }

        if reference_sign.abs() <= EPSILON {
            reference_sign = turn;
            continue;
        }

        if turn.signum() != reference_sign.signum() {
            return false;
        }
    }

    true
}

/// Epsilon equality for navmesh portal/endpoint identity (not bit-identity).
pub(crate) fn points_equal(left: Point2, right: Point2) -> bool {
    (left.x - right.x).abs() <= EPSILON && (left.y - right.y).abs() <= EPSILON
}

fn shares_any_cell(left: &[usize], right: &[usize]) -> bool {
    left.iter().any(|cell| right.contains(cell))
}

#[cfg(test)]
mod tests {
    use super::{Navmesh, NavmeshCell, NavmeshPortal, NavmeshQuery, NavmeshQueryResult};
    use condor_core::Point2;

    #[test]
    fn validates_and_queries_a_two_cell_mesh() {
        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().expect("valid mesh");
        assert!(matches!(
            navmesh.query(NavmeshQuery::new(
                Point2::new(1.0, 1.0),
                Point2::new(3.0, 1.0)
            )),
            NavmeshQueryResult::Connected { .. }
        ));
    }
}