waymark/

lib.rs

//! Detour component for navigation mesh pathfinding
//!
//! Detour is a pathfinding component that works with navigation meshes
//! generated by Recast, or navigation meshes created by other means.

// Allow unused code in tests - test code often has intentionally unused variables
// for demonstration or future use
#![cfg_attr(test, allow(unused, unused_comparisons))]

#[cfg(feature = "serialization")]
pub mod binary_format;
pub mod bvh_tree;
pub mod detour_common;
pub mod detour_math;
pub mod dt_status;
pub mod error;
mod hierarchical_pathfinding;
pub mod nav_mesh;
mod nav_mesh_builder;
mod nav_mesh_query;
pub mod node_pool;
mod path_queue;
pub mod poly_query;
pub mod raycast_hit;
mod sliced_pathfinding;
mod status;

#[cfg(test)]
mod advanced_navigation_function_tests;
#[cfg(test)]
mod concurrency_safety_tests;
#[cfg(all(test, feature = "serialization"))]
mod cross_platform_serialization_tests;
#[cfg(test)]
mod detour_common_geometry_tests;
#[cfg(test)]
mod detour_edge_cases_tests;
#[cfg(test)]
mod detour_math_operations_tests;
#[cfg(test)]
mod detour_memory_scalability_tests;
#[cfg(test)]
mod detour_multi_tile_tests;
#[cfg(test)]
mod detour_off_mesh_connection_tests;
#[cfg(test)]
mod detour_parameter_validation_tests;
#[cfg(test)]
mod detour_query_filter_tests;
#[cfg(test)]
mod detour_raycast_comprehensive_tests;
#[cfg(test)]
mod detour_spatial_query_tests;
#[cfg(test)]
mod platform_compatibility_tests;
#[cfg(test)]
mod test_mesh_helpers;

use glam::Vec3;

pub use dt_status::{
    DtStatus, dt_status_detail, dt_status_failed, dt_status_in_progress, dt_status_succeed,
};
pub use error::DetourError;
pub use hierarchical_pathfinding::{
    Cluster, ClusterConnection, HierarchicalConfig, HierarchicalPath, HierarchicalPathfinder,
    Portal,
};
pub use nav_mesh::{
    BVNode, Link, MeshTile, NavMesh, OffMeshConnection, Poly, PolyDetail, TileHeader,
    decode_poly_ref, encode_poly_ref,
};
pub use nav_mesh_builder::{ExternalLinkRequest, NavMeshBuilder};
pub use nav_mesh_query::{MoveAlongSurfaceResult, NavMeshQuery, Node, NodeState};
pub use node_pool::{DT_NULL_IDX, DtNode, DtNodePool, DtNodeQueue, NodeFlags, NodeIndex};
pub use path_queue::{DT_PATHQ_INVALID, DtPathQueue, DtPathQueueRef};
pub use poly_query::{CollectPolysQuery, FindNearestPolyQuery, PolyQuery};
pub use raycast_hit::{RaycastHit, RaycastOptions, RaycastResult};
pub use sliced_pathfinding::{
    SlicedPathConfig, SlicedPathState, SlicedPathfindingQuery, find_path_sliced,
};
pub use status::Status;

/// External link flag - indicates a polygon edge connects to an adjacent tile
pub const DT_EXT_LINK: u16 = 0x8000;

/// Navigation mesh parameters
#[derive(Debug, Clone)]
#[non_exhaustive]
#[cfg_attr(
    feature = "serialization",
    derive(serde::Serialize, serde::Deserialize)
)]
pub struct NavMeshParams {
    /// Origin of the navigation mesh
    pub origin: [f32; 3],
    /// Tile width and height
    pub tile_width: f32,
    pub tile_height: f32,
    /// Maximum number of tiles in the mesh
    pub max_tiles: i32,
    /// Maximum number of polygons per tile
    pub max_polys_per_tile: i32,
}

