Pathfinding via keyframe animation

[animats]

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.)

 

 

 

[animats]

Well, after leaving this running overnight, it seems to stay out of trouble. That alone is a big improvement over SL pathfinding. This is starting to look like the way to do NPCs. Keyframed NPCs have worked well in many places of SL, but they're usually stuck on rigid tracks. Now they can get some freedom of movement.

Keyframed motion in SL is a bit strange. It's semi-physical; it can push or carry physical objects. Collisions with physical objects, including avatars, are detected. But collisions with non-physical objects are not. This includes other keyframed objects. On the other side, keyframed objects don't trigger collisions in llVolumeDetect, and are not avatars or physical objects to llSensor. llSensor will detect scripted objects with type "(ACTIVE|SCRIPTED) ", but that triggers on everything in range that has a script. SL's low-overhead tests for moving objects don't work. So doors don't open for keyframed objects.

A useful test for doors is to use llSensor with type "AGENT|ACTIVE", then test for nonzero velocity for each object sensed. That picks up avatars, pathfinding animesh, vehicles, and keyframed motion. (Also the door, so that has to be excluded.)

[Lucia Nightfire]

I seem to remember telling you to use keyframe motion a long time ago, heh.

[Mollymews]

37 minutes ago, Lucia Nightfire said:

I seem to remember telling you to use keyframe motion a long time ago, heh.

this is true.  But sometimes we need to work thru and discover all this ourselves. Same with region crossings.  If nothing else animats does expansively document his journey down the various paths he takes. From an informational/sharing pov then I think is all good that he does so

[animats]

I've used keyframe animation with canned paths before. This is keyframe animation with dynamically generated paths and collision avoidance. I just give it the destination, and it figures out the route by itself. It can find and reach avatars anywhere on the parcel. Including going up stairs. I haven't seen that done in SL by anyone else.

It doesn't even seem to have been done for bots that are avatars. SmartMates (apparently the last survivor of the bot list on the wiki) doesn't have that. They just follow waypoints or the user that owns them. Smartbots offers a kitten, a gorilla, an alpaca, and a bodyguard. Those require a server, a paid account with the server operator, and an extra SL account. Now that we have animesh, we should be able to do that sort of thing entirely within SL.