Graphs are mostly used for navigating the agents in the game scene. Thanks to graphs and graph search algorithms, the agents can find the best path (“best” here can mean the shortest, the one with the most score points, etc.) between two points and the agents can travel.

In graph terminology, the waypoints are called nodes and the footpaths connecting them are called edges (Figure 1).

Graphs can be used to represent any kinds of networks, from telephone networks to the World Wide Web, electronic circuits and artificial neural networks. In a game, the graph can represent locations and paths among them as mentioned above, or a “tech-tree” (dependency graphs) for indicating the resources required to upgrade each unit, and so on.

Graphs can be either connected or unconnected. A graphs is considered as connected if it is possible to trace a path from every single node to every other. For example, the graph in Figure 1 is a connected graph.

A graph can be formally defined as the set of nodes linking
with the set of edges:

G = { N, E }

where G is the graph, N is the nodes, and E is the edges.

Many graphs have weighted edges representing the cost of moving from one node to another. These weights can be imagined as the distance between the points (nodes) or required resources as in the “tech-tree”.

The ratio between the edges and nodes indicate whether a graph is sparse or dense (Figure 2). Sparse graphs have fewer connections per node then the dense graphs have. Sparse graphs are preferred in game developments since they require fewer CPU and memory usage. This may also affect the algorithm or data structure that will be used. For example, knowing whether a graph is dense or sparse is helpful when appropriate data structure and algorithm for path planning.

Sometimes you need to implement a graph where the connections are directional.We can reflect this information using a graph called a digraph, or DAG for short.

A digraph has edges that are directed, or one way. The nodes that define a directed edge are known as an ordered pair and specify the direction of the edge. For example, the ordered pair 5-3 indicates that it is possible to travel from node 5 to node 3, but not from node 3 to 5.

Adjacency matrices and adjacency lists are two common data structure to implement graphs.

Adjacency matrices use a two-dimensional matrix (2d-array). Type of the matrix depends on your need. If you only need the graph’s connectivity information, then it is better to have a matrix of bools or int. If there is a cost associated with traversing an edge, then it would be better to have a matrix of floats.

Adjacency matrices are inefficient for large sparse graphs since most of the matrix is used storing unnecessary “zero” values. In such cases, it is better to use adjacency list. An adjacency list graph stores a linked list of all its adjacent edges.

Since adjacency lists do not waste space to store null connections, they are more efficient for sparse graphs. The amount of space required to store
a graph is proportional to

N + E

where N is the number of the nodes, and E is the number of the edges. This would be N^2 for an adjacency matrix to store the same graph.

You can find sparse graph implementation on my GitHub page.

You can check Mat Buckland’s book if you feel you need more details.