Second Life Pathfinding Performance

I’m seeing a load of misinformation on Pathfinding performance. Back in May I wrote an article getting into Pathfinding (PF) performance. See: #SL Pathfinding Update Week 20. Scroll down and read the section on The Size of the Problem.

Navmesh w/X-Ray Enabled

PF has several different aspects. One could break it into two main parts. One is the part where PF figures out where everything is in the region and how to treat it, as what are obstacles and where are the paths. This is a slow and calculation intense process. But, it really only has to run at region start up, when a region’s ground topology changes, or things are built on the ground. It is sort of an initialization process.

Another part is when PF has to find what has moved, like a door opening. Things like a door that cut across paths are called cuts. PF has to find things that move and ‘cut’ the Navigation Mesh mostly referred to as Navmesh. The cut calc’s are very fast. They only need to revise the previously calculated Navmesh.

The Navmesh initial calcs take time measured in tens of seconds. Recalculations of the Navmesh are minimized as much as possible. But they at least run in a separate server thread. This prevents the region and other regions in the simulator from freezing until the calc is completed.

With region idle there are more CPU cycles available for PF calcs. If you are thinking what happens at grid wide roll outs, consider that a server is brought up with the new software and then regions are moved into it. Most of these regions will quickly drop into Idle Mode as no one is in them. So, the initialization of PF should happen pretty quickly and likely before most people return to the region.

The cut calcs are fast but they are capped at 4ms. This is 4ms of script frame time, which is 22ms for a region running at full speed 22ms or 45 FPS. (4/22=18% and seems huge huh?)

The thing is the 4ms can only be taken from free script time. If the region is overloaded and lagging the PF calcs for new cuts will never run. So, opening a door will not register on PF and the Navmesh will get out of date. PF characters will not go through the open door. If it it is recently closed, they won’t notice the closing and will pass through it. The result is the rest of the region having priority will run at pre-PF speeds. It is PF that will degrade not the region.

The character updates are handled very much like path cuts. The time they can use is also capped. Somewhere in my Pathfinding articles is the time required to handle character updates. While we measure time for most things in SL in milliseconds character updates are measured in microseconds. As the caps are hit we’ll see PF characters slowing down. Again they slow down before the rest of the region does.

Summary

In early May I was worried about PF performance and what the system was going to do to non-optimized regions. I took some heat for that. The Lindens corrected every concern I had… or maybe they just started explaining what they were doing better and I had misunderstood.

Whatever the case I doubt those turning off PF for performance reasons can  measure the difference in region performance.

The regions with the Debug versions of PF will tend to run slower, because of the debug code. I doubt any such versions are running on the main grid. But, most of the previous versions were likely to have debug code, so be careful comparing past performance with current performance.

Scroll down to see Lorca Linden’s comment.

