condor_navmesh/algorithms/

tra_star.rs

//! Prepared-routing lane: TRA* builders and waypoint-database policy surfaces.
//!
//! # Surface (prepared, not static pathfinder)
//!
//! TRA* is **not** a [`crate::NavmeshPathfinder`]. Every public entry is a
//! [`PreparedNavmeshBuilder`] that clones a validated static [`Navmesh`], indexes
//! adjacency (via [`StaticPreparedNavmesh`]), and returns an
//! immutable map with a local `search` method. Use this lane when many queries
//! share one mesh; use channel search / TA* / Polyanya for independent one-shots.
//!
//! **Dynamic availability**: builders never read
//! [`DynamicNavmeshState`](crate::DynamicNavmeshState). When cells or portals
//! toggle, materialize a new static mesh and re-`preprocess` (or run
//! [`DynamicPreparedNavmeshQuery`](crate::DynamicPreparedNavmeshQuery) for the
//! connectivity rebuild helper). Prepared waypoint caches are discarded with the
//! old map—there is no incremental repair.
//!
//! # Builder lifecycle
//!
//! 1. Hold a validated static [`Navmesh`] (or materialization).
//! 2. Call `Builder::preprocess` → `Prepared*` map (or `Prepared*::builder()`).
//! 3. Call `prepared.search(query)` repeatedly until the underlying mesh changes.
//! 4. On mesh or availability change, drop the map and preprocess again.
//!
//! # Routing core (shared)
//!
//! All variants run the same geometric pipeline: connectivity precheck → prepared
//! neighbor BFS corridor → portal chain → midpoint **seed policy** → funnel
//! string-pull → walkability. Cost is Euclidean segment length over the funnelled
//! [`PolygonPath`] (no per-cell weights). Seed policy is the
//! only intentional difference between variants.
//!
//! # Waypoint-database policy ladder
//!
//! | Surface | Seed / cache policy |
//! | --- | --- |
//! | [`TRAStarBuilder`] / [`PreparedTRAStar`] | Default midpoints each query (no DB) |
//! | [`TRAStarPortalTransitionCacheBuilder`] | Eager directed `(from,to)` midpoint table |
//! | [`TRAStarWaypointDatabaseStaticBuilder`] | Eager per-cell waypoint lists |
//! | [`TRAStarWaypointDatabaseLazyQueryBuilder`] | Scratch map per query; no retention |
//! | [`TRAStarWaypointDatabaseAdaptiveLruBuilder`] | Single-tier recency LRU across queries |
//! | [`TRAStarWaypointDatabaseTwoTierLruBuilder`] | Probation → protected segmented LRU |
//! | [`TRAStarWaypointDatabaseCostAwareEvictionBuilder`] | Cost-weighted eviction signals |
//! | Fixed admission / promotion / demotion builders | Threshold + hit-count + overflow rules |
//! | [`TRAStarWaypointDatabasePolicyProfileBuilder`] | Named curated bundle (v1) |
//!
//! Portfolio recommendation for exact prepared navmesh routing points at base
//! [`TRAStarBuilder`]; policy variants are for cache-behavior evidence and knobs.
//!
//! # Examples
//!
//! ```
//! use condor_navmesh::{
//!     Navmesh, NavmeshCell, Point2, PreparedNavmesh, PreparedNavmeshBuilder, TRAStarBuilder,
//! };
//!
//! let navmesh = Navmesh::new(
//!     vec![NavmeshCell::new(
//!         "cell-0",
//!         vec![
//!             Point2::new(0.0, 0.0),
//!             Point2::new(2.0, 0.0),
//!             Point2::new(0.0, 2.0),
//!         ],
//!     )],
//!     vec![],
//! );
//! let builder = TRAStarBuilder;
//! let prepared = builder.preprocess(&navmesh).expect("prep fails only with invalid navmesh");
//! assert_eq!(prepared.name(), "tra-star");
//! ```
use std::collections::{BTreeMap, VecDeque};

use crate::navmesh::points_equal;
use crate::{
    Navmesh, NavmeshQuery, NavmeshQueryResult, NavmeshSearchResult, Point2, PolygonPath,
    PreparedNavmesh, PreparedNavmeshBuildError, PreparedNavmeshBuilder, StaticPreparedNavmesh,
    StaticPreparedNavmeshBuilder,
};

const EPSILON: f64 = 1e-9;
const ADAPTIVE_LRU_CAPACITY: usize = 256;
const COST_AWARE_EVICTION_WEIGHT: f64 = 0.35;
const FIXED_ADMISSION_COST_THRESHOLD: f64 = 2.5;
const FIXED_PROMOTION_RULE_HITS: usize = 2;

/// Base TRA* preprocess: adjacency snapshot + corridor/funnel search, no waypoint cache.
///
/// Default prepared surface for multi-query exact-style routing on a static mesh.
/// Prefer this unless a specific midpoint-cache policy is required.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct TRAStarBuilder;

impl PreparedNavmeshBuilder for TRAStarBuilder {
    type Map = PreparedTRAStar;

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

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

/// Immutable prepared TRA* map wrapping a [`StaticPreparedNavmesh`].
///
/// Preprocess once, then [`Self::search`] per query. Drop and rebuild when the
/// source mesh or availability overlay changes; this type is not patched in place.
#[derive(Debug, Clone, PartialEq)]
pub struct PreparedTRAStar {
    prepared: StaticPreparedNavmesh,
}

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

    /// Borrowed static prepared navmesh (adjacency / portal tables).
    #[must_use]
    pub fn prepared_navmesh(&self) -> &StaticPreparedNavmesh {
        &self.prepared
    }

    /// Routes with default portal-midpoint seeds and funnel string-pull.
    ///
    /// Same connectivity and walkability errors as static pathfinders; found vs
    /// no-path are both successful outcomes with visit stats.
    pub fn search(&self, query: NavmeshQuery) -> NavmeshSearchResult {
        search_with_midpoint_seed(self, query, default_midpoint_seed)
    }
}

impl PreparedNavmesh for PreparedTRAStar {
    fn name(&self) -> &'static str {
        "tra-star"
    }

    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<&[crate::NavmeshPortal]> {
        self.prepared.portals_from(cell_index)
    }

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

/// Eager directed portal-midpoint table built at preprocess (no eviction).
///
/// Materializes every `(from_cell, to_cell)` midpoint once; query seeds the funnel
/// from that table. Use when the full transition set fits memory and must stay hot.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct TRAStarPortalTransitionCacheBuilder;

impl PreparedNavmeshBuilder for TRAStarPortalTransitionCacheBuilder {
    type Map = PreparedTRAStarPortalTransitionCache;

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

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

/// Prepared TRA* with an eager map from directed cell transitions to portal midpoints.
///
/// Preprocess materializes every portal midpoint; query seeds the funnel from that table.
#[derive(Debug, Clone, PartialEq)]
pub struct PreparedTRAStarPortalTransitionCache {
    prepared: PreparedTRAStar,
    portal_transition_midpoints: BTreeMap<(usize, usize), Point2>,
}

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

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

    /// Number of directed `(from_cell, to_cell)` midpoint entries retained after preprocess.
    #[must_use]
    pub fn portal_transition_count(&self) -> usize {
        self.portal_transition_midpoints.len()
    }

    /// Routes with precomputed portal-midpoint seeds and funnel string-pull.
    pub fn search(&self, query: NavmeshQuery) -> NavmeshSearchResult {
        search_with_midpoint_seed(self, query, |corridor, cells| {
            self.midpoint_seed_from_transitions(cells, corridor)
        })
    }

