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()
agent.goAround()
Now ofcourse this is just a simple example, but hopefully it
gets the point across.
