Solving mazes with Depth-First Search
Background/Interest
The inspiration for this article came from one of the many labs I did during my Data Structures and Algorithms II course at The University of Tennessee, Knoxville. The mazes lab, in particular, helped reignite my passion for computer science and programming. Up till this point, I had always enjoyed CS but a lot of the course work felt rooted in theory. This lab was the first my first taste of application, as I was able to implement and see a traversal algorithm at work.
It amazed me to see how we were able to implement an algorithm to solve a pretty straight forward maze like the one in figure 0. What really blew me away though was the fact that the same algorithm, if implemented well, could be used to solve a much much large maze-like the one shown in figure 1. Up till this point, I always understood that code should take into account and be written in a scalable manner but I always assumed that writing scalable code would be super hard to read/write. Turns out it actually wasn’t that hard! Writing up this lab was a truly satisfying experience and I hope to share some of that excitement with y’all. Let’s get started!
Depth-First Search
In order to figure out how to traverse a maze through code, we first need to understand what depth-first search is. Depth-first search (sometimes referred to in this article as DFS) is a graph/tree traversal algorithm that follows a path as far as it can until it either, reaches the goal or has nowhere else to go. It’s almost like running as far as you can in one direction until you hit a wall. Hopefully that analogy helps clear up any lingering confusion. You might even be starting to see how we can use Depth-First Search to solve a maze!
Before we dive into the algorithm itself there are a few things we need to understand about depth-first search first. There are many approaches and styles to implementing a depth-first search algorithm and a lot of those implementation choices will entirely depend on the problem you’re trying to solve. So first let's define some assumptions. These assumptions may seem really straight forward but they’re really important in helping us come up with a solution to solve our maze.
Assumptions
Each maze has a starting point and an ending point.
This assumption is mostly for simplicity’s sake. We could handle edge cases all day. Like how there may not be any path that leads to an exit in the maze but that isn’t the point of this article. Instead, we’re going to keep our constraints as close to an actual maze as possible. Surely an actual maze would have an exit. :)
Mazes are composed of walls.
These walls will be considered untraversable. This means we, unfortunately, can’t code our solution in a way that bypasses walls. So unless we’ve recently found a way to walk through matter, we’ve defined a constraint. Therefore, we need to find some way to alert the computer where walls exist or rather what paths are available at any given point in the maze.
We only care about finding the first available path through the maze.
This third and final assumption we’re making may seem a bit shocking but it’s important to understand that in our implementation of DFS we aren’t concerned with finding the shortest path. We only care that there is a path and that we’re able to return in. If you’re interested in learning about shortest path algorithms like Dijkstra’s here’s a link.
Steps of Depth-First Search
Alright! Now that we have our assumptions clearly written down let’s get started with an example of DFS!
The structure in figure 2 is one way to represent a graph. There are many ways to represent graphs but for this example, we’re only concerned with the fact that our graph contains nodes and edges.
Nodes, shown as the gray squares with numbers, hold all the data that we care about. The numbers on the nodes represent ID’s these ID’s are powerful as they are unique for every single node and provide a lot of utility we’ll use to solve our maze. The visited property defines a way that we can determine if we’ve seen a node already. That way we aren’t traversing over nodes multiple times.
Edges are what link nodes together. If there is no edge between two nodes like in the instance of node3 — node 5 we can go back to our second assumption(mazes have walls) and use no edge as an indication that we can’t travel in that direction aka a wall is there!
The Call Stack, represented as that elongated rectangle in the diagram, is a structure under the hood. The stack piles function calls, in our case node calls, and shows us what point we are at in the execution of the program. The stack is also what will ultimately give us the power to return a path from the graph!
Traversing
That was a lot of terminology! Still with me? Now let’s start running Depth-First search and traverse our graph. Remember the first assumption? Graphs typically don’t have a designated starting point but in order to perform DFS, we have to start somewhere so we’ll start with Node 1.
Step 1
What’s happing in figure 3 is that we call DFS on Node 1 which puts it on the call stack. We mark Node 1 as visited so that we don’t accidentally evaluate the node again as that could lead to us never finding a path! We then check to see if Node 1 is equal to the node we’re looking for (Node 6.) It isn’t so we move on to Node 1’s adjacency list. Every node holds a list of references to all nodes that they are connected to. So we see that Node 2 is connected to Node 1 and move on to the next step!
Step 2
After looking at Node 1’s adjacency list we end up evaluating Node 2. The steps are similar we mark the node as visited, then check to see if it’s equal to the node we’re looking for. It’s not so we call DFS on Node 2 to go even deeper into the graph.
Now we look at Node 2’s adjacency list. Visually, we can see that Node 2 is connected to node 1, 0, 3 and 4. That’s four edges meaning four different paths we can take. So how do we choose? Well, in all honestly, the actual node we choose doesn’t matter. The order is entirely dependent on how we stored our nodes in the adjacency list. For completeness sake I’ll show how it works for all of them. We’ve already visited Node 1 so that’s off the table. Let’s start with Node 0.
Step 3
Now that we’ve moved onto Node 0 we go through the same routine as before. We mark it as visited, check if it’s equal to Node 6 and then call Depth-First Search on Node 0 to try and move deeper into the maze. However, you may have noticed that the only connector Node 0 has is to Node 2 which we’ve already visited. So what happens now? Well, when we call DFS on Node 0 we’ve hit a point where we can’t go further down a path so no more function calls (nodes) are added to the stack. Instead, we have to do something called backtracking.
Step 4
So I threw another term at you, backtracking. The call stack works by evaluating function calls. It’s sort of a nested structure.
Node 1 and Node 2 are still on the stack because they are still part of a potential path. Once we hit Node 0 though no other paths exists. This means we’re done with the DFS call on Node 0 and hence we have to backtrack to Node 2 in order to progress deeper in the structure. So we look at the next node in 2’s adjacency list and begin to evaluate Node 3.
Step 5
Now we do more of the same. We end the DFS call on Node 3 and thus removing it from the stack. We hop back to 2’s adjacency list and begin to evaluate Node 4. We notice that Node 4 is connected to another node we haven’t traversed yet and begin the DFS cycle again!
Step 6 and Step 7
Much like before for figures 8 and 9 we visit, compare and call DFS on each node. Only once we hit Node 6 does our goal check finally become true! Now if you look at the call stack in figure 9 you’ll notice that it contains a path from Node 6 all the way to Node 1( 6 → 5 → 4 → 2 → 1.)All that thanks to backtracking! Now that the function has finally evaluated to true we can begin to remove all our DFS calls from the stack and print off the values. Thus giving us our path!
Cool, what about the maze thing?
What we did above with DFS is exactly how we’ll solve our maze.
For instance, take the maze shown in figure 10 we can take this maze and break it down into rows and columns. Once we do that we can start to see a grid form, represented by the pink dotted squares. By now I’m sure you can see where I’m going with this. We can represent each box in the grid as a node and the lack of a wall as an edge!
Once we abstract the image enough, we end up with something like figure 10! Very similar to the graph of the traversing exercise we went through.
Conclusion
By now I’m sure you understand exactly how our traversal algorithm could generate the path shown in figure 11. Which is just one of a couple of available paths. We learned about some graph theory, depth-first search, the call stack and how all of it applies to finding a path through a maze. I hope y’all enjoyed reading this article as much as I enjoyed writing it!
Resources
For another cool take on backtracking check out my friend and fellow classmate article where he uses backtracking to solve a Sudoku puzzle!
Whimsical to create the visualizations.
