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
| Item | Kind | Description |
|---|---|---|
Navigation | struct | |
NavigationAgent | struct | |
NavigationSteering | struct | |
NavigationMesh | struct | |
NavigationPortal | struct | |
PathSearch | struct | The PathSearch struct retains A* working storage so repeated searches do not allocate. |
TrivialGraph | struct | The TrivialGraph struct provides simple edge-list storage for small or reference graphs. |
BitMatrixGraph | struct | The BitMatrixGraph struct provides dense graph storage with contiguous bit-packed rows. |
NavigationArea | enum | |
NavigationMeshBuildError | enum | |
NavigationPathError | enum | |
StringPullError | enum | |
Graph | trait | The Graph trait provides indexed nodes for path searches. |
NodeIterator | trait | |
string_pull | fn | |
string_pull_into | fn | |
a_star | fn | Finds the lowest-cost path from start to target. |
a_star_batch | fn | Finds a lowest-cost path for every (start, target) request on one graph. |
NavigationVertexHandle | type | |
NodeHandle | type | |
NodeEdge | type | |
NAVIGATION_TOLERANCE | const |
Structs
Navigation
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: Whentrue, 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 registeringsetup_debug_mesh_render_passfirst.
Implementations
-
fn new(world: &MessageScope, parameters: impl Parameters) -> SelfRelated:
MessageScopeCreates a system that builds from the navigation areas published in
worldfrom now on, set up fromparameters, the navigation subtree of the application's. -
fn update(&mut self, delta: MediaTime) -> Result<(), NavigationMeshBuildError>Related:
MediaTime,NavigationMeshBuildErrorAdopts the area and agent changes published since the last update,
deltaago, and rebuilds the mesh when anyarea 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:
NavigationPathErrorFinds the route from where
agentstands totarget, 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::steerto go around other agents. Keeppathbetweensearches to reuse its storage. With debug drawing on, the route stays visible until the next search.
-
fn mesh(&self) -> &NavigationMeshRelated:
NavigationMeshReturns the mesh built at the latest update that changed an area.
-
fn steer(&mut self, agent: Handle, velocity: Vector) -> NavigationSteeringRelated:
NavigationSteeringReturns the velocity for
agentto follow its route while passing crowds and staying on the mesh.Call after
Self::updatewith the velocity toward the next route point at the character's gait speed, or zeroto 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
NavigationAgent
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) -> SelfCreates an agent that occupies a circle of
radiusmeters on XZ. -
fn with_precedence(self, precedence: f32) -> SelfRanks the agent among those it meets: it steps aside only for agents of equal or greater
precedence, andagents 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
-
fn clone(&self) -> NavigationAgentRelated:
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
-
fn eq(&self, other: &NavigationAgent) -> boolRelated:
NavigationAgent
impl Pointee for NavigationAgent
-
type Metadata = ()
impl Read for NavigationAgent
impl StructuralPartialEq for NavigationAgent
impl WithSubscriber for NavigationAgent
NavigationSteering
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::VectorThe desired velocity after passing, following, and boundary constraints.
-
following_speed:f32The 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
NavigationMesh<Space>
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:
NavigationMeshBuildErrorBuilds 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
Navigationdoes with eachNavigationArea. Every polygon mustbe 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_pathnext.
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>
NavigationPortal<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>) -> SelfCreates 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>) -> boolRelated:
NodeHandle,GraphFinds the lowest-cost path from
starttotargetand writes it intopath.pathis replaced. It includes both endpoints, or is left empty when thetarget is unreachable; the return value reports reachability. See
a_starfor thedistancecontract.
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) -> NodeHandleRelated:
NodeHandle -
fn push_connected(&mut self, x: NodeHandle, value: N) -> NodeHandleRelated:
NodeHandle -
fn connect(&mut self, x: NodeEdge)Related:
NodeEdge -
fn get(&self, node: NodeHandle) -> &NRelated:
NodeHandle -
fn node_iterator<'a>(self: &'a Self, node: NodeHandle) -> impl NodeIterator<N> + 'aRelated:
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) -> SelfCreates a graph that can hold up to
capacitynodes. -
fn push(&mut self, value: N) -> NodeHandleRelated:
NodeHandleAdds an unconnected node and returns its handle.
-
fn push_connected(&mut self, node: NodeHandle, value: N) -> NodeHandleRelated:
NodeHandleAdds a node connected to
nodeand returns its handle. -
fn connect(&mut self, (a, b): NodeEdge)Related:
NodeEdgeConnects 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
NavigationArea
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
-
WalkableA rectangle agents may walk on.
-
ObstacleA rectangle cut out of every walkable area it overlaps, at any height.
Implementations
-
fn walkable(half_x: f32, half_z: f32) -> SelfCreates a walkable rectangle reaching
half_xmeters along local X andhalf_zalong local Z from its center. -
fn obstacle(half_x: f32, half_z: f32) -> SelfCreates an obstacle rectangle reaching
half_xmeters along local X andhalf_zalong 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
-
fn clone(&self) -> NavigationAreaRelated:
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) -> boolRelated:
NavigationArea
impl Pointee for NavigationArea
-
type Metadata = ()
impl Read for NavigationArea
impl StructuralPartialEq for NavigationArea
impl WithSubscriber for NavigationArea
NavigationMeshBuildError
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
-
TooManyVerticesThe vertex count exceeds the handle range.
-
TooManyPolygonsThe polygon count exceeds the handle range.
-
NonFiniteVertexA vertex contains NaN or infinity.
-
PolygonTooSmallA polygon contains fewer than three vertices.
-
InvalidVertexA polygon references a missing vertex.
-
RepeatedVertexA polygon references one vertex more than once.
-
DegeneratePolygonA polygon has zero projected area on XZ.
-
NonConvexPolygonA polygon's XZ boundary is concave or self-intersecting.
-
NonManifoldEdgeMore than two polygons share an edge.
-
InconsistentSharedEdgeTwo 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
-
fn clone(&self) -> NavigationMeshBuildErrorRelated:
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
-
fn eq(&self, other: &NavigationMeshBuildError) -> boolRelated:
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
NavigationPathError
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
-
NonFiniteStartThe start contains NaN or infinity.
-
NonFiniteTargetThe target contains NaN or infinity.
-
StartOutsideMeshNo polygon covers the start's XZ coordinates.
-
TargetOutsideMeshNo polygon covers the target's XZ coordinates.
-
UnreachableThe 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
-
fn clone(&self) -> NavigationPathErrorRelated:
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
-
fn eq(&self, other: &NavigationPathError) -> boolRelated:
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
-
NonFiniteStartThe start contains NaN or infinity.
-
NonFiniteTargetThe target contains NaN or infinity.
-
NonFinitePortalA 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
-
fn clone(&self) -> StringPullErrorRelated:
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
-
fn eq(&self, other: &StringPullError) -> boolRelated:
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
NavigationVertexHandle
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
NAVIGATION_TOLERANCE
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.