Pathfinding overview

Tuesday August 7th saw the roll-out of pathfinding across the main Second Life Server Release Channel. For those of you who may still be unaware of what pathfinding is, there is an overview on the SL wiki. However, for those wanting a shorter description, here’s how Rod Humble introduced it back in December 2011:

NPCs: coming to a region new you … ?

Because worlds feel most vibrant when they are full of life, one of our next focuses for Second Life is the ability to make high-quality “life” within it. So in 2012, we will be rolling out more advanced features that will allow the creation of artificial life and artificial people to be much smoother. 

So, simply put, pathfinding is the means by a range of automated characters – people, animals, monsters, mobile objects (“mobs”) and so on – can be created and set into motion within Second Life far easier than has previously been the case. These can then navigate their way around obstacles, follow roads, climb inclines, and so on using  specialised LSL commands and the “navmesh”.

Pathfinding has a wide variety of potential uses – as “background” in role-play sims using non-player characters (NPCs), the creation of game-play mechanics (such as the use of “food” to attract animals), and so on. Characters can be set to have certain behaviours – such as chasing you or fleeing from you, and so on.

Above: a video by “fpady”, demonstrating pathfinding using a spider which pursues an avatar

The following is designed to provide a very high-level overview of pathfinding and some of its key aspects as they are likely to impact the majority of SL users. It is not intended as an in-depth guide, and should not be used as such. Nor is it designed to be any kind of tutorial for creating pathfinding characters  nor as a tutorial. Links are given throughout (and at the end) to more comprehensive information which can be referred to for a deeper understanding of pathfinding.

Viewer Tools

Pathfinding brings with it a new set of viewer tools and panels. Fore detailed information on these tools see, Pathfinding Tools in the Viewer. The folllowing notes are for broad guidance only, and are based on accessing the tools through the official SL Viewer.

Floaters

Pathfinding has three new floaters: Linksets, Characters and View / Test, all of which are explored in a little more detail later in this article. They are accessed either via the Build menu or through the right-click context menu thus:

• The Build menu includes a new Pathfinding option, which opens a sub-menu allowing you to access any of the three new floaters
• Right clicking on an object in a pathfinding region will display a Show in Linksets option in the context menu, which will open the Linskets floater
• Right clicking on a pathfinding character will display an option to open the Characters floater

Information Panels and Address Bar Icons

Pathfinding adds a number of additional informational panels in the Build, Object Profile and Statistics floater of the viewer, as well as a new set of icons which many be displayed in the viewer’s Address Bar / SLurl Bar. Full details on these can be found in Pathfinding Tools in the Viewer, linked-to above.

Rebake Region Button

There is also a new button  – the Rebake Region button  – which may periodically appear towards of the bottom of your viewer’s window when on a region where the navmesh is being modified (see Navmesh, below).

At the time of writing, the tools are only fully available in the Beta (3.4.0.262596) and Development (3.4.1.262722) versions of the official SL Viewer, although this will obviously change as the new code is more widely adopted. Niran’s Viewer 1.48 provides the core pathfinding tools, but does not include the additional pathfinding attribute panels in the Build floater.

Navmesh

For those not familiar with the term, “navmesh” is short for navigation mesh. This is a representation of a region’s geometry generated and used by the Havok physics engine to determine paths for pathfinding characters. An overview of the navmesh is available on the SL wiki.

Every region where pathfinding is enabled has a navmesh, which is also shared with their immediate neighbours to allow cross-region pathfinding. For users not directly involved in the creation of pathfinding elements, the navmesh should be totally transparent, although the updates to the Havok physics engine required for it to work have led to a number of issues, some of which have yet to be resolved, which may have an impact on some activities in regions with pathfinding enabled (see Issues, JIRA and Bugs on the next page).

By default, the navmesh is active across an entire region (but it can be disabled if required – see Console Commands on the next page). However, parcels set to No Entry for objects  will cut the navmesh at their borders, and pathfinding characters will not be able to navigate across them (although there is a bug with this (PATH-787, which is not open to public viewing): if a parcel is set to No Entry for object and sits on the border between two pathfinding enabled sims, it is possible that characters may attempt to cross the region boundary and enter the parcel. This is currently being worked-on by LL).

Region Rebakes

The navmesh can be somewhat fluid in nature, depending upon what is going on in a region and whether anything is being changed within the region which may affect the navmesh (see Objects, the Navmesh and Optimising Performance below for an example of changing the navmesh).

Optional pop-up which may be displayed on viewers in regions where the navmesh needs to be rebaked

