Byte Engine Docs
View on docs.rs

pathfinding

Generated Rust API reference for byte_engine.

byte_engine / gameplay / pathfinding


Module pathfinding

Graph search, navigation meshes, and XZ-plane path finding.

Declare where agents walk with NavigationArea components on the world and let a Navigation system build their NavigationMesh; then call NavigationMesh::find_path on it for a string-pulled world-space path, and Navigation::steer to keep each NavigationAgent moving along it clear of the others. Build a mesh directly with NavigationMesh::from_areas or NavigationMesh::new when the polygons don't come from the world. Use a_star for one search on an arbitrary graph, and a_star_batch or a retained PathSearch when several searches share one graph, so they also share their working storage.

Contents

Quick Reference

ItemKindDescription
Navigationstruct
NavigationAgentstruct
NavigationSteeringstruct
NavigationMeshstruct
NavigationPortalstruct
PathSearchstructThe PathSearch struct retains A* working storage so repeated searches do not allocate.
TrivialGraphstructThe TrivialGraph struct provides simple edge-list storage for small or reference graphs.
BitMatrixGraphstructThe BitMatrixGraph struct provides dense graph storage with contiguous bit-packed rows.
NavigationAreaenum
NavigationMeshBuildErrorenum
NavigationPathErrorenum
StringPullErrorenum
GraphtraitThe Graph trait provides indexed nodes for path searches.
NodeIteratortrait
string_pullfn
string_pull_intofn
a_starfnFinds the lowest-cost path from start to target.
a_star_batchfnFinds a lowest-cost path for every (start, target) request on one graph.
NavigationVertexHandletype
NodeHandletype
NodeEdgetype
NAVIGATION_TOLERANCEconst

Structs

struct Navigation {
    // [REDACTED: Private Fields]
}

Defined in crates/byte-engine/src/gameplay/pathfinding/navigation.rs:124-135

The Navigation struct keeps the navigation mesh of a world's areas for the path searches that run on it, and the world's agents for finding their paths and steering them around each other.

Create it with Self::new before the areas and agents it reads, then call Self::update once per tick before the searches that should see that tick's changes. Find each agent's path with Self::find_path, then pass the velocity toward a point along it to Self::steer.

Configuration

Read from the parameters the caller routes to it, usually app.parameters().scope("navigation"):

  • debug: When true, draws the mesh's boundary, each agent's radius, and each agent's latest path in the world as debug meshes, which the application shows by registering setup_debug_mesh_render_pass first.

Implementations

  • fn new(world: &MessageScope, parameters: impl Parameters) -> Self

    Related: MessageScope

    Creates a system that builds from the navigation areas published in world from now on, set up from

    parameters, the navigation subtree of the application's.

  • fn update(&mut self, delta: MediaTime) -> Result<(), NavigationMeshBuildError>

    Related: MediaTime, NavigationMeshBuildError

    Adopts the area and agent changes published since the last update, delta ago, and rebuilds the mesh when any

    area changed.

    When the rebuild fails, the previous mesh stays and the error says which polygon was invalid.

  • fn find_path<'path>(&mut self, agent: Handle, target: Point, path: &'path mut Vec<Point>) -> Result<&'path [Point], NavigationPathError>

    Related: NavigationPathError

    Finds the route from where agent stands to target, moving both ends onto the mesh first.

    The route describes the walkable surface, so its length measures progress and arrival independently of moving

    crowds. Pass a velocity toward a point along it to Self::steer to go around other agents. Keep path between

    searches to reuse its storage. With debug drawing on, the route stays visible until the next search.

  • fn mesh(&self) -> &NavigationMesh

    Related: NavigationMesh

    Returns the mesh built at the latest update that changed an area.

  • fn steer(&mut self, agent: Handle, velocity: Vector) -> NavigationSteering

    Related: NavigationSteering

    Returns the velocity for agent to follow its route while passing crowds and staying on the mesh.

    Call after Self::update with the velocity toward the next route point at the character's gait speed, or zero

    to stand. Moving agents retain their passing side and yield speed to a slower leader or a blocked forward

    range. Standing agents get a separation velocity only when crowded. Mesh boundaries can also reduce speed.

    With root-motion clips, choose a gait at or below the result's speed, turn toward its direction at the

    character's bounded rate, then publish the root-motion transform.

Trait Implementations

impl ArchivePointee for Navigation
  • type ArchivedMetadata = ()
  • fn pointer_metadata(_: &<T as ArchivePointee>::ArchivedMetadata) -> <T as Pointee>::Metadata
impl<ST> CastableFrom for Navigation
impl Downcast for Navigation
  • fn into_any(self: Box<T>) -> Box<dyn Any>
  • fn into_any_rc(self: Rc<T>) -> Rc<dyn Any>
  • fn as_any(&self) -> &dyn Any
  • fn as_any_mut(&mut self) -> &mut dyn Any
impl DowncastSync for Navigation
  • fn into_any_arc(self: Arc<T>) -> Arc<dyn Any + Send + Sync>
impl Instrument for Navigation
impl LayoutRaw for Navigation
  • fn layout_raw(_: <T as Pointee>::Metadata) -> Result<Layout, LayoutError>
impl<T, N1> Niching for Navigation
  • unsafe fn is_niched(niched: *const NichedOption<T, N1>) -> bool
  • fn resolve_niched(out: Place<NichedOption<T, N1>>)
impl Pointee for Navigation
  • type Metadata = ()
impl Read for Navigation
impl WithSubscriber for Navigation
struct NavigationAgent {
    // [REDACTED: Private Fields]
}

Defined in crates/byte-engine/src/gameplay/pathfinding/navigation.rs:58-61

The NavigationAgent struct declares something that moves on the navigation mesh and that other agents steer around, as a world component.

