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

edge when planning paths and will modify their animation appropriately when
they traverse it. (You could even remove/disable the edge to represent condi
-
tions making the stream impassable, like a flood.)
An Annotated Edge Class Example
An annotated edge is easily created by deriving from GraphEdge and adding
an additional data member to represent the flag (or flags, depending on
what sort of information you’d like the edge to represent). Here’s an
example:
class NavGraphEdge : public GraphEdge
{
public:
//enumerate some behavior flags
enum BehaviorType
{
normal = 1 << 0,
tippy_toe=1<<1,
swim = 1 << 2,
crawl = 1 << 3,
creep = 1 << 4
};
protected:
//the behavior associated with traversing this edge
BehaviorType m_iBehavior;
/* EXTRANEOUS DETAIL OMITTED */
};
z
TIP If your game design requires edge and/or node annotation you will often
find that the extra fields in the node/edge classes are unused (or set to “nor
-
mal”) for the majority of instances in the navgraph. This can be a significant
waste of memory if your graph is large. In such cases I recommend you use a
hash-map type lookup table or, in the case where there is a large amount of
annotation per instance, create a special data structure that each edge or node
can store a pointer to.
Modifying the Path Planner Class to Accommodate
Annotated Edges
To accommodate edge annotation, the path planner and search algorithm
classes must be modified to return paths that contain the additional infor
-
mation. To facilitate this, Raven makes use of the
PathEdge class — a
simple data structure that stores node position and edge annotation infor
-
mation. Here is its listing:
class PathEdge
{
private:
350 | Chapter 8
Paths as Nodes or Paths as Edges?
//positions of the source and destination nodes this edge connects
Vector2D m_vSource;
Vector2D m_vDestination;
//the behavior associated with traversing this edge
int m_iBehavior;
public:
PathEdge(Vector2D Source,
Vector2D Destination,
int Behavior):m_vSource(Source),
m_vDestination(Destination),
m_iBehavior(Behavior)
{}
Vector2D Destination()const;
void SetDestination(Vector2D NewDest);
Vector2D Source()const;
void SetSource(Vector2D NewSource);
int Behavior()const;
};
The Raven_PathPlanner::CreatePath methods and the corresponding search
algorithms are altered slightly to create
std::lists of PathEdges. Here’s the
listing of the modified
CreatePathToPosition method with the changes in
bold.
bool Raven_PathPlanner::CreatePathToPosition(Vector2D TargetPos,
std::list<PathEdge>& path)
{
//if the target is unobstructed from the bot's position, a path does not need
//to be calculated, and the bot can ARRIVE directly at the destination.
if (!m_pOwner()->GetWorld()->isPathObstructed(m_pOwner->Pos(),
TargetPos,
m_pOwner->BRadius()))
{
//create an edge connecting the bot's current position and the
//target position and push it on the path list (flagged to use the
//"normal" behavior)
path.push_back(PathEdge(m_pOwner->Pos(), TargetPos, NavGraphEdge::normal));
return true;
}
//find the closest unobstructed node to the bot's position.
int ClosestNodeToBot = GetClosestNodeToPosition(m_pOwner->Pos());
if (ClosestNodeToBot == no_closest_node_found)
{
//no path possible
return false;
}
Practical Path Planning | 351
Paths as Nodes or Paths as Edges?
//find the closest visible unobstructed node to the target position
int ClosestNodeToTarget = GetClosestNodeToPosition(TargetPos);
if (ClosestNodeToTarget == no_closest_node_found)
{
//no path possible
return false;
}
//create an instance of the A* search class.
typedef Graph_SearchAStar<Raven_Map::NavGraph, Heuristic_Euclid> AStar;
AStar search(m_NavGraph, ClosestNodeToBot, ClosestNodeToTarget);
//grab the path as a list of PathEdges
path = search.GetPathAsPathEdges();
//if the search has been successful add the first and last edges manually to
//the path
if (!path.empty())
{
path.push_front(PathEdge(m_pOwner->Pos(),
path.front().GetSource(),
NavGraphEdge::normal));
path.push_back(PathEdge(path.back().GetDestination(),
TargetPos,
NavGraphEdge::normal));
return true;
}
else
{
//no path found by the search
return false;
}
}
A bot can now easily query the annotation of path edges and make appro
-
priate behavior adjustments. In pseudocode, each time a bot pops a new
edge of the list it does something like this:
if (Bot.PathPlanner.CreatePathToPosition(destination, path))
{
PathEdge next = GetNextEdgeFromPath(path)
switch(next.Behavior)
{
case behavior_stealth:
set stealth mode
break
case behavior_swim
set swim mode
break
etc
352 | Chapter 8
Paths as Nodes or Paths as Edges?

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