Navigation Mesh, Path Finding and Implementation in Resistance 3

Artificial intelligence is creating the illusion of intelligent agents.

In class we discussed that a navigation mesh is a simplified version of the complex level mesh. We also talked about Recast which is a handy tool that will import the mesh of your level and will create a nav mesh from that. Now how does it do that? The image below outlines the process at a very high level:

Figure 1: Recast's Navigation mesh generation algorithm. Source: Insomniac Game's GDC 2011

I wanted to talk about something that we sort of touched on in class but didn`t go into too much detail about: so you setup Recast, generate your Nav Mesh…now what?

What algorithms and data structures do you use to store this data and once you store this data, how do you use it to create “intelligent” agents?

You may say “just put it in a graph and traverse the graph using the A* algorithm”, and that’s correct but what type of graph implementation should you use and how do you implement A* traversal? In this post I will talk about a couple different ways to store graph data and the A* graph traversal algorithm. I will also briefly talk about Insomniac Game’s implantation of these things in Resistance 3.

Storing The Data

Well let’s reflect on the data we have from our nav mesh. We have nodes, which are the vertices which make up the triangles and edges which are the lines that connect the vertices together. Consider the following example:

How would you, the human capable of thought go from the green square to the red square? Nothing is blocking you so you would simply say “just go in a straight line”, which is absolutely correct. But the real question is how would the computer perform this task? The computer knows which node it is currently on (the green one) and which node it needs to get to (the red one) and that’s it. We must define a relationship between the nodes. These relationships are known as edges. An edge connects two nodes and defines that if I am on node X I may travel to node Y. The question now is how do we do this? Well we could just have a giant matrix and store Boolean values which specify whether two nodes are connected or not. This is known as an adjacency matrix.

Example of an adjacency matrix. Source: Programming Game AI by Example by Mat Buckland

In the example above, the matrix stores which nodes a given node is connected to and which nodes it isn’t connected too. A "1" defines that there is a valid connection and a "0" defines that there is not a valid connection. This is a perfectly valid data structure but it wastes quite a bit of memory. Another more memory efficient data structure are adjacency lists. Adjacency lists allow you to deduce the same relationship between nodes but use significantly less memory. This is done by simply storing which nodes a given node is connected too and making the assumption that any other node not on the adjacency list is not connected.

Example of an adjacency list. Source: Programming Game AI by Example by Mat Buckland

For each node, you must specify which nodes it is connected to. Storing an adjacency matrix for each node would be a memory massacre so use an adjacency list instead. Below is how you could go about storing your navigation data.

How I stored data for navigation in a past project

Each node has an ID which I use as an index into the two lists in the code above. For example: Data about Node 0 is stored in index 0 of the _nodes list and the adjacency list for Node 0 is stored in index 0 of the _edges list.

Traversing the Graph

Now that you have your data organized in a nice graph, you can finally traverse the graph. There are many algorithms to traverse a graph, if you are interested in learning about these algorithms I highly recommend the book “Programming Game AI By Example” by Mat Buckland, this book goes into great detail about each traversal method and provides excellent examples. The A* algorithm really is the best of the bunch, not only does it find the most efficient path from A to B, it’s also the fastest.

Suppose I place some obstacles in our example above:

The blue path is the most optimal route returned by the algorithm. Those red branches are all of the paths that the algorithm once considered. Clearly from this visualization, you should be able to see that the computer’s method of finding the most optimal path varies significantly from a human’s. The A* algorithm is a cost based search. This means each edge has a cost associated with it. It also means that the most optimal path may not necessarily be the one with the least amount of nodes.

Resistance 3

In the Insomniac Game’s GDC 2011 talk about navigation they discussed that the Recast library was used to generate their navigation meshes. Their usage of AI using navigation meshes is rather straight forward, it is outlined below:

First they are requesting and setting the requirements that an agent needs, then they are finding and smoothing a path. Smoothing a path is done to create a more natural movement of an agent as the follow a path. An exaggerated example of this can be seen below.

They are then using an obstacle avoidance steering behaviour to ensure the agent does not get stuck. The obstacle avoidance steering behaviour is not very difficult, you essentially just cast a sphere around your agent and test for collision, if there is no collision then carry on if there is the obstacle avoidance function will return a direction vector pointing away from the obstacle. Since steering behaviours can be summed together (via weighted average), if you are performing both avoidance and path following on an agent, the direction will point away from the obstacle and will still guide your agent to the next node in it’s path. In the most simple implementation of steering behaviours, this direction will be multiplied by your agent’s speed and therefore move your agent in that direction.

Since the agent is not just sliding along the path, its also animating so they may have special animations when specific obstacles are encountered. For example if there is a knee high obstacle, instead of making the agent awkwardly run around it, they may just play a “stepping over” animation.

I asked this question before, but I’ll ask it again: You the human see a knee high obstacle, what do you do? You just step over it. Now how will the computer know that an obstacle is knee high? The way Insomniac solved this problem was by having a designer go in and place identfiers on specific obsticales in the world and when an enemy encourters one of these identifiers, they would handle it accordingly. For example there is an enemy who is able to jump onto roof tops and there is another enemy who must go around. Both enemies use the same nav mesh, by placing identifiers around the world, and giving each AI a type, you could do a condition:

If (obstacleIdentifier == Building && agent.Type == roofJumper)

               agent.jumpOnRoof()

If (obstacleIdentifier == Building && agent.Type == roofJumper)
               agent.goAround()

Now ofcourse this is just a simple example, but hopefully it gets the point across.