Create one on the world scope with a Transform under the same handle, usually beside a character's body, and give it the character's radius. Then call Navigation::steer each tick to pick the velocity the character moves at. Publish it again under the same handle to change its precedence as the character settles or sets off.

Implementations

  • fn new(radius: f32) -> Self

    Creates an agent that occupies a circle of radius meters on XZ.

  • fn with_precedence(self, precedence: f32) -> Self

    Ranks the agent among those it meets: it steps aside only for agents of equal or greater precedence, and

    agents of less precedence step aside for it.

    Use it so a character that has settled holds its spot against one still arriving, and a player holds its

    course against every NPC. Any number does, infinities included.

Trait Implementations

impl ArchivePointee for NavigationAgent
  • type ArchivedMetadata = ()
  • fn pointer_metadata(_: &<T as ArchivePointee>::ArchivedMetadata) -> <T as Pointee>::Metadata
impl<ST> CastableFrom for NavigationAgent
impl Clone for NavigationAgent
impl Copy for NavigationAgent
impl Debug for NavigationAgent
  • fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result
impl Downcast for NavigationAgent
  • fn into_any(self: Box<T>) -> Box<dyn Any>
  • fn into_any_rc(self: Rc<T>) -> Rc<dyn Any>
  • fn as_any(&self) -> &dyn Any
  • fn as_any_mut(&mut self) -> &mut dyn Any
impl DowncastSync for NavigationAgent
  • fn into_any_arc(self: Arc<T>) -> Arc<dyn Any + Send + Sync>
impl Instrument for NavigationAgent
impl LayoutRaw for NavigationAgent
  • fn layout_raw(_: <T as Pointee>::Metadata) -> Result<Layout, LayoutError>
impl<T, N1> Niching for NavigationAgent
  • unsafe fn is_niched(niched: *const NichedOption<T, N1>) -> bool
  • fn resolve_niched(out: Place<NichedOption<T, N1>>)
impl PartialEq for NavigationAgent
impl Pointee for NavigationAgent
  • type Metadata = ()
impl Read for NavigationAgent
impl StructuralPartialEq for NavigationAgent
impl WithSubscriber for NavigationAgent
struct NavigationSteering {
    pub velocity: math::Vector,
    pub following_speed: f32,
}

Defined in crates/byte-engine/src/gameplay/pathfinding/navigation.rs:92-98

The NavigationSteering struct lets a character select a passing direction and a gait that leaves headway.

Use Self::velocity for the desired motion. A clip-driven controller can use Self::following_speed to require enough headway for a complete start and stop before it resumes following a leader.

Fields

  • velocity: math::Vector

    The desired velocity after passing, following, and boundary constraints.

  • following_speed: f32

    The leader's forward speed plus available contact clearance over two seconds, or infinity without a leader. This ceiling is independent of the requested speed, so a standing follower can check room before setting off.

Trait Implementations

impl ArchivePointee for NavigationSteering
  • type ArchivedMetadata = ()
  • fn pointer_metadata(_: &<T as ArchivePointee>::ArchivedMetadata) -> <T as Pointee>::Metadata
impl<ST> CastableFrom for NavigationSteering
impl Downcast for NavigationSteering
  • fn into_any(self: Box<T>) -> Box<dyn Any>
  • fn into_any_rc(self: Rc<T>) -> Rc<dyn Any>
  • fn as_any(&self) -> &dyn Any
  • fn as_any_mut(&mut self) -> &mut dyn Any
impl DowncastSync for NavigationSteering
  • fn into_any_arc(self: Arc<T>) -> Arc<dyn Any + Send + Sync>
impl Instrument for NavigationSteering
impl LayoutRaw for NavigationSteering
  • fn layout_raw(_: <T as Pointee>::Metadata) -> Result<Layout, LayoutError>
impl<T, N1> Niching for NavigationSteering
  • unsafe fn is_niched(niched: *const NichedOption<T, N1>) -> bool
  • fn resolve_niched(out: Place<NichedOption<T, N1>>)
impl Pointee for NavigationSteering
  • type Metadata = ()
impl Read for NavigationSteering
impl WithSubscriber for NavigationSteering
struct NavigationMesh<Space> {
    // [REDACTED: Private Fields]
}

Defined in crates/byte-engine/src/gameplay/pathfinding/navigation_mesh.rs:155-163

The NavigationMesh struct provides connected convex polygons for XZ-plane path queries.

Construct a mesh with NavigationMesh::new. Shared vertex indices define portals, so adjacent polygons must reference the same two indices along their common edge. Paths model a point-sized agent, so authored polygons must already account for required wall clearance. Call NavigationMesh::find_path next to locate endpoints, search the polygon graph, and string-pull the resulting corridor.

Implementations

  • fn from_areas(walkable: &[impl AsRef<[Point<Space>]>], obstacles: &[impl AsRef<[Point<Space>]>]) -> Result<Self, NavigationMeshBuildError>

    Related: NavigationMeshBuildError

    Builds a navigation mesh that covers the walkable polygons minus the obstacle polygons, on XZ.

    Use it when walkable surfaces and the obstacles on them are authored as separate shapes, as

    Navigation does with each NavigationArea. Every polygon must

    be convex on XZ, in either winding; polygons without area are ignored. Where walkable polygons overlap, the

    earlier one keeps the overlap, and every vertex keeps the height of the walkable polygon it came from. Obstacles

    cut at every height. Polygons that touch along an edge connect. Call Self::find_path next.

Trait Implementations

impl ArchivePointee for NavigationMesh<Space>
  • type ArchivedMetadata = ()
  • fn pointer_metadata(_: &<T as ArchivePointee>::ArchivedMetadata) -> <T as Pointee>::Metadata
impl<ST> CastableFrom for NavigationMesh<Space>
impl Downcast for NavigationMesh<Space>
  • fn into_any(self: Box<T>) -> Box<dyn Any>
  • fn into_any_rc(self: Rc<T>) -> Rc<dyn Any>
  • fn as_any(&self) -> &dyn Any
  • fn as_any_mut(&mut self) -> &mut dyn Any
