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 and a summary/tutorial of this engine component I made.

Pathfinding

While there are some common approaches to accelerate A*, such as jump point search, they sometimes apply only to a grid but not a graph. Therefore, I will be starting with the traditional A* for pathfinding.

I have separated my A* implementation into another blog post, where I will be talking about it in more detail and also showing the codes.

Below shows the deer follow a path from node 0 -> 1 -> 2 -> 4 that was retrieved with A*.

EngineUpdateAStar.gif

Agent Delegate

I use a custom created delegate class in my navigation agent and agent manager to allow users to provide callbacks functions that listen to important events, such as when does the agent reach its destination. These two classes are separated into another standalone .lib project.

I have also separated the explanation toward the delegate class into another separate post, where I can explain it in a more detailed fashion and demonstrate how to use it.

Summary & Tutorial

Below is the detailed walkthrough of how to use my navigation system within the Engine structure that we use in our class, and is intended for other classmates in the class, so if you’re not one of them, this might not be useful to you at all.

Project Setup

The navigation system contains three separate projects. I will be going through each of them and put the needed project reference below them. Click here to download the zip of all three projects.

Update 11/30: Found and fixed some bugs in the navigation system.
Update 12/02: Changed some implementations and interfaces, now the agents and nodes have more knowledge of the overall system (which agents standing on which nodes, which graph they are using, etc.)
The new version is here.

  1. NavigationGraphBuilder
    This is the builder tool that builds a Lua file into a binary file at your destination game folder. To use this properly, the codes below need to be added into AssetBuildFunctions.lua

    -- Navigation Graph Asset Type
    --------------------
    NewAssetTypeInfo( "navigationgraphs",
    	{
    		ConvertSourceRelativePathToBuiltRelativePath = function( i_sourceRelativePath )
    			-- Change the source file extension to the binary version
    			local relativeDirectory, file = i_sourceRelativePath:match( "(.-)([^/\\]+)$" )
    			local fileName, extensionWithPeriod = file:match( "([^%.]+)(.*)" )
    			local binaryExtension = "bin"
    			return relativeDirectory .. fileName .. extensionWithPeriod .. binaryExtension
    		end,
    		GetBuilderRelativePath = function()
    			return "NavigationGraphBuilder.exe"
    		end
    	}
    )
    

    You also need to add the navigation graph lua file path into the AssetsToBuild.lua.

    navigationgraphs =
    {
    	{path = "navgraphs/testNavGraph.nvg"}
    }
    

    References Needed:
    Asserts
    AssetBuildLibrary
    Math
    Platform
    Windows

  2. Delegate
    This project provides the cDelegate and cMulticastDelegate class to use with the navigation agent.
    References Needed:
    Asserts
  3. NavigationGraph
    The main project with the navigation graph and agent classes.
    References Needed:
    Asserts
    Logging
    Math
    Physics
    Platform
    Results

System Initialization

It’s very easy to initialize the navigation system. the variables can just be declared as null pointers in the beginning. Also, a path to the built binary file of navigation graph is needed.

// 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;

// Delegates for navigation
eae6320::Navigation::AgentEventReceiver s_agentMoveSuccessReceiver;
eae6320::Navigation::AgentEventReceiver s_agentMoveInterruptReceiver;

After that, you can initialize them with some provided static factory functions. Note that the graph should be created first since other systems need a reference to it.
After navigation graph manager, you need to create a navigation agent manager with the graph manager passing in.

Now you can ask the agent manager to create agents for you by passing in pointers to their corresponding rigid body and specify movement speed and target acceptance radius (how far is close enough that the agent can stop moving). The full function signature is shown below.

// let the manager create a new agent for user, and then register to itself. Requires a rigid body pointer, can specify move speed (default to 10.0f) and acceptance radius (default to 5.0f)
eae6320::cResult CreateNewAgent(cNavigationGraphAgent *& o_agentPtr, Physics::sRigidBodyState * i_rigidBody, float i_moveSpeed = 10.0f, float i_acceptanceRadius = 5.0f);