When a change is made that does require an update to the navmesh, a Rebake Region button will appear towards the bottom of all pathfinding-capable viewers connected to the region, together with an optional pop-up message (right).

Anyone can click the Region Rebake button in order to initiate the rebake. Once the button has been clicked, it will change its appearance as the rebake proceeds (which can take a little time, depending on the complexity of the navmesh).

The Region Rebake button: indicating a region rebake is required  (t),  and while a rebake is in progress (b)

Objects, the Navmesh and Optimising Performance

Where pathfinding is enabled, objects need to be optimised to ensure the navmesh functions correctly. This requires setting the correct attributes for each object within the region. By default, all objects within a region are set to one of two attributes: Moveable Obstacle (all non-phantom objects) and Moveable Phantom (all phantom objects). Neither of these attributes contribute to navmesh calculations.

If pathfinding is enabled, but is not being used within a region, it is possible to leave objects with these default attributes. While this may have some impact on region performance, depending upon how heavily the region is being used, it shouldn’t be something that is overly noticeable to users.

However, if pathfinding is being actively used within a region, then the objects within the region must have their attributes properly set in order for the navmesh to be properly calculated and characters can properly navigate through / around / over them. This means updating objects to one of the following four attribute types, all of which directly contribute to navmesh calculations. These are: Walkable, Static Obstacle, Material Volume, and Exclusion Volume.

All six object atributes should be used as follows :

• Walkable: all objects / surfaces pathfinding characters can move across (the terrain of a region is always set to Walkable and cannot be changed)
• Static Obstacle: any object that should block character movement and which does not move (e.g. walls, trees, fences, railings, etc.)
• Material Volume: can be used with phantom objects to alter the rate at which characters can move across a specific area (e.g. imagine a wooded area: a single Material Volume phantom prim could be used to reduce the speed characters traverse the woods, or even just the densest part of the woods)
• Exclusion Volume: can used with phantom objects to create areas where characters cannot roam
• Movable Obstacle: any object that should move (e.g. doors, gates, etc.), but which blocks pathfinding characters from moving through (so a door can still open / close, but characters will not move through it, regardless of its state)
• Movable Phantom: phantom objects that have no affect on pathfinding characters

An example of how these attributes might be used is to imagine a room where pathfinding characters are to be active:

• The floor would be set to Walkable
• The walls and furniture would set to Static Obstacle
• Doors would be set to Moveable Obstacle
• If the room included a specific area where characters were not to roam, it would be denoted using a phantom prim set to Exclusion Volume.

Note that objects set to attributes that contribute to navmesh calculations will generate a request for a region rebake in order for the navmesh to be updated. Additionally, these objects have some special restrictions applied to them:

• They cannot change their physical shape via LSL script (changing object position, shape parameters, scale, rotation, physics shape type, and linking/unlinking is generally blocked)
• They can only be physically changed via the build tool by avatars who have modify permission and are in the same region as the object (i.e. they cannot be physically changed by avatars located in a different region, nor can they be moved across region boundaries by editing them and dragging them).

 

Changing Object Attributes

Object attributes are set through the Linksets floater of the pathfinding tools, and details can be found in the Pathfinding Quick Start Guide and the Visual Guide to Pathfinding.

Setting an object’s attributes

Attributes can also be set universally for a region using the console command update-pathfinding-objects. This can be used to globally set an attribute against all unscripted or all scripted or all scripted and unscripted objects in a region. This command should be used with care, and only after the instructions have been understood, as it is theoretically possible to permanently break certain scripted objects.

The viewer pathfinding tools include a Navmesh View / Test floater. The View tab in this floater allows the navmesh and the attributes applied to objects to be easily visualised. Object attributes are colour-coded (so that Static Objects are coloured red, for example), and are independently selectable so you can view the navmesh Walkables, or the Static Objects or the Exclusion Volumes or the Material Volumes within a region, or any combination thereof. Note that objects set to Moveable Obstacle or Moveable Phantom are not visible in the navmesh view, except where the navmesh is being overlaid on the normal world view.

Visualising the navmesh: overlaid with the world view (t) and on its own, showing Walkable and Static objects (b)

Characters, LSL Functions, the Modular Pathfinding Kit and Scripts

There are a number of LSL functions linked to the creation of pathfinding characters, together with a Modular Pathfinding Kit which can be used to help with the creation of pathfinding creatures. In addition, LL have written a number of debug scripts which can be used to assist with the creation of pathfinding characters:

