Path finding algorithms in 20 lines of code | DFS, BFS & A-star
This tutorial will demonstrate how to implement the Depth-first search (DFS) algorithm in just 20 lines of Python code. Although the algorithm may appear complex in some implementations, it can be implemented quite easily from the pseudocode. Despite its brevity, our implementation will be general, effective, and capable of handling both discrete and continuous environments. While the primary focus of this tutorial is the implementation, a thorough course on Udemy dedicated to pathfinding algorithms (DFS, BFS & A*) is available in case you wish to reinforce your knowledge about them.
We will examine the issue of a robot navigating in a room, wich should reach point B from point A. However, our implementation will be completely generic, allowing you to use your own environments without any alterations to the code.
The environment needs to provide a single function that is required by the DFS, BFS, and A* algorithms. This implies that if you want to incorporate the algorithm into your game or environment, you only need to create an API providing this function. The function is called get_adjacent_nodes, and it returns the nodes that can be reached from a specific node.
Implementation
The code is a direct implementation of the pseudocode, nothing more is needed.
The code is a direct implementation of the pseudocode. First, we create an empty stack to store the nodes and the corresponding paths required to reach them. In Python, a stack can be easily created by utilizing a list. We then add the starting node v to the stack, and since the path to reach this node only includes the node itself, we append it to the stack as is.
Then, we loop while the stack is not empty. Within each iteration of the loop, we extract a node and its corresponding path from the start node. If the node has not been discovered yet, we will process it and add it to the set of processed nodes — to avoid redundant computations in the future. The data structure used to represent the discovered nodes is a set, since it is an efficient method of verifying whether an element is present in it or not. Using less efficient data structures can significantly impact the algorithm’s performance.
If the node that has been extracted from the stack is the target node, we have reached the target and can return the path to reach it. Additionally, we can return the set of discovered nodes for computing statistics, such as the number of nodes explored, but this is not required.
If the node is not the target, we must continue exploring. To achieve this, we obtain all neighboring nodes and add them to the stack. We must also remember to update the path to these nodes.
I hope this tutorial was helful to you. If it was, consider clapping this story, and do not forget to follow for more tutorials related to Artificial Intelligence, and Machine Learning.