    fn from_prepared(prepared: PreparedTRAStar) -> Self {
        let mut portal_transition_midpoints = BTreeMap::new();
        for cell_index in 0..prepared.navmesh().cells().len() {
            let Some(portals) = prepared.portals_from(cell_index) else {
                continue;
            };

            for &portal in portals {
                let neighbor = if portal.left_cell == cell_index {
                    portal.right_cell
                } else {
                    portal.left_cell
                };
                portal_transition_midpoints
                    .entry((cell_index, neighbor))
                    .or_insert_with(|| crate::algorithms::channel_search::portal_midpoint(&portal));
            }
        }

        Self {
            prepared,
            portal_transition_midpoints,
        }
    }

    fn midpoint_seed_from_transitions(
        &self,
        cells: &[usize],
        corridor: &crate::navmesh::corridor::NavmeshCorridor,
    ) -> Vec<Point2> {
        cells
            .windows(2)
            .enumerate()
            .map(|(index, pair)| {
                self.portal_transition_midpoints
                    .get(&(pair[0], pair[1]))
                    .copied()
                    .or_else(|| {
                        corridor.portals.get(index).copied().map(|portal| {
                            crate::algorithms::channel_search::portal_midpoint(&portal)
                        })
                    })
                    .unwrap_or(corridor.goal)
            })
            .collect()
    }
}

/// Eager per-cell portal-midpoint waypoint lists (full static database, no eviction).
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct TRAStarWaypointDatabaseStaticBuilder;

impl PreparedNavmeshBuilder for TRAStarWaypointDatabaseStaticBuilder {
    type Map = PreparedTRAStarWaypointDatabaseStatic;

    fn name(&self) -> &'static str {
        "tra-star-waypoint-database-static"
    }

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

/// Per-query lazy midpoints only—scratch storage discarded after each `search`.
///
/// Useful as a no-retention baseline against LRU / static DB policies.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct TRAStarWaypointDatabaseLazyQueryBuilder;

impl PreparedNavmeshBuilder for TRAStarWaypointDatabaseLazyQueryBuilder {
    type Map = PreparedTRAStarWaypointDatabaseLazyQuery;

    fn name(&self) -> &'static str {
        "tra-star-waypoint-database-lazy-query"
    }

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

/// Capacity-bounded single-tier LRU of portal midpoints across queries (recency only).
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct TRAStarWaypointDatabaseAdaptiveLruBuilder;

impl PreparedNavmeshBuilder for TRAStarWaypointDatabaseAdaptiveLruBuilder {
    type Map = PreparedTRAStarWaypointDatabaseAdaptiveLru;

    fn name(&self) -> &'static str {
        "tra-star-waypoint-database-adaptive-lru"
    }

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

/// Two-tier probation/protected midpoint LRU; first hit promotes into protected.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct TRAStarWaypointDatabaseTwoTierLruBuilder;

impl PreparedNavmeshBuilder for TRAStarWaypointDatabaseTwoTierLruBuilder {
    type Map = PreparedTRAStarWaypointDatabaseTwoTierLru;

    fn name(&self) -> &'static str {
        "tra-star-waypoint-database-two-tier-lru"
    }

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

/// Cost-weighted eviction of cached midpoints (recency blended with low-cost bias).
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct TRAStarWaypointDatabaseCostAwareEvictionBuilder;

/// Retain midpoints only when portal segment cost meets a fixed admission threshold.
///
/// Below-threshold midpoints still seed the current query; they are not stored.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct TRAStarWaypointDatabaseFixedAdmissionThresholdBuilder;

/// Fixed admission threshold plus multi-hit promotion from probation to protected.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct TRAStarWaypointDatabaseFixedPromotionRuleBuilder;

/// Fixed admission + promotion, with protected overflow that **evicts** (not demotes).
///
/// Differs from two-tier demotion: least-recent protected entries leave the cache.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct TRAStarWaypointDatabaseFixedDemotionRuleBuilder;

/// Named admission / promotion / demotion parameter bundle for the curated policy lane.
///
/// Prefer [`TRAStarWaypointDatabasePolicyProfileBuilder`] over composing fixed-rule
/// builders by hand when the portfolio needs a single stable algorithm id.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub enum TRAStarWaypointDatabasePolicyProfile {
    /// v1 fixed thresholds: admission cost `2.5`, promotion after `2` probation hits,
    /// protected overflow evicts least-recent protected.
    #[default]
    V1,
}

impl TRAStarWaypointDatabasePolicyProfile {
    /// Stable algorithm name string for this profile (matches builder `name()`).
    #[must_use]
    pub const fn name(self) -> &'static str {
        match self {
            Self::V1 => "tra-star-waypoint-database-policy-profile-v1",
        }
    }

    /// Minimum portal segment cost required to admit a midpoint into the cache.
    #[must_use]
    pub const fn admission_cost_threshold(self) -> f64 {
        match self {
            Self::V1 => FIXED_ADMISSION_COST_THRESHOLD,
        }
    }

    /// Probation hits required before promoting a midpoint into the protected tier.
    #[must_use]
    pub const fn promotion_hits_required(self) -> usize {
        match self {
            Self::V1 => FIXED_PROMOTION_RULE_HITS,
        }
    }
}

/// Preprocess builder that materializes a named [`TRAStarWaypointDatabasePolicyProfile`].
///
/// Stable `name()` comes from the profile (e.g. policy-profile-v1), not a generic builder id.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct TRAStarWaypointDatabasePolicyProfileBuilder {
    profile: TRAStarWaypointDatabasePolicyProfile,
}

impl TRAStarWaypointDatabasePolicyProfileBuilder {
    /// Builds with the given named policy profile.
    #[must_use]
    pub const fn new(profile: TRAStarWaypointDatabasePolicyProfile) -> Self {
        Self { profile }
    }

    /// Policy profile this builder will materialize.
    #[must_use]
    pub const fn policy_profile(self) -> TRAStarWaypointDatabasePolicyProfile {
        self.profile
    }
}

impl PreparedNavmeshBuilder for TRAStarWaypointDatabaseCostAwareEvictionBuilder {
    type Map = PreparedTRAStarWaypointDatabaseCostAwareEviction;

    fn name(&self) -> &'static str {
        "tra-star-waypoint-database-cost-aware-eviction"
    }

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

impl PreparedNavmeshBuilder for TRAStarWaypointDatabaseFixedAdmissionThresholdBuilder {
    type Map = PreparedTRAStarWaypointDatabaseFixedAdmissionThreshold;

    fn name(&self) -> &'static str {
        "tra-star-waypoint-database-fixed-admission-threshold"
    }

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

impl PreparedNavmeshBuilder for TRAStarWaypointDatabaseFixedPromotionRuleBuilder {
    type Map = PreparedTRAStarWaypointDatabaseFixedPromotionRule;

    fn name(&self) -> &'static str {
        "tra-star-waypoint-database-fixed-promotion-rule"
    }

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

impl PreparedNavmeshBuilder for TRAStarWaypointDatabaseFixedDemotionRuleBuilder {
    type Map = PreparedTRAStarWaypointDatabaseFixedDemotionRule;

    fn name(&self) -> &'static str {
        "tra-star-waypoint-database-fixed-demotion-rule"
    }

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

impl PreparedNavmeshBuilder for TRAStarWaypointDatabasePolicyProfileBuilder {
    type Map = PreparedTRAStarWaypointDatabasePolicyProfile;

    fn name(&self) -> &'static str {
        self.profile.name()
    }

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

#[derive(Debug, Clone, Copy, PartialEq)]
struct CellWaypointEntry {
    to_cell: usize,
    waypoint: Point2,
}

/// Prepared TRA* with an eager per-cell portal-midpoint waypoint database.
///
/// All directed midpoints materialize at preprocess; no eviction across queries.
#[derive(Debug, Clone, PartialEq)]
pub struct PreparedTRAStarWaypointDatabaseStatic {
    prepared: PreparedTRAStar,
    waypoint_database: BTreeMap<usize, Vec<CellWaypointEntry>>,
}

