why some games don’t have random map generation features.) One solu

tion for this problem, however, is to use expanded geometry techniques.
Expanded Geometry
If a game environment is constructed from polygons it’s possible to use the
information present in those shapes to automatically create a POV graph,
which, for large maps can be a real timesaver. This is achieved by first
expanding the polygons by an amount proportional to the bounding radius
of the game agents. See Figures 8.2 A and B. The vertices defining this
expanded geometry are then added as nodes to a navigation graph. Finally,
an algorithm is run to test for line of sight between the vertices, and edges
are added to the graph appropriately. Figure 8.2 C shows the finished navi

gation graph.
As the polygons are expanded by an amount not less than an agent’s
bounding radius, an agent can search the resulting navigation graph to cre

ate paths that safely negotiate the environment without bumping into walls.
NavMesh
One approach growing in popularity with game developers is to use a net

work of convex polygons, called a navmesh, to describe the walkable areas
of a game environment. A convex polygon has the valuable property that it
allows unobstructed travel from any point in the polygon to any other. This
is useful because it enables an environment to be represented using a graph
Practical Path Planning  335
Navigation Graph Construction
Figure 8.2. Creating a POV using expanded geometry