Navmesh

Navmeshes are useful structures to find paths between different points, here's some work i did for a school project on a diablo clone.

I already had experience with some aspect of navmeshes and associated pathing techniques but we wanted to use the navmesh generated by unity, unfortunetely there was no known way to access the navmesh specific data, instead the only thing available was the raw triangulation data of an presumably unprocessed navmesh, presented here is the process required to get a working navmesh from an unsuitable mesh.

The first apparent problem was vertex duplicates, this was easily fixed by combining vertices and updating indicides. The second problem was flipped triangles, this was also easely fixed by simply switching indices.

The biggest problem was that some vertices were generated and placed on the edge of other triangles, this was fixed by projecting vertices onto the edges and checking if the distance from the edge was small enough to assume it was on the edge, I also had to check that the projected point was between the edge vertices and not extended outwards on either side. When a case was found we clip the triangle in question in two at the point of the edge, and update the indices.

Triangles are then merged into convex polygons.



The property of edges was then determined including their aproximate cost to travel to as well as their connection status. Unconnected edges are rendered as black.



A simple A* algorthim was decent enough for a set of polygons, and a funnel algorithm for the specific path.



And finally here it is used by the player controller:



Additional adjustments had to be made, such as slight adjust of the path to distance it from walls.







END