Game Development Reference
In-Depth Information
always ask me. I frequent the Game Coding Complete forums quite often. The code
lives in pathing.h and pathing.cpp in the Dev\Source\GCC4\AI\ directory.
Keep in mind that this is by no means the only way to navigate through the world.
Remember, the key to successful navigation is to simplify the agents
view of the
world so you can cut down on how much you have to process. A few hundred or
even a few thousand pathing nodes are much faster to process than trying to deal
with world geometry at runtime.
Another very common technique is something called a navigation mesh, which is a
simple mesh that can be built by the artists or designers and represents the walk-
able terrain. The concept is really no different than the graph above. The center of
each triangle is a node, and the edges that connect to other triangles are the arcs.
There will probably have to be a bit more smoothing involved or else the paths
may not look good, but if your meshes are dense enough with decent tolerances,
it may not be much of an issue. Game Programming Gems has an article called
“
'
that serves
as a great introduction to using navigation meshes if you find yourself interested
in learning more.
Simplified 3D Movement and Pathfinding Using Navigation Meshes
”
Most of the time, you
ll probably want to have multiple agents all navigating through
the world at once. What happens if two or more agents are trying to hit the same
node at the same time? What about two agents coming toward each other along the
same arc? Figure 18.5 shows exactly what could happen.
The simplest solution to both of these issues is to turn off the node or arc in ques-
tion. As soon as an agent starts traveling down an arc, give it exclusive access to that
arc. If another agent happens to reach a point in its path where it has to travel down
that same arc in the opposite direction, force it to replan from its current node to its
target node, ignoring that particular arc.
The above scenario works well for relatively open areas, but what happens when your
agents are in a confined space such as an office building? When I worked on Rat
Race, we had this exact problem. There were over a dozen agents in a small office
building, all pathing around the world. It was okay most of the time, but there were
several choke points where it all just broke down, like the stairwell. The solution to
this problem was to implement a dynamic avoidance algorithm. Each agent was
given a personal comfort radius around it. If another agent entered that radius and
they were both moving, they would calculate how much they had to turn to avoid
'
