This project randomly generates a solvable maze and visualizes three different search algorithms with each having their own unique strategy for solving the maze.
Table of Contents
- Randomly generates a maze with an actual solution
- Visualizes the possible solutions from 3 different algorithms
- Times how long it takes for each algorithm to complete the maze
Python 3.7+
- Download the code or clone the repository
git clone https://github.com/ddang9390/MazePath-Visualizer.git - Navigate to the project directory
cd MazePath-Visualizer - Run the main file
python3 main.py
This project utilizes the Recursive Backtracking algorithm to generate the mazes and also visualizes the way three classic search algorithms can solve a maze.
Recursive backtracking is what is used to randomly generate the mazes. This is how the process goes after making a grid filled with walls:
- Starting from a certain cell, we would select a random unvisited neighbor of that cell
- Break the walls between the cell and the neighbor
- Then recursively call ourself on that neighbor
- If a cell has no unvisited neighbors, we would have hit a dead end. Thus we backtrack to a previous cell and start over
- Repeat the process until all cells in the grid have been visited
DFS is a recursive algorithm that would randomly choose a path and go as far down as it can. Once it cannot go further, it backtracks until it reaches a point where it can choose a different path. It repeats itself until it reaches the goal.
This algorithm does not guarantee that it will find the shortest path, it is entirely up to luck. For smaller and simpler mazes, it could find a path relatively quickly. But for more complex mazes, it may often reach dead-ends further delaying the time it takes to reach the end. With some especially bad luck, DFS may reach a solution where it would take the longest possible time.
Once BFS reaches a crossroad, it would not choose a random path like DFS. Instead it would choose to go through every single possible path. It would repeat this process until the goal is reached.
BFS would have a better chance than DFS when it comes to finding the sortest path to the goal. However the time it takes to reach the goal will be dependent on the complexity of the maze since it would have to go through every possible path before reaching the goal. Because of this, there are moments when DFS would be faster than BFS. There may even be moments that BFS would take the longest possible time to solve the maze.
The A* algorithm would be making use of a heuristic function to find its way to the goal. In the case of this project, the Manhattan distance formula is being used. Manhattan distance is the sum of the absolute differences between the coordinates of two points in a path.
This Manhattan distance formula would be used to find two things:
- The g-score: The distance from the start to the current cell in the maze
- The h-score: The distance from the current cell in the maze to the goal
These two scores are then summed up to find the f-score of the cell. The f-score is what is used to determine the optimal path from the start to the goal.
The shortest path is guaranteed to be found. Since it does not have to go through every path like BFS, A* would prove to be a more efficient algorithm thus resulting in it being the faster algorithm in the majority of cases.
Daniel Dang - https://www.linkedin.com/in/daniel-dang-704791a6/