Game Development Reference
In-Depth Information
Figure 9.3
Skulls of the Shogun
with its AI debug mode enabled to illustrate the
square grid it uses for pathfinding.
However, for a game with real-time action, NPCs generally don't move from
square to square on a grid. Because of this, the majority of games utilize either
path nodes or navigation meshes. With both of these representations, it is possible
to manually construct the data in a level editor. But manually inputting this data
can be tiresome and error prone, so most engines employ some automation in the
process. The algorithms to automatically generate this data are beyond the scope
of this topic, though more information can be found in this chapter's references.
Path nodes
first became popular with the first-person shooter (FPS) games re-
leased by id Software in the early 1990s. With this representation, a level designer
places path nodes at locations in the world that the AI can reach. These path nodes
directly translate to the nodes in the graph. Automation can be employed for the
edges. Rather than requiring the designer to stitch together the nodes by hand, an
automated process can check whether or not a path between two relatively close
nodesisobstructed.Iftherearenoobstructions,anedgewillbegeneratedbetween
these two nodes.
The primary drawback with path nodes is that the AI can only move to locations
on the nodes or edges. This is because even if a triangle is formed by path nodes,
there is no guarantee that the interior of the triangle is a valid location. There may
