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

The downside to using cells as the skeleton for a navgraph is that the
search spaces can quickly become extremely large. Even a modest 100 x
100 cell map will need a graph made up of up to 10,000 nodes and 78,000
(or so) edges. Given that RTS games usually have dozens or even hundreds
of AI units active at any one time, with many of them requesting graph
searches each update step, that’s a hell of a lot of number crunching to be
done, not to mention the related memory cost. Fortunately there are a num
-
ber of methods available to ease the burden, which we’ll be taking a look at
later in the chapter.
Points of Visibility
A points of visibility (POV) navigation graph is created by placing graph
nodes, usually by hand, at important points in the environment such that
each graph node has line of sight to at least one other. Positioned carefully,
the graph nodes will make a graph connecting all the important areas in the
world geometry. Figure 8.1 shows a simple POV graph created for a Raven
map (Raven_DM1).
One feature of POV graphs is that they may be easily expanded to include
nodes that proffer information over and above the connectivity data. For
example, nodes can easily be added to a POV graph to represent good snip
-
ing, cover, or ambush positions. The downside is that if a game map is
large and complex the map designer can spend an awful lot of precious
development time positioning and tweaking the graph. A POV graph can
also be problematic if you plan to include any type of map generation fea
-
ture, since you must then develop some automated method to generate the
POV graph structure as well for the new maps to be of any use. (This is
334 | Chapter 8
Navigation Graph Construction
Figure 8.1. Points of visibility navigation graph

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