A* pathfinding and navigation mesh #2

I was generating the graph for pathfinding by triangulating the navigation mesh. Every vertex of the mesh was one node, and the edges of the resulting triangles would be used to connect the nodes.

If you remove the nodes on the convex vertices of the outer shell of the mesh, and nodes on the concave vertices from the holes of the mesh, you can get an optimized graph, since no shortest path will ever go trough those nodes.

Before: 882 nodes, 3522 connections

After: 439 nodes, 1226 connections