Navigation Mesh

Pathfinding

After running the algorithm and determining which space can be navigated by the player, I used the boundaries between each triangle as gateways for pathfinding. The techniques used in my other pathfinding worked well for this purpose and it was just a matter of building a network of nodes on all the existing gateways.

Computational Cost

This particular navigation mesh algorithm was pretty computational expensive because of how many triangles have to be generated. To reduce the cost of the process, I implemented a greedy heuristic approach for merging triangles and simplifying the path network.

Algorithm Development

The focus of this project was to develop an algorithm that divides a map into triangles which represent a space navigable by the player. The process starts first by forming small triangles in the map that do not intersect with any boundaries or obstacles and then finishes by merging them into larger triangles.

C#

Unity

Game AI

Computational Geometry