Navmesh triangles merge


#1

Hi.
While using the Astar project and a small comparison with unity navmesh, I noticed that in unity after generation, navmesh is a set of convex polygons, not just triangles like in astar. (at least they show it so in the editor). And I had a question, why Astar does not merge a lot of triangles into polygons? This could significantly shorten the time to find the path by decreasing the vertices in the graph.


#2

Hi

This package uses triangles because they are significantly simpler to handle in pretty much all respects. If convex polygons would be used instead then several algorithms in the package would have to be significantly more complex and probably slower. There are some drawbacks to using triangles, mostly that it is easier for suboptimal paths to be found when using triangles compared to using convex polygons, however I think that the performance should be roughly the same due to the complexity of the additional code roughly cancelling out the additional nodes that need to be searched.
There are other ways to improve the pathfinding performance, especially for static graphs. See https://arongranberg.com/astar/documentation/dev_4_1_7_6425cc50/optimization.php.