condor_navmesh/navmesh/

prepared.rs

//! Build-once / query-many contracts for navmesh adjacency snapshots.
//!
//! # Role
//!
//! This module is the **prepared substrate**, not a solver. A
//! [`PreparedNavmeshBuilder`] clones a validated static [`Navmesh`] and indexes
//! neighbors and portals for repeated lookup. Algorithm lanes (notably TRA* in
//! [`crate::algorithms::tra_star`]) wrap these tables and add routing or
//! waypoint-cache policy; they still rebuild through the same preprocess contract.
//!
//! # Immutability and dynamic updates
//!
//! Prepared maps are **immutable snapshots**. Dynamic availability never patches
//! them in place. When [`crate::DynamicNavmeshState::prepared_stale`] is set,
//! discard the map and rebuild from a fresh
//! [`crate::DynamicNavmeshState::materialize`] snapshot (see
//! [`crate::DynamicPreparedNavmeshQuery`]).
//!
//! # Query contract
//!
//! Locate/query defaults still delegate to the owned mesh. The value of
//! preparation is indexed neighbor and portal access for corridor search and
//! prepared pathfinders, plus a stable builder `name()` for reports.

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

use crate::navmesh::{NavmeshValidationError, corridor::NavmeshCorridor};
use crate::{Navmesh, NavmeshPortal, NavmeshQuery, NavmeshQueryResult, Point2};

/// Preprocesses a validated static navmesh into an immutable prepared map.
///
/// Builders may add indexing, acceleration, or algorithm-specific caches (TRA*
/// waypoint databases). The starter [`StaticPreparedNavmeshBuilder`] only
/// materializes adjacency tables. Callers must re-run preprocess after any mesh
/// or availability change—maps are not updated in place.
pub trait PreparedNavmeshBuilder {
    /// Immutable prepared map type produced by this builder.
    type Map: PreparedNavmesh;

    /// Stable builder name for reports and dynamic-query metadata.
    fn name(&self) -> &'static str;

    /// Validates and snapshots `navmesh` into a query-ready prepared map.
    ///
    /// # Errors
    ///
    /// Returns [`PreparedNavmeshBuildError`] when the source mesh fails validation.
    fn preprocess(&self, navmesh: &Navmesh) -> Result<Self::Map, PreparedNavmeshBuildError>;
}

/// Immutable prepared navmesh snapshot with fast adjacency and portal lookup.
///
/// Owns (or borrows through) a static [`Navmesh`]. Default locate/query methods
/// forward to that mesh so connectivity semantics match the unprepared substrate.
pub trait PreparedNavmesh {
    /// Stable prepared-map name (usually the builder name).
    fn name(&self) -> &'static str;

    /// Owned static mesh snapshot this preparation was built from.
    fn navmesh(&self) -> &Navmesh;

    /// First cell containing `point`; see [`Navmesh::locate_point`].
    fn locate_point(&self, point: Point2) -> Option<usize> {
        self.navmesh().locate_point(point)
    }

    /// All cells containing `point`; see [`Navmesh::locate_cells`].
    fn locate_cells(&self, point: Point2) -> Vec<usize> {
        self.navmesh().locate_cells(point)
    }

    /// Cell-graph connectivity for `query`; see [`Navmesh::query`].
    fn query(&self, query: NavmeshQuery) -> NavmeshQueryResult {
        self.navmesh().query(query)
    }

    /// Indexed neighbor cell list for `cell_index`, or `None` if out of range.
    fn neighbors(&self, cell_index: usize) -> Option<&[usize]>;

    /// Indexed portals incident to `cell_index`, or `None` if out of range.
    fn portals_from(&self, cell_index: usize) -> Option<&[NavmeshPortal]>;

    /// Portal joining two cells when one was recorded at preprocess time.
    ///
    /// If multiple portals connect the same pair, the first in navmesh order wins
    /// (matches corridor materialization).
    fn portal_between(&self, left_cell: usize, right_cell: usize) -> Option<NavmeshPortal>;

    /// BFS over prepared neighbors: whether `start_cell` can reach `goal_cell`.
    ///
    /// Out-of-range indices return `false`. Prefer this over scanning raw portals
    /// when the prepared index is already available.
    fn cells_connected(&self, start_cell: usize, goal_cell: usize) -> bool {
        let cell_count = self.navmesh().cells().len();
        if start_cell >= cell_count || goal_cell >= cell_count {
            return false;
        }

        let mut seen = vec![false; cell_count];
        let mut frontier = VecDeque::from([start_cell]);
        seen[start_cell] = true;

        while let Some(cell_index) = frontier.pop_front() {
            if cell_index == goal_cell {
                return true;
            }

            let Some(neighbors) = self.neighbors(cell_index) else {
                continue;
            };

            for &neighbor in neighbors {
                if neighbor >= seen.len() || seen[neighbor] {
                    continue;
                }
                seen[neighbor] = true;
                frontier.push_back(neighbor);
            }
        }

        false
    }

    /// Builds a [`NavmeshCorridor`] for a known cell sequence using the owned mesh portals.
    ///
    /// Returns `None` when `cells` is empty or any consecutive pair lacks a portal.
    fn materialize_corridor(
        &self,
        start: Point2,
        goal: Point2,
        cells: &[usize],
    ) -> Option<NavmeshCorridor> {
        NavmeshCorridor::from_cells(self.navmesh(), start, goal, cells)
    }
}