/// Prepared TRA* that computes midpoints on demand without cross-query retention.
///
/// Each `search` builds a scratch map discarded at query end (no durable cache policy).
#[derive(Debug, Clone, PartialEq)]
pub struct PreparedTRAStarWaypointDatabaseLazyQuery {
    prepared: PreparedTRAStar,
}

#[derive(Debug, Default)]
struct WaypointLruCache {
    entries: BTreeMap<(usize, usize), Point2>,
    order: VecDeque<(usize, usize)>,
}

impl WaypointLruCache {
    fn get(&mut self, key: (usize, usize)) -> Option<Point2> {
        let waypoint = self.entries.get(&key).copied()?;
        self.promote(key);
        Some(waypoint)
    }

    fn insert(&mut self, key: (usize, usize), waypoint: Point2, capacity: usize) {
        if self.entries.insert(key, waypoint).is_some() {
            self.promote(key);
            return;
        }

        self.order.push_back(key);
        while self.entries.len() > capacity {
            if let Some(evicted) = self.order.pop_front() {
                self.entries.remove(&evicted);
            } else {
                break;
            }
        }
    }

    fn len(&self) -> usize {
        self.entries.len()
    }

    fn promote(&mut self, key: (usize, usize)) {
        if let Some(position) = self.order.iter().position(|entry| *entry == key) {
            let _ = self.order.remove(position);
        }
        self.order.push_back(key);
    }
}