impl DowncastSync for NavigationMesh<Space>
  • fn into_any_arc(self: Arc<T>) -> Arc<dyn Any + Send + Sync>
impl<Space> Graph for NavigationMesh<Space>
  • fn node_count(&self) -> usize
  • fn neighbors(&self, node: NodeHandle) -> impl Iterator<Item = NodeHandle> + '_

    Related: NodeHandle

impl Instrument for NavigationMesh<Space>
impl LayoutRaw for NavigationMesh<Space>
  • fn layout_raw(_: <T as Pointee>::Metadata) -> Result<Layout, LayoutError>
impl<T, N1> Niching for NavigationMesh<Space>
  • unsafe fn is_niched(niched: *const NichedOption<T, N1>) -> bool
  • fn resolve_niched(out: Place<NichedOption<T, N1>>)
impl Pointee for NavigationMesh<Space>
  • type Metadata = ()
impl Read for NavigationMesh<Space>
impl WithSubscriber for NavigationMesh<Space>
struct NavigationPortal<Space> {
    pub left: math::Point<Space>,
    pub right: math::Point<Space>,
}

Defined in crates/byte-engine/src/gameplay/pathfinding/navigation_mesh.rs:16-21

The NavigationPortal struct carries an oriented polygon opening through an XZ path corridor.

left and right are relative to travel through the corridor. Pass ordered portals to string_pull after adding the start and target positions separately.

Fields

  • left: math::Point<Space>

    The endpoint on the traveler's left.

  • right: math::Point<Space>

    The endpoint on the traveler's right.

Implementations

  • fn new(left: Point<Space>, right: Point<Space>) -> Self

    Creates a portal oriented relative to the path's travel direction.

Trait Implementations

impl ArchivePointee for NavigationPortal<Space>
  • type ArchivedMetadata = ()
  • fn pointer_metadata(_: &<T as ArchivePointee>::ArchivedMetadata) -> <T as Pointee>::Metadata
impl<ST> CastableFrom for NavigationPortal<Space>
impl<Space> Clone for NavigationPortal<Space>
  • fn clone(&self) -> Self
impl<Space> Copy for NavigationPortal<Space>
impl<Space> Debug for NavigationPortal<Space>
  • fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result
impl Downcast for NavigationPortal<Space>
  • fn into_any(self: Box<T>) -> Box<dyn Any>
  • fn into_any_rc(self: Rc<T>) -> Rc<dyn Any>
  • fn as_any(&self) -> &dyn Any
  • fn as_any_mut(&mut self) -> &mut dyn Any
impl DowncastSync for NavigationPortal<Space>
  • fn into_any_arc(self: Arc<T>) -> Arc<dyn Any + Send + Sync>
impl Instrument for NavigationPortal<Space>
impl LayoutRaw for NavigationPortal<Space>
  • fn layout_raw(_: <T as Pointee>::Metadata) -> Result<Layout, LayoutError>
impl<T, N1> Niching for NavigationPortal<Space>
  • unsafe fn is_niched(niched: *const NichedOption<T, N1>) -> bool
  • fn resolve_niched(out: Place<NichedOption<T, N1>>)
impl<Space> PartialEq for NavigationPortal<Space>
  • fn eq(&self, other: &Self) -> bool
impl Pointee for NavigationPortal<Space>
  • type Metadata = ()
impl Read for NavigationPortal<Space>
impl WithSubscriber for NavigationPortal<Space>

PathSearch<P>

struct PathSearch<P> {
    // [REDACTED: Private Fields]
}

Defined in crates/byte-engine/src/gameplay/pathfinding.rs:65-68

The PathSearch struct retains A* working storage so repeated searches do not allocate.

Keep one per system that searches every tick, or let a_star_batch own one for a batch. A search may run on any graph; storage grows to the largest graph seen. P is what a search carries along its route, such as the point a navigation mesh path enters each polygon at; a plain graph search carries nothing.

Implementations

  • fn new() -> Self
  • fn find_into<T>(&mut self, start: NodeHandle, target: NodeHandle, graph: &impl Graph<T>, distance: impl Fn(NodeHandle, NodeHandle) -> f32, path: &mut Vec<NodeHandle>) -> bool

    Related: NodeHandle, Graph

    Finds the lowest-cost path from start to target and writes it into path.

    path is replaced. It includes both endpoints, or is left empty when the

    target is unreachable; the return value reports reachability. See

    a_star for the distance contract.

Trait Implementations

impl ArchivePointee for PathSearch<P>
  • type ArchivedMetadata = ()
  • fn pointer_metadata(_: &<T as ArchivePointee>::ArchivedMetadata) -> <T as Pointee>::Metadata
impl<ST> CastableFrom for PathSearch<P>
impl<P> Default for PathSearch<P>
  • fn default() -> Self
impl Downcast for PathSearch<P>
  • fn into_any(self: Box<T>) -> Box<dyn Any>
  • fn into_any_rc(self: Rc<T>) -> Rc<dyn Any>
  • fn as_any(&self) -> &dyn Any
  • fn as_any_mut(&mut self) -> &mut dyn Any
impl DowncastSync for PathSearch<P>
  • fn into_any_arc(self: Arc<T>) -> Arc<dyn Any + Send + Sync>
impl Instrument for PathSearch<P>
impl LayoutRaw for PathSearch<P>
  • fn layout_raw(_: <T as Pointee>::Metadata) -> Result<Layout, LayoutError>
impl<T, N1> Niching for PathSearch<P>
  • unsafe fn is_niched(niched: *const NichedOption<T, N1>) -> bool
  • fn resolve_niched(out: Place<NichedOption<T, N1>>)
