## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

click on the bot to select it and you will be able to see the path it’s follow
-
ing shown as a series of red dots. Notice how the bot’s movement looks
okay as long as it sticks to positions along the navigation graph. Now
right-click on the bot again to “possess” it. Once possessed, you can
right-click anywhere else in the environment and the bot will attempt to
calculate a path to that point (as long as the point is located within a navi
-
gable area of the map). Observe how the bot has to backtrack to follow
certain paths.
Finely Grained Graphs
Poor paths and inaccessible positions can be improved by increasing the
granularity of the navigation graph. Figure 8.6 is an example of a very
finely granulated graph created for the Raven_DM1 map. Creating a graph
like this by hand is extremely tedious, so a flood fill algorithm is utilized
by the map editor to do the majority of the work. See the following sidebar
for further details.
Since finely grained graphs are similar in topology to tile-based navigation
graphs — and therefore present similar challenges to the AI programmer
— I’ll be using them as a basis to demonstrate the techniques described in
the remainder of this chapter. This way I hope to kill several birds with one
stone, and by the end of the chapter you’ll understand how to create an
agent capable of planning paths through any game environment, be it an
FPS, RTS, or RPG.
Practical Path Planning | 339
Figure 8.6. A finely granulated navigation graph
Using the Flood Fill Algorithm to Create a
To use the flood fill algorithm to create a navigation graph a single
“seed” node is first placed somewhere in the map. See Figure 8.7, top
left. The algorithm then “grows” a graph by expanding nodes and
edges outward from the seed in each available direction, and then
from the nodes on the fringe of the graph, until all the navigable area
is filled. The figure shows the first six iterations of such a process.
This is a similar sort of technique paint programs use to fill an
irregular shape, except instead of flooding a shape with a color the
editor uses the algorithm to flood a map with graph nodes and edges.
Individual nodes can then be moved, deleted, or added by the
designer to give the desired result. To ensure that an agent’s move
-
ment is unrestricted, during the process the algorithm ensures that all
nodes and edges are positioned a minimum distance equal to the
agent’s bounding radius from any walls.
340 | Chapter 8