• llWanderWithin_debugging – for simple wandering characters
• llPatrolPoints_debugging – for characters following a set coordinate path
• llFlee_debugging – for characters that avoid avatars
• Path_update_debugging -For path_update events

When creating a character, there are a number of points to remember:

• Pathfinding does not provide a way to animate characters. Instead, existing methods to animate characters must be used. For information on animating characters, please see Animation and Animation Streamlined in the SL wiki.
• Pathfinding does enable more dynamic movement and provides a better system for controlling character movement than was previously possible.
• Characters cannot be used as attachments (so no pathfinding cat sitting on your shoulder!)
• Characters are incompatible with some features, such as keyframed motion, being phantom, size changes, and others.

The pathfinding tools within the viewer provide a Characters floater that can be used to locate characters moving throughout a region and to identify the CPU cost of characters affecting the performance of a region.

Console Commands

Pathfinding includes a number of console commands which can be used via the region debug console (CTRL+SHIFT+~ or Develop -> UI -> Region Debug Console). These are:

• update-pathfinding-objects (see Objects and the Navmesh, above)
• set dynamic_pathfinding false – will disable pathfinding for a region
• set dynamic_pathfinding true – will enable pathfinding for a region

Notes:

• These commands can only be used by estate owners / estate managers
• set dynamic_pathfinding_false and set dynamic_pathfinding true will require a region restart to takes effect
• Disabling pathfinding does not alter the physics of a region; all it does is disable the navmesh and the ability of pathfinding characters to use the region
• Once pathfinding has been disabled for a region, it will remain disabled through all subsequent server roll-outs (including those with further pathfinding updates) until actively re-enabled by the estate owner / manager, or Linden Lab explicitly override the disabled setting.

Land Impact Accounting System

Pathfinding introduces a modified land impact accounting system which changes prim accounting for legacy prims:

• All legacy-style prims have their streaming cost capped at 1.0 (except for sculpts, which will be capped at 2.0). This provides the benefit of not penalizing prim-based creators for optimizing their content by opting into the new system and will make the streaming cost more reflective of the true network cost of the objects.
• Server cost will be adjusted to MIN{ (0.5*num_prims) + (0.25 * num_scripts), num_prims }. This preserves the current value for unscripted linksets and reduce the cost for linksets containing fewer than 2*num_prims scripts. It provides the benefit of rewarding creators for reducing the number of scripts in their objects.

Issues and JIRA

There is a range of known issues and bugs around pathfinding which are still in the process of being resolved. The Release Notes highlight the following issues:

• The collision pipeline has been reorganized. This may affect avatar collisions/control, vehicle movement, and collision callbacks in LSL scripts.
• The terrain collision shape has been changed from a “heightfield” to a “mesh” to provide more efficient collisions, ray-trace, and navmesh computations.
  • This may change some collision details. In particular see the “Known Issues” list below.
  • When changing the terrain its visible appearance will update immediately, but its collision shape will not.
  • The server will wait at least 10 seconds since the last change before computing the new shape, and the computation time may take several seconds.
  • Where there is a discrepancy between visible and colliding terrain shapes object and avatar collisions may appear incorrect.

In addition, the following JIRA related to pathfinding have yet to be resolved:

• Vehicles being very iratic and jittery
• Physical Objects Fall Through Terrain Mesh
• Invalid force in llApplyRotationalImpulse bug 
• Hacked mixed volumedetect linksets become non-phantom after the region is rolled back from pathfinding to a non-pathfinding version
• llUnSit() moves avatar to incorrect position (a clamped object_position + sit_target) if object_position + sit_target is outside the sim boundaries and the sat-upon object is rotated
• Linking a flexi prim as a child of a non-flexi causes the flexi prim to go non-phantom (PATH-796 – not open to public viewing)

Resources

• SL wiki pathfinding overview
• Pathfinding Tools in the SL Viewer
• What is the NavMesh?
• Pathfinding “Quick Start” guide
• Visual Guide to Pathfinding
• LSL pathfinding functions
  
• Modular Pathfinding Kit
• Pathfinding scripts (to assist with the creation of pathfinding characters)
• Pathfinding Release Notes
• In addition, the following may be of use:
  • Animation
  • Animation Streamlined
  • Best practices for Second Life vehicle construction
  • Good Building Practices

Related Links

• Pathfinding Performance – Nalates Urriah – dealing with misconceptions about performance impacts with pathfinding)
• Pathfinding and prim accounting Nalates Urriah – coverage of the accounting changes
• llVolumeDetect(True) and Land Impact Changes – the issue that prompted further revision of land impact accounting