pathfinder: does not check jump clearance

[bengardner]

The pathfinder fails to check clearance when computing a path that includes a jump.
The result is that it creates an invalid solution.

Here is an ASCII illustration of the side-view. s=start, d=destination.

XXXZ
      d
s   XXX
XXXXXXX

The villager can stand on any node on the path between S and D, but there is a jump that requires a clear spot above the node before the ledge. The 'Z' node is blocking the jump.

I discovered this when I tossed down a sapling and there was tree leaves blocking the path.

It looks like there is an unused function named check_clearance() in pathfiinder.lua that was intended to handle this.

Describe the solution you'd like
I expected the path to go left or right a bit and then hop up on the ledge.

Describe alternatives you've considered
The simple fix would be to fix pathfinder.lua to use something like check_clearance() if the neighbor move requires a jump.

Minetest has a built-in pathfinder that appears to handle this situation. But it doesn't do diagonals, have the ability to climb/descend a ladder, or handle water, so I don't consider it usable as-is. Quite a pity, because pathfinding is something that should/could be handled in C++ for performance reasons.

Another option is to rebase workiing_villager on top of a different module that handles all the low-level movement.
I've looked at mobkit and creatura. Both handle pathfinding and basic functions and have decent "AI" hooks.

Additional context
I didn't take a screenshot of the original problem, but I was able to reproduce it easy enough with cobblestone instead of tree leaves.

In the screenshot, a woodcutter is trying to reach a sapling.

[sfence]

Pathfinder is one of the weakest things in this mod.

But I am not enough brave to try rewriting it.

[bengardner]

I looked into it a bit. The neighbor selection code was a bit broken and overly complicated. I can send a patch for that.
It also looks like the villager doesn't move to the center of the node when following waypoints. That is causing navigation failures when the path is correct. May just need a +0.5 thrown in there to convert the node position to a mob position. I haven't figured that out, yet.

[bengardner]

The problem with cutting corners isn't easily fixed. The waypoint-following code faces the waypoint and then moves forward. When it gets 'close enough' (distance=1) to the next waypoint, it is deleted. The villager will never follow the path exactly and will always cut corners. It can usually get around the corner after a few tries, but it just looks silly.

Tightening the tolerance doesn't work, as the face-and-move strategy isn't accurate enough to get much closer.
Making the tolerance looser makes the problem worse.