gurknathe/pathfinding-algorithms

A Python implementation and visualization of various pathfinding and graph search algorithms.

Pathfinding/Graph Search Algorithms

This is a Python (3.10+) implementation and visualization of various pathfinding algorithms.

There is also a web version of this at this hyperlink. However, there are a number of features that are missing including node-to-node updating. So, the final grid will display basically immediately after you click Run. Additionally, not every algorithm is implemented yet.

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.

Warning: There is an issue with PyGame that can cause the program to crash. On my system running Linux Mint, the update display function causes a segmentation fault. Non-Windows users seem to be the group affected by this, so if you're using Windows, you should be fine.

Command line arguments

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>

Keydown Events

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

Testing

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. The Floyd-Warshall algorithm takes up the most time and can vary significantly in its execution time (e.g., most of the time I get a run time of ~260 seconds where as of writing this I record a run time of ~670 seconds).

Node Types

• 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

Algorithm Progress

Currently implemented algorithms (25/25):

- A*
- Beam Search
- Bellman Ford's Algorithm
- Best First Search
- Bidirectional A*
- Bidirectional search
- Breadth First Search (BFS)
- B*
- Depth First Search (DFS)
- Dijkstra's Algorithms
- Fast Marching Method (FMM)
- Flood Fill Algorithm
- Floyd-Warshall's algorithm
- Fringe search
- Greedy Best First Search (GBFS)
- Greedy Best Line Search (GBLS)
- Iterative Deepening (IDA*)
- Iterative Deepening DFS (IDDFS)
- Jump Point Search (JPS)
- Lexicographic BFS (LBFS)
- Lifelong Planning A* (LPA*)
- Random Walk
- Random Walk with LIFO Queue
- Shortest Path Faster Algorithm (SPFA)
- Theta*

Currently looking at:

- None

Planned algorithms (Going to look at them):

- None

Possible incorrectly implemented algorithms:

• B*
• Jump Point Search