O'Reilly logo

Programming Game AI by Example by Mat Buckland

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

where each node represents a convex space (instead of a point). Figure 8.3
shows the map from Figure 8.1 partitioned in such a way.
Why is this a good thing? Well, navmeshes are efficient. The data structure
required to store one is compact and can be searched very quickly. In addi-
tion, where environments are constructed entirely from polygons — like
the majority of 3D FPS type games — it’s possible to use algorithms to
partition the walkable areas of the maps automatically.
The Raven Navigation Graph
Because they provide me with the greatest opportunity for demonstrating a
varied range of techniques, the navigation graphs for Raven maps are cre
-
ated using the POV method. You saw earlier how the navgraph shown in
Figure 8.1 was created by positioning nodes by hand inside a map editor. In
this example a small number of nodes have been positioned at important
intersections. Since each node is effectively representing a large spatial
region, this type of graph can be said to be coarsely granulated (or
grained). Coarsely granulated graphs are very compact data structures.
They use very little memory and are quick to search and relatively easy to
create, although they do have several limitations. Let’s take a look at some
of their faults.
Coarsely Granulated Graphs
If a game restricts its agents to movement along the edges of a navigation
graph only, such as the movement of the characters in the Pac-Man range
of games (see Screenshot 8.1), then a coarsely granulated navgraph is the
336 | Chapter 8
The Raven Navigation Graph
Figure 8.3. Raven_DM1 partitioned into a navmesh
perfect choice. However, if you are designing a navgraph for a game where
the characters are given more freedom, coarse graphs can be harbingers of
all sorts of problems.
For example, most RTS/RPG games use a control system where the user is
free to command characters to move to any navigable area of the map.
Normally this is done with a couple of mouse clicks, one to select the NPC
and another to select the position it should move to. To move the NPC into
position the AI must follow these steps:
1. Find the closest visible graph node to the NPC’s current location, say,
node A.
2. Find the closest visible graph node to the target location, say, node B.
3. Use a search algorithm to find the least cost path from A to B.
4. Move the NPC to node A.
5. Move the NPC along the path calculated in step 3.
6. Move the NPC from B to the target location.
If these steps are followed with a coarsely grained graph, such as the one
shown earlier, unsightly paths will regularly occur. See Figure 8.4 for an
example.
Some of these kinks can be ironed out using a path smoothing algo
-
rithm, such as the one discussed later in this chapter, but due to the
coarseness of the navigation graph there will still be many occasions where
an agent will zigzag unnaturally at the start and end points of a path. Even
worse, when using coarse graphs there are almost always a few positions
on the map to which there is no line of sight from any of the graph nodes,
effectively rendering those areas invisible to any path planner. Figure 8.5
illustrates two positions on the Raven_DM1 map that are inaccessible to
Practical Path Planning | 337
The Raven Navigation Graph
Screenshot 8.1: Pacmen at play
the path planner. These “invisible” areas are fairly easy to spot when test-
ing a small map, but are much harder to find as the complexity of a map
increases. This is reflected in a number of games that have been released
with such problems.
You can observe these problems first hand by running the Raven_
CoarseGraph executable. When the demo is run the bot will explore the
environment by creating paths to randomly selected graph nodes. Right-
338 | Chapter 8
The Raven Navigation Graph
Figure 8.4. The path of an agent moving from its current position to the one marked
by the X. (The closest node to the agent and the closest node to the target are shown
by a and b respectively.) Notice how the agent must double back on itself twice to get
to the target location. Nasty.
Figure 8.5. Map positions that are “invisible” to the navigation graph

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required