impl Pointee for PathSearch<P>
  • type Metadata = ()
impl Read for PathSearch<P>
impl<R, P> ReadPrimitive for PathSearch<P>
impl WithSubscriber for PathSearch<P>

TrivialGraph<N>

struct TrivialGraph<N> {
    // [REDACTED: Private Fields]
}

Defined in crates/byte-engine/src/gameplay/pathfinding.rs:242-245

The TrivialGraph struct provides simple edge-list storage for small or reference graphs.

Implementations

  • fn new() -> Self
  • fn push(&mut self, value: N) -> NodeHandle

    Related: NodeHandle

  • fn push_connected(&mut self, x: NodeHandle, value: N) -> NodeHandle

    Related: NodeHandle

  • fn connect(&mut self, x: NodeEdge)

    Related: NodeEdge

  • fn get(&self, node: NodeHandle) -> &N

    Related: NodeHandle

  • fn node_iterator<'a>(self: &'a Self, node: NodeHandle) -> impl NodeIterator<N> + 'a

    Related: NodeHandle, NodeIterator

Trait Implementations

impl ArchivePointee for TrivialGraph<N>
  • type ArchivedMetadata = ()
  • fn pointer_metadata(_: &<T as ArchivePointee>::ArchivedMetadata) -> <T as Pointee>::Metadata
impl<ST> CastableFrom for TrivialGraph<N>
impl Downcast for TrivialGraph<N>
  • fn into_any(self: Box<T>) -> Box<dyn Any>
  • fn into_any_rc(self: Rc<T>) -> Rc<dyn Any>
  • fn as_any(&self) -> &dyn Any
  • fn as_any_mut(&mut self) -> &mut dyn Any
impl DowncastSync for TrivialGraph<N>
  • fn into_any_arc(self: Arc<T>) -> Arc<dyn Any + Send + Sync>
impl<N> Graph for TrivialGraph<N>
  • fn node_count(&self) -> usize
  • fn neighbors(&self, node: NodeHandle) -> impl Iterator<Item = NodeHandle> + '_

    Related: NodeHandle

impl Instrument for TrivialGraph<N>
impl LayoutRaw for TrivialGraph<N>
  • fn layout_raw(_: <T as Pointee>::Metadata) -> Result<Layout, LayoutError>
impl<T, N1> Niching for TrivialGraph<N>
  • unsafe fn is_niched(niched: *const NichedOption<T, N1>) -> bool
  • fn resolve_niched(out: Place<NichedOption<T, N1>>)
impl Pointee for TrivialGraph<N>
  • type Metadata = ()
impl Read for TrivialGraph<N>
impl WithSubscriber for TrivialGraph<N>

BitMatrixGraph<N>

struct BitMatrixGraph<N> {
    // [REDACTED: Private Fields]
}

Defined in crates/byte-engine/src/gameplay/pathfinding.rs:342-347

The BitMatrixGraph struct provides dense graph storage with contiguous bit-packed rows.

Use BitMatrixGraph::with_capacity when you know the maximum node count. The fixed capacity keeps rows stable as nodes are added and lets Graph::neighbors scan each row without pointer indirection.

Implementations

  • fn with_capacity(capacity: usize) -> Self

    Creates a graph that can hold up to capacity nodes.

  • fn push(&mut self, value: N) -> NodeHandle

    Related: NodeHandle

    Adds an unconnected node and returns its handle.

  • fn push_connected(&mut self, node: NodeHandle, value: N) -> NodeHandle

    Related: NodeHandle

    Adds a node connected to node and returns its handle.

  • fn connect(&mut self, (a, b): NodeEdge)

    Related: NodeEdge

    Connects both endpoints of an undirected edge.

Trait Implementations

impl ArchivePointee for BitMatrixGraph<N>
  • type ArchivedMetadata = ()
  • fn pointer_metadata(_: &<T as ArchivePointee>::ArchivedMetadata) -> <T as Pointee>::Metadata
impl<ST> CastableFrom for BitMatrixGraph<N>
impl Downcast for BitMatrixGraph<N>
  • fn into_any(self: Box<T>) -> Box<dyn Any>
  • fn into_any_rc(self: Rc<T>) -> Rc<dyn Any>
  • fn as_any(&self) -> &dyn Any
  • fn as_any_mut(&mut self) -> &mut dyn Any
impl DowncastSync for BitMatrixGraph<N>
  • fn into_any_arc(self: Arc<T>) -> Arc<dyn Any + Send + Sync>
impl<N> Graph for BitMatrixGraph<N>
  • fn node_count(&self) -> usize
  • fn neighbors(&self, node: NodeHandle) -> impl Iterator<Item = NodeHandle> + '_

    Related: NodeHandle

impl Instrument for BitMatrixGraph<N>
impl LayoutRaw for BitMatrixGraph<N>
  • fn layout_raw(_: <T as Pointee>::Metadata) -> Result<Layout, LayoutError>
impl<T, N1> Niching for BitMatrixGraph<N>
  • unsafe fn is_niched(niched: *const NichedOption<T, N1>) -> bool
  • fn resolve_niched(out: Place<NichedOption<T, N1>>)
impl Pointee for BitMatrixGraph<N>
  • type Metadata = ()
impl Read for BitMatrixGraph<N>
impl WithSubscriber for BitMatrixGraph<N>

Enums

enum NavigationArea {
    Walkable {
        half_extents: [f32; 2],
    },
    Obstacle {
        half_extents: [f32; 2],
    },
}

Defined in crates/byte-engine/src/gameplay/pathfinding/navigation.rs:10-15

The NavigationArea enum declares where agents may walk and where they may not, as world components.

Create one on the world scope with a Transform under the same handle, usually beside the floor or wall it describes. The rectangle lies in the area's local XZ plane, centered on its origin; the transform's position and orientation place it and its scale is ignored. Navigation combines every area into its mesh.

