Pathfinding

Pathfinding uses the region’s navmesh, a map of walkable surfaces built from the land and from objects marked as walkable or obstacles. Scripts can use it in two ways.

The light approach asks the navmesh for a path with llGetStaticPath and moves the object along it with keyframed motion or your own movement code. Active pathfinding turns the object into a character, a physics capsule the region steers.

Characters are limited in movement and physics, so the light approach often works better. Pathfinding is not a general game AI: for grid-based games or better paths, a script can run its own search.

Concepts

• The navmesh is built from the land and from objects, each with a pathfinding type
  • Objects take part as walkable surfaces, static obstacles, movable obstacles, exclusion volumes or material volumes
  • Read any object’s type with llGetObjectDetails
• Static paths (recommended)
  • Ask for a list of points between two positions for a character of a given size and type
  • It ignores movable obstacles and works in any region regardless of dynamic pathfinding status
  • Snap a position to the navmesh before asking for a path
  • Move along the points with keyframed motion
• Characters
  • Turn the linkset into a character, change its settings, or make it a normal object again
  • A character has a size, speed, turning and avoidance settings, and a type that affects which navmesh surfaces it prefers
• Behaviours: characters can navigate to a point, patrol, wander, pursue, evade and flee
  • Commands stop pathfinding or make the character jump
  • path_update reports progress and failures; moving_start and moving_end fire as the object starts and stops

Functions and events

list	llGetStaticPath(vector start_pos, vector end_pos, float radius, list params)
list	llGetClosestNavPoint(vector point, list options)
void	llCreateCharacter(list options)
void	llUpdateCharacter(list options)
void	llDeleteCharacter()
void	llNavigateTo(vector pos, list options)
void	llPursue(key target, list options)
void	llExecCharacterCmd(integer command, list options)
event	path_update(integer type, list reserved)

Static paths

The recommended approach: get waypoints from the static navmesh, then move with llSetKeyframedMotion or your own code.

Alternatives

For grid-based games or better paths, run your own search, such as A* over a grid, and test lines of sight with raycasts.

Scripting Details

list	llGetStaticPath(vector start_pos, vector end_pos, float radius, list params) Returns waypoints between two positions on the static navmesh for a character of the given radius; takes CHARACTER_TYPE in its params
list	llGetClosestNavPoint(vector point, list options) Returns the closest position on the navmesh to a point, or an empty list if none is found
void	llSetKeyframedMotion(list keyframes, list options) Smoothly moves a non-physical object through positions, rotations and times; use it to follow a static path
void	llCreateCharacter(list options) Converts the linkset into a pathfinding character, required to use the character functions
void	llUpdateCharacter(list options) Updates the character’s settings
void	llDeleteCharacter() Converts the linkset back to a standard physical object
void	llNavigateTo(vector pos, list options) Navigates to a position in the current or adjacent regions
void	llPatrolPoints(list patrolPoints, list options) Patrols through a list of points in order
void	llWanderWithin(vector origin, vector dist, list options) Wanders around a central point within a bounding distance
void	llPursue(key target, list options) Pursues a target, optionally intercepting it
void	llEvade(key target, list options) Evades a target, hiding from it if a hiding spot is available
void	llFleeFrom(vector position, float distance, list options) Keeps a given distance from a position
void	llExecCharacterCmd(integer command, list options) Sends a command to the pathing system; currently only stopping or jumping
event	path_update(integer type, list reserved) Triggered on changes or failures in the character’s status, such as reaching the goal
event	moving_start() Triggered when the object starts moving
event	moving_end() Triggered when the object stops moving

Additional

• llGetStaticPath — path query options (GetStaticPathParam)
  • CHARACTER_TYPE — Preferred surface type, a CharacterType such as CHARACTER_TYPE_A (humanoid) or CHARACTER_TYPE_NONE
• llGetClosestNavPoint — options (GetClosestNavPointParam)
  • GCNP_RADIUS — How far out to search for a navigation point
  • GCNP_STATIC — Use the static navmesh, ignoring dynamic obstacles
• llCreateCharacter and llUpdateCharacter — character settings (CharacterParam)
  • CHARACTER_RADIUS, CHARACTER_LENGTH — Size of the collision capsule
  • CHARACTER_ORIENTATION — Capsule orientation (CharacterOrientation)
  • CHARACTER_DESIRED_SPEED, CHARACTER_MAX_SPEED — Desired and maximum speed
  • CHARACTER_AVOIDANCE_MODE — What the character avoids (CharacterAvoidanceMode); AVOID_NONE disables avoidance
  • TRAVERSAL_TYPE — Movement traversal type (CharacterTraversalType)
  • CHARACTER_STAY_WITHIN_PARCEL — Keep the character on its starting parcel
• llExecCharacterCmd — commands (CharacterCommand)
  • CHARACTER_CMD_STOP — Stops any current pathfinding operation
  • CHARACTER_CMD_SMOOTH_STOP — Stops it in a smooth fashion
  • CHARACTER_CMD_JUMP — Jumps; the first option is a height between 0.1m and 2.0m
• llNavigateTo — FORCE_DIRECT_PATH moves in a straight line
• llPatrolPoints — PATROL_PAUSE_AT_WAYPOINTS pauses at each waypoint
• llWanderWithin — WANDER_PAUSE_AT_WAYPOINTS pauses after each waypoint
• llPursue — PURSUIT_OFFSET offsets the goal from the target; PURSUIT_INTERCEPT predicts the target’s position
• path_update — the type is a CharacterPathUpdateType
  • PU_GOAL_REACHED — The character reached its goal
  • PU_SLOWDOWN_DISTANCE_REACHED — The character is near its goal
  • PU_FAILURE_UNREACHABLE — A previously valid goal became unreachable
• llGetObjectDetails — OBJECT_PATHFINDING_TYPE returns an OPT_* value (ObjectPathfindingType)
  • OPT_CHARACTER, OPT_AVATAR — Characters and avatars
  • OPT_LEGACY_LINKSET — Movable obstacles, movable phantoms, physical and volumedetect objects
  • OPT_OTHER — Attachments, Linden trees and grass
• llGetSimStats — SIM_STAT_PCT_CHARS_STEPPED is the percentage of characters updated each frame

Constant groups

Constant groups GetStaticPathParam 1GetClosestNavPointParam 3CharacterType 5CharacterParam 14CharacterAvoidanceMode 3CharacterOrientation 2CharacterTraversalType 3CharacterNavigateParam 1CharacterPatrolPointsParam 1CharacterWanderWithinParam 1CharacterPursueParam 5CharacterCommand 3CharacterPathUpdateType 13ObjectPathfindingType 8

Alternatives

For grid-based games or better paths, a script can run its own search, such as A* over a grid, and use raycasts to test lines of sight.

list	llCastRay(vector start_pos, vector end_pos, list options)

Related

See also Category PathfindingSL Wiki PathfindingSL Wiki LSL Pathfinding TypesFeature MovementFeature AnimeshFeature MathPlanned Recipe: following a static path with keyframed motionPlanned Recipe: A* search over a grid

Related features

• Movement
• Animesh
• Physics

Categories

• Pathfinding (15)