Navmesh path planning produces sub-optimal paths

[JulianKu]

Hi :)

I was wondering how the path from an agent to the goal is computed when using a navMesh. On my custom map, I encounter the following path planning. In shows the planned path in yellow where I would expect a more optimal path something like the path I've drawn in red.

I thought the underlying planning algorithm is A* which should output an optimal path. Is the planning taking something into account that I missed? I am happy for everyone that can provide help.

I also attach my project files, in case the problem could be with the navmesh.

project.zip

[JulianKu]

I think I might know what's causing this issue: In this corridor-like setting with this alternating triangle-orientation, the path trough the node centers is rather inefficient as the triangle centers are forming a zigzag path. Unfortunately, this does not make it easy to solve I guess...

[curds01]

Fortunately, I can answer this one without looking at your project.

You have stumbled upon an artifact I've been meaning to fix for a while. Given the current implementation, what you got is exactly what I would expect. Well, that's not strictly true. But knowing what I know, I'm unsurprised to see your result.

Path planning using nav mesh happens in two stages:

1. Computing the path envelope
2. Finding a path in the envelope.

Your bad path is due to some aggressive simplifications in the first step. Essentially, we create a graph and do a path search on that graph. The graph consists of a single node per polygon in the mesh. Two nodes are adjacent in the graph if their corresponding polygons share an internal edge. The "distance" between the graph nodes is the distance between the two polygon centroids. This generally produces acceptable results, but it can also produce the results you're seeing.

You've got some large triangles. Those large triangles have centroids that can be quite far away from the optimal path. So, the envelope search considers passing through those triangles as very expensive and ends up finding the yellow path instead. It is optimal, only when you consider triangle centroids.

I've been meaning to change the envelope search so that it truly finds the shortest path across the open space. The changes would also do a better job of finding truly traversible paths (right now it's also possible to create an environment where a space is not traversible but the search algorithm believes it is).

The changes basically entail encoding the mesh as a different kind of graph. In this case each internal edge of the mesh becomes a node. And two nodes are connected if they exist in the same polygon. The cost between the nodes is the minimum cost between the two edges. This would make it less sensitive to the centroid problem. I'm still working out some of the other minor issues that'll arise.

[curds01]

(You hit comment moments before I did. :))

[JulianKu]

Thanks for your answer! Unfortunately, right now I do not have the time to tackle the problem at its root.

As a kind of hacky solution, I'd like to try making the distribution of triangles sizes more uniform. I essentially do not really care about the optimal path but pedestrians moving trough the corridor on somewhat reasonable paths. Maybe with equally sized triangles this will do...

[curds01]

Triangle sizes seems a reasonable way forward. But don't make too many triangles. Ultimately, the path planning is constrained to the envelope. It'll try and stay inside the envelope which can introduce likewise zig-zaggy (although with a lower amplitude) behavior. Also, it means you're more likely to get pushed out of your envelope which triggers re-planning -- probably ok for behavior, but computationally more expensive.

I really need to elevate the importance of the nav mesh refactor.

[JulianKu]

Alright, thanks a lot! I will see whether it works out for me. You can close the issue if you want or keep it open to leave it as a reminder or so :sweat_smile:

[curds01]

I'm leaving it open but am going to change the title to more directly reflect the bug that's been discussed. Your image does a great job of illustrating the problem statement.