/// Parameters for building navigation mesh tiles with off-mesh connections
#[derive(Debug, Clone)]
#[non_exhaustive]
#[cfg_attr(
    feature = "serialization",
    derive(serde::Serialize, serde::Deserialize)
)]
pub struct NavMeshCreateParams {
    /// Navigation mesh parameters
    pub nav_mesh_params: NavMeshParams,
    /// Vertices of the navigation mesh polygon [x,y,z,...]
    pub verts: Vec<f32>,
    /// Vertex count
    pub vert_count: i32,
    /// Polygons [first_index, index_count, ...]
    pub polys: Vec<u16>,
    /// Polygon flags
    pub poly_flags: Vec<PolyFlags>,
    /// Polygon areas
    pub poly_areas: Vec<u8>,
    /// Polygon count
    pub poly_count: i32,
    /// Max vertices per polygon
    pub nvp: i32,
    /// Detailed mesh vertices [x,y,z,...]
    pub detail_meshes: Vec<u32>,
    /// Detailed mesh vertices [x,y,z,...]
    pub detail_verts: Vec<f32>,
    /// Detail vert count
    pub detail_vert_count: i32,
    /// Detailed mesh triangles [vert0, vert1, vert2, ...]
    pub detail_tris: Vec<u8>,
    /// Detail triangle count
    pub detail_tri_count: i32,

    // Off-mesh connection parameters
    /// Off-mesh connection vertices [(ax,ay,az,bx,by,bz) * count]
    pub off_mesh_con_verts: Vec<f32>,
    /// Off-mesh connection radii
    pub off_mesh_con_rad: Vec<f32>,
    /// Off-mesh connection flags
    pub off_mesh_con_flags: Vec<PolyFlags>,
    /// Off-mesh connection area IDs
    pub off_mesh_con_areas: Vec<u8>,
    /// Off-mesh connection directions (0=bidir, 1=A->B, 2=B->A)
    pub off_mesh_con_dir: Vec<u8>,
    /// Off-mesh connection user IDs
    pub off_mesh_con_user_id: Vec<u32>,
    /// Number of off-mesh connections
    pub off_mesh_con_count: i32,

    /// Tile bounds
    pub bmin: [f32; 3],
    pub bmax: [f32; 3],
    /// Walkable height
    pub walkable_height: f32,
    /// Walkable radius
    pub walkable_radius: f32,
    /// Walkable climb
    pub walkable_climb: f32,
    /// Cell size
    pub cs: f32,
    /// Cell height
    pub ch: f32,
    /// Build BVH tree
    pub build_bv_tree: bool,
}

impl Default for NavMeshParams {
    fn default() -> Self {
        Self {
            origin: [0.0, 0.0, 0.0],
            tile_width: 0.0,
            tile_height: 0.0,
            max_tiles: 0,
            max_polys_per_tile: 0,
        }
    }
}

impl Default for NavMeshCreateParams {
    fn default() -> Self {
        Self {
            nav_mesh_params: NavMeshParams::default(),
            verts: Vec::new(),
            vert_count: 0,
            polys: Vec::new(),
            poly_flags: Vec::new(),
            poly_areas: Vec::new(),
            poly_count: 0,
            nvp: 6,
            detail_meshes: Vec::new(),
            detail_verts: Vec::new(),
            detail_vert_count: 0,
            detail_tris: Vec::new(),
            detail_tri_count: 0,
            off_mesh_con_verts: Vec::new(),
            off_mesh_con_rad: Vec::new(),
            off_mesh_con_flags: Vec::new(),
            off_mesh_con_areas: Vec::new(),
            off_mesh_con_dir: Vec::new(),
            off_mesh_con_user_id: Vec::new(),
            off_mesh_con_count: 0,
            bmin: [0.0, 0.0, 0.0],
            bmax: [0.0, 0.0, 0.0],
            walkable_height: 0.0,
            walkable_radius: 0.0,
            walkable_climb: 0.0,
            cs: 0.3,
            ch: 0.2,
            build_bv_tree: true,
        }
    }
}

impl NavMeshCreateParams {
    /// Sets the walkable height (world units).
    pub fn with_walkable_height(mut self, height: f32) -> Self {
        self.walkable_height = height;
        self
    }

    /// Sets the walkable radius (world units).
    pub fn with_walkable_radius(mut self, radius: f32) -> Self {
        self.walkable_radius = radius;
        self
    }

    /// Sets the walkable climb height (world units).
    pub fn with_walkable_climb(mut self, climb: f32) -> Self {
        self.walkable_climb = climb;
        self
    }

    /// Sets the cell size (xz-plane resolution).
    pub fn with_cell_size(mut self, cs: f32) -> Self {
        self.cs = cs;
        self
    }

    /// Sets the cell height (y-axis resolution).
    pub fn with_cell_height(mut self, ch: f32) -> Self {
        self.ch = ch;
        self
    }

