Sub-optimal paths, triangulation to blame?


#1

Hi,

I’m struggling to find a way to address this kind of issue in my game:

It ends up being a really bad user experience when you click to move a guy and they take an obviously much-longer path to the destination. I understand the reasons behind it tech-wise, but regardless of how I play with the settings I can never get a Recast graph to generate a decent mesh that gives me expected behaviors. Raycasts are not a reasonable option for me as that will not handle even simple cases such as pathing around a cylinder.

It seems to me that fundamentally it’s the triangulation algorithm that is responsible for this since it generates all the triangle slivers. Is it possible that using something like a conforming Delaunay triangulation for each voxel countour could help ameliorate this issue?


#2

Just to see how it’d work I hacked up the triangulation inside of the recast generator to use Triangle.NET. This doesn’t work correctly at voxelized contour boundaries (as you can see from the areas where triangles aren’t sharing some vertices), but when testing within a contour the pathing results are of a much higher quality due to node center points being distributed much better.

I don’t understand the ported over recast code well enough to know if there is a way to pull off either a) contour stitching by adding vertices/triangles at intersection points or b) the ability to generate contours to define the areas that are holes and then feed the entire polygon + holes into the triangulator.


#3

Hi

The ideal solution to this problem is to use some other search algorithm like Theta* instead of A*. Unfortunately it would take a lot of work to support that (mostly because of trying to keep compatibility).

Nice that you managed to get good results using a delaunay triangulation. Recast cannot use this directly unfortunately because it has to handle overlapping surfaces (think multiple floors in a building), so what recast does is to split it up into smaller regions that do not overlap.
Creating a bunch of inner points in the navmesh also has the downside of reducing the performance, but I suppose that trade-off can be worth it.

I’m sorry that I don’t have a good solution to offer you for this :/.