There is stuff happening in Pathfinding. This past week has seen several changes roll out. A new Project Viewer and another version of the Pathfinding server code made it to the Pathfinding regions in ADITI, the preview grid.
In the PATHTEST1,2,3, and 4 sandboxes in ADITI one can see how Pathfinding works without having to program and build their own characters. You can visit and click the big box shown in the image above. You can get all characters for the different Pathfinding behaviors; Evade, Pursue, Patrol, Wander, etc.
Region owners can sign up to be a beta tester in AGNI. Contact Lorca Linden to volunteer.
You may notice that the Pathfinding regions’ World Map tiles are messed up. It’s only a cosmetic problem. The Lindens already have a fix in QA.
Andrew Linden explained the SL Viewer uses some Havok code to render/display the Navmesh. Havok is SL’s physic engine and proprietary code owned by a third party company and licensed to the Lab. This means it will be a challenge for Third Party Viewers (TPV) without a Havok license to add the Nevmesh tools to their viewers. AFAIK only Firestorm has a Havok license.
The new Pathfinding tools in the viewer are in a large way are only about editing the Navmesh.
SL is probably going to be the only ‘game’ with an in-game Navmesh editor. If you have played with other game development tools, Like Unreal Engine, you know that creating the Navmesh is a task handled in the development tools.
Also, Navmeshes in most games are static. Being able to edit the mesh in near real time creates a somewhat dynamic nature for Second Life’s Navmeshes.
Most of the editing code is the Lab’s. But, some parts of the Navmesh render/display process use functions provided by the Havok library.
Pathfinding Server Side
Actual Pathfinding is done in the SL region servers using Havok’s highly optimized pathfinding and collision detection. Changes to the Navmesh have a significant impact on many parts of the SL system. The result is UI checks are being added to prevent errors in the Navmesh being sent to the server. Also, the Navmesh will be somewhat protected from changes that will affect it. Once a change is detected additional changes are throttled via a timer.
Additional changes made during the timed throttle period are stacked up in the system. I’m unclear where the changes are held. I am guessing they transfer into the SL Asset System. As more changes are made, the timer is updated. Only when no changes have been made for the throttle time does the system add the revised Navmesh to the Havok Engine for a new Navmesh computation.
In SL time the Havok conversion of the Navmesh into something Havok can use for collision detection is epic. The calculation takes from a couple of seconds to tens of seconds. That is an amazingly long time considering much of the going-ons in SL happen microseconds (1/1,000,000 sec).
The Navmesh calculation is done by the Havok code in the server. It is the Lab’s code that manages the Havok process and throttles incoming changes. Andrew Linden says, “…we also throttle the rate at which dynamic objects cut the navmesh (things that are not part of the navmesh, but move around and create obstacles for the AI characters). That last throttle is to help reduce lag when lots of objects exist that are NOT part of the navmesh. At the moment it is somewhat restrictive. That is, if you have 10 objects moving simultaneously. one objects effect on the navmesh may take some time to register for the purposes of the AI characters. So, a character might think a path is open, when in fact it was recently blocked by a moving obstacle. Because that obstacle’s “cut” (footprint where it blocks navigation) has not been updated yet.
AI characters can navigate around each other and also around objects that are moving around (via llSetPos() for example). However, the “knowledge” that a particular object has changed navigation paths may lag behind the objects actual motion, especially if there are lots of objects moving at once.
as soon as an AI character asks how to get from PointA to PointB, it knows how to get there… if there is a path according to the navmesh. so you could make a very complex maze and an AI character would be able to navigate it no problem, assuming there is a solution.
Anyway, that lag I just mentioned… I expect us to be able to reduce it eventually. But we’ll have to do more performance testing to pick the right amount of throttling and maybe we can make the software smarter to further reduce it.
Falcon Linden is the lead developer for Pathfinding, Andrew Linden is a helper, and Lorca Linden is managing the region owners’ membership in the beta test. Several other developers are working on the viewer UI stuff.
Pathfinding is open to region owners in AGNI. Contact Lorca Linden is you are interested. Pathfinding is going to be a big thing in SL. Think Hyperactive-Meeroos.
Second Life 3.3.2 (253194)
This version: Apr 5 2012 16:49:16 (Project Viewer – Pathfinding) works with Navmesh. The previous version had a problem with HUD’s. PATHBUG-63. That seems to be fixed.
While it is unlikely anyone would, I changed my graphics settings while the Navmesh was displayed. Doing so breaks the Navmesh display, it disappears. One can close and reopen the Navmesh Edit/Test after changing the graphics settings and the Navmesh displays as expected whatever your settings.
Also, the viewer is fast. I get 25 to 30 FPS in ADITI. That is with Navmesh displaying, but no L&S, AO, or Sun/Moon.
There are still lots of bugs to be found. The Lindens ask that all bug reports include the time and location, as in which region, a bug is encountered.
One of the known bugs comes form minimum turn radius. The user can set the turn radius when building the script. On platforms and near water edges or Navmesh edges the minimum radius can force a character over the edge, into the water, or off the Navmensh. This pretty much kills the character behavior.
I’m not sure whether this minimum radius problem is something they can fix or whether it is some we will have to handle when we write scripts. Fortunately the path_update event allows us to handle such events.
Andrew Linden says they are starting to see a light ahead. So, the end of the project and its roll out is in sight. I take that to mean we’ll likely see Pathfinding roll out in the next few months. I’ll guess 3 to 6 months, with 3 being,I think, the more likely guesstimate. Of course all the typical caveats go with that guess.