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.

This update shows the progress I made during the past week.

Navigation Graph Builder

Below is the Lua file format I created last time that specifies a graph. Now the I’m building the asset builder, I need to examine this more and think about how I can minimize read/write when creating/using the binary file.


If I read and write out all the nodes’ coordinates first, it’s really convenient the I can just assign the memory locations to our Math::sVector, and since all of them are floats (4 bytes), they align very nicely. However, since I split up the nodes with their corresponding connectivity arrays, I need to specify the node ids that correspond to each array later on. So, I am thinking about another format like this.


At first glance, this increases the number of table layers in the file, which increases the complexity when reading the file in. This won’t be an issue if this approach can make the file more readable/understandable. However, this is not the case in my opinion since there are some empty connectivities that took up lines without giving much information. Also, if the users want to debug some paths between the nodes, they would have to make more jumps between the lines and potentially get lost more often. The same arguments can be applied to the binary formats.

In summary, I’m going to stick to the first Lua format, and build them into a binary file with different sections. Below is what the final Lua file looks like.


After getting built by my navigation builder, the output binary file looks like below.

The red underlined part is the number of nodes in the graph.
The green underlined parts are the three float position values of each node.
The white underlined is the node id in connectivity array.
The yellow underlined is the number of nodes connected in the connectivity array.
The blue underlined is the node’s id that is connected in the connectivity array.


I feel like it has the potential to be more compact, but that may require some assumptions from the user side knowing how the builder works, so I am going to keep it like this for now.

Size comparison:

Lua file: 441 bytes
Binary file: 176 bytes

Another win for our binary format.


Initializing the navigation system is fairly easy, right now I declare some static variables on the top of cMyGame.cpp.

// global static navigation variables
// ======================
// navigation graph
eae6320::Navigation::cNavigationGraphManager* s_navGraphMgr = nullptr;
const char * s_navGraphMgrFilePath = "data/navgraphs/testnavgraph.nvgbin";

// navigation agents and manager
eae6320::Navigation::cNavigationGraphAgentManager* s_navAgentManager = nullptr;

eae6320::Navigation::cNavigationGraphAgent* s_navAgent1 = nullptr;
eae6320::Navigation::cNavigationGraphAgent* s_navAgent2 = nullptr;
eae6320::Navigation::cNavigationGraphAgent* s_navAgent3 = nullptr;

And then the variables can be initialized through some static factory functions that I provide to the user.

// Navigation classes
// =====================
    // initialize navigation graph
    result = eae6320::Navigation::cNavigationGraphManager::GetNewNavGraphManager(s_navGraphMgr, s_navGraphMgrFilePath);
    if (result != eae6320::Results::Success) {
        EAE6320_ASSERT(false && "GetNewNavGraphManager unsuccessful!");
    EAE6320_ASSERT(s_navGraphMgr != nullptr && "s_navGraphMgr returned nullptr by static factory function!");

    // initialize navigation agents manager
    result = wae6320::Navigation::cNavigationGraphAgentManager::GetNewNavGraphAgentManager(s_navAgentManager, s_navGraphMgr);
    if (result != eae6320::Results::Success) {
        EAE6320_ASSERT(false && "GetNewNavGraphAgentManager unsuccessful!");
    EAE6320_ASSERT(s_navAgentManager != nullptr && "s_navAgentManager returned nullptr by static factory function!");

    // create an agent for torus object
    s_navAgentManager->CreateNewAgent(s_navAgent1, &(s_planeObject.GetRigidBody()));
    s_navAgentManager->CreateNewAgent(s_navAgent2, &(s_torusObject.GetRigidBody()));
    s_navAgentManager->CreateNewAgent(s_navAgent3, &(s_cylinderObject.GetRigidBody()), 20.0f, 1.0f);

Moving with Navigation Agent

After the navigation graph manager, agent manager and agents are all initialized. Agents can be easily instructed to move to certain nodes by specifying the node ID. The gif below shows that moving one of the agents to node #1 with just one line of code.



What’s Next

The one main element that is missing so far is pretty much just graph pathfinding. I will start with A* and then move onto some optimized versions of it. I will also need to think about how much of the pathfinding I should try to keep and reuse. Since storing a whole matrix within our manager and only calculate once provides the lowest computation time, but introduce a larger use of memory space (N^2). Also, I will try to implement as many stretch goals as possible.

Future Goals

Firstly, the navigation agents can have some delegates/multi-cast delegates to inform interested parties that their movements have completed successfully or failed somehow. With this implemented, it will add a ton of flexibility and usability to the navigation agent.

Secondly, Since our navigation is a graph, there are some potential opportunities to perform optimization, such as merging nodes that have exactly the same input and outputs or removing the nodes with zero degrees of input/output. I will add these in toward the end if I have enough time.

Lastly, the navigation manager doesn’t accept empty graph currently. However, I do see the potential of needing this feature, maybe someone needs to just construct with an empty graph, and then expanding it procedurally. For simplicity’s sake, I am requiring the user to pass in a valid graph for now.