Graph search algorithms like Dijkstra’s Algorithm and A* work on weighted directed graphs, sets of nodes connected by edges that have numeric weights (movement costs) attached to them. Can they also work on grids? Yes: a grid can be viewed as a special case of a graph.
This article is an introduction to the parts of graph theory we use in graph-based pathfinding algorithms, and how grids are represented.
Properties of graphs#
A graph-based pathfinding algorithm needs to know what the locations are and also which locations are connected to which other ones. You typically know a lot more than this, like the size and coordinates of the locations, but the algorithm doesn’t actually know about these aspects. It only knows what the connections are.
A mathematical graph is a set of nodes and edges. The nodes (also called vertices or objects) are connected together by the edges (also called links or connections or arrows or arcs). For any graph we need to know two things:
- Set of nodes in the graph
- Set of edges from each node
What does the above graph look like?
- Set of nodes: .
- Set of edges from each node:
Note that the layout of the graph is not part of the graph. The graph in the above diagram and the graph shown below are the same graph:
Try it for yourself: make a list of the nodes in the graph, and then make a list of the edges connected to each node. You’ll get the same answer for both diagrams.
Graph search algorithms don’t really “understand” the layout or properties of a grid. They only understand the connectivity. Pathfinding algorithms that can harness the additional properties of a grid can run more quickly than regular A*. I’ll explore that in another article.
Let’s see how to encode a grid in graph form.
Grids in graph form#
When working with a square grid, we need to make a list of nodes. We aren’t limited to rectangles, but for simplicity, here’s the code for a 20x10 rectangle:
all_nodes = [] for x in range(20): for y in range(10): all_nodes.append([x, y])
The edges are going to be the four directions: east, north, west, south. For any node we need to know the other nodes connected to this one by an edge. We call these neighbors:
def neighbors(node): dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]] result = [] for dir in dirs: result.append([node[0] + dir[0], node[1] + dir[1]]) return result
If your game allows diagonal movement, you’ll have eight entries in dirs.
However, we want to return only the nodes that we can move to, so we’ll add a check:
def neighbors(node): dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]] result = [] for dir in dirs: neighbor = [node[0] + dir[0], node[1] + dir[1]] if neighbor in all_nodes: result.append(neighbor) return result
An alternate way to check is to make sure the coordinates are in range. This only works if the map is rectangular. Here’s code for the 20x10 map we generated earlier:
def neighbors(node): dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]] result = [] for dir in dirs: neighbor = [node[0] + dir[0], node[1] + dir[1]] if 0 <= neighbor[0] < 20 and 0 <= neighbor[1] < 10: result.append(neighbor) return result
In practice, we will want to annotate the graph with additional information, such as whether you can walk over a square.
Variants#
I glossed over how edges are handled. In graph theory, there are several ways to handle edges:
- An undirected graph has edges that go in both directions. This is pretty common for game maps. In the example earlier, each undirected edge such as B↔C was listed twice, once as B→C and once as C→B.
- A directed graph has edges that can go one direction but not the other. One-way doors, jumping off a ledge, and portals can be one way edges in games. A graph can have edge B→C without having edge C→B.
- A multigraph can have multiple edges between the same nodes. Being able to swim across a river or take a raft across the same river is an example in games. Node B could have more than one edge B→C leading to node C.
In addition, you can annotate nodes and edges with extra information. One annotation that shows up often in pathfinding algorithms is edge weights. A weighted graph allows numeric weights on each edge. In a weighted undirected graph, we might mark a paved road as weight 1 and a twisty forest path as weight 4 to make the pathfinder favor the road. In a weighted directed graph, we might mark downhill edge B→C with weight 2 and mark uphill edge C→B with weight 5 to make it easier to walk downhill.
Obstacles#
How do we represent a grid’s obstacles in a graph form? There are three general strategies:
- Remove nodes. If obstacles occupy grid squares, you can remove those nodes from the graph (all_nodes). You also need to remove the corresponding edges, which happens automatically if you’re using “
if neighbor in all_nodes” to test whether an edge is added, but not if you’re testing whether x/y are in range. - Remove edges. If obstacles occupy the borders between squares, you can remove those edges from the graph by adding an additional check in the
neighbors()function. If obstacles occupy the squares, you can remove the edges that lead to those squares. - Infinite weight edges. If obstacles occupy the borders between squares, you can mark those edges with Infinity as the weight. If obstacles occupy the squares, you can mark edges leading to obstacles as having Infinity as the weight. In your graph search function, you’ll have to exit before visiting nodes with Infinity as the cost.
Altering the weights may be easier if you want to change the obstacles after the graph is constructed.
More#
Why do I keep using grids with my pathfinding tutorials? Because they’re easy to use, and were incredibly common back when I started working on games. They work with graph-based pathfinding algorithms. I plan to build some demos of non-grid pathfinding graphs too, but grids are easier to explain.
I didn’t cover alternate representations of edges. I typically use a list of edges per node, but you could also use a global set of edges, or a matrix representation that keeps track of which pairs of nodes have an edge between them. Read more on Wikipedia[1].
I also didn’t cover graphs for other uses in games. Although graph search is an obvious match for pathfinding on maps, you can also use it for lots of other problems. You could represent rooms (nodes) and hallways (edges) in a dungeon exploration game. You could represent players (nodes) and their friendships (edges) in a social game. You could represent possible behaviors as a graph[2] and then search over it to decide which behavior to execute. You could represent all possible board configurations as nodes[3] and game moves as edges and then search over a portion of it to decide how to move. You could represent an NPC’s state as a node[4] and the actions as edges. You could represent conversation topics in an NPC dialog database. You could use graphs for generating rivers and roads in a map generator[5]. You could represent your game’s economy as a graph, with wheat and bread as nodes and baking as an edge. 3D polygonal meshes can also be viewed as graphs. Graphs are a neat abstraction. If you can make your data look like a graph, you can reuse a wide variety of graph algorithms.
There’s lots more written about graphs and graph theory. Plus magazine[6] has lots of links to interesting uses of graphs and Wikipedia[7] may also be a reasonable starting point.