Reply
Linden
Lorca Linden
Posts: 1

Pathfinding FAQ

We’d like to thank those of you who participated in the pathfinding beta and those who have started building pathfinding enabled objects and characters since the grid-wide release of the pathfinding server code.  We’ve been collecting questions and address many of them here. Feedback continues to be much appreciated!

Q: Will pathfinding cause massive lag on my region/parcel?
A: No. For much of the pathfinding beta, this was a valid concern for mainland regions and any region where Second Life users did not update the pathfinding properties of their linksets to make them “static” (sometimes called “permanent,” meaning that the linkset use had been set to “walkable,” “static obstacle,” “exclusion volume,” or “material phantom.”)

Updating your linksets may still improve performance and is required to get optimal behavior from pathfinding enabled creatures on your region, but the worst-case performance has now been capped in such a way that most regions will not notice a performance difference after enabling pathfinding. In a full region, no more than 4ms/frame (on average) will be spent updating the navmesh to account for “movable obstacles” (the default for existing prims) each frame.

On homesteads, this is capped at 1ms/frame. Reduced performance should only be noticeable on regions where (a) performance was already poor (i.e., spare time was less than 4ms for a full region or 1ms for a homestead), and (b) linksets have not been marked static.

Q: Will updating a build to use pathfinding be time consuming?
A: In most cases, it should be relatively straightforward to retrofit an existing build to work with pathfinding. We designed the new pathfinding “Linksets” floater to allow you to select batches of objects and update their pathfinding properties at once. We have also provided a new simulator console command (the simulator console can be accessed with ctrl+shift+` -- note that it’s a “backtick,” which is found to the left of the ‘1’ key on US keyboards), which will allow residents to set all linksets (or just those that are unscripted) on their parcel (or on a group-owned parcel) to either walkable or static obstacle.

For estate managers, this can be used to modify all linksets on the region. You do not need to have mod rights to a linkset to update its pathfinding properties. They can be changed by anyone with (a) ownership of the object, (b) mod rights to the object, or (c) ownership of the parcel or region on which the object is present. (Note that to apply changes to unowned objects for which you do not have mod rights, but which are present on your parcel, you must use the console command and not the linksets floater.)  See more details about the pathfinding bulk update tool here.  

Q: When will the pathfinding tools be released in the SL Viewer and where can I get a beta version of the viewer tools?
A: We expect to have the pathfinding tools integrated into the main viewer by the end of September!  In the meantime,  you can get access to the tools - which are very helpful to anyone looking to build or retrofit pathfinding friendly environments - by downloading the latest beta viewer here.  

Q: Will I be able to move my objects around once I’ve marked them as static?
A: If you move or alter a linkset which has been marked as static, the navmesh will be marked as “dirty” and you will be presented with a button to “rebake” it that updates it to account for your changes. Two limitations will remain: (1) you cannot modify a static linkset unless you are in the same region as its root prim, and (2) scripts in static objects will not be permitted to modify the object in a way which would dirty the navmesh (e.g., linking/delinking prims, changing the shape or transform of any prim which is not set to physics shape type “none.”) If you’re wondering how to make your house’s doors work with pathfinding, see the question below.

Q: How can I enable pathfinding on my house which has scripted doors?
A: Because of the rule that scripts on a walkable object (such as a house) are prohibited from modifying the linkset in a way which would invalidate the navmesh (e.g., by changing its physics shape to open a door), it will be necessary to build houses and similar linksets a bit differently.

Instead of having the door as part of the linkset scripted to open/close, the linkset will instead have to “rez out” the door from its inventory as a separate object. The door can then be scripted to swing/slide open or close using llSetKeyframedMotion. This will allow pathfinding objects to respond correctly to the door while avoiding the expensive process of fully recomputing the navmesh. In the near future, we plan to make examples of this type of build available along with a guide about how to easily retrofit an existing house to work with pathfinding.  

Q: Why does terrain editing behave differently now than before?
A: For performance reasons, we no longer represent the terrain as a heightfield (like a topographic map,http://en.wikipedia.org/wiki/Topographic_map) for collisions on the server. Instead, we use a “welded mesh.” Collisions are much more efficient for most terrain, but updating the mesh is much slower.

To account for this, there’s now a built-in delay of about 30 seconds after you stop editing the terrain before we begin to rebuild the mesh (which can take up to a minute or two). Until the mesh has been updated, objects and avatars will not collide with it properly and you may notice artifacts like avatars bouncing up and down when walking on the edited areas of the terrain.

Q: What are those percentages listed in the linkset floater? (Note that the majority of users will never need to worry about this advanced feature)
A: Those numbers are the walkability coefficients of the linkset for each character type. This is perhaps the most advanced, complex, and non-intuitive feature of pathfinding.

Let’s say you have a build that involves animals and human NPCs. The build consists of a network of roads and some grassland. For the most part, you’d like to keep the animals on the grass and the humans on the roads. But if a human NPC is trying to get from point A to point B and taking the road would take 100x longer (because it’s a winding road, let’s say) than just cutting across the grass, you’d like them to take the direct path across the grass. This is exactly what walkability coefficients and character types are meant to address.

To do this, you’d script your human NPCs to use CHARACTER_TYPE_A and your animals to use CHARACTER_TYPE_B. Then you would open up the linksets floater and set the walkability coefficients for the terrain to “A=1%, B=100%” meaning that pathfinding characters using CHARACTER_TYPE_A will move 100x slower on the terrain (and prefer paths that avoid the terrain unless the path is much longer), but that creatures using CHARACTER_TYPE_B will move at full speed on the terrain. Then you would select all your roads in the linksets floater and set them to “A=100%, B=0%” meaning that characters using CHARACTER_TYPE_A will move at full speed on the roads but creatures using CHARACTER_TYPE_B will avoid the roads at all costs.

Note that to handle certain inconsistencies, if a pathfinding character finds itself in an area with zero walkability for its CHARACTER_TYPE, it will move at full speed in order to be able to escape. This can happen if, for example, the character is pushed into the area by collisions or is forced into the area due to its movement properties (like turn radius).


Q: As a content creator, what character type should I make my pet (or butler or AI car)?
A: To promote interoperability between linksets and characters, we suggest the following for characters which will be sold for general use. Humans/Humanoid NPCs/Pets: CHARACTER_TYPE_A
Wild Animals/Off-Road Vehicles: CHARACTER_TYPE_B
Road-Going Vehicles: CHARACTER_TYPE_C
Other: CHARACTER_TYPE_D

Remember that the key feature is not what the character is but rather on which surfaces you want it to prefer to travel -- and how quickly it can do so. For example, while a rideable horse might be a pet, it’s probably better to treat it as a wild animal/off-road vehicle so that it doesn’t try to walk into your customers’ houses. Similarly, if you are selling prefab road pieces, you will probably want to set those to have high walkability coefficients for types A and C, and a low coefficient for type B.

Q: What can I do with the View/Test floater if I’m not using pathfinding?
A: The views available via the View/Test floater are not just useful for pathfinding. When you view walkables, static obstacles, material volumes, and exclusion volumes (but not “movable objects”), you’re getting a peek into the physics engine. This is currently the only method available in the Second Life Viewer by which Second Life users can see the real physics representations of their objects, which can be a useful tool for optimizing the physics of your region.

For instance, if you’re wondering how the simulator “sees” the vehicle or the weird sculpty lawn ornament you’re building, try temporarily making that linkset part of the navmesh, re-baking, and viewing it. We hope to turn this into more of a feature in the future.

In the meantime, there is one caveat to be aware of: the pathfinding visualization does not account for an object’s convex radius, which is an extra bit of collision tolerance used internally. On account of this, certain linksets may appear to be a bit smaller in the viewer than they are in the engine.  We have also added a handy feature within the pathfinding tools that will let you teleport directly to objects for which you have edit rights.
Hitomi Tiponi
Posts: 1,146
Topics: 9
Registered: ‎02-10-2010

Re: Pathfinding FAQ

[ Edited ]

Reply to Lorca Linden - view message

Thanks for that excellent set of FAQs Lorca - will they be added to the SL Wiki? (pretty please :smileyhappy:)


One related question that I have been asked is:

I have a House/vehicle/other thing with some movable parts but it is 'no mod' - what should I do?
I believe the answer is just to leave it as 'movable object' and that there is no, or infinitessimal slowing down of the siim caused by that.  It may seem odd to have walls of a building marked as 'movable object' but it seems to work fine.

Starlight - a brighter future for Viewer 3 and TPVs


Linden
Falcon Linden
Posts: 39

Re: Pathfinding FAQ

Reply to Hitomi Tiponi - view message

Hi Hitomi,

You're correct that if you have a no mod object with moving parts, you should leave it as a movable object. In the case of a house, depending on its construction you may be able to work around this limitation and still use pathfinding characters inside. To do so, you would create a new set of transparent floor prims that lie just above the floor of the house and set /those/ to be walkable. If the walls of the house are made of independent prims (and not, e.g., a hollowed box) then it should be possible for characters to walk around the new floors. Unfortunately, the only way to test this is to actually try it because the effect of the movable obstacle house on the navmesh won't be visible in the viewer's pathtest view.

Good luck,

Falcon

Prokofy Neva
Posts: 1,962
Topics: 52
Blog Posts: 0
Ideas: 0
Registered: ‎02-25-2009

Re: Pathfinding FAQ

[ Edited ]

Reply to Lorca Linden - view message

Throughout my entire Second Life (eight years today!) I've always heard Lindens solemnly tell me that we must Avoid Collisions. That if a sim is acting up, it's probably because we have thingsg colliding. That we should not put chickens in coops because it makes them bang again static objects as they wander and all that physics dings the sim's performance.

Always and everywhere, we try to remove colliding objects using the estate menus where you can see them -- pets, other automatic things moving. We try to keep the number of those colliding things down because they add to lag.


So now along comes this Pathfinding thing, and I have to wonder (since you didn't mention it in your essay here) what all those collisions are going to do. Here are pets that are designed to deliberately wend their way through things, and likely they're going to collide on the sides of things on their way, no?

How do you see this playing out?

*Ravenglass Rentals* ~ Low-Cost Refundable Beautiful Mainland~ +Set Home to Here!+ http://bit.ly/6twVeI
Resident
Frionil Fang
Posts: 1

one unanswered question

Reply to Lorca Linden - view message

I have trouble explaining this to the owners of a region I and my group are renting from.

Nothing about pathfinding requires deleting everything and rerezzing it, right?

There are some lag issues on the Sim, which someone has told the managers is because of pathfinding and everything below 300 meters must be removed and rebuilt to "fix" things. No amount of convincing or linking to faqs helps, as they said a Linden told them, one which I haven't been able to contact through them.

Nothing in the pf docs suggests this (nor the magic number 300), as far as I can tell, and the way I figured it, it's enough to set stuff to static obstacle mode to optimize pf performance.

I'm trying to save everyone on the Sim from a lot of trouble rebuilding everything including myself, so who is in the right here? I suspect this is all a misunderstanding, or then I'm horribly mistaken.
.
Thanks.
Contributor
Freya Mokusei
Posts: 2,023

Re: one unanswered question

Reply to Frionil Fang - view message

You're right. Deleting/re-rezzing won't help anything at all. Ever.

300m isn't a limitation that applies to Pathfinding, since physics runs up until 4096m. So far as I can recall nothing uses this value (the closest is the 'map image' which is taken at a view of approximately 350m), so it is an easy way to prove the information is junk.

The only thing they MAY HAVE meant is that it can be necessary to rename objects from 'Object' to something more useful, if setting up Pathfinding on your parcel.

The NavMesh can be recalculated without needing to re-rez anything.

Good luck.

Honored Resident
Starlight Harbour
Posts: 6

Getting realistic motion for a humanoid

Reply to Freya Mokusei - view message

I"m new at Pathfinding tools but familiar with scripting and physics.  I'm having trouble getting my pathfinding object to not behave like a bug,  sort of sniffing around, turning in full circles occasionally,  and in general acting as if it's not sure where it' going,  even when it IS assigned a target.

I've tried just going to a single distant point,   tried solving in advance for the path and then trying to walk the path one step at a time,   changing various speed and acceleration parameters, and it still behaves like a bug.


I'm not talking animation of the legs.  I just want the center-of-mass to move in a smooth, sensible, flowing manner.


Ideas?


thank you.

 

Linden
Falcon Linden
Posts: 39

Re: Pathfinding FAQ

Reply to Prokofy Neva - view message


Prokofy Neva wrote:

Throughout my entire Second Life (eight years today!) I've always heard Lindens solemnly tell me that we must Avoid Collisions. That if a sim is acting up, it's probably because we have thingsg colliding. That we should not put chickens in coops because it makes them bang again static objects as they wander and all that physics dings the sim's performance.

Always and everywhere, we try to remove colliding objects using the estate menus where you can see them -- pets, other automatic things moving. We try to keep the number of those colliding things down because they add to lag.


So now along comes this Pathfinding thing, and I have to wonder (since you didn't mention it in your essay here) what all those collisions are going to do. Here are pets that are designed to deliberately wend their way through things, and likely they're going to collide on the sides of things on their way, no?

How do you see this playing out?


Hi Prokofy,

One of the primary purposes of pathfinding was to provide a method for moving characters through the world that would be low-impact in terms of the physics system. Pathfinding characters use a map of the region (the navmesh) and predictive algorithms to avoid collisions wherever possible. This allows them to generally keep their collisions limited to the ground. I.e., no, pathfinding characters are not likely to collide on the sides of things. At the same time, all characters are represented by a special physics shape (a capsule, like a medicinal gelcap--a cylinder with hemispherical endcaps) for which particularly efficient collision calculations are possible. For pathfinding characters, the worst case collisions performance is generally caused by situations where many characters are confined to a small space and are continuously forced to bump one another in order to reach their goal.

The chickens you mention were non-performant because (a) their shapes were complex and (b) they navigated in large part by bumping into things. Keeping them in a coup only made matters worse as you were confining many of them to one small area leading them to collide not only with each other but with the walls.

Falcon

Linden
Falcon Linden
Posts: 39

Re: one unanswered question

Reply to Frionil Fang - view message

Hi Frionil,

 

Freya is correct. There is absolutely no need to delete and re-rez your objects. You are correct in that setting your objects to 'static obstacle' should eliminate the vast majority of pathfinding-related computations (assuming that there are no characters around). If you provide the name of your region, we may be able to investigate the cause of your performance issues. 

 

Falcon

Prokofy Neva
Posts: 1,962
Topics: 52
Blog Posts: 0
Ideas: 0
Registered: ‎02-25-2009

Re: Pathfinding FAQ

[ Edited ]

Reply to Falcon Linden - view message

Do not dis my chickens as "nonperformant," Falcon.


My chickens are not "nonperformant".

 

They don't navigate by bumping into things unless people get in their way.


Your little pathfinding beasties cannot hold a candle to my chickens.


My chickens will fight your pathfinders any day of the week. My sim or yours.

 

 

*Ravenglass Rentals* ~ Low-Cost Refundable Beautiful Mainland~ +Set Home to Here!+ http://bit.ly/6twVeI