Pathfinding in SL has been troublesome. I've made some nice pathfinding animesh characters, but they don't move well enough. Characters keep going off-path and running into things. They hit corners of buildings and spin around. They go off-parcel and get stuck. Under sim overload, this gets worse. Much worse. Slowing them down helps, but then they move like zombies. That's no good.
There's keyframe animation, but that tends to be too rigid, following permanent built-in paths. The movement from keyframe animation works well; it's just too repetitive.
So I've written my own pathfinding system in LSL. It uses llGetStaticPath to get a rough path, avoiding static obstacles. Then it uses llCastRay calls, many, many llCastRay calls, to check that path. If an obstacle is encountered, it runs a maze solver in LSL and works out a path around the obstacle. Once the path has been computed, the path is followed using keyframe animation.
New pathfinding system tester. I'm using a bronze monolith for testing. I'll switch to an animesh character later.
Just for testing, the planner puts down a trail of temporary markers. They disappear in about a minute. The green path is mostly from llGetStaticPath. That path hit the doorframe. The maze solver took over and corrected that. The maze solver's work is shown in yellow.
Though the parking lot and around the parked vehicles. The maze solver worked out a path around the vehicles. The maze solver is grid-based, and the result gets straightened out a bit afterward. Where you see green on top of yellow, the green is the path it actually took. This is actually three maze solves in a row. Looks a bit more robotic than I'd like.
Using keyframe animation means the characters follow the planned path at full speed, even on an overloaded sim. No more zombie-speed movement. No more banging into doorframes and tables.The movement quality is comparable to ordinary SL avatars. The turns are smoothed out and the character rotates going into and out of the turn; it doesn't stop dead and pivot in place. I'm currently running the monolith at faster than SL walking speed. No problems with that.
Script overload shows up as a delay in starting movement. Maze solving in LSL is slow, but it's overlapped with movement, so the maze is usually solved before the character gets there.
The system will avoid avatars when necessary. If an avatar moves into the path, the obstacle will be detected. But then there's a delay of several seconds while the planning system computes a new path. I want to use a "looking around, impatient" animation for my characters while they're on hold waiting for the planner to catch up.
A big win with this is much better performance in cluttered areas. SL's pathfinding system needs a lot of open space. The minimum opening width for SL pathfinding is about double door width. Even then, the characters tend to bang into the edges of the doorframe. This system, if there's 1m of space, can get through. So it can get through a standard door. And maneuver around inside a restaurant or club. I'm thinking of a NPC waitress.
All this requires a parcel with pathfinding enabled, and with big objects marked as walkable or static. The maze solver will handle going around little stuff, movable objects, and avatars. The maze solver can only handle an area of obstacles about 20m across, so big obstacles must be made static.
This does not turn on the full SL pathfinding system, which has a constant overhead of about 20% of a sim's script time. Overhead for one character seems to be about 1ms per frame. 10 characters in an empty sim pushed the load up to 2ms per frame. So it's less than the built-in pathfinding for small numbers of characters, and there's no compute load when the characters are not moving. Not low enough overhead for large, active breedable herds, though.
It doesn't seem to impact heavily loaded sims much, because it's making large numbers of llCastRay calls, and those are throttled. So it slows down rather than impacting the sim. That needs further testing. Vir Linden indicated at Creator User Group that making large numbers of llCastRay calls is OK.
This isn't done yet, but it's working well enough for a demo. I have the monolith running at the Animats workshop in Vallone as a test, and you can visit if you like. The tester behaves much like my animesh NPCs, which use regular pathfinding, and approach new visitors. When there are no new visitors, it moves randomly between some patrol points. It doesn't have the social graces yet. It tends to bump into avatars and stop, it gets too close to them, and it doesn't say "Excuse me" like my NPCs.
(This was way too much work. LSL is not a good language for something this complex.)