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

//returns true if the graph is directed
bool isDigraph()const;
//returns true if the graph contains no nodes
bool isEmpty()const;
//returns true if a node with the given index is present in the graph
bool isPresent(int nd)const;
//methods for loading and saving graphs from an open file stream or from
//a filename
bool Save(const char* FileName)const;
bool Save(std::ofstream& stream)const;
bool Load(const char* FileName);
bool Load(std::ifstream& stream);
//clears the graph ready for new node insertions
void Clear();
//iterators clients may use to access nodes and edges
class ConstEdgeIterator;
class EdgeIterator;
class NodeIterator;
class ConstNodeIterator;
};
From the information in this section you have learned that graphs are a
powerful tool to have at your disposal. However, the graph data structure
alone has few uses. Much of the power of graphs is only realized when
they are operated upon by algorithms designed to explore them, either to
find a specific node or to find a path between nodes. The rest of this chap-
ter is devoted to a study of several of those algorithms.
Graph Search Algorithms
Graph theory has been a popular area of study of mathematicians for many
years and numerous algorithms have been devised to search and explore a
graph’s topology. Among other things, by utilizing search algorithms it is
possible to:
n
Visit every node in a graph, effectively mapping out the graph’s
topology.
n
Find any path between two nodes. This is useful if you want to find a
node but you don’t really care how you get there. For example, this
type of search can be used to find one (or more) of the solutions to
the Towers of Hanoi puzzle.
n
Find the best path between two nodes. What is “best” depends on the
problem. If the graph to be searched is a navgraph, the best path may
be the shortest path between two nodes, the path that takes an agent
between two points in the fastest time, the path that avoids enemy
line of sight, or the most quiet path (à la Thief). If the graph is a state
The Secret Life of Graphs | 209
Graph Search Algorithms

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