This is a Python (3.10+) implementation and visualization of various pathfinding algorithms.
The graph used is a static, undirected, unweighted, strongly connected graph (aka, a grid that doesn't change while algorithm is running).
The visualization is implemented using PyGame. Credits to Tech With Tim.
A maze generator is implemented, it has at least one valid path from the start to end node. The implementation is based on this.
See the explanations for the implemented algorithms here.
There are three optional command line arguments: width, # rows, algorithm type.
Disclaimer: Testing is done on default settings, there is no guarantee, as of now, that things work smoothly for different widths and rows.
width >= 2
rows >= 2
algorithm = astar, bfs, dfs, dijkstra, rand, yen [See Algorithms.py for full list]
./pathfinding.py <width> <# rows> <algorithm type>
While an algorithm isn't running:
- Press T to test algorithms
- Press B to go to previous algorithm in list
- Press N to go to next algorithm in list
- Press Q to exit
- Press C to clear grid
- Press G to generate a new maze
- Left Click to place Start, then End, then Obstacles
- Right Click to remove Start, End, or Obstacles
After an algorithm has run:
- W, Left Click, or Right Click to clear the Algorithm Mark-up
While an algorithm is running:
- Press S key to stop the algorithm
The testing function runs every implemented algorithm for the current grid. It outputs the time it took to run the algorithm and the number of node checks while running. The results are written into a CSV file, which can be found in the main/testing/results directory. An example output is given for a randomly generated maze, with default settings.
The testing will take longer as the visitable nodes increases. For my system, and a randomly generated maze on default settings, it takes ~4 minutes to run and save the data.
- Start: where the search algorithm will start
- End: where the search algorithm is trying to get to
- Obstacle: a position the algorithms avoid
- Check/Uncheck: markup for visualizing the algorithm
- Path: markup for visualizing the found path
- Default: a position that can be traversed
Currently implemented algorithms (19/30):
- A*
- Beam Search
- Bellman Ford's Algorithm
- Best First Search
- Bidirectional search
- Branch & Bound
- Breadth First Search (BFS)
- B*
- Depth First Search (DFS)
- Dijkstra's Algorithms
- Floyd-Warshall's algorithm
- Greedy Best First Search (GBFS)
- Greedy Best Line Search (GBLS)
- Iterative Deepening (IDA*)
- Iterative Deepening DFS (IDDFS)
- Jump Point Search (JPS)
- Lexicographic BFS
- Random Walk
- Theta*
Currently looking at:
- None
Planned algorithms (Going to look at them):
- Fast Iterative Method
- Fast Marching Method
- Fast Sweeping Method
- Fringe search
- Johnson's
- Kruskal's
- Lifelong Planning A* (LPA*)
- SMA*
- SUB
- Viterbi algorithm
- Yen's k-Shortest Paths
Possible incorrectly implemented algorithms: