3.3 Pathfinding Algorithms

A pathfinding algorithm is a computer program that finds the shortest route/path between two points. This means using an algorithm to find the best way through a maze. It is mainly based on graphs and graph theory, which is why it can be really slow.

The most common pathfinding algorithms include:

1. A* (Best Overall very flexible and great use cases)
2. Breadth First Search (decent, starts from the root and explores children of the root children)
3. Depth First Search (decent, starts from the root and sees one of it’s children’s sub tree)
4. Greedy (decent, makes educated guesses, the node with the least estimated distance from the current node to the end node will be used next)

We will discuss the first three.

DFS (Depth First Search)

DFS is one of the easiest search algorithms. Since it only goes in one direction until it arrives at a stop, it is the easiest to implement. The way DFS works is out of its current neighbors, it picks the first one it sees and visits it, then it does the same thing. Again and again and again, until it arrives at a stop. Then it goes back one level and then picks the other neighbor. This process keeps on going until we finally reach the endpoint.

DFS can also be implemented in 2 unique ways, recursively and iteratively.

Recursively:

In this case, this is our logic:

• Check if we have visited the node we are on.
• If we have, don’t do anything.
• If we haven’t, visit this node.
• Once we visit this node add this to our visited set and then visit all the other neighbors using this function.

Here’s what that would look like in code:

def dfs(visited, graph, node):
   if node not in visited:
       print(node)
       visited.add(node)
       for neighbour in graph[node]:
           dfs(visited, graph, neighbour)

View code on GitHub.