/// Prepared navmesh preprocess failed because the source mesh failed validation.
///
/// Fail-closed: builders do not emit a partial prepared map when validation fails.
#[derive(Debug, Clone, PartialEq, thiserror::Error)]
#[non_exhaustive]
pub enum PreparedNavmeshBuildError {
    /// Source [`Navmesh`] failed [`Navmesh::validate`] during preprocess.
    #[error("invalid navmesh: {source}")]
    InvalidNavmesh {
        /// Underlying cell/portal validation failure.
        #[from]
        source: NavmeshValidationError,
    },
}

/// Starter builder that indexes neighbors and portals from a static navmesh.
///
/// Clones the mesh, validates it, and builds per-cell neighbor/portal tables plus a
/// bidirectional portal lookup. No hierarchical or algorithm-specific caches.
#[derive(Debug, Clone, Copy, Default)]
pub struct StaticPreparedNavmeshBuilder;

impl PreparedNavmeshBuilder for StaticPreparedNavmeshBuilder {
    type Map = StaticPreparedNavmesh;

    fn name(&self) -> &'static str {
        "static-prepared-navmesh"
    }

    fn preprocess(&self, navmesh: &Navmesh) -> Result<Self::Map, PreparedNavmeshBuildError> {
        navmesh
            .validate()
            .map_err(PreparedNavmeshBuildError::from)?;

        let mut neighbors = vec![Vec::new(); navmesh.cells().len()];
        let mut portals_from = vec![Vec::new(); navmesh.cells().len()];
        let mut portal_lookup = BTreeMap::new();

        for &portal in navmesh.portals() {
            neighbors[portal.left_cell].push(portal.right_cell);
            neighbors[portal.right_cell].push(portal.left_cell);

            portals_from[portal.left_cell].push(portal);
            portals_from[portal.right_cell].push(portal);

            // First portal in navmesh order wins for duplicate cell pairs.
            portal_lookup
                .entry((portal.left_cell, portal.right_cell))
                .or_insert(portal);
            portal_lookup
                .entry((portal.right_cell, portal.left_cell))
                .or_insert(portal);
        }

        Ok(StaticPreparedNavmesh {
            navmesh: navmesh.clone(),
            neighbors,
            portals_from,
            portal_lookup,
        })
    }
}

/// Pass-through prepared snapshot owning a cloned navmesh and adjacency indexes.
///
/// Safe to share across queries until the underlying availability overlay changes;
/// then rebuild rather than mutating this type.
#[derive(Debug, Clone, PartialEq)]
pub struct StaticPreparedNavmesh {
    navmesh: Navmesh,
    neighbors: Vec<Vec<usize>>,
    portals_from: Vec<Vec<NavmeshPortal>>,
    portal_lookup: BTreeMap<(usize, usize), NavmeshPortal>,
}

impl StaticPreparedNavmesh {
    /// Returns the default static prepared builder.
    #[must_use]
    pub fn builder() -> StaticPreparedNavmeshBuilder {
        StaticPreparedNavmeshBuilder
    }
}

impl PreparedNavmesh for StaticPreparedNavmesh {
    fn name(&self) -> &'static str {
        "static-prepared-navmesh"
    }

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

    fn neighbors(&self, cell_index: usize) -> Option<&[usize]> {
        self.neighbors.get(cell_index).map(Vec::as_slice)
    }

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

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

#[cfg(test)]
mod tests {
    use super::{PreparedNavmesh, PreparedNavmeshBuilder, StaticPreparedNavmesh};
    use crate::navmesh::corridor::NavmeshCorridor;
    use crate::{Navmesh, NavmeshCell, NavmeshPortal, Point2};

    #[test]
    fn portal_between_selects_same_portal_as_corridor_for_duplicate_pair() {
        let p0 = NavmeshPortal {
            left_cell: 0,
            right_cell: 1,
            start: Point2::new(2.0, 0.0),
            end: Point2::new(2.0, 2.0),
        };
        let p1 = NavmeshPortal {
            left_cell: 0,
            right_cell: 1,
            start: Point2::new(2.0, 2.0),
            end: Point2::new(2.0, 4.0),
        };
        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, 4.0),
                        Point2::new(0.0, 4.0),
                    ],
                ),
                NavmeshCell::new(
                    "right",
                    vec![
                        Point2::new(2.0, 0.0),
                        Point2::new(4.0, 0.0),
                        Point2::new(4.0, 4.0),
                        Point2::new(2.0, 4.0),
                    ],
                ),
            ],
            vec![p0, p1],
        );
        navmesh
            .validate()
            .expect("two-portal navmesh should validate");

        let prepared = StaticPreparedNavmesh::builder()
            .preprocess(&navmesh)
            .expect("preprocess should succeed");

        assert_eq!(prepared.portal_between(0, 1), Some(p0));
        assert_eq!(prepared.portal_between(1, 0), Some(p0));

        let corridor = NavmeshCorridor::from_cells(
            &navmesh,
            Point2::new(1.0, 1.0),
            Point2::new(3.0, 1.0),
            &[0, 1],
        )
        .expect("corridor should build");
        assert_eq!(corridor.portals[0], p0);
    }
}