Variants

  • Walkable

    A rectangle agents may walk on.

  • Obstacle

    A rectangle cut out of every walkable area it overlaps, at any height.

Implementations

  • fn walkable(half_x: f32, half_z: f32) -> Self

    Creates a walkable rectangle reaching half_x meters along local X and half_z along local Z from its center.

  • fn obstacle(half_x: f32, half_z: f32) -> Self

    Creates an obstacle rectangle reaching half_x meters along local X and half_z along local Z from its center.

    Agents are points to the mesh, so include the clearance they need in the extents.

Trait Implementations

impl ArchivePointee for NavigationArea
  • type ArchivedMetadata = ()
  • fn pointer_metadata(_: &<T as ArchivePointee>::ArchivedMetadata) -> <T as Pointee>::Metadata
impl<ST> CastableFrom for NavigationArea
impl Clone for NavigationArea
impl Copy for NavigationArea
impl Debug for NavigationArea
  • fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result
impl Downcast for NavigationArea
  • fn into_any(self: Box<T>) -> Box<dyn Any>
  • fn into_any_rc(self: Rc<T>) -> Rc<dyn Any>
  • fn as_any(&self) -> &dyn Any
  • fn as_any_mut(&mut self) -> &mut dyn Any
impl DowncastSync for NavigationArea
  • fn into_any_arc(self: Arc<T>) -> Arc<dyn Any + Send + Sync>
impl Instrument for NavigationArea
impl LayoutRaw for NavigationArea
  • fn layout_raw(_: <T as Pointee>::Metadata) -> Result<Layout, LayoutError>
impl<T, N1> Niching for NavigationArea
  • unsafe fn is_niched(niched: *const NichedOption<T, N1>) -> bool
  • fn resolve_niched(out: Place<NichedOption<T, N1>>)
impl PartialEq for NavigationArea
  • fn eq(&self, other: &NavigationArea) -> bool

    Related: NavigationArea

impl Pointee for NavigationArea
  • type Metadata = ()
impl Read for NavigationArea
impl StructuralPartialEq for NavigationArea
impl WithSubscriber for NavigationArea
enum NavigationMeshBuildError {
    TooManyVertices,
    TooManyPolygons,
    NonFiniteVertex {
        vertex: NavigationVertexHandle,
    },
    PolygonTooSmall {
        polygon: super::NodeHandle,
    },
    InvalidVertex {
        polygon: super::NodeHandle,
        vertex: NavigationVertexHandle,
    },
    RepeatedVertex {
        polygon: super::NodeHandle,
        vertex: NavigationVertexHandle,
    },
    DegeneratePolygon {
        polygon: super::NodeHandle,
    },
    NonConvexPolygon {
        polygon: super::NodeHandle,
    },
    NonManifoldEdge {
        first: NavigationVertexHandle,
        second: NavigationVertexHandle,
    },
    InconsistentSharedEdge {
        first: NavigationVertexHandle,
        second: NavigationVertexHandle,
    },
}

Defined in crates/byte-engine/src/gameplay/pathfinding/navigation_mesh.rs:808-841

Describes why indexed geometry could not form a navigation mesh.

Variants

  • TooManyVertices

    The vertex count exceeds the handle range.

  • TooManyPolygons

    The polygon count exceeds the handle range.

  • NonFiniteVertex

    A vertex contains NaN or infinity.

  • PolygonTooSmall

    A polygon contains fewer than three vertices.

  • InvalidVertex

    A polygon references a missing vertex.

  • RepeatedVertex

    A polygon references one vertex more than once.

  • DegeneratePolygon

    A polygon has zero projected area on XZ.

  • NonConvexPolygon

    A polygon's XZ boundary is concave or self-intersecting.

  • NonManifoldEdge

    More than two polygons share an edge.

  • InconsistentSharedEdge

    Two polygons sharing an edge have projected interiors on the same side.

Trait Implementations

impl ArchivePointee for NavigationMeshBuildError
  • type ArchivedMetadata = ()
  • fn pointer_metadata(_: &<T as ArchivePointee>::ArchivedMetadata) -> <T as Pointee>::Metadata
impl<ST> CastableFrom for NavigationMeshBuildError
impl Clone for NavigationMeshBuildError
impl Copy for NavigationMeshBuildError
impl Debug for NavigationMeshBuildError
  • fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result
impl Display for NavigationMeshBuildError
  • fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result
impl Downcast for NavigationMeshBuildError
  • fn into_any(self: Box<T>) -> Box<dyn Any>
  • fn into_any_rc(self: Rc<T>) -> Rc<dyn Any>
  • fn as_any(&self) -> &dyn Any
  • fn as_any_mut(&mut self) -> &mut dyn Any
impl DowncastSync for NavigationMeshBuildError
  • fn into_any_arc(self: Arc<T>) -> Arc<dyn Any + Send + Sync>
impl Eq for NavigationMeshBuildError
impl<K> Equivalent for NavigationMeshBuildError
  • fn equivalent(&self, key: &K) -> bool
impl Error for NavigationMeshBuildError
impl Instrument for NavigationMeshBuildError
impl LayoutRaw for NavigationMeshBuildError
  • fn layout_raw(_: <T as Pointee>::Metadata) -> Result<Layout, LayoutError>
impl<T, N1> Niching for NavigationMeshBuildError
  • unsafe fn is_niched(niched: *const NichedOption<T, N1>) -> bool
  • fn resolve_niched(out: Place<NichedOption<T, N1>>)
impl PartialEq for NavigationMeshBuildError
impl Pointee for NavigationMeshBuildError
  • type Metadata = ()
impl Read for NavigationMeshBuildError
impl StructuralPartialEq for NavigationMeshBuildError
impl ToString for NavigationMeshBuildError
  • fn to_string(&self) -> String
