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

//get a reference to the node at the given node index
const graph_type::NodeType& node = G.GetNode(CurrentNodeIdx);
//if the extra info field is pointing to a giver-trigger, test to make sure
//it is active and that it is of the correct type.
if ((node.ExtraInfo() != NULL) &&
node.ExtraInfo()->isActive() &&
(node.ExtraInfo()->EntityType() == target) )
{
bSatisfied = true;
}
return bSatisfied;
}
};
Armed with this termination condition and the customized Dijkstra search
algorithm, it’s a simple matter to find the path with the least cost to an
active item of a specific type. Let’s say you want to find the closest health
pack to the graph node with index 6. Here’s how:
typedef FindActiveTrigger<Trigger<Raven_Bot> > term_con;
typedef Graph_SearchDijkstra_TS<RavenMap::NavGraph, term_con> SearchDij;
//instantiate the search
SearchDij dij(G, //the graph
6, //the source node
type_health); //the item type we are searching for
//grab the path
std::list<int> path = dij.GetPathToTarget();
where type_health is an enumerated value.
Ü
3D NOTE By now I hope you understand there is no difference between
pathfinding in 3D and pathfinding in 2D. Sure, for an agent to get around in
most 3D environments it might have to do stuff like jump ravines and use lifts,
but these considerations should be transparent to a path planner. They simply
manifest themselves as edge cost adjustments so that the search algorithm can
account for the cost of doing the jump, traversing the ledge, using a lift, or
doing whatever when it is searching for the least cost path to a target position.
If this is still not evident, I strongly recommend you backtrack and reread Chap
-
ter 5 while keeping in mind that a graph may exist in any number of
dimensions.
Paths as Nodes or Paths as Edges?
So far we’ve been thinking about paths as a series of position vectors, or
waypoints. Often though, paths comprised of graph edges give the AI pro
-
grammer additional flexibility. As an example, let’s consider a game with
NPCs that must have their movement between certain points in the envi
-
ronment constrained to a specific type such as “tiptoe across here,” “crawl
under here,” or “run quickly here.” You may think that the game’s relevant
navgraph nodes could be annotated with flags indicating the desired
348 | Chapter 8
Paths as Nodes or Paths as Edges?
behavior (for example, a node could be tagged with the “tiptoe” behavior
to make an agent start tiptoeing as soon as it reaches that node), but in
practice there are problems with this approach.
For example, Figure 8.10 shows part of a navgraph where one of the
edges,A-B,traverses a river. The game design requires that agents must
change to the “swim” behavior when traveling from A to B (or vice versa),
so the nodes A and B are annotated to reflect this. Let’s say an agent is fol
-
lowing the pathe-A-B-h.When the agent reaches node A its behavior
will change to swimming and it can cross the edge to B safely. So far so
good, but unfortunately at this point it runs into problems. When it reaches
node B, which is also annotated with the swim behavior, it will continue
swimming along the edgeB-h.Notgood. If this isn’t bad enough, let’s say
an agent wants to follow the pathe-A-c.Assoon as it reaches A it will
still start swimming even though it has no intention of crossing the river!
This problem can easily be resolved, however, if the graph edges are anno
-
tated instead of the nodes. This way an agent can easily query the edge
information as it follows the path and change behavior accordingly. Given
the previous example this means that the edgeA-Bisannotated with the
instruction to swim and all the other edges with the instruction to walk (or
whatever else might be appropriate). Now, when an agent follows the path
e-A-B-hitsmovement will be correct.
z
TIP Using annotation you can easily specify edge behavior that is modified dur
-
ing gameplay. For instance, you could design a map that has a makeshift bridge
— like a fallen log — crossing a stream, which agents traverse normally until
the bridge is destroyed or moved. When the bridge is removed, the annotation
of the edge is changed to “swim” and its cost increased to reflect the additional
amount of time required to move along it. In this way, agents still consider the
Practical Path Planning
| 349
Paths as Nodes or Paths as Edges?
Figure 8.10. A navgraph spanning a river

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