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 noncontrived 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 depthfirst 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 depthfirst versus breadthfirst. A depthfirst approach fully explores each branch before continuing on to the next one. A breadthfirst method travels across each node on one level of the graph before moving on to the next. The choice between depthfirst and breadthfirst depends on the organization and expectations of the graph data. A depthfirst 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 depthfirst algorithm, but the graph is small enough that a breadthfirst 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, depthfirst 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 

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.
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 

Conclusion
This implementation of a depthfirst 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