/// Prepared TRA* with a capacity-bounded single-tier LRU of portal midpoints.
///
/// Midpoints fill on first use and survive across queries until capacity eviction (recency only).
#[derive(Debug)]
pub struct PreparedTRAStarWaypointDatabaseAdaptiveLru {
    prepared: PreparedTRAStar,
    capacity: usize,
    waypoint_lru_cache: std::sync::Mutex<WaypointLruCache>,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum LruTier {
    Probation,
    Protected,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum ProtectedOverflowPolicy {
    DemoteToProbation,
    EvictLeastRecentProtected,
}

#[derive(Debug, Clone, Copy, PartialEq)]
struct SegmentedWaypointEntry {
    waypoint: Point2,
    tier: LruTier,
}

#[derive(Debug, Default)]
struct WaypointSegmentedLruCache {
    entries: BTreeMap<(usize, usize), SegmentedWaypointEntry>,
    probation_order: VecDeque<(usize, usize)>,
    protected_order: VecDeque<(usize, usize)>,
}

impl WaypointSegmentedLruCache {
    fn get(&mut self, key: (usize, usize), protected_capacity: usize) -> Option<Point2> {
        let waypoint = self.entries.get(&key)?.waypoint;
        let tier = self.entries.get(&key)?.tier;
        match tier {
            LruTier::Probation => {
                Self::remove_from_order(&mut self.probation_order, key);
                if let Some(entry) = self.entries.get_mut(&key) {
                    entry.tier = LruTier::Protected;
                }
                self.protected_order.push_back(key);
                self.rebalance_protected(protected_capacity);
            }
            LruTier::Protected => {
                Self::remove_from_order(&mut self.protected_order, key);
                self.protected_order.push_back(key);
            }
        }
        Some(waypoint)
    }

    fn insert(
        &mut self,
        key: (usize, usize),
        waypoint: Point2,
        capacity: usize,
        protected_capacity: usize,
    ) {
        if let Some(entry) = self.entries.get_mut(&key) {
            entry.waypoint = waypoint;
            let _ = self.get(key, protected_capacity);
            return;
        }

        self.entries.insert(
            key,
            SegmentedWaypointEntry {
                waypoint,
                tier: LruTier::Probation,
            },
        );
        self.probation_order.push_back(key);

        self.evict_to_capacity(capacity);
        self.rebalance_protected(protected_capacity);
    }

    fn len(&self) -> usize {
        self.entries.len()
    }

    fn probation_len(&self) -> usize {
        self.probation_order.len()
    }

    fn protected_len(&self) -> usize {
        self.protected_order.len()
    }

    fn evict_to_capacity(&mut self, capacity: usize) {
        while self.entries.len() > capacity {
            let evicted = self
                .probation_order
                .pop_front()
                .or_else(|| self.protected_order.pop_front());
            if let Some(key) = evicted {
                self.entries.remove(&key);
            } else {
                break;
            }
        }
    }

    fn rebalance_protected(&mut self, protected_capacity: usize) {
        while self.protected_order.len() > protected_capacity {
            let Some(demoted) = self.protected_order.pop_front() else {
                break;
            };

            if let Some(entry) = self.entries.get_mut(&demoted) {
                entry.tier = LruTier::Probation;
                Self::remove_from_order(&mut self.probation_order, demoted);
                self.probation_order.push_back(demoted);
            }
        }
    }

    fn remove_from_order(order: &mut VecDeque<(usize, usize)>, key: (usize, usize)) {
        if let Some(position) = order.iter().position(|entry| *entry == key) {
            let _ = order.remove(position);
        }
    }
}

/// Prepared TRA* with probation/protected two-tier LRU midpoint cache.
///
/// First hit promotes probation → protected; protected overflow demotes to probation.
#[derive(Debug)]
pub struct PreparedTRAStarWaypointDatabaseTwoTierLru {
    prepared: PreparedTRAStar,
    capacity: usize,
    protected_capacity: usize,
    waypoint_lru_cache: std::sync::Mutex<WaypointSegmentedLruCache>,
}

#[derive(Debug, Clone, Copy, PartialEq)]
struct CostAwareWaypointEntry {
    waypoint: Point2,
    tier: LruTier,
    cost_signal: f64,
    probation_hits: usize,
}

#[derive(Debug, Default)]
struct WaypointCostAwareCache {
    entries: BTreeMap<(usize, usize), CostAwareWaypointEntry>,
    probation_order: VecDeque<(usize, usize)>,
    protected_order: VecDeque<(usize, usize)>,
}

impl WaypointCostAwareCache {
    fn get(
        &mut self,
        key: (usize, usize),
        protected_capacity: usize,
        promotion_hits_required: usize,
        overflow_policy: ProtectedOverflowPolicy,
    ) -> Option<Point2> {
        let entry = self.entries.get(&key).copied()?;
        match entry.tier {
            LruTier::Probation => {
                Self::remove_from_order(&mut self.probation_order, key);
                if entry.probation_hits + 1 >= promotion_hits_required {
                    if let Some(stored) = self.entries.get_mut(&key) {
                        stored.tier = LruTier::Protected;
                        stored.probation_hits = 0;
                    }
                    self.protected_order.push_back(key);
                    self.rebalance_protected(protected_capacity, overflow_policy);
                } else {
                    if let Some(stored) = self.entries.get_mut(&key) {
                        stored.probation_hits += 1;
                    }
                    self.probation_order.push_back(key);
                }
            }
            LruTier::Protected => {
                Self::remove_from_order(&mut self.protected_order, key);
                self.protected_order.push_back(key);
            }
        }
        Some(entry.waypoint)
    }

    fn insert(
        &mut self,
        key: (usize, usize),
        waypoint: Point2,
        cost_signal: f64,
        capacity: usize,
        protected_capacity: usize,
    ) {
        if let Some(entry) = self.entries.get_mut(&key) {
            entry.waypoint = waypoint;
            entry.cost_signal = cost_signal;
            let _ = self.get(
                key,
                protected_capacity,
                1,
                ProtectedOverflowPolicy::DemoteToProbation,
            );
            return;
        }

        self.entries.insert(
            key,
            CostAwareWaypointEntry {
                waypoint,
                tier: LruTier::Probation,
                cost_signal,
                probation_hits: 0,
            },
        );
        self.probation_order.push_back(key);

        self.evict_to_capacity(capacity);
        self.rebalance_protected(
            protected_capacity,
            ProtectedOverflowPolicy::DemoteToProbation,
        );
    }

    fn len(&self) -> usize {
        self.entries.len()
    }

    fn probation_len(&self) -> usize {
        self.probation_order.len()
    }

    fn protected_len(&self) -> usize {
        self.protected_order.len()
    }

    fn evict_to_capacity(&mut self, capacity: usize) {
        while self.entries.len() > capacity {
            self.evict_one();
        }
    }

    fn evict_one(&mut self) {
        let from_probation = !self.probation_order.is_empty();
        let order = if from_probation {
            &self.probation_order
        } else {
            &self.protected_order
        };

        let Some(key) = self.select_eviction_candidate(order) else {
            return;
        };

        if from_probation {
            Self::remove_from_order(&mut self.probation_order, key);
        } else {
            Self::remove_from_order(&mut self.protected_order, key);
        }
        self.entries.remove(&key);
    }

    fn select_eviction_candidate(
        &self,
        order: &VecDeque<(usize, usize)>,
    ) -> Option<(usize, usize)> {
        let len = order.len();
        order
            .iter()
            .copied()
            .enumerate()
            .filter_map(|(index, key)| {
                self.entries.get(&key).map(|entry| {
                    let recency_priority = (len.saturating_sub(index)) as f64 / len.max(1) as f64;
                    let low_cost_priority = 1.0 / (1.0 + entry.cost_signal);
                    let eviction_priority = recency_priority * (1.0 - COST_AWARE_EVICTION_WEIGHT)
                        + low_cost_priority * COST_AWARE_EVICTION_WEIGHT;
                    (key, eviction_priority)
                })
            })
            .max_by(|(_, left), (_, right)| left.total_cmp(right))
            .map(|(key, _)| key)
    }

    fn rebalance_protected(
        &mut self,
        protected_capacity: usize,
        overflow_policy: ProtectedOverflowPolicy,
    ) {
        while self.protected_order.len() > protected_capacity {
            let Some(demoted) = self.protected_order.pop_front() else {
                break;
            };

            match overflow_policy {
                ProtectedOverflowPolicy::DemoteToProbation => {
                    if let Some(entry) = self.entries.get_mut(&demoted) {
                        entry.tier = LruTier::Probation;
                        entry.probation_hits = 0;
                        Self::remove_from_order(&mut self.probation_order, demoted);
                        self.probation_order.push_back(demoted);
                    }
                }
                ProtectedOverflowPolicy::EvictLeastRecentProtected => {
                    self.entries.remove(&demoted);
                }
            }
        }
    }

    fn remove_from_order(order: &mut VecDeque<(usize, usize)>, key: (usize, usize)) {
        if let Some(position) = order.iter().position(|entry| *entry == key) {
            let _ = order.remove(position);
        }
    }
}

/// Prepared TRA* that evicts cached midpoints using cost-weighted signals (not recency alone).
#[derive(Debug)]
pub struct PreparedTRAStarWaypointDatabaseCostAwareEviction {
    prepared: PreparedTRAStar,
    capacity: usize,
    protected_capacity: usize,
    waypoint_cost_cache: std::sync::Mutex<WaypointCostAwareCache>,
}

/// Prepared TRA* that gates cache admission on a fixed transition-cost threshold.
///
/// Midpoints below the threshold are still used for the current seed but are not retained.
#[derive(Debug)]
pub struct PreparedTRAStarWaypointDatabaseFixedAdmissionThreshold {
    prepared: PreparedTRAStar,
    capacity: usize,
    protected_capacity: usize,
    admission_threshold: f64,
    waypoint_cost_cache: std::sync::Mutex<WaypointCostAwareCache>,
}

/// Prepared TRA* that promotes probation midpoints after a fixed hit count.
///
/// Combines fixed admission threshold with multi-hit promotion into the protected tier.
#[derive(Debug)]
pub struct PreparedTRAStarWaypointDatabaseFixedPromotionRule {
    prepared: PreparedTRAStar,
    capacity: usize,
    protected_capacity: usize,
    admission_threshold: f64,
    promotion_hits_required: usize,
    waypoint_cost_cache: std::sync::Mutex<WaypointCostAwareCache>,
}

/// Prepared TRA* that demotes protected midpoints under a fixed overflow policy.
///
/// Protected overflow evicts the least-recent protected entry rather than demoting to probation.
#[derive(Debug)]
pub struct PreparedTRAStarWaypointDatabaseFixedDemotionRule {
    prepared: PreparedTRAStar,
    capacity: usize,
    protected_capacity: usize,
    admission_threshold: f64,
    promotion_hits_required: usize,
    waypoint_cost_cache: std::sync::Mutex<WaypointCostAwareCache>,
}

/// Prepared TRA* bound to a named [`TRAStarWaypointDatabasePolicyProfile`].
///
/// Curated policy bundle; v1 delegates to fixed-admission + promotion + demotion rules.
#[derive(Debug)]
pub struct PreparedTRAStarWaypointDatabasePolicyProfile {
    profile: TRAStarWaypointDatabasePolicyProfile,
    waypoint_policy: PreparedTRAStarWaypointDatabaseFixedDemotionRule,
}

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

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

    /// Total directed midpoint entries in the eager waypoint database.
    #[must_use]
    pub fn waypoint_entry_count(&self) -> usize {
        self.waypoint_database
            .values()
            .map(std::vec::Vec::len)
            .sum()
    }

    /// Routes using the static waypoint database for funnel midpoint seeds.
    pub fn search(&self, query: NavmeshQuery) -> NavmeshSearchResult {
        search_with_midpoint_seed(self, query, |corridor, cells| {
            self.midpoint_seed_from_waypoint_database(cells, corridor)
        })
    }

    fn from_prepared(prepared: PreparedTRAStar) -> Self {
        let mut waypoint_database = BTreeMap::new();

        for cell_index in 0..prepared.navmesh().cells().len() {
            let Some(prepared_neighbors) = prepared.neighbors(cell_index) else {
                continue;
            };

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

            let entries = neighbors
                .into_iter()
                .filter_map(|neighbor| {
                    prepared
                        .portal_between(cell_index, neighbor)
                        .map(|portal| CellWaypointEntry {
                            to_cell: neighbor,
                            waypoint: crate::algorithms::channel_search::portal_midpoint(&portal),
                        })
                })
                .collect::<Vec<_>>();

            if !entries.is_empty() {
                waypoint_database.insert(cell_index, entries);
            }
        }

        Self {
            prepared,
            waypoint_database,
        }
    }

    fn lookup_waypoint(&self, from_cell: usize, to_cell: usize) -> Option<Point2> {
        self.waypoint_database.get(&from_cell).and_then(|entries| {
            entries
                .iter()
                .find_map(|entry| (entry.to_cell == to_cell).then_some(entry.waypoint))
        })
    }

    fn midpoint_seed_from_waypoint_database(
        &self,
        cells: &[usize],
        corridor: &crate::navmesh::corridor::NavmeshCorridor,
    ) -> Vec<Point2> {
        cells
            .windows(2)
            .enumerate()
            .map(|(index, pair)| {
                self.lookup_waypoint(pair[0], pair[1])
                    .or_else(|| {
                        corridor.portals.get(index).copied().map(|portal| {
                            crate::algorithms::channel_search::portal_midpoint(&portal)
                        })
                    })
                    .unwrap_or(corridor.goal)
            })
            .collect()
    }
}

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

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

