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

GraphNode():m_iIndex(invalid_node_index){}
GraphNode(int idx):m_iIndex(idx){}
virtual ~GraphNode(){}
int Index()const;
void SetIndex(int NewIndex);
};
Because often you will require that a node contains additional information,
GraphNode is typically used as a base class from which to derive custom-
built nodes. For example, a navigation graph’s nodes must store spatial
information, and a dependency graph’s nodes must contain information
about the assets they represent.
A node class designed for use within a navigation graph might look
something like this:
template < class extra_info = void*>
class NavGraphNode : public GraphNode
{
protected:
//the node's position
Vector2D m_vPosition;
//often you will require a navgraph node to contain additional information.
//For example a node might represent a pickup such as armor in which
//case m_ExtraInfo could be an enumerated value denoting the pickup type,
//thereby enabling a search algorithm to search a graph for specific items.
//Going one step further, m_ExtraInfo could be a pointer to the instance of
//the item type the node is twinned with. This would allow a search algorithm
//to test the status of the pickup during the search. See Chapter 8 for further
//info.
extra_info m_ExtraInfo;
public:
/*INTERFACE OMITTED */
};
Please note that although the node class listed here uses a 2D vector to rep
-
resent a node’s position, a graph can exist in any number of dimensions
you like. If you are creating a navigation graph for a 3D game, simply use
3D vectors. Everything will work just the same.
The GraphEdge Class
The GraphEdge class encapsulates the basic information required to denote a
connection between two graph nodes. Here’s the code:
class GraphEdge
{
protected:
The Secret Life of Graphs
| 205
Implementing a Graph Class
//An edge connects two nodes. Valid node indices are always positive.
int m_iFrom;
int m_iTo;
//the cost of traversing the edge
double m_dCost;
public:
//ctors
GraphEdge(int from, int to, double cost):m_dCost(cost),
m_iFrom(from),
m_iTo(to)
{}
GraphEdge(int from, int to):m_dCost(1.0),
m_iFrom(from),
m_iTo(to)
{}
GraphEdge():m_dCost(1.0),
m_iFrom(invalid_node_index),
m_iTo(invalid_node_index)
{}
Occasionally it’s useful to be able to create a GraphEdge with either or both
indices set to an “invalid” (negative) value. The enumerated value
invalid_node_index found in the file NodeTypeEnumerations.h is used
here to initialize
From and To in the default constructor.
virtual ~GraphEdge(){}
int From()const;
void SetFrom(int NewIndex);
int To()const;
void SetTo(int NewIndex);
double Cost()const;
void SetCost(double NewCost);
};
If you are working on a platform where memory use is a much greater con
-
cern than the speed of searching a graph, you can get good savings on
cell-based graphs (or graphs of equal or greater density) by not explicitly
storing the cost of each edge. Instead, you can save memory by omitting
the cost field from the
GraphEdge class and calculate the cost “on-the-fly”
using a function of attributes of its two adjacent nodes. For example, if the
edge cost is equal to the distance between two nodes, the function would be
the Euclidean distance. Something like:
206 | Chapter 5
Implementing a Graph Class

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