Strange behavior on elevations.

[kWeb24]

Hey,

I came across a strange navigation behavior. I'm not sure if it's a bug or something I missed.

The green line on the attached graphic is the expected path. Gray points are intermediate points that should be added to the path.

The red line is the current behavior. Yellow points are points that are in the path.

It seems that the height difference is ignored if the destination or the point where the change of direction is required are at the same height.

[donmccurdy]

Hm that’s surprising - what’s the scale of the map (1 unit = 1 meter?)? If you can share the navmesh that would be helpful, thanks.

[kWeb24]

@donmccurdy Yeah, i'll share it when i come home. Its scale 1, no transforms etc. Just basic plane.

Btw, you can reproduce this behavior in demo. Just place the ball at the bottom of the stairs and move it upstairs. Like on the image below.

The ball will dive into stairs.

[donmccurdy]

Hm, apparently this issue happens on the original PatrolJS repo as well: nickjanssen/PatrolJS#5

Reading through this article, it's probably caused by the string-pulling algorithm. I'm not entirely sure if that should be fixed within that algorithm, or if it's better for the code that actually moves the character ("steering algorithm") in the demo to handle clamping to the ground.

[kWeb24]

Yeah it is caused by the string pulling algorithm. A* returns correct path. Also i have to agree with you that in the case when we have character it is better to fix it in movement controller.

My case is a bit different, i'm using it for finding path in a 3D building model for navigation in shopping mall. This bug requires to create virtuall object that act as a player for correct camera movement because it can't just follow nav path.

So i think i have to create workaround.

If that's PatrolJS bug then you can close this issue since I agree with you about where it should be fixed.

[donmccurdy]

Let's keep the bug open - even if the string pulling argorithm is doing the right thing, I think I'd like the demo to keep the NPC on the ground. Maybe that requires extra code in the demo, or a helper function to flatten the path onto the navmesh. The existing clampStep function might be enough.

[kWeb24]

Sure, I'll let you know about my solution when i find some time to hang with it.

[sync3ds]

Any news about this issue? I'm facing the same problem and i've seen that the demo is still reproducing the wrong behaviour.
Many thanks.

[Mattiemus]

I am not sure that the current string pull algorithm works well if you have a true 3d nav mesh utilizing stacked bridges for example. In this case it might not be possible to re-map the string pulled path to the nav mesh due to potential ambiguity.

This can be solved very simply be updating the stringPull() method within Channel.js such that the loop looks something like the following:

for (let i = 1; i < portals.length; i++) {
  const left = portals[i].left;
  const right = portals[i].right;

  pts.push(new Vector3(
    MathUtils.lerp(left.x, right.x, 0.5),
    MathUtils.lerp(left.y, right.y, 0.5),
    MathUtils.lerp(left.z, right.z, 0.5)
  ));
}

Here I am taking the midpoint of each edge along the path. This is not optimal at all and results in a path with a lot of nodes, though it will perfectly match the underlying navmesh geometry.

Maybe there could be an option passed into findPath that specifies if we want to apply string pulling or not?

[kWeb24]

I'm not working on the 3d mall project anymore but if i remember correctly i did a workaround with separate meshes. Each shop has a z-level property and indicies that leads to stairs or elevators was just marked as lets say portal nodes that virtually connects different z-level meshes.

So if I know before pathfinding that target was on another z-level i was just looking for the closest portal node that leads to the given z-level. Then after reaching that node i was doing second pathfinding on the target z-level mesh. Transition between portal nodes was just smooth camera movement.

Anyway, the option to disable string pulling is a good one for now.