Pathfinding
Have you ever gone on Google maps or Wazes to get directions from your house to a restaurant before Covid-19?
Well that is one of the examples of the use of pathfinding algorithms. Pathfinding algorithms are used to find the shortest way from a starting point to a destination. This is a common programming algorithm that has many different types of solutions that would depend on the goal of the problem and the type of maze that it is used on.
Goals
If you are still here and was expecting to be able to understand how Google uses Pathfinding algorithms work in Google maps or other navigation applications, then this article will not be for you. I will be explaining one of the most common pathfinding algorithm depth-first search. This algorithm will start from the start point and iterate all of the given paths until they reach the goal.
Understanding the Graph
Before explaining DFS, I will have to explain the graph that we will be working on. Starting from a simple 3x3 grid, ‘1’ will be the path that we are trying to traverse, while ‘0’ are paths that we can not cross. The starting point will be the top left corner and the end point will be the bottom right corner. While currently it is a simple 3x3 and a preset starting and ending point. It is work for the current example and can be scaled later.
So how do we get to the exit?
Well we will have to go right once, down twice, and right once right?
Well you are right if this is not programing, but giving simple directions. In programming you will have to check every path to see you can traverse it. If you can traverse down a certain path then you go to it and check all the paths again. This is repeated until you reach the end point. Now let’s make it harder:
This is the same as before except it is a 5x5 grid. The start and end points are the same being in the top left corner and the bottom right corner. Using this grid we can finally talk about DFS.
Depth-first Search will start at the root, the starting point, and check it’s children nodes to see if it is a ‘1’, if it can it will go to it. So now we are on the second ‘1’ on line 4. Now we see if there is a ‘1’ connecting to it that we can travel down. This seems familiar doesn’t it? Well it is the same as what we have done for the 3x3 grid. So we will do this until we get to the ‘1’ on the 5th row 3rd column. This is where DFS comes in, depth first search will travel down each path as far as possible and if it can not go down anymore it will backtrack and take a different path. So using the 5x5 grid it will travel down the right path until it can’t find another way forward before it will start going on the downward path.
Another way I can explain Depth-First Search is imagine you are stuck in a maze and you reached a cross-road in the maze, like the image above. Which path will you choose? Well in this case it does not matter which path you choose, but you will go down that path and hope that it leads you to the exit. If you hit a dead-end then go back to the cross-road and take the path you did not choose.
Now let’s talk about a scenario where there are more than one path to then end and the paths are connected.
In this case, if DFS will check both paths when it reaches the first crossroad on line 7 column 2. For the sake of this example, let go down the bottom path. When it reaches the line 9 column 4 comes across another cross road, one that leads to the end and another that leads back to the beginning. When you are using DFS, it will always go down all available paths whether or not it is the correct one. So, the path leading to the right is the correct one, but what about the path heading up. If you follow that path it will lead you back to first crossroad with the option to go up or down. When you follow the path down, you reach the same crossroad as before, with the option to go up. Do you see a pattern here? DFS always traverses down all available paths, unless you state that it should. To do this, we can mark the path down as visited and if a path has already been visited then do not go down that path.
Recursive
Things to keep in mind when writing a recursive solution for depth first search:
1. See if your current node is the goal, if it is the goal return true.
2. Mark your current node as visited if it is not your goal.
3. Iterate through all the child nodes that can be traveled during which make sure to check
4. Recursively go though all the all the child node, while checking all the previous
5. If none of the paths lead to the exit return false
Conclusion
While Depth-First Search will not guarantee the shortest path nor will it guarantee to be the fastest. It is one of the more simple algorithm to understand.