    /// Sets the AABB bounds.
    pub fn with_bounds(mut self, bmin: [f32; 3], bmax: [f32; 3]) -> Self {
        self.bmin = bmin;
        self.bmax = bmax;
        self
    }

    /// Sets whether to build the BV tree for spatial queries.
    pub fn with_build_bv_tree(mut self, build: bool) -> Self {
        self.build_bv_tree = build;
        self
    }

    /// Sets the navigation mesh parameters.
    pub fn with_nav_mesh_params(mut self, params: NavMeshParams) -> Self {
        self.nav_mesh_params = params;
        self
    }

    /// Validates and returns the params.
    ///
    /// Checks that vertex/polygon counts match the corresponding data arrays
    /// and that cell dimensions are positive. Returns `Err(DetourError::InvalidParam)`
    /// on mismatch.
    pub fn build(self) -> Result<Self, DetourError> {
        self.validate()?;
        Ok(self)
    }

    /// Validates the create params without consuming them.
    pub fn validate(&self) -> Result<(), DetourError> {
        if self.cs <= 0.0 || self.ch <= 0.0 {
            return Err(DetourError::InvalidParam);
        }

        if self.vert_count > 0 && self.verts.len() != self.vert_count as usize * 3 {
            return Err(DetourError::InvalidParam);
        }

        if self.poly_count > 0 {
            let expected_poly_data = self.poly_count as usize * 2 * self.nvp as usize;
            if self.polys.len() < expected_poly_data {
                return Err(DetourError::InvalidParam);
            }
        }

        if self.detail_tri_count > 0 && self.detail_tris.len() < self.detail_tri_count as usize * 4
        {
            return Err(DetourError::InvalidParam);
        }

        if self.off_mesh_con_count > 0 {
            let n = self.off_mesh_con_count as usize;
            if self.off_mesh_con_verts.len() < n * 6 || self.off_mesh_con_rad.len() < n {
                return Err(DetourError::InvalidParam);
            }
        }

        Ok(())
    }
}

bitflags::bitflags! {
    /// Navigation mesh parameter flags
    #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
    #[cfg_attr(feature = "serialization", derive(serde::Serialize, serde::Deserialize))]
    pub struct NavMeshFlags: u16 {
        /// Enables off-mesh connections
        const OFF_MESH_CONNECTIONS = 0x01;
    }
}

/// Polygon types in the navigation mesh
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
#[cfg_attr(
    feature = "serialization",
    derive(serde::Serialize, serde::Deserialize)
)]
#[repr(u8)]
pub enum PolyType {
    /// Regular ground polygon
    Ground = 0,
    /// Off-mesh connection
    OffMeshConnection = 1,
}

bitflags::bitflags! {
    /// Flags describing polygon attributes
    #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
    #[cfg_attr(feature = "serialization", derive(serde::Serialize, serde::Deserialize))]
    pub struct PolyFlags: u16 {
        /// Polygon is walkable
        const WALK = 0x01;
        /// Polygon is swimmable
        const SWIM = 0x02;
        /// Polygon is door
        const DOOR = 0x04;
        /// Polygon is jump
        const JUMP = 0x08;
        /// Polygon is disabled
        const DISABLED = 0x10;
        /// Polygon is climbable
        const CLIMB = 0x20;
    }
}

bitflags::bitflags! {
    /// Flags describing query filter options
    #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
    #[cfg_attr(feature = "serialization", derive(serde::Serialize, serde::Deserialize))]
    pub struct QueryFilterFlags: u16 {
        /// Include polygons with `PolyFlags::WALK`
        const WALK = 0x01;
        /// Include polygons with `PolyFlags::SWIM`
        const SWIM = 0x02;
        /// Include polygons with `PolyFlags::DOOR`
        const DOOR = 0x04;
        /// Include polygons with `PolyFlags::JUMP`
        const JUMP = 0x08;
        /// Include polygons with `PolyFlags::DISABLED`
        const DISABLED = 0x10;
        /// Include polygons with `PolyFlags::CLIMB`
        const CLIMB = 0x20;
    }
}

/// Navigation mesh query filter
#[derive(Debug, Clone)]
#[cfg_attr(
    feature = "serialization",
    derive(serde::Serialize, serde::Deserialize)
)]
pub struct QueryFilter {
    /// Filter flags
    pub flags: QueryFilterFlags,
    /// Costs for different area types
    pub area_cost: [f32; 32],
    /// Include flags
    pub include_flags: PolyFlags,
    /// Exclude flags
    pub exclude_flags: PolyFlags,
}

