Consider using polyanya for the pathfinding algorithm.

[andriyDev]

If your nav mesh is poorly laid out, this can result in taking extra long paths just by bad luck (and it looks really strange).

We can improve this by using the polyanya algorithm. We don't actually care about its straight line path, but we can store the nodes we pass through as the corridor and recreate the same kind of path we use today (so only the pathfinding algorithm needs to change, particularly the AStarProblem we create).

[ColinGilbert]

Would this be upstreamed if someone were to come up with a good pull request? I think its a good beginner/intermediate issue.

[andriyDev]

Very maybe. I'd definitely call it more of an intermediate issue, since it requires integrating with all the off mesh links, node costs, etc.

I'm much less convinced this is necessary after #124. Going through the centers of nodes really messed up estimates, and always using the node center as the start/end points also meant the estimates were messed up. But now going through the centers of edges should lead to much better paths.

There is still situations where polyanya can produce more optimal paths (effectively when a portal is REALLY long, meaning it would be a large detour to go through the center of the edge. But I think these situations are fairly rare, and can be fixed by tessellating edges (a little undesirable).