impl WithSubscriber for NavigationMeshBuildError
enum NavigationPathError {
    NonFiniteStart,
    NonFiniteTarget,
    StartOutsideMesh,
    TargetOutsideMesh,
    Unreachable,
}

Defined in crates/byte-engine/src/gameplay/pathfinding/navigation_mesh.rs:56-67

Describes why a navigation path could not be produced.

Variants

  • NonFiniteStart

    The start contains NaN or infinity.

  • NonFiniteTarget

    The target contains NaN or infinity.

  • StartOutsideMesh

    No polygon covers the start's XZ coordinates.

  • TargetOutsideMesh

    No polygon covers the target's XZ coordinates.

  • Unreachable

    The start and target polygons are disconnected.

Trait Implementations

impl ArchivePointee for NavigationPathError
  • type ArchivedMetadata = ()
  • fn pointer_metadata(_: &<T as ArchivePointee>::ArchivedMetadata) -> <T as Pointee>::Metadata
impl<ST> CastableFrom for NavigationPathError
impl Clone for NavigationPathError
impl Copy for NavigationPathError
impl Debug for NavigationPathError
  • fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result
impl Display for NavigationPathError
  • fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result
impl Downcast for NavigationPathError
  • fn into_any(self: Box<T>) -> Box<dyn Any>
  • fn into_any_rc(self: Rc<T>) -> Rc<dyn Any>
  • fn as_any(&self) -> &dyn Any
  • fn as_any_mut(&mut self) -> &mut dyn Any
impl DowncastSync for NavigationPathError
  • fn into_any_arc(self: Arc<T>) -> Arc<dyn Any + Send + Sync>
impl Eq for NavigationPathError
impl<K> Equivalent for NavigationPathError
  • fn equivalent(&self, key: &K) -> bool
impl Error for NavigationPathError
impl Instrument for NavigationPathError
impl LayoutRaw for NavigationPathError
  • fn layout_raw(_: <T as Pointee>::Metadata) -> Result<Layout, LayoutError>
impl<T, N1> Niching for NavigationPathError
  • unsafe fn is_niched(niched: *const NichedOption<T, N1>) -> bool
  • fn resolve_niched(out: Place<NichedOption<T, N1>>)
impl PartialEq for NavigationPathError
impl Pointee for NavigationPathError
  • type Metadata = ()
impl Read for NavigationPathError
impl StructuralPartialEq for NavigationPathError
impl ToString for NavigationPathError
  • fn to_string(&self) -> String
impl WithSubscriber for NavigationPathError

StringPullError

enum StringPullError {
    NonFiniteStart,
    NonFiniteTarget,
    NonFinitePortal {
        portal: usize,
    },
}

Defined in crates/byte-engine/src/gameplay/pathfinding/navigation_mesh.rs:93-100

Describes why a portal corridor could not be string-pulled.

Variants

  • NonFiniteStart

    The start contains NaN or infinity.

  • NonFiniteTarget

    The target contains NaN or infinity.

  • NonFinitePortal

    A portal endpoint contains NaN or infinity.

Trait Implementations

impl ArchivePointee for StringPullError
  • type ArchivedMetadata = ()
  • fn pointer_metadata(_: &<T as ArchivePointee>::ArchivedMetadata) -> <T as Pointee>::Metadata
impl<ST> CastableFrom for StringPullError
impl Clone for StringPullError
impl Copy for StringPullError
impl Debug for StringPullError
  • fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result
impl Display for StringPullError
  • fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result
impl Downcast for StringPullError
  • fn into_any(self: Box<T>) -> Box<dyn Any>
  • fn into_any_rc(self: Rc<T>) -> Rc<dyn Any>
  • fn as_any(&self) -> &dyn Any
  • fn as_any_mut(&mut self) -> &mut dyn Any
impl DowncastSync for StringPullError
  • fn into_any_arc(self: Arc<T>) -> Arc<dyn Any + Send + Sync>
impl Eq for StringPullError
impl<K> Equivalent for StringPullError
  • fn equivalent(&self, key: &K) -> bool
impl Error for StringPullError
impl Instrument for StringPullError
impl LayoutRaw for StringPullError
  • fn layout_raw(_: <T as Pointee>::Metadata) -> Result<Layout, LayoutError>
impl<T, N1> Niching for StringPullError
  • unsafe fn is_niched(niched: *const NichedOption<T, N1>) -> bool
  • fn resolve_niched(out: Place<NichedOption<T, N1>>)
impl PartialEq for StringPullError
impl Pointee for StringPullError
  • type Metadata = ()
impl Read for StringPullError
impl StructuralPartialEq for StringPullError
impl ToString for StringPullError
  • fn to_string(&self) -> String
impl WithSubscriber for StringPullError

Traits

Graph<N>

trait Graph<N> { ... }

Defined in crates/byte-engine/src/gameplay/pathfinding.rs:236-239

The Graph trait provides indexed nodes for path searches.

Required Methods

  • fn node_count(&self) -> usize
  • fn neighbors(&self, node: NodeHandle) -> impl Iterator<Item = NodeHandle> + '_

Implementors

NodeIterator<T>

trait NodeIterator<T>: Eq { ... }

Defined in crates/byte-engine/src/gameplay/pathfinding.rs:424-429

Required Methods

  • fn handle(&self) -> NodeHandle
  • fn cost(&self) -> f32
  • fn value(&self) -> &T
  • fn neighbors(&self) -> impl Iterator<Item = Self>

Functions

string_pull

fn string_pull<Space>(start: math::Point<Space>, target: math::Point<Space>, portals: &[NavigationPortal<Space>]) -> Result<Vec<math::Point<Space>>, StringPullError>

Defined in crates/byte-engine/src/gameplay/pathfinding/navigation_mesh.rs:510-518

Pulls a shortest XZ polyline taut through an ordered portal corridor.