    /// Routes with per-query lazy midpoint materialization (no cross-query cache).
    pub fn search(&self, query: NavmeshQuery) -> NavmeshSearchResult {
        search_with_midpoint_seed(self, query, |corridor, cells| {
            self.midpoint_seed_from_lazy_waypoint_database(cells, corridor)
        })
    }

    fn from_prepared(prepared: PreparedTRAStar) -> Self {
        Self { prepared }
    }

    fn lookup_or_insert_lazy_waypoint(
        &self,
        query_waypoint_database: &mut BTreeMap<usize, Vec<CellWaypointEntry>>,
        from_cell: usize,
        to_cell: usize,
    ) -> Option<Point2> {
        if let Some(entries) = query_waypoint_database.get(&from_cell)
            && let Some(waypoint) = entries
                .iter()
                .find_map(|entry| (entry.to_cell == to_cell).then_some(entry.waypoint))
        {
            return Some(waypoint);
        }

        let waypoint = self
            .prepared
            .portal_between(from_cell, to_cell)
            .map(|portal| crate::algorithms::channel_search::portal_midpoint(&portal))?;

        query_waypoint_database
            .entry(from_cell)
            .or_default()
            .push(CellWaypointEntry { to_cell, waypoint });

        Some(waypoint)
    }

    fn midpoint_seed_from_lazy_waypoint_database(
        &self,
        cells: &[usize],
        corridor: &crate::navmesh::corridor::NavmeshCorridor,
    ) -> Vec<Point2> {
        let mut query_waypoint_database: BTreeMap<usize, Vec<CellWaypointEntry>> = BTreeMap::new();

        cells
            .windows(2)
            .enumerate()
            .map(|(index, pair)| {
                self.lookup_or_insert_lazy_waypoint(&mut query_waypoint_database, pair[0], pair[1])
                    .or_else(|| {
                        corridor.portals.get(index).copied().map(|portal| {
                            crate::algorithms::channel_search::portal_midpoint(&portal)
                        })
                    })
                    .unwrap_or(corridor.goal)
            })
            .collect()
    }
}

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

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

    /// Maximum midpoint entries retained in the adaptive LRU.
    #[must_use]
    pub fn lru_capacity(&self) -> usize {
        self.capacity
    }

    /// Midpoints currently held in the adaptive LRU (across queries).
    #[must_use]
    pub fn retained_waypoint_count(&self) -> usize {
        self.waypoint_lru_cache
            .lock()
            .expect("adaptive waypoint cache lock should not be poisoned")
            .len()
    }

    /// Routes while updating the adaptive LRU midpoint cache.
    pub fn search(&self, query: NavmeshQuery) -> NavmeshSearchResult {
        search_with_midpoint_seed(self, query, |corridor, cells| {
            self.midpoint_seed_from_adaptive_lru(cells, corridor)
        })
    }

    fn from_prepared(prepared: PreparedTRAStar, capacity: usize) -> Self {
        Self {
            prepared,
            capacity,
            waypoint_lru_cache: std::sync::Mutex::new(WaypointLruCache::default()),
        }
    }

    fn lookup_or_insert_waypoint(&self, from_cell: usize, to_cell: usize) -> Option<Point2> {
        let mut cache = self
            .waypoint_lru_cache
            .lock()
            .expect("adaptive waypoint cache lock should not be poisoned");
        let key = (from_cell, to_cell);
        if let Some(waypoint) = cache.get(key) {
            return Some(waypoint);
        }

        let waypoint = self
            .prepared
            .portal_between(from_cell, to_cell)
            .map(|portal| crate::algorithms::channel_search::portal_midpoint(&portal))?;
        cache.insert(key, waypoint, self.capacity);
        Some(waypoint)
    }

    fn midpoint_seed_from_adaptive_lru(
        &self,
        cells: &[usize],
        corridor: &crate::navmesh::corridor::NavmeshCorridor,
    ) -> Vec<Point2> {
        cells
            .windows(2)
            .enumerate()
            .map(|(index, pair)| {
                self.lookup_or_insert_waypoint(pair[0], pair[1])
                    .or_else(|| {
                        corridor.portals.get(index).copied().map(|portal| {
                            crate::algorithms::channel_search::portal_midpoint(&portal)
                        })
                    })
                    .unwrap_or(corridor.goal)
            })
            .collect()
    }
}

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

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

    /// Total midpoint capacity across probation and protected segments.
    #[must_use]
    pub fn lru_capacity(&self) -> usize {
        self.capacity
    }

    /// Capacity reserved for the protected LRU segment.
    #[must_use]
    pub fn protected_segment_capacity(&self) -> usize {
        self.protected_capacity
    }

    /// Midpoints currently retained in either tier.
    #[must_use]
    pub fn retained_waypoint_count(&self) -> usize {
        self.waypoint_lru_cache
            .lock()
            .expect("segmented waypoint cache lock should not be poisoned")
            .len()
    }

    /// Midpoints currently in the probation segment.
    #[must_use]
    pub fn retained_probation_count(&self) -> usize {
        self.waypoint_lru_cache
            .lock()
            .expect("segmented waypoint cache lock should not be poisoned")
            .probation_len()
    }

    /// Midpoints currently in the protected segment.
    #[must_use]
    pub fn retained_protected_count(&self) -> usize {
        self.waypoint_lru_cache
            .lock()
            .expect("segmented waypoint cache lock should not be poisoned")
            .protected_len()
    }

    /// Routes while updating the two-tier midpoint LRU.
    pub fn search(&self, query: NavmeshQuery) -> NavmeshSearchResult {
        search_with_midpoint_seed(self, query, |corridor, cells| {
            self.midpoint_seed_from_two_tier_lru(cells, corridor)
        })
    }

    fn from_prepared(prepared: PreparedTRAStar, capacity: usize) -> Self {
        let protected_capacity = capacity / 2;
        Self {
            prepared,
            capacity,
            protected_capacity,
            waypoint_lru_cache: std::sync::Mutex::new(WaypointSegmentedLruCache::default()),
        }
    }

    fn lookup_or_insert_waypoint(&self, from_cell: usize, to_cell: usize) -> Option<Point2> {
        let mut cache = self
            .waypoint_lru_cache
            .lock()
            .expect("segmented waypoint cache lock should not be poisoned");
        let key = (from_cell, to_cell);
        if let Some(waypoint) = cache.get(key, self.protected_capacity) {
            return Some(waypoint);
        }

        let waypoint = self
            .prepared
            .portal_between(from_cell, to_cell)
            .map(|portal| crate::algorithms::channel_search::portal_midpoint(&portal))?;
        cache.insert(key, waypoint, self.capacity, self.protected_capacity);
        Some(waypoint)
    }

    fn midpoint_seed_from_two_tier_lru(
        &self,
        cells: &[usize],
        corridor: &crate::navmesh::corridor::NavmeshCorridor,
    ) -> Vec<Point2> {
        cells
            .windows(2)
            .enumerate()
            .map(|(index, pair)| {
                self.lookup_or_insert_waypoint(pair[0], pair[1])
                    .or_else(|| {
                        corridor.portals.get(index).copied().map(|portal| {
                            crate::algorithms::channel_search::portal_midpoint(&portal)
                        })
                    })
                    .unwrap_or(corridor.goal)
            })
            .collect()
    }
}

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

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

    /// Total midpoint capacity before cost-weighted eviction.
    #[must_use]
    pub fn eviction_capacity(&self) -> usize {
        self.capacity
    }

    /// Capacity reserved for the protected segment.
    #[must_use]
    pub fn protected_segment_capacity(&self) -> usize {
        self.protected_capacity
    }

    /// Midpoints currently retained under the cost-aware policy.
    #[must_use]
    pub fn retained_waypoint_count(&self) -> usize {
        self.waypoint_cost_cache
            .lock()
            .expect("cost-aware waypoint cache lock should not be poisoned")
            .len()
    }

    /// Midpoints currently in probation.
    #[must_use]
    pub fn retained_probation_count(&self) -> usize {
        self.waypoint_cost_cache
            .lock()
            .expect("cost-aware waypoint cache lock should not be poisoned")
            .probation_len()
    }

    /// Midpoints currently in the protected segment.
    #[must_use]
    pub fn retained_protected_count(&self) -> usize {
        self.waypoint_cost_cache
            .lock()
            .expect("cost-aware waypoint cache lock should not be poisoned")
            .protected_len()
    }

    /// Routes while updating the cost-aware midpoint cache.
    pub fn search(&self, query: NavmeshQuery) -> NavmeshSearchResult {
        search_with_midpoint_seed(self, query, |corridor, cells| {
            self.midpoint_seed_from_cost_aware_eviction(cells, corridor)
        })
    }

    fn from_prepared(prepared: PreparedTRAStar, capacity: usize) -> Self {
        let protected_capacity = capacity / 2;
        Self {
            prepared,
            capacity,
            protected_capacity,
            waypoint_cost_cache: std::sync::Mutex::new(WaypointCostAwareCache::default()),
        }
    }

    fn lookup_or_insert_waypoint(&self, from_cell: usize, to_cell: usize) -> Option<Point2> {
        let mut cache = self
            .waypoint_cost_cache
            .lock()
            .expect("cost-aware waypoint cache lock should not be poisoned");
        let key = (from_cell, to_cell);
        if let Some(waypoint) = cache.get(
            key,
            self.protected_capacity,
            1,
            ProtectedOverflowPolicy::DemoteToProbation,
        ) {
            return Some(waypoint);
        }

        let portal = self.prepared.portal_between(from_cell, to_cell)?;
        let waypoint = crate::algorithms::channel_search::portal_midpoint(&portal);
        let cost_signal = segment_cost(portal.start, portal.end);
        cache.insert(
            key,
            waypoint,
            cost_signal,
            self.capacity,
            self.protected_capacity,
        );
        Some(waypoint)
    }

    fn midpoint_seed_from_cost_aware_eviction(
        &self,
        cells: &[usize],
        corridor: &crate::navmesh::corridor::NavmeshCorridor,
    ) -> Vec<Point2> {
        cells
            .windows(2)
            .enumerate()
            .map(|(index, pair)| {
                self.lookup_or_insert_waypoint(pair[0], pair[1])
                    .or_else(|| {
                        corridor.portals.get(index).copied().map(|portal| {
                            crate::algorithms::channel_search::portal_midpoint(&portal)
                        })
                    })
                    .unwrap_or(corridor.goal)
            })
            .collect()
    }
}

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

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

    /// Minimum portal segment cost required to retain a midpoint in cache.
    #[must_use]
    pub fn admission_cost_threshold(&self) -> f64 {
        self.admission_threshold
    }

    /// Total midpoint capacity before eviction.
    #[must_use]
    pub fn eviction_capacity(&self) -> usize {
        self.capacity
    }

    /// Capacity reserved for the protected segment.
    #[must_use]
    pub fn protected_segment_capacity(&self) -> usize {
        self.protected_capacity
    }

    /// Midpoints currently retained (above the admission threshold).
    #[must_use]
    pub fn retained_waypoint_count(&self) -> usize {
        self.waypoint_cost_cache
            .lock()
            .expect("fixed-threshold waypoint cache lock should not be poisoned")
            .len()
    }

    /// Midpoints currently in probation.
    #[must_use]
    pub fn retained_probation_count(&self) -> usize {
        self.waypoint_cost_cache
            .lock()
            .expect("fixed-threshold waypoint cache lock should not be poisoned")
            .probation_len()
    }

    /// Midpoints currently in the protected segment.
    #[must_use]
    pub fn retained_protected_count(&self) -> usize {
        self.waypoint_cost_cache
            .lock()
            .expect("fixed-threshold waypoint cache lock should not be poisoned")
            .protected_len()
    }

    /// Routes while applying the fixed admission-threshold cache policy.
    pub fn search(&self, query: NavmeshQuery) -> NavmeshSearchResult {
        search_with_midpoint_seed(self, query, |corridor, cells| {
            self.midpoint_seed_from_fixed_admission_threshold(cells, corridor)
        })
    }

    fn from_prepared(prepared: PreparedTRAStar, capacity: usize, admission_threshold: f64) -> Self {
        let protected_capacity = capacity / 2;
        Self {
            prepared,
            capacity,
            protected_capacity,
            admission_threshold,
            waypoint_cost_cache: std::sync::Mutex::new(WaypointCostAwareCache::default()),
        }
    }

    fn lookup_or_insert_waypoint(&self, from_cell: usize, to_cell: usize) -> Option<Point2> {
        let mut cache = self
            .waypoint_cost_cache
            .lock()
            .expect("fixed-threshold waypoint cache lock should not be poisoned");
        let key = (from_cell, to_cell);
        if let Some(waypoint) = cache.get(
            key,
            self.protected_capacity,
            1,
            ProtectedOverflowPolicy::DemoteToProbation,
        ) {
            return Some(waypoint);
        }

        let portal = self.prepared.portal_between(from_cell, to_cell)?;
        let waypoint = crate::algorithms::channel_search::portal_midpoint(&portal);
        let cost_signal = segment_cost(portal.start, portal.end);
        if cost_signal < self.admission_threshold {
            return Some(waypoint);
        }

        cache.insert(
            key,
            waypoint,
            cost_signal,
            self.capacity,
            self.protected_capacity,
        );
        Some(waypoint)
    }

    fn midpoint_seed_from_fixed_admission_threshold(
        &self,
        cells: &[usize],
        corridor: &crate::navmesh::corridor::NavmeshCorridor,
    ) -> Vec<Point2> {
        cells
            .windows(2)
            .enumerate()
            .map(|(index, pair)| {
                self.lookup_or_insert_waypoint(pair[0], pair[1])
                    .or_else(|| {
                        corridor.portals.get(index).copied().map(|portal| {
                            crate::algorithms::channel_search::portal_midpoint(&portal)
                        })
                    })
                    .unwrap_or(corridor.goal)
            })
            .collect()
    }
}

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

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

    /// Minimum portal segment cost required to retain a midpoint in cache.
    #[must_use]
    pub fn admission_cost_threshold(&self) -> f64 {
        self.admission_threshold
    }

    /// Probation hits required before promoting into the protected tier.
    #[must_use]
    pub fn promotion_hits_required(&self) -> usize {
        self.promotion_hits_required
    }

    /// Total midpoint capacity before eviction.
    #[must_use]
    pub fn eviction_capacity(&self) -> usize {
        self.capacity
    }

    /// Capacity reserved for the protected segment.
    #[must_use]
    pub fn protected_segment_capacity(&self) -> usize {
        self.protected_capacity
    }

    /// Midpoints currently retained under the promotion rule.
    #[must_use]
    pub fn retained_waypoint_count(&self) -> usize {
        self.waypoint_cost_cache
            .lock()
            .expect("fixed-promotion waypoint cache lock should not be poisoned")
            .len()
    }

    /// Midpoints currently in probation.
    #[must_use]
    pub fn retained_probation_count(&self) -> usize {
        self.waypoint_cost_cache
            .lock()
            .expect("fixed-promotion waypoint cache lock should not be poisoned")
            .probation_len()
    }

    /// Midpoints currently in the protected segment.
    #[must_use]
    pub fn retained_protected_count(&self) -> usize {
        self.waypoint_cost_cache
            .lock()
            .expect("fixed-promotion waypoint cache lock should not be poisoned")
            .protected_len()
    }

    /// Routes while applying fixed admission + multi-hit promotion.
    pub fn search(&self, query: NavmeshQuery) -> NavmeshSearchResult {
        search_with_midpoint_seed(self, query, |corridor, cells| {
            self.midpoint_seed_from_fixed_promotion_rule(cells, corridor)
        })
    }

    fn from_prepared(
        prepared: PreparedTRAStar,
        capacity: usize,
        admission_threshold: f64,
        promotion_hits_required: usize,
    ) -> Self {
        let protected_capacity = capacity / 2;
        Self {
            prepared,
            capacity,
            protected_capacity,
            admission_threshold,
            promotion_hits_required,
            waypoint_cost_cache: std::sync::Mutex::new(WaypointCostAwareCache::default()),
        }
    }

    fn lookup_or_insert_waypoint(&self, from_cell: usize, to_cell: usize) -> Option<Point2> {
        let mut cache = self
            .waypoint_cost_cache
            .lock()
            .expect("fixed-promotion waypoint cache lock should not be poisoned");
        let key = (from_cell, to_cell);
        if let Some(waypoint) = cache.get(
            key,
            self.protected_capacity,
            self.promotion_hits_required,
            ProtectedOverflowPolicy::DemoteToProbation,
        ) {
            return Some(waypoint);
        }

        let portal = self.prepared.portal_between(from_cell, to_cell)?;
        let waypoint = crate::algorithms::channel_search::portal_midpoint(&portal);
        let cost_signal = segment_cost(portal.start, portal.end);
        if cost_signal < self.admission_threshold {
            return Some(waypoint);
        }

        cache.insert(
            key,
            waypoint,
            cost_signal,
            self.capacity,
            self.protected_capacity,
        );
        Some(waypoint)
    }

    fn midpoint_seed_from_fixed_promotion_rule(
        &self,
        cells: &[usize],
        corridor: &crate::navmesh::corridor::NavmeshCorridor,
    ) -> Vec<Point2> {
        cells
            .windows(2)
            .enumerate()
            .map(|(index, pair)| {
                self.lookup_or_insert_waypoint(pair[0], pair[1])
                    .or_else(|| {
                        corridor.portals.get(index).copied().map(|portal| {
                            crate::algorithms::channel_search::portal_midpoint(&portal)
                        })
                    })
                    .unwrap_or(corridor.goal)
            })
            .collect()
    }
}

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

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

    /// Minimum portal segment cost required to retain a midpoint in cache.
    #[must_use]
    pub fn admission_cost_threshold(&self) -> f64 {
        self.admission_threshold
    }

    /// Probation hits required before promoting into the protected tier.
    #[must_use]
    pub fn promotion_hits_required(&self) -> usize {
        self.promotion_hits_required
    }

    /// Total midpoint capacity before eviction.
    #[must_use]
    pub fn eviction_capacity(&self) -> usize {
        self.capacity
    }

    /// Capacity reserved for the protected segment.
    #[must_use]
    pub fn protected_segment_capacity(&self) -> usize {
        self.protected_capacity
    }

    /// Midpoints currently retained under the demotion rule.
    #[must_use]
    pub fn retained_waypoint_count(&self) -> usize {
        self.waypoint_cost_cache
            .lock()
            .expect("fixed-demotion waypoint cache lock should not be poisoned")
            .len()
    }

    /// Midpoints currently in probation.
    #[must_use]
    pub fn retained_probation_count(&self) -> usize {
        self.waypoint_cost_cache
            .lock()
            .expect("fixed-demotion waypoint cache lock should not be poisoned")
            .probation_len()
    }

    /// Midpoints currently in the protected segment.
    #[must_use]
    pub fn retained_protected_count(&self) -> usize {
        self.waypoint_cost_cache
            .lock()
            .expect("fixed-demotion waypoint cache lock should not be poisoned")
            .protected_len()
    }

    /// Routes while applying fixed demotion on protected overflow.
    pub fn search(&self, query: NavmeshQuery) -> NavmeshSearchResult {
        search_with_midpoint_seed(self, query, |corridor, cells| {
            self.midpoint_seed_from_fixed_demotion_rule(cells, corridor)
        })
    }

    fn from_prepared(
        prepared: PreparedTRAStar,
        capacity: usize,
        admission_threshold: f64,
        promotion_hits_required: usize,
    ) -> Self {
        let protected_capacity = capacity / 2;
        Self {
            prepared,
            capacity,
            protected_capacity,
            admission_threshold,
            promotion_hits_required,
            waypoint_cost_cache: std::sync::Mutex::new(WaypointCostAwareCache::default()),
        }
    }

    fn lookup_or_insert_waypoint(&self, from_cell: usize, to_cell: usize) -> Option<Point2> {
        let mut cache = self
            .waypoint_cost_cache
            .lock()
            .expect("fixed-demotion waypoint cache lock should not be poisoned");
        let key = (from_cell, to_cell);
        if let Some(waypoint) = cache.get(
            key,
            self.protected_capacity,
            self.promotion_hits_required,
            ProtectedOverflowPolicy::EvictLeastRecentProtected,
        ) {
            return Some(waypoint);
        }

        let portal = self.prepared.portal_between(from_cell, to_cell)?;
        let waypoint = crate::algorithms::channel_search::portal_midpoint(&portal);
        let cost_signal = segment_cost(portal.start, portal.end);
        if cost_signal < self.admission_threshold {
            return Some(waypoint);
        }

        cache.insert(
            key,
            waypoint,
            cost_signal,
            self.capacity,
            self.protected_capacity,
        );
        Some(waypoint)
    }

    fn midpoint_seed_from_fixed_demotion_rule(
        &self,
        cells: &[usize],
        corridor: &crate::navmesh::corridor::NavmeshCorridor,
    ) -> Vec<Point2> {
        cells
            .windows(2)
            .enumerate()
            .map(|(index, pair)| {
                self.lookup_or_insert_waypoint(pair[0], pair[1])
                    .or_else(|| {
                        corridor.portals.get(index).copied().map(|portal| {
                            crate::algorithms::channel_search::portal_midpoint(&portal)
                        })
                    })
                    .unwrap_or(corridor.goal)
            })
            .collect()
    }
}

