Navmesh
This was my main area of responsibility on the first project using our group-made engine. The focus was on importing an .obj file from an external source, building it to a graph, and using it for pathfinding purposes in our Spite game.
The Interface
The interface for this system is in the NavmeshManager class. It holds functions for building .obj files, getting data related to pathfinding, and rendering the mesh for debug purposes. There is also a custom raytrace method used for when enemies don't follow a path but rather just moves in a direction. This trace can also function as a cone to better avoid areas that might trap the enemy or otherwise impact the experience.
Privately it is friended to the AStar and Funneling algorithm. In part for these classes to access private data in this class, but also to hide the constructor from being used by anything else. There is also references to the importer class and to the node graph.
Building a mesh..
We parse the .obj file and create the necessary structures to hold the data, to make a vector of raw data. The BuildMesh function then takes this raw data to create the final node graph.
The BuildMesh function itself is mostly handling the threads used for the AddNeighboors function below. The raw data is split in 4 intervals, each given to a thread.
We work with triangulated navmeshes, meaning each node can only have three neighboors. The mesh is then looped over the interval to find nodes that share two vertices, this is done by use of a std::set. Since the entries in a set are unique we can assume that if the set has four entries, two vertices must be shared.
This process is time consuming and is not something we do at runtime, instead we save the resulting data to a file.
The Structures
There are four kinds of structures making up the graph.
Navmesh:
The top one, consists only of a vector of NavNodes, this approach was chosen because it was simpler to use our serializer class, which relies on inheritance.
NavNode:
This struct holds one NavTriangle as its "current" node, and a vector of NavNode pointers as its "neighboors. This one is also the object holding additional data such as weights, or status.
NavTriangle:
This is our geometry class, it is made up of three NavPoints, and holds mainly functions for collision-checks, and data such as plane normal and center position.
NavPoint:
The lowest level buildingblock, it holds only a position and an ID.
The Pathfinding/Funneling
For this problem we implemented a simple AStar algorithm from one of the earlier courses. Slightly modified to fit with the framework of this navmesh implementation. It does basicly what you'd expect, find the node we're standing on right now, find the node we want to go to, find the quickest path there, and return the nodes in a vector.
The funneling algorithm is very custom made. I started out using resources from various forums, to get a grasp on how it works. Then I sat down with pen and paper to test scenarios and to write some pseudo-code handling those situations. It ended up working surprisingly well, even though some bugs still persists.
Thoughts
This is probably the system that I've had the most fun working on. Even though the pipeline was a bit messy, I've gotten praise on how simple the interface is to use. When we started out, we knew about what a navmesh was, but had no idea on how to import it to our engine and implement it for use. This has really been a learning experience.