25 thoughts on “Second Life Pathfinding Performance

  1. Thanks, Nalates. I’m still a bit confused (as I think may be others) by the second sentence in the Pathfinding Quick Start Guide : “You will need to use the linkset tools to change the pathfinding attributes of the objects on your region to improve region performance!

    Does that, in fact, mean something like “you will need to change the pathfinding attributes .. to improve the performance of pathfinding in your region”? Because that’s not how it reads to me.

    And my concerns about the effect of pathfinding objects colliding with unoptimised objects, or trying to calculate a path round them, were not to do not with script time, but with the effect on the physics engine having to handle all this. Am I mistaken there?

    • Part of the problem is the wiki is a mix of current and out-of-date content.

      If I understand correctly, the Havok PF tools are only needed to edit LINKSETS which in some cases seems to be a word interchanged with Navmesh in the PF context. Individual prims can be edited by any one with build rights. If they have a viewer updated with at least the non-Havok PF Tools, they can trigger the update of the PF Navmesh. (I think that includes prim linksets) It gets confusing and I too am a mix of up-to-date and out-of-date.

      PF characters only collide with objects added to the Navmesh or cut list… the Navmesh initialization takes into account pretty much everything in the region near the terrain. Anything not scripted is added to the Navmesh as a static object, I think I have that right. Anything that is scripted is added to the cut list (Navmesh dynamic) and checked to see if it has moved. But the amount of checking time is capped. So, most everything is ‘DEFAULT OPTIMIZED’. You can improve the optimizing by designating something like a scripted vending machine that does not move as STATIC.

      Falon and Lorca Linden feel the amount of region performance that can be improved by making additional optimizations will be small. They tried to get the majority of things found in a region handled automatically. It will take some time to know how well they did. The Lindens are hoping PF performance will be a non-issue.

      • Thanks again, Nalates. I’m glad I’m not the only one who finds the material in the wiki profoundly confusing!

        I can understand perfectly well most of the information there about optimising the physics shapes of potential obstacles to pathfinding objects and why I might need to do it, but the stuff about scripted objects and movable or static obstacles has me completely confused. If, as what you say seems to suggest, it doesn’t, in fact, make a huge amount of difference if the sim thinks vending machines or furniture might start moving around, then I’m not too worried.

        I’m still a bit confused about scripted doors that are part of linkset; I think that’s only an issue if pathfinding objects need to know if doors are actually open or closed, but I’m not certain.

        I have to say, I think LL were unfair in blaming your tsunami comments for any confusion about pathfinding. What I take away from LL’s published advice about how I will need to use the pathfinding tools to change the pathfinding attributes of the objects in my region (regions, in fact) to improve region performance is that, until I can make time to do that, it’s prudent to keep pathfinding turned off.

        I think, from what you say, I’m probably being over-cautious. It looks as if leaving pathfinding turned on, without having optimised anything, won’t make any difference at all unless someone starts introducing pathfinding objects into the region and, even then, it shouldn’t make enough difference to worry me. But if that’s what LL mean, I wish they would say that.

        As it is, the effect of what we’ve been told officially has been to make a lot of people, including me, turn off pathfinding, and a considerable number (not including me) to say, in effect, “it all looks like a lot of work, so it can stay off and if my tenants want to have pathfinding objects they’ll have to move,” which can’t be what LL intended.

        • I do think LINKSET in this context is confusing. The recommendation is that doors not be part of the building’s linkset. You have probably already found that separating the doors from the building can reduce your Land Impact cost. The separate door can then be a dynamic item in the Navmesh. The building can be made STATIC and dropped out of the path cutting calcs.

          As the Lindens blaming me… some of them are short sighted and others something less than completely informed. So, I suspect some may. But, Hamlet’s and my posts got them talking and explaining in ways they had not before the tsunami warning. In general the Lindens I deal with understand where I’m coming from and are pretty good people.

          As fun NPC’s come out and pets using PF proliferate I think most region owners will be pressed into enabling PF. There are just too many fun possibilities.

          • i’m really confusing with linkset also and one of your sentence in make me more confuse : “The recommendation is that doors not be part of the building’s linkset.” I do have my doors of my home linked to the whole house how i have to set such objects on pathfinding region, if you know ? precision is i do not have any estate right over the sim just renter of a home parcel over the sim either not have modify right on the house object. thanks for the great post it’s make it a bit cleaver than others i found on the net. and in real case try of explain. i thinks adding to confuse this feature is over all people not understand and don’t want to/need technicals thinking.It’s implicated. They just want use things not want to know how is made… 🙂

            • Doors would be set to Movable Obstacles. All objects are Movable Obstacles by default. If you rez a cube it is a movable obstacle.

              Everyone that can rez items can set their Navmesh ‘Link Use’ or type. You do not have to have land ownership, just build permission. The problem in rental areas is when buildings are owned by the Land Lord. You have to get them to make changes. Fortunately the changes are mostly unnecessary. Only when you plan to have a high number of PF Characters does it start to matter.

              Thanks for the kind words.

  2. I get the impression the Phoenix/ Firrestorm blog on the matter of performance started a panic. The wording was certainly not the best (particularly as they has a quote in full from LL on another page). I’m not saying it caused the problem – but it seems to have added a lot of fuel to the fire (particularly stating unoptimised regions could take a performance hit of “18%”.

    Talking to LL myself, I get the impression that while performance may be impacted, it’s not something that would actually be overtly noticeable by users (and have said so myself in my own overview post on pathfinding (which I admit avoided delving into technicalities, as I wanted to cover the general concepts – and am drafting a piece that is more angled towards dividing wheat from chaffe).

    The problem here is that now misinformation is out, *anything* said that is slightly negative around pathfinding is going to get seized upon – similarly, when people start hitting lag (or anything else) on a region, pathfinding is liable to become the devil in the works where blame is concerned.

    I suspect the next hoo-haw will be around the accounting system, some of which will be justified, but much is liable to be based on hearsay and misunderstanding.

    That all said, LL must take a portion of the blame here. There have been no blog posts clearly explaining pathfinding in lay terms, no attempts to let people know what is going on outside of the server forum (much of which would likely go over a lot of heads) – not even an announcement that PF has been rolled out, where the tools are and what to expect, where to get help.

    • I think we see things about the same.

      The FS/PH team has their baggage and relationships with the Lab and various people in the Lab. I wouldn’t say they exactly have each other’s back. But, may be that’s just me.

      I’m not sure I’ll ever know how much my tsunami email to Hamlet changed things. At the time what they were saying sounded like a disaster in the making. Did the tsunami email change things? Did I misunderstand and what we have now is what they always planned to do? If it is, they certainly missed explaining it that way… or I just didn’t get it. Whatever the case, I think they have done an amazing job on PF.

      Many users think the Lab has some obligation to explain things to us. Just watch Oskar’s Deploys thread. It draws a collection of uninformed peeps regularly slamming Oskr and other Lindens. Pure transference and no glimmer of a hope for enlightenment. So, I don’t see the Lab doing explanations to any but those interested enough to show up at a UG. I see the community as having brought that about.

      • There has always been a vocal contingent in the user community that will shout rather than listen – as I’ve written on my own blog (“Communications: it isn’t always the Lab”). However, that is no reason for LL to completely abstain from broad communications, especially when it is in their own interests to do so (as with pathfinding, if they really want to see it taken-up en masse).

        Does the company have an obligation to communicate? Actually, and speaking purely as someone who has spent her entire career in publishing & PR, yes it does.

        Communication is part an parcel of providing a service for any customer-facing organisation; LL is actually no different. It is ironic that while they have sought to improve what they regard as customer services, communication – which is the very backbone of company / customer relations, and so very much as part of customer service, has been allowed to die.

        And “communications” doesn’t necessarily equate to “full disclosure”, obviously there are points at which the company has a right to say “no comment” (which is one of the reasons I disagree with people who are still upset at Rod Humble’s refusal to discuss tier pricing at last year’s SLCC). But again, “no comment” is very far removed from saying nothing whatsoever.

        What “communication” does mean is taking the time to keep users reasonably informed as to what is going on – not through focused channels such as UGs (which, incidentally, are *not* regarded as “official” channels of communication where LL’s management are concerned) . Rather it means taking reasonable efforts to use the channels by which the largest number of users are liable to be touched.

        There are many reasons for this – some of which (at the risk of sounding like I’m touting my blog, which is not the intent) I covered well over a year ago in “Business. Collaboration and Creative Growth”.

        As such, and while I very much do agree with you in that users can be as much a part of the problem as anything else, the onus for establishing a reasonable level of informative communication with as broad a base of the user community as possible does lie with Linden Lab. And it is not something they should be opting out of or something we should feel particularly sanguine about.

        • You make good points. I agree with them. I think I give more weight to the community side of the communication problems than you. After all we can only change what we do. We can’t change the Lab. I don’t mean for that to detract from what you said. I just think it is easier for us to change than to change the Lab.

          • I agree, we can only change what lies within our power – which is why I try to point out inaccurate thinking on the part of the community as you do.

            But we can influence the Lab – as Lorca’s comment below points out only too well: there were misconceptions which came to the Lab’s attention, and they sought to overcome problems through better communications.

            This is where the synergy comes into play – a synergy that has, on the whole been a positive dynamic for LL / user relations, the vocal minority notwithstanding. It’s also a dynamic those that the sharp end of LL, who have direct contact with users, do seem to appreciate and understand. It is so be regretted that more senior staff in LL do not seem to share that view.

  3. Finding that the sim had 1319 movable obstacles (because all likely scripted objects were set to that) I decided to go through the ‘movable obstacle’ linksets and change them en masse to ‘static obstacle’. Then I went and changed all really movable objects (about 180 doors etc.) back to ‘static obstacle’ – not an easy job as some were named ‘object’ but I thought worthwhile. But then after a rebake and even a region restart I noticed several objects weren’t performing correctly. Some static objects with poseballs and also some tp posts stopped working – but they worked fine when set to being a ‘movable obstacle’. Is there a list of non-moving objects that seem to be affected in this way (or what LSL scripting items affect this)?

    • A correction – meant to say ” I went and changed all really movable objects (about 180 doors etc.) back to ‘movable obstacle’” or it wouldn’t make sense!

    • I don’t know that there is a list. Probably not. I suppose we could add one to the wiki.

      Some pose balls rez, others change position, and some are stationary. I would expect only the stationary to work as static. Pose balls as some part of a linkset could be challenging when they move.

      I would not be surprised that PF makes mistakes figuring out which is what.

      Doors static… I was wondering.

  4. Although Lindens do not generally post on Resident blogs, I am going to make an exception in this one case. Don’t expect us to make a habit of it, though 😉

    I want to start off by thanking Nalates for what I feel has been even handed coverage of pathfinding as a whole. While I disagreed with several of the assertions made in the “Tsunami” post, it did make us realize that there were misconceptions about pathfinding that needed clarification (particularly in regards to performance implications) and was a useful data point in identifying Resident concerns while we were still in the development phase.

    The 18% performance hit figure referenced on the Phoenix Viewer blog is a worst case scenario that will rarely be seen in practice – eg, you could see that large of a hit on a poorly optimized region that contains hundreds of pathfinding characters running simultaneously. Average perceived (viewer side) fps grid wide was actually .03 fps higher yesterday afternoon than it was the afternoon before. Average server side performance grid wide was also inline before and after pathfinding server code was rolled out. Region crash rates – excluding a bumpy couple hours during the roll out – remain low. All of this is to say that as far as the Lab can tell, Pathfinding has not had a negative performance or stability impact in the vast majority of situations.

    I also want to make clear that the impact on some vehicles is not directly related to pathfinding per say but rather the underlying physics and terrain optimizations that made pathfinding possible and have benefits beyond pathfinding. As far as we can tell, only a small percentage of existing content is affected by this physics upgrade.

    We do not consider pathfinding to be fully released until the pathfinding viewer tools are out of beta. This is why we have not yet made an official announcement. I agree that we need to do a pass on our pathfinding related wiki as some of the information there has not been updated since we were in alpha. We plan to make a blog post in the near future that will address some common misconceptions we have heard about pathfinding. We also plan to continue updating the “Good Building Practices” guide so that it will be a useful resource for Residents looking to make optimized content.

    We understand that pathfinding can be a confusing topic at times and appreciate the effort interested Residents are making to absorb the technical details. If you have any burning questions about pathfinding, please come to our user group on Pathtest1 (on Aditi) at 4PM SLT Thursdays and ask away. Above all, we are extremely excited to see what you Residents create with the new pathfinding tools and LSL functions!

    • Thanks for the comment, Lorca. And I’m delighted that the materials in the wiki are to be updated — as a scripter, that’s my primary source for technical information, and when parts of it are inaccurate or outdated, I get confused.

    • Thank you for that post Lorca. Information like this needs the widest dissemination (and I’m pleased to see other bloggers are picking up on it) so I do wish that Linden Lab would improve their policy on communications through an official channel. Without official comment it is too easy for rumours/gossip to escalate and taint the good work that is being done by Linden Lab.

  5. Pingback: Pathfinding and region performance – Lorca Linden comments | Living in the Modem World

  6. Pingback: DOH! LL are About To Bork Up SL - Page 4 - SLUniverse Forums

  7. Pingback: Spaced out | Serendipidy Haven's Blog

  8. Pingback: Pathfinding parte 2. Scriptare un personaggio in LSL. « VIRTUAL WORLDS MAGAZINE

  9. Pingback: Pathfinding, 7 Agosto 2012, una catastrofe per SecondLife o una nuova potenzialità (come le mesh l’anno scorso)? | VIRTUAL WORLDS MAGAZINE

  10. Pingback: Pathfinding parte 2. Scriptare un personaggio in LSL. | VIRTUAL WORLDS MAGAZINE

Leave a Reply to Hitomi Tiponi Cancel reply

Your email address will not be published. Required fields are marked *