The result includes start and target, omits redundant collinear portal points, and preserves the Y coordinate of every emitted input point. Portals must already be oriented left-to-right in the direction of travel. Use NavigationMesh::find_path when the corridor should be searched and oriented from indexed navigation geometry.

string_pull_into

fn string_pull_into<'path, Space>(start: math::Point<Space>, target: math::Point<Space>, portals: &[NavigationPortal<Space>], path: &'path mut Vec<math::Point<Space>>) -> Result<&'path [math::Point<Space>], StringPullError>

Defined in crates/byte-engine/src/gameplay/pathfinding/navigation_mesh.rs:524-545

Pulls a portal corridor while reusing path for output storage.

Existing output is cleared only after all inputs are validated. On error, path remains unchanged. Use this in repeated path queries to avoid allocating a new output vector.

a_star

fn a_star<T>(start: NodeHandle, target: NodeHandle, graph: &impl Graph<T>, distance: impl Fn(NodeHandle, NodeHandle) -> f32) -> Vec<NodeHandle>

Defined in crates/byte-engine/src/gameplay/pathfinding.rs:26-35

Finds the lowest-cost path from start to target.

distance must return a non-negative, finite edge cost for adjacent nodes and an admissible cost estimate for other node pairs. The returned path includes both endpoints, or is empty when the target is unreachable.

a_star_batch

fn a_star_batch<T>(requests: impl IntoIterator<Item = (NodeHandle, NodeHandle)>, graph: &impl Graph<T>, distance: impl Fn(NodeHandle, NodeHandle) -> f32, resolve: impl FnMut(usize, &[NodeHandle]))

Defined in crates/byte-engine/src/gameplay/pathfinding.rs:44-56

Finds a lowest-cost path for every (start, target) request on one graph.

The requests share one PathSearch, so the batch allocates its working storage once instead of once per request. resolve receives each request's index and its path in request order; the path is empty when the target is unreachable. Build the graph once before calling this so the batch also shares that cost.

Type Aliases

type NavigationVertexHandle = u32;

Defined in crates/byte-engine/src/gameplay/pathfinding/navigation_mesh.rs:4

A vertex index in a NavigationMesh.

NodeHandle

type NodeHandle = u32;

Defined in crates/byte-engine/src/gameplay/pathfinding.rs:233

NodeEdge

type NodeEdge = (NodeHandle, NodeHandle);

Defined in crates/byte-engine/src/gameplay/pathfinding.rs:422

Constants

const NAVIGATION_TOLERANCE: f32 = 0.00100000005f32;

Defined in crates/byte-engine/src/gameplay/pathfinding/navigation_mesh.rs:10

The distance in meters under which navigation geometry treats XZ points as coincident or collinear.

NavigationMesh::new counts a corner within it of the line through its neighbors as straight, and NavigationMesh::from_areas welds vertices, joins edges, and drops slivers within it.

On this page