Initialization code.

// 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 = eae6320::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())); // use default movement speed 10.0 and acceptance radius 5.0f
    s_navAgentManager->CreateNewAgent(s_navAgent2, &(s_torusObject.GetRigidBody())); // use default movement speed 10.0 and acceptance radius 5.0f
    s_navAgentManager->CreateNewAgent(s_navAgent3, &(s_cylinderObject.GetRigidBody()), 20.0f, 1.0f); // specify custom movement speed and acceptance radius
}
{
    // Delegates
    s_agentMoveSuccessReceiver = eae6320::Navigation::AgentEventReceiver::Create(this);
    s_agentMoveInterruptReceiver = eae6320::Navigation::AgentEventReceiver::Create(this);

    s_navAgent3->OnAgentMoveSuccess()->AddDelegate(s_agentMoveSuccessReceiver);
    s_navAgent3->OnAgentMoveInterrupt()->AddDelegate(s_agentMoveInterruptReceiver);
}

Since the template arguments often disappear from the code snippets for unknown reasons, refer to the screenshot below for the delegates creation.

AgentDelegates.PNG

To make the agents actually work, you will need to call the navigation agent manager’s update function within your UpdateSimulationBasedOnTime and pass in the delta time.

// Update Navigation system
// ===========================
{
    s_navAgentManager->Update(i_elapsedSecondCount_sinceLastUpdate);
}

To tell the agents to move to places, there are two functions that you can use, one that takes an unsigned int, while the other takes a vector. If you pass in a vector, the graph will find a node that is closest to the vector and inform the agent to move to that node.

// Use node id number
s_navAgent3->MoveTo(1);

// Use a vector
eae6320::Math::sVector targetLocation = eae6320::Math::sVector(0.0f, 0.0f, 5.0f);
s_navAgent3->MoveTo(targetLocation);

There is also an interrupt function that you can use to stop the agent’s current movement.

s_navAgent3->Interrupt();

To clean up the navigation system before shutting down, you will only need to call the cleanup functions on the two manager classes, and they will handle cleaning up the graph nodes and also the agents on their own.

// Navigation clean up
// ======================
if (s_navAgentManager) {
    s_navAgentManager->CleanUp();
}
if (s_navGraphMgr) {
    s_navGraphMgr->CleanUp();
}

If Only They Had Made It

One feature I really wanted to add for this tool was nodes visualization to give the graph nodes a visual representation inside our game world so that it will be easier and more convenient to debug. However, considering the fact that all of us has different mesh builder, different binary mesh file representation, and different mesh classes in the game. There wasn’t really anything that I could do to make it easier for other people to add this feature to the project except just making a file in Maya.

Another feature that I wanted to implement was dynamically node insert/remove. Right now, my graph system can only initialize with a fixed graph and doesn’t have the ability to dynamically increase or decrease the size of the graph, which is something that can be crucial for an actual game. Try to think about a procedurally generated node based adventure game or something like that, sounds pretty fun!

Lastly, you can refer to my A* implementation to check out my struggle with std::priority_queue.

Summary

Even though I constantly keep the mindset of “platform independent” and “public interfaces” in my head throughout all of the past assignments, I have never thought about them so seriously as I have during this project. Because I know that some of our classmates might actually become the users of this component, I spent so much time and effort iterating on the public interfaces, thinking about the structures and trying to come up with features that can potentially be something that other people might ask for. When creating functions that should only be accessed by other classes but are not a part of the public interface, I declared the functions that require access in the other class friends of this class, preventing unnecessary access permission.

Overall, I’m pretty proud of what I made and really think this project is a great practice for us to step into the mindset of an engineer creating components for other fellow engineers to use. I’m also really excited about adding other people’s components into my engine to actually make a game!

Executable

Press ‘M’ to make the deer start moving toward destination, press ‘N’ to interrupt.

x64 (D3D)