Valerie vs. Dacy - two approaches to pathfinding

[animats]

Valerie on the left, Dacy at right.

I've been working on pathfinding NPCs for some time now. It's been a lot of work, but success is in sight. Here are my two characters, Valerie and Dacy. They're on the same parcel, and they have the same behavior goals, but use completely different systems. So anyone can compare the two approaches.

Valerie uses SL's system pathfinding. Plus extensive recovery code. If you run SL pathfinding and are trying to get to a destination in anything but total open space, something will go wrong within 30 seconds. (That's why most pathfinding characters just do "Wander" - it keeps going and does something random.) Most of those problems can be overcome. More or less. In overloaded sims, pathfinding breaks down.

Dacy uses a completely new system, which I wrote over the summer. This starts with llGetStaticPath, which quickly returns a path based only on static obstacles. llGetStaticPath finds a path on walkable surfaces, considering only static obstacles. Width is considered, but height is not. So you get a path which may go through avatars, under tables, and through anything not in the static navmesh, like a parked car. So, the new system makes lots of llCastRay calls to check for obstacles, and has a full maze solver for the hard cases. My planner then turns out a list of keyframes for llSetKeyframedMotion, which moves the character. During motion, more llCastRay calls and collision events check for changes in the world. If something stops the character, the whole planning process is started over from the current position, taking into account the new obstruction. During the several seconds needed for replanning, Dacy folds her arms and looks around, annoyed.

The overhead on this is not too bad. Ten characters use about 2-3ms per frame. So somewhere between 10-20 characters, the overhead level of built-in pathfinding is reached. I've tried 50 characters; that used half the script time in an empty sim. In an overloaded sim, movement still works fine, and at full speed. The arms-crossed poses are longer, as Dacy waits to get enough script time to plan.

Dacy can move much faster than Valerie. If I turn Valerie's speed up, she bumps into things. If I turn Dacy's speed up, she moves fine, and stops occasionally at the difficult points while the planner catches up. I usually have her walking at normal SL walk speed. She can run fast if needed.

Stop by my place in Vallone and take a look.  Comments welcomed. All this is still experimental; there's no product yet.

 

[animats]

New discovery recently. If you take a building that has interior floors and stairs, and set the entire building's pathfinding type to "walkable", it works! Floors are walkable and walls are static obstacles. If the physics model is reasonable, that's all you have to do. No need to prep the object for pathfinding. Needs to be tested more, but I've tried it on two buildings in a sandbox and it worked.

Somebody got this right years ago but didn't document it. The feeling I get about pathfinding is that somebody really good designed it, but before it was finished, they left.

[Lucia Nightfire]

7 hours ago, animats said:

Somebody got this right years ago but didn't document it. The feeling I get about pathfinding is that somebody really good designed it, but before it was finished, they left.

There are still bugs out the wazoo with PF and they also put the cart before the horse. They should have implemented Animesh back then, THEN implemented PF later.