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
1 2 3 4 5
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
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
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.
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
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