impl Default for QueryFilter {
    fn default() -> Self {
        let mut area_cost = [1.0; 32];

        // Default costs for different areas
        // These costs can be adjusted for different movement types
        area_cost[0] = 1.0; // Walkable ground
        area_cost[1] = 2.0; // Shallow water
        area_cost[2] = 5.0; // Deep water

        Self {
            flags: QueryFilterFlags::WALK,
            area_cost,
            include_flags: PolyFlags::WALK,
            exclude_flags: PolyFlags::DISABLED,
        }
    }
}

impl QueryFilter {
    /// Checks if a polygon passes the filter
    pub fn pass_filter(
        &self,
        _poly_ref: PolyRef,
        _tile: &nav_mesh::MeshTile,
        poly: &nav_mesh::Poly,
    ) -> bool {
        // If include_flags is empty, include all polygons (unless explicitly excluded)
        let include = if self.include_flags.is_empty() {
            true
        } else {
            (poly.flags & self.include_flags) != PolyFlags::empty()
        };

        // Check if polygon has any of the exclude flags
        let exclude = (poly.flags & self.exclude_flags) != PolyFlags::empty();

        // Pass if included and not excluded
        include && !exclude
    }

    /// Gets the cost to move from one position to another
    #[allow(clippy::too_many_arguments)]
    pub fn get_cost(
        &self,
        pa: &[f32; 3],
        pb: &[f32; 3],
        _prev_ref: PolyRef,
        _prev_tile: Option<&nav_mesh::MeshTile>,
        _prev_poly: Option<&nav_mesh::Poly>,
        _cur_ref: PolyRef,
        _cur_tile: &nav_mesh::MeshTile,
        cur_poly: &nav_mesh::Poly,
        _next_ref: PolyRef,
        _next_tile: Option<&nav_mesh::MeshTile>,
        _next_poly: Option<&nav_mesh::Poly>,
    ) -> f32 {
        // Calculate distance
        let dx = pb[0] - pa[0];
        let dy = pb[1] - pa[1];
        let dz = pb[2] - pa[2];
        let dist = (dx * dx + dy * dy + dz * dz).sqrt();

        // Get area cost
        let area = cur_poly.area.min(31) as usize;

        // Return distance * area cost
        dist * self.area_cost[area]
    }
}

/// Polygon reference (unique identifier for a polygon)
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
#[cfg_attr(
    feature = "serialization",
    derive(serde::Serialize, serde::Deserialize)
)]
pub struct PolyRef(u32);

impl PolyRef {
    /// Creates a new polygon reference
    pub fn new(id: u32) -> Self {
        Self(id)
    }

    /// Returns the raw ID of the polygon reference
    pub fn id(&self) -> u32 {
        self.0
    }

    /// Checks if the polygon reference is valid
    pub fn is_valid(&self) -> bool {
        self.0 != 0
    }
}

impl From<u32> for PolyRef {
    fn from(id: u32) -> Self {
        Self(id)
    }
}

impl From<PolyRef> for u32 {
    fn from(reference: PolyRef) -> Self {
        reference.0
    }
}

/// Maximum number of vertices per navigation polygon
pub const MAX_VERTS_PER_POLY: usize = 6;

/// A path result from a pathfinding query
#[derive(Debug, Clone)]
#[cfg_attr(
    feature = "serialization",
    derive(serde::Serialize, serde::Deserialize)
)]
pub struct Path {
    /// Polygon references along the path
    pub poly_refs: Vec<PolyRef>,
    /// Waypoints along the path
    pub waypoints: Vec<Vec3>,
}

impl Default for Path {
    fn default() -> Self {
        Self::new()
    }
}

impl Path {
    /// Creates a new empty path
    pub fn new() -> Self {
        Self {
            poly_refs: Vec::new(),
            waypoints: Vec::new(),
        }
    }

    /// Returns the number of polygons in the path
    pub fn poly_count(&self) -> usize {
        self.poly_refs.len()
    }

    /// Returns the number of waypoints in the path
    pub fn waypoint_count(&self) -> usize {
        self.waypoints.len()
    }

    /// Checks if the path is empty
    pub fn is_empty(&self) -> bool {
        self.poly_refs.is_empty()
    }

    /// Clears the path
    pub fn clear(&mut self) {
        self.poly_refs.clear();
        self.waypoints.clear();
    }
}