This blog series is a part of the write-up assignments of our Game Engineering II class in the Master of Entertainment Arts & Engineering program at University of Utah.

For our first final project, we are making an engine component that provides a platform-independent interface that other people can also use it later on.

Topic

The topic I chose is navigation mesh generation and pathfinding. Since this is something that we often take for granted when using some commercial game engines like Unreal and Unity. But I think it is extremely important for me to understand the underlying work of the system so I will have the ability to tailor it for different genres of games and optimize it when needed. However, this is a not a small topic for a three weeks project. I will start with some of the most essential pieces and move onto other parts later on.

Where To Start

The first thing that I am going to do is to change our camera class into a full FPS camera. So that I can get a higher degree of freedom to look around the scene. Since we are using quaternion as our rigid body’s orientation, I need to add more functionality to our quaternion and vector class so the rotation in 3D space can be handled smoothly. This is fun enough to play around with and probably not going to take too much time.

The next thing is to create to navigation mesh system that can analyze the geometry of our level, generate appropriate navigation mesh with our custom data structure, and provide an interface to extract some data when needed. One challenging part about this is to dynamically generate visual indications of our navigation mesh. I plan to use some pre-defined navigation mesh specific effects with dynamically generated mesh objects.

The next step would be setting starting and ending positions, and then implement a navigation path structure that can calculate a path with the navigation mesh with some string pulling (funnel) algorithm. And hopeful see our objects move in action!

If all the above is done, I will probably implement some mouse interaction with ray casting so we can easily use the mouse to indicate where the object should move to.

Interface

I am definitely going to spend some time studying Recast to better understand how it works and implement my own navigation system. But I am imagining something like

void cNavMesh::GenerateNavigationMesh(std::vector i_floorObjects);

navMeshArea* cNavMesh::GetNavigationMeshAreas() const;
navMeshArea* cNavMesh::GetNavigationMesh(unsigned int i_meshID) const;
unsigned int cNavMesh::GetNavigationMeshAresCount() const;

navMeshVert* cNavMesh::GetNavigationMeshVertices() const;
navMeshEdges* cNavMesh::GetNavigationMeshEdges() const;

But of course, comparing to the thousands of lines of code in Recase, the is extremely simplified. But I think should be a good starting point!

Update (11/5)

Since the original plan was a bit too ambitious, also probably not so easy for other people in the class to adopt and use it. Our teacher gave me some suggestions. Right now the goals are gonna be as listed.

  1. A Lua file format to allow the users to specify all the nodes within the game, and the connectivity between them (basically a graph).
  2. A builder project that can build the Lua file into my own binary format so they can be used later in the game.
  3. Have a NavigationGraphMaster class that holds the graph information.
  4. A Navigation Agent class that can hold a pointer to the rigid body, and listens to the game update event.
  5. The agent accepts some MoveTo(int i_nodeID) function and the navigation master will calculate the route and start moving the rigid body every frame.

Some stretch goals might include displaying the nodes/path in the game with some predefined mesh. Or, instead of directly move along the path, having some smoothing so the turns won’t look so stiff.