Module pathfindingContentsQuick ReferenceStructsNavigationConfigurationImplementationsTrait Implementationsimpl ArchivePointee for Navigationimpl<ST> CastableFrom for Navigationimpl Downcast for Navigationimpl DowncastSync for Navigationimpl Instrument for Navigationimpl LayoutRaw for Navigationimpl<T, N1> Niching for Navigationimpl Pointee for Navigationimpl Read for Navigationimpl WithSubscriber for NavigationNavigationAgentImplementationsTrait Implementationsimpl ArchivePointee for NavigationAgentimpl<ST> CastableFrom for NavigationAgentimpl Clone for NavigationAgentimpl Copy for NavigationAgentimpl Debug for NavigationAgentimpl Downcast for NavigationAgentimpl DowncastSync for NavigationAgentimpl Instrument for NavigationAgentimpl LayoutRaw for NavigationAgentimpl<T, N1> Niching for NavigationAgentimpl PartialEq for NavigationAgentimpl Pointee for NavigationAgentimpl Read for NavigationAgentimpl StructuralPartialEq for NavigationAgentimpl WithSubscriber for NavigationAgentNavigationSteeringFieldsTrait Implementationsimpl ArchivePointee for NavigationSteeringimpl<ST> CastableFrom for NavigationSteeringimpl Downcast for NavigationSteeringimpl DowncastSync for NavigationSteeringimpl Instrument for NavigationSteeringimpl LayoutRaw for NavigationSteeringimpl<T, N1> Niching for NavigationSteeringimpl Pointee for NavigationSteeringimpl Read for NavigationSteeringimpl WithSubscriber for NavigationSteeringNavigationMesh<Space>ImplementationsTrait Implementationsimpl ArchivePointee for NavigationMesh<Space>impl<ST> CastableFrom for NavigationMesh<Space>impl Downcast for NavigationMesh<Space>impl DowncastSync for NavigationMesh<Space>impl<Space> Graph for NavigationMesh<Space>impl Instrument for NavigationMesh<Space>impl LayoutRaw for NavigationMesh<Space>impl<T, N1> Niching for NavigationMesh<Space>impl Pointee for NavigationMesh<Space>impl Read for NavigationMesh<Space>impl WithSubscriber for NavigationMesh<Space>NavigationPortal<Space>FieldsImplementationsTrait Implementationsimpl ArchivePointee for NavigationPortal<Space>impl<ST> CastableFrom for NavigationPortal<Space>impl<Space> Clone for NavigationPortal<Space>impl<Space> Copy for NavigationPortal<Space>impl<Space> Debug for NavigationPortal<Space>impl Downcast for NavigationPortal<Space>impl DowncastSync for NavigationPortal<Space>impl Instrument for NavigationPortal<Space>impl LayoutRaw for NavigationPortal<Space>impl<T, N1> Niching for NavigationPortal<Space>impl<Space> PartialEq for NavigationPortal<Space>impl Pointee for NavigationPortal<Space>impl Read for NavigationPortal<Space>impl WithSubscriber for NavigationPortal<Space>PathSearch<P>ImplementationsTrait Implementationsimpl ArchivePointee for PathSearch<P>impl<ST> CastableFrom for PathSearch<P>impl<P> Default for PathSearch<P>impl Downcast for PathSearch<P>impl DowncastSync for PathSearch<P>impl Instrument for PathSearch<P>impl LayoutRaw for PathSearch<P>impl<T, N1> Niching for PathSearch<P>impl Pointee for PathSearch<P>impl Read for PathSearch<P>impl<R, P> ReadPrimitive for PathSearch<P>impl WithSubscriber for PathSearch<P>TrivialGraph<N>ImplementationsTrait Implementationsimpl ArchivePointee for TrivialGraph<N>impl<ST> CastableFrom for TrivialGraph<N>impl Downcast for TrivialGraph<N>impl DowncastSync for TrivialGraph<N>impl<N> Graph for TrivialGraph<N>impl Instrument for TrivialGraph<N>impl LayoutRaw for TrivialGraph<N>impl<T, N1> Niching for TrivialGraph<N>impl Pointee for TrivialGraph<N>impl Read for TrivialGraph<N>impl WithSubscriber for TrivialGraph<N>BitMatrixGraph<N>ImplementationsTrait Implementationsimpl ArchivePointee for BitMatrixGraph<N>impl<ST> CastableFrom for BitMatrixGraph<N>impl Downcast for BitMatrixGraph<N>impl DowncastSync for BitMatrixGraph<N>impl<N> Graph for BitMatrixGraph<N>impl Instrument for BitMatrixGraph<N>impl LayoutRaw for BitMatrixGraph<N>impl<T, N1> Niching for BitMatrixGraph<N>impl Pointee for BitMatrixGraph<N>impl Read for BitMatrixGraph<N>impl WithSubscriber for BitMatrixGraph<N>EnumsNavigationAreaVariantsImplementationsTrait Implementationsimpl ArchivePointee for NavigationAreaimpl<ST> CastableFrom for NavigationAreaimpl Clone for NavigationAreaimpl Copy for NavigationAreaimpl Debug for NavigationAreaimpl Downcast for NavigationAreaimpl DowncastSync for NavigationAreaimpl Instrument for NavigationAreaimpl LayoutRaw for NavigationAreaimpl<T, N1> Niching for NavigationAreaimpl PartialEq for NavigationAreaimpl Pointee for NavigationAreaimpl Read for NavigationAreaimpl StructuralPartialEq for NavigationAreaimpl WithSubscriber for NavigationAreaNavigationMeshBuildErrorVariantsTrait Implementationsimpl ArchivePointee for NavigationMeshBuildErrorimpl<ST> CastableFrom for NavigationMeshBuildErrorimpl Clone for NavigationMeshBuildErrorimpl Copy for NavigationMeshBuildErrorimpl Debug for NavigationMeshBuildErrorimpl Display for NavigationMeshBuildErrorimpl Downcast for NavigationMeshBuildErrorimpl DowncastSync for NavigationMeshBuildErrorimpl Eq for NavigationMeshBuildErrorimpl<K> Equivalent for NavigationMeshBuildErrorimpl Error for NavigationMeshBuildErrorimpl Instrument for NavigationMeshBuildErrorimpl LayoutRaw for NavigationMeshBuildErrorimpl<T, N1> Niching for NavigationMeshBuildErrorimpl PartialEq for NavigationMeshBuildErrorimpl Pointee for NavigationMeshBuildErrorimpl Read for NavigationMeshBuildErrorimpl StructuralPartialEq for NavigationMeshBuildErrorimpl ToString for NavigationMeshBuildErrorimpl WithSubscriber for NavigationMeshBuildErrorNavigationPathErrorVariantsTrait Implementationsimpl ArchivePointee for NavigationPathErrorimpl<ST> CastableFrom for NavigationPathErrorimpl Clone for NavigationPathErrorimpl Copy for NavigationPathErrorimpl Debug for NavigationPathErrorimpl Display for NavigationPathErrorimpl Downcast for NavigationPathErrorimpl DowncastSync for NavigationPathErrorimpl Eq for NavigationPathErrorimpl<K> Equivalent for NavigationPathErrorimpl Error for NavigationPathErrorimpl Instrument for NavigationPathErrorimpl LayoutRaw for NavigationPathErrorimpl<T, N1> Niching for NavigationPathErrorimpl PartialEq for NavigationPathErrorimpl Pointee for NavigationPathErrorimpl Read for NavigationPathErrorimpl StructuralPartialEq for NavigationPathErrorimpl ToString for NavigationPathErrorimpl WithSubscriber for NavigationPathErrorStringPullErrorVariantsTrait Implementationsimpl ArchivePointee for StringPullErrorimpl<ST> CastableFrom for StringPullErrorimpl Clone for StringPullErrorimpl Copy for StringPullErrorimpl Debug for StringPullErrorimpl Display for StringPullErrorimpl Downcast for StringPullErrorimpl DowncastSync for StringPullErrorimpl Eq for StringPullErrorimpl<K> Equivalent for StringPullErrorimpl Error for StringPullErrorimpl Instrument for StringPullErrorimpl LayoutRaw for StringPullErrorimpl<T, N1> Niching for StringPullErrorimpl PartialEq for StringPullErrorimpl Pointee for StringPullErrorimpl Read for StringPullErrorimpl StructuralPartialEq for StringPullErrorimpl ToString for StringPullErrorimpl WithSubscriber for StringPullErrorTraitsGraph<N>Required MethodsImplementorsNodeIterator<T>Required MethodsFunctionsstring_pullstring_pull_intoa_stara_star_batchType AliasesNavigationVertexHandleNodeHandleNodeEdgeConstantsNAVIGATION_TOLERANCE