Byte Engine Docs

Navigation

Look up navigation areas, route and steering results, and navigation mesh tolerances and limits.

Navigation describes where agents can walk. An application creates navigation areas on the world scope and places them with transforms. The navigation system combines them into one navigation mesh that path searches run on. The message model it builds on is in World and messages.

Areas

KindEffect
WalkableAdds its rectangle to the navigable surface.
ObstacleRemoves its rectangle from every walkable area it overlaps, at any height.
PropertyDefaultUnitNotes
Half extentsRequiredMeters, area spaceHalf the rectangle's size along local X and local Z. Both must be finite and greater than zero.

An area's rectangle lies in its local XZ plane, centered on its origin. Its transform's position and orientation place the rectangle in the world, and its scale is ignored. An area without a transform isn't part of the mesh.

Building the mesh

RuleBehavior
SurfaceThe mesh covers the union of every walkable rectangle minus the union of every obstacle rectangle, both projected onto XZ.
OverlapWhere walkable areas overlap on XZ, the area created first keeps the overlap.
HeightEach mesh vertex keeps the height of the walkable rectangle it lies on. Where vertices of rectangles at different heights merge, the rectangle created first sets the height. Obstacles have no height.
PolygonsThe mesh is a set of convex polygons. Polygons that share an edge share both of its vertices, so an agent can cross from one to the other.
SeamsWalkable areas whose edges touch or overlap on XZ connect along the shared part of the edge.
ClearanceThe mesh models a point-sized agent. Size obstacles to include the clearance agents need.
EmptyNo walkable area gives an empty mesh, which contains no point.

Updating the mesh

RuleBehavior
CreatePublish the area through the world scope's factory. Publishing again under the same handle replaces it.
PlaceSend a transformation update for the handle. A later update moves the area.
DeleteDelete the handle. The area leaves the mesh.
RebuildEach navigation update adopts the area changes published since the last one and rebuilds the whole mesh when any area changed. An update without changes keeps the mesh. Agents moving never rebuild it.

Create the navigation system before the areas it builds from, and update it before the path searches that should see a step's changes.

Queries

QueryResult
PathThe corners from a start to a target, both included, that a point-sized agent follows through the mesh. Two points that see each other across the mesh get their straight line, however the mesh is split between them. Fails when either end isn't on the mesh or no polygons connect them.
Closest pointA point the mesh covers, moved onto the mesh's surface. Any other point moves to the nearest point of the mesh's boundary on XZ, at the boundary's height. An empty mesh has no closest point.
Closest boundary pointThe point of the mesh's boundary closest on XZ to a point, on or off the mesh. An empty mesh has none.

Agents

An agent is something that moves on the mesh and that other agents steer around, such as a character.

PropertyDefaultUnitNotes
RadiusRequiredMetersThe circle on XZ the agent occupies. Finite and greater than zero.
Precedence0Who holds their course when two agents meet: an agent steps aside only for agents of equal or greater precedence. Any number, infinities included.
RuleBehavior
CreatePublish the agent through the world scope's factory. Publishing again under the same handle replaces its radius.
PlaceSend a transformation update for the handle. The agent is at the transform's position. An agent without a transform doesn't take part in steering.
VelocityThe agent's displacement per second, averaged over about a quarter of a second. Each navigation update moves it toward the displacement since the previous update over the time between them, by one minus e to the power of minus that time over 0.25 s. An agent that stops moving slows to zero this way.
DeleteDelete the handle. Other agents stop steering around it.

Steering

Steering selects a passing direction for a moving agent or a separation velocity for a standing agent. Routes describe the walkable surface independently of other agents. Their length excludes local passes around other agents.

InputMeaning
AgentThe agent that steers. Its radius sizes contacts with other agents. An agent without a transform gets its input velocity unchanged.
VelocityThe desired velocity on XZ at the agent's gait speed. Zero means standing still.
RuleResult
PrecedenceAn agent yields only to others of equal or greater precedence.
Contact distanceThe sum of both radii plus 0.15 m of comfort distance.
PredictionEach other agent moves at its velocity for the time needed to reach its current position at the requested speed, up to 2 s.
Blocked directionsThe headings that intersect another agent's predicted contact circle within the prediction distance. Overlapping angular intervals form one blocked range.
Passing directionAn endpoint of the blocked range containing the desired heading. A gap wide enough for the agent remains available. Passing keeps the requested speed unless a leader or boundary limits it.
Passing sideThe endpoint nearest the current heading, or the desired heading while still, with the clockwise side for equal angles. The side holds while the endpoint's agent remains in the blocked range or ahead through a clear range. If the side's one-second travel, limited to 1 m, ends outside the mesh, the other side is used when it ends on the mesh.
FollowingAnother agent ahead within contact width, travelling within about 37 degrees of the desired heading and faster than 0.2 m/s, is a leader. The speed ceiling is its forward speed plus the gap between contact circles divided by 2 s, at least zero. A follower yields speed instead of passing that leader.
No forward passWhen the chosen endpoint turns at least 90 degrees away from the desired heading, the result is zero, so followers wait instead of reversing into the line behind them.
StandingThe sum of velocities away from current overlaps, each of the overlap depth divided by 0.25 s. A coincident pair separates toward positive X. Standing agents don't anticipate future crossings.

The mesh boundary constrains the resulting velocity:

RuleResult
On the meshThe component toward the closest boundary point is limited to the distance to that point over 0.5 s.
Off the meshThe component away from the closest boundary point is removed. Components toward or along it remain.

The result carries a desired velocity and a following speed ceiling. The following ceiling isn't limited by the requested speed and is infinity without a leader.

The result is a desired velocity. A character with limited turning or root motion may follow it at a different velocity. Steering doesn't guarantee collision-free motion for such a character.

Debug drawing

With the navigation.debug parameter set to true, the navigation system draws the mesh's boundary, each agent's radius as a circle where it stands, and each agent's latest path in the world as debug meshes, 5 cm above the surface, moving the circle with the agent, replacing the path at the agent's next search, and removing both when the agent is deleted. The application shows them by registering the debug mesh render pass.

Tolerances

ToleranceValueRule
Coincident vertices1 mmVertices closer than this on XZ merge into one.
On the mesh1 mmA point within this of a polygon's edge counts as on the polygon, so a point put on the boundary by rounding is on the mesh.
Straight corners1 mmA polygon corner closer than this to the line through its neighbors counts as straight.
Slivers1 mmParts of a walkable area thinner than this are dropped.

Limits

LimitValue
Area shapeRectangles
LevelsOne: obstacles cut walkable areas at every height
Vertices and polygonsFewer than 2^32 each

Rust API

On this page