Navmesh Generation Research Project

• Researched and programmed generation of a navigation mesh in C++

• Algorithms used: Ear Clipping Method, A* Pathfinding, Funnel Algorithm

My Junior year at DigiPen, I took a class in AI. In this class, I implemented nodes for behavior trees, wrote an A* pathfinding algorithm, and wrote terrain analysis features for an AI (sightlines, searching for the player, how open a map was, etc.). My capstone for this class was a research project on any topic of my choosing.

I worked closely with Ryan Garvan to produce a walkable triangular navmesh. In the class, we had only worked on a grid system, so Ryan and i worked to turn that grid system into a more memory efficient (and speedier!) triangular mesh. To do this, we had to research and implement The Funnel Algorithm and Ear Clipping Method.

Part of the project was writing and making a 10 minute presentation: Watch for a full demonstration!