Practical Path Planning
ou saw in Chapter 5 how navigation graphs can be utilized by agents
to plan paths between locations in the environment. However, when it
comes down to implementing that theory in practice, you’ll find there are
all sorts of problems to overcome before your agents start moving around
like you want them to. This chapter addresses many of the practical issues
encountered when designing the path planning module(s) of game agents.
Although the demos in this chapter are based around the Raven framework,
most of the techniques are applicable across a wide range of game genres.
Navigation Graph Construction
To determine a path from A to B using a search algorithm such as those
discussed in Chapter 5, a game environment must be partitioned into a data
structure the algorithms can explore: a navigation graph. Because there are
many ways of representing the geometry that makes up a game world —
tile-, vector-, or polygon-based for example — it’s hardly surprising there
are numerous methods of converting the pertinent spatial information into a
graph-like data structure. Let’s examine several of the popular methods uti-
lized in modern games.
Tile- or cell-based games like those found abundantly in the RTS and war
game genres have large and sometimes complex environments based on
squares or hexes. It therefore makes sense to design the game’s navigation
graph around these cells: Each graph node represents the center of a cell,
with the graph edges denoting the connections between adjacent cells. In
games of this type there will occasionally be a cost for maneuvering a
game unit — like a tank or soldier — across the varying types of terrain.
Water and mud are, after all, much more difficult for a Sherman tank to
cross than tarmac or compacted earth. Since each cell is normally assigned
a specific terrain type by the map designer, it’s a trivial matter to use this
information to weight the edges of the navigation graph accordingly. The
algorithms employed to search the graph can make use of this additional
information to determine appropriate paths through the terrain, ones that
avoid water and mud or go around hills rather than over the top of them.