impl PreparedTRAStarWaypointDatabasePolicyProfile {
    /// Returns a default-profile [`TRAStarWaypointDatabasePolicyProfileBuilder`].
    #[must_use]
    pub fn builder() -> TRAStarWaypointDatabasePolicyProfileBuilder {
        TRAStarWaypointDatabasePolicyProfileBuilder::default()
    }

    /// Named policy profile bound into this prepared map.
    #[must_use]
    pub fn policy_profile(&self) -> TRAStarWaypointDatabasePolicyProfile {
        self.profile
    }

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

    /// Profile admission cost threshold (see [`TRAStarWaypointDatabasePolicyProfile`]).
    #[must_use]
    pub fn admission_cost_threshold(&self) -> f64 {
        self.waypoint_policy.admission_cost_threshold()
    }

    /// Profile promotion hit count.
    #[must_use]
    pub fn promotion_hits_required(&self) -> usize {
        self.waypoint_policy.promotion_hits_required()
    }

    /// Total midpoint capacity before eviction.
    #[must_use]
    pub fn eviction_capacity(&self) -> usize {
        self.waypoint_policy.eviction_capacity()
    }

    /// Capacity reserved for the protected segment.
    #[must_use]
    pub fn protected_segment_capacity(&self) -> usize {
        self.waypoint_policy.protected_segment_capacity()
    }

