Computer science students are typically introduced to graph traversal early in their coursework. It’s also a topic often used as a talking point or whiteboard exercise during many engineering interviews. Outside of those contexts, it might be hard to find a non-contrived reason to brush up on graph traversal algorithms. I recently reacquainted myself while working on a game I’ve been building in my spare time. The game contains a galaxy map with interconnected star systems, and the player uses the map to calculate a flight path between those systems. This post discusses a depth-first search algorithm with path tracing used to build this feature.

Choosing an Algorithm

Selecting a method for traversing a graph involves two decisions. First, decide between depth-first versus breadth-first. A depth-first approach fully explores each branch before continuing on to the next one. A breadth-first method travels across each node on one level of the graph before moving on to the next. The choice between depth-first and breadth-first depends on the organization and expectations of the graph data. A depth-first search is more appropriate for graphs with very deep branches containing many nodes. In this application, the graph contains ten nodes with multiple potential paths between any two nodes. I selected a depth-first algorithm, but the graph is small enough that a breadth-first search would perform just as well.

The second question when selecting a graph traversal algorithm is iteration versus recursion. The trade off here is a question of complexity. Many people find recursion harder to reason about. The order that the nodes are traversed in can also vary slightly between the two methods. For this use case, I selected an iterative approach mostly because I can’t remember previously writing an iterative, depth-first search algorithm.

Finding the Destination

This implementation uses two data structures: A stack to keep track of the nodes to search, and an array containing a list of nodes that were already visited.

1
2
3
4
5

1. Pop the next node off the stack. This is the node currently being examined.
2. Mark this node as visited.
3. If this node is the destination, we're done!
4. If not, push each node adjacent to this one on to the stack unless it was already visited.
5. Go back to 1.

In plain English, that’s all it takes to traverse the graph for a desired destination. This is an iterative approach, but it’s worth noting that the only difference between this and a recursive implementation is the stack. In a recursive method, the stack is implied because it’s the call stack. Steps one and five then change slightly. Instead of looping and going back to the first step, call the same function again on the next adjacent node.

Leaving a Trail of Breadcrumbs

The algorithm returns the destination node, but that’s not particularly helpful for this use case. We already knew there was a path between the origin and destination because we designed the graph! The real value of this feature lies in showing a highlighted route to the player and storing it for future reference. As the player flies to subsequent systems, update the pointer to the head of the path to keep track of the current route. The full algorithm has one new step and one new data structure. The new data structure is a dictionary with keys and values that are both graph nodes.

1
2
3
4
5
6
7
8

1. Pop the next node off the stack. This is the node currently being examined.
2. Mark this node as visited.
3. If this node is the destination, we're done!
4. Otherwise, for each node adjacent to this one...
    4.1 Push the adjacent node onto the stack.
    4.2 Add the adjacent node to the path dictionary as a key if it does not yet exist.
        The value is the current node being examined.
5. Go back to 1.

Retracing Our Steps

Unwind the path dictionary by starting from the destination and retracing the path back to its origin. Record each node along the way in a new array, and the result will be a list of nodes in the traveled path.

1
2
3
4
5

1. Set X equal to the destination.
2. Add X to the array of nodes.
3. Set Y to the value of the path dictionary entry where the key equals X.
4. Set X equal to Y.
5. Repeat 2-4 until X equals the origin.

With an array of nodes representing the navigational path in hand, a route can be painted for the player on the screen and stored somewhere for future reference.

Real Code

The final implementation uses C# (this game is built in Unity). The definition of the GalaxyMapNode class is not shown – nor is the full listing for the class containing this method – but the few parts that are relevant can be discerned from context.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

private GalaxyMapNode[] DfsPath(GalaxyMapNode destination) {
        GalaxyMapNode   current = null;
        GalaxyMapNode   found   = null;
        GalaxyMapNode[] visited = { };
        GalaxyMapNode[] path    = { };

        Stack<GalaxyMapNode> stack                         = new Stack<GalaxyMapNode>();
        Dictionary<GalaxyMapNode, GalaxyMapNode> parentMap = new Dictionary<GalaxyMapNode, GalaxyMapNode>();

        stack.Push(currentPosition);

        while (stack.Count > 0) {
            current = stack.Pop();        // Pop the next node off the stack...

            if (current == destination) { // If this node is the destination...
                found = current;
                break;                    // ...we're done!
            }

            if (!ArrayUtility.Contains(visited, current)) {
                ArrayUtility.Add(ref visited, current);

                // For each adjacent node...
                foreach (GalaxyMapNode adjacent in current.GetAdjacentNodes()) {
                    stack.Push(adjacent);              // Push each one onto the stack.

                    if (!parentMap.ContainsKey(adjacent)) {
                        parentMap[adjacent] = current; // Add to the path dictionary.
                    }
                }
            }
        }

        current = found; // now we backtrack for the path

        while (current != currentPosition) {
            ArrayUtility.Add(ref path, current);
            current = parentMap[current];
        }

        ArrayUtility.Add(ref path, currentPosition);

        System.Array.Reverse(path);

        return path;
  }

Conclusion

This implementation of a depth-first iterative search is not optimal or perfect by any means. However, the size and structure of the graph is known, and perfect optimization isn’t necessary in order to meet the requirements.

If you enjoyed this post, please consider subscribing