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

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 time-saver. 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

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