    /// Midpoints currently retained under the bound profile.
    #[must_use]
    pub fn retained_waypoint_count(&self) -> usize {
        self.waypoint_policy.retained_waypoint_count()
    }

    /// Midpoints currently in probation.
    #[must_use]
    pub fn retained_probation_count(&self) -> usize {
        self.waypoint_policy.retained_probation_count()
    }

    /// Midpoints currently in the protected segment.
    #[must_use]
    pub fn retained_protected_count(&self) -> usize {
        self.waypoint_policy.retained_protected_count()
    }

    /// Routes under the bound policy profile's midpoint cache rules.
    pub fn search(&self, query: NavmeshQuery) -> NavmeshSearchResult {
        self.waypoint_policy.search(query)
    }

    fn from_prepared(
        prepared: PreparedTRAStar,
        profile: TRAStarWaypointDatabasePolicyProfile,
    ) -> Self {
        let waypoint_policy = match profile {
            TRAStarWaypointDatabasePolicyProfile::V1 => {
                PreparedTRAStarWaypointDatabaseFixedDemotionRule::from_prepared(
                    prepared,
                    ADAPTIVE_LRU_CAPACITY,
                    profile.admission_cost_threshold(),
                    profile.promotion_hits_required(),
                )
            }
        };
        Self {
            profile,
            waypoint_policy,
        }
    }
}

