On seeing some more unexpected pathfinding results, I’ve done some more in depth testing and found that the path cost calculations are generating wildly differing values when the start/end is moved across nav polygon (not tile) boundaries.
In the image above, the testing actor gives a path cost of 90 and pathfinding steps of 0. When moving one or both endpoints a tiny distance onto the next polygon, the pathfinding steps will jump up to 2 or 3, and with each jump, the path cost also jumps up, by around a further 90 each time. Note that the drawn path remains a simple, straight line.
I don’t know the code, but my assumption is that pathfinding steps is a measure of the searching algorithm and shouldn’t have any direct bearing on the actual cost in a gameplay sense, yet it appears that it does. So I’m guessing there’s a bug in there somewhere.
Note that this is not merely limited to the output results of the navigation testing actor. It is leading to incorrect pathing in practice. In the below image, nav polygon edges are aligned with the camera direction, so the direct path crosses a couple of them, which is bumping up the calculated cost enough that the cost of going via my custom links as shown is actually lower.
This behavior is a side effect of how Recast is finding paths - the pathing distance is measured between centers of portal edges (edges shared by two polygons). Path string-pulling is done as a post-processing step (and is optional). The behavior you observe depends heavily on navmesh’s triangulation, so you can try different triangulation methods and see if it helps. Also, playing around with area costs usually helps a lot here .
So I’ve looked at the code and I think I see what you mean. String pulling seems to be on by default, and it makes sense since if it wasn’t done at all then pathing routes would surely look strange. But I wonder in that case why cost calculation is done before string pulling, rather than afterwards in order to get more accurate costs?
Changing to the ChunkyMonotone partitioning allows me to reduce polygon size and so lessen the effect, but it seems very inefficient to create lots more polygons just for this purpose. Am I missing a better solution? My environments will generally be very flat and mostly have a single area cost - I don’t quite understand in what way you mean playing with area cost could help?
But I wonder in that case why cost calculation is done before string pulling, rather than afterwards in order to get more accurate costs?
It’s not this way for two reasons: simplicity and efficiency. And it’s usually good enough. If this is a huge problem for your game I’d suggest implementing your own pathfinding - you can do it by extending ReacatNavMesh and supplying custom FindPath-family functions.
My environments will generally be very flat and mostly have a single area cost - I don’t quite understand in what way you mean playing with area cost could help?
If you’re using mostly ‘default’ cost then changing costs won’t help you much.
In summary, this is a project-specific issue because a solution depends heavily on how your levels look, how you generate navmesh, etc. You’ll have to find the best way by trying different things. If you share a lot more details about your navigation requirements and setup I might be able to suggest some things.
Thanks Mieszko, that makes sense. I’ve played around some more and I can see that the problems are indeed mostly caused by the flat and simple nature of the levels. Even with ChunkyMonotone and high subdivision, there are still issues depending on what corridor is chosen on the largely regular grid of polygons.
My project will have small maps and won’t be performance intensive. As such, my gut feeling is the way to avoid unnecessarily angled paths would be to stick to default partitioning to minimize the number of polygons, but then change the pathfinding implementation as you mention. I’d think with a small nav mesh, it would be feasible to do a more exhaustive search to try to find (when it exists) the precise corridor that contains the straight line between two given points. I don’t know enough about how A* works to say for sure, but I think I’ll leave it for now and tackle that further down the line.
