 Each “1” represents a connection between two nodes, and each “0” repre
-
sents the lack of a connection. By reading the values directly off the matrix
from Figure 5.12, we know that there is no connection from node 2 to 6,
but there is an edge connecting 4 to 2.
Adjacency matrices are intuitive, but for large sparse graphs this type of
representation is inefficient as most of the matrix is used storing unneces
-
sary zero values. A much better data structure for sparse graphs (the most
commonly occurring graphs in game AI) is the adjacency list.
For each node present, an adjacency list graph stores a linked list of all
its adjacent edges. Figure 5.13 shows how this works for the previous
example.
Adjacency lists are efficient for storing sparse graphs because they don’t
waste space storing null connections. The amount of space required to store
a graph using this type of data structure is proportional toN+E(number
of nodes + number of edges), whereas for an adjacency matrix it is propor
-
tional to N
2
(number of nodes squared).
As most of the graphs you will come across in AI game development are
sparse, an adjacency list will frequently be your data structure of choice.
With this in mind let’s take a look at the source code required to implement
such a graph.
The GraphNode Class
GraphNode encapsulates the minimum information a node requires for an
adjacency list graph representation: a unique identifying number, or index.
Here’s the listing of the graph node declaration:
class GraphNode
{
protected:
//every node has an index. A valid index is >= 0
int m_iIndex;
public:
204 | Chapter 5
Implementing a Graph Class
Figure 5.13. An adjacency list representation of the digraph from Figure 5.6

Get Programming Game AI by Example now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.