impl PreparedNavmesh for PreparedTRAStarWaypointDatabaseStatic {
    fn name(&self) -> &'static str {
        "tra-star-waypoint-database-static"
    }

    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<&[crate::NavmeshPortal]> {
        self.prepared.portals_from(cell_index)
    }

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

impl PreparedNavmesh for PreparedTRAStarWaypointDatabaseLazyQuery {
    fn name(&self) -> &'static str {
        "tra-star-waypoint-database-lazy-query"
    }

    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<&[crate::NavmeshPortal]> {
        self.prepared.portals_from(cell_index)
    }

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

impl PreparedNavmesh for PreparedTRAStarWaypointDatabaseAdaptiveLru {
    fn name(&self) -> &'static str {
        "tra-star-waypoint-database-adaptive-lru"
    }

    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<&[crate::NavmeshPortal]> {
        self.prepared.portals_from(cell_index)
    }

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

impl PreparedNavmesh for PreparedTRAStarWaypointDatabaseTwoTierLru {
    fn name(&self) -> &'static str {
        "tra-star-waypoint-database-two-tier-lru"
    }

    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<&[crate::NavmeshPortal]> {
        self.prepared.portals_from(cell_index)
    }

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

impl PreparedNavmesh for PreparedTRAStarWaypointDatabaseCostAwareEviction {
    fn name(&self) -> &'static str {
        "tra-star-waypoint-database-cost-aware-eviction"
    }

    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<&[crate::NavmeshPortal]> {
        self.prepared.portals_from(cell_index)
    }

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

impl PreparedNavmesh for PreparedTRAStarWaypointDatabaseFixedAdmissionThreshold {
    fn name(&self) -> &'static str {
        "tra-star-waypoint-database-fixed-admission-threshold"
    }

    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<&[crate::NavmeshPortal]> {
        self.prepared.portals_from(cell_index)
    }

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

impl PreparedNavmesh for PreparedTRAStarWaypointDatabaseFixedPromotionRule {
    fn name(&self) -> &'static str {
        "tra-star-waypoint-database-fixed-promotion-rule"
    }

    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<&[crate::NavmeshPortal]> {
        self.prepared.portals_from(cell_index)
    }

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

impl PreparedNavmesh for PreparedTRAStarWaypointDatabaseFixedDemotionRule {
    fn name(&self) -> &'static str {
        "tra-star-waypoint-database-fixed-demotion-rule"
    }

    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<&[crate::NavmeshPortal]> {
        self.prepared.portals_from(cell_index)
    }

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

impl PreparedNavmesh for PreparedTRAStarWaypointDatabasePolicyProfile {
    fn name(&self) -> &'static str {
        self.profile.name()
    }

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

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

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

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

impl PreparedNavmesh for PreparedTRAStarPortalTransitionCache {
    fn name(&self) -> &'static str {
        "tra-star-portal-transition-cache"
    }

    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<&[crate::NavmeshPortal]> {
        self.prepared.portals_from(cell_index)
    }

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

fn search_with_midpoint_seed(
    prepared: &impl PreparedNavmesh,
    query: NavmeshQuery,
    midpoint_seed_builder: impl Fn(&crate::navmesh::corridor::NavmeshCorridor, &[usize]) -> Vec<Point2>,
) -> NavmeshSearchResult {
    let (start_cell, goal_cell) = match prepared.query(query) {
        NavmeshQueryResult::Connected {
            start_cell,
            goal_cell,
        } => (start_cell, goal_cell),
        NavmeshQueryResult::InvalidStart => {
            return Err(crate::NavmeshSearchError::InvalidStart { point: query.start });
        }
        NavmeshQueryResult::InvalidGoal => {
            return Err(crate::NavmeshSearchError::InvalidGoal { point: query.goal });
        }
        NavmeshQueryResult::NoPath { .. } => return crate::navmesh::search_not_found(0),
    };

    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,
        );
    }

    let (Some(cells), visited_nodes) =
        search_prepared_cell_corridor(prepared, start_cell, goal_cell, query.budget)?
    else {
        return crate::navmesh::search_not_found(0);
    };

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

    let midpoint_seed = midpoint_seed_builder(&corridor, &cells);
    let baseline_points =
        crate::navmesh::funnel::pull_string(prepared.navmesh(), &corridor, midpoint_seed.clone());
    if baseline_points.len() >= 2 && !prepared.navmesh().path_is_walkable(&baseline_points) {
        return crate::navmesh::search_not_found(visited_nodes);
    }

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

    let chosen_points = if refined_points.len() >= 2
        && 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,
    )
}

fn default_midpoint_seed(
    corridor: &crate::navmesh::corridor::NavmeshCorridor,
    _cells: &[usize],
) -> Vec<Point2> {
    corridor
        .portals
        .iter()
        .map(crate::algorithms::channel_search::portal_midpoint)
        .collect()
}

fn search_prepared_cell_corridor(
    prepared: &impl PreparedNavmesh,
    start_cell: usize,
    goal_cell: usize,
    budget: condor_core::SearchBudget,
) -> Result<(Option<Vec<usize>>, usize), crate::NavmeshSearchError> {
    let cell_count = prepared.navmesh().cells().len();
    if start_cell >= cell_count || goal_cell >= cell_count {
        return Ok((None, 0));
    }

    let mut seen = vec![false; cell_count];
    let mut parents = vec![None; cell_count];
    let mut frontier = std::collections::VecDeque::from([start_cell]);
    let mut visited_nodes = 0;
    let watch = condor_core::BudgetWatch::start(budget);

    seen[start_cell] = true;
    parents[start_cell] = Some(start_cell);

    while let Some(cell_index) = frontier.pop_front() {
        visited_nodes += 1;
        if cell_index == goal_cell {
            return Ok((
                reconstruct_cell_path(&parents, start_cell, goal_cell),
                visited_nodes,
            ));
        }

        watch.check(visited_nodes)?;

        let Some(prepared_neighbors) = prepared.neighbors(cell_index) else {
            continue;
        };
        let mut neighbors = prepared_neighbors.to_vec();
        neighbors.sort_unstable();

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

            seen[neighbor] = true;
            parents[neighbor] = Some(cell_index);
            frontier.push_back(neighbor);
        }
    }

    Ok((None, visited_nodes))
}

fn reconstruct_cell_path(
    parents: &[Option<usize>],
    start_cell: usize,
    goal_cell: usize,
) -> Option<Vec<usize>> {
    let mut cells = vec![goal_cell];
    let mut current = goal_cell;

    while current != start_cell {
        let parent = parents[current]?;
        cells.push(parent);
        current = parent;
    }

    cells.reverse();
    Some(cells)
}

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