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,
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
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