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, however, it only has one correct path from 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.

width >= 2
rows >= 2
algorithm = astar, bfs, dfs, dijkstra, rand, yen [See line 8 of Algorithms.py for full list]

./pathfinding.py <width> <# rows> <algorithm type>

While an algorithm isn't running:

• 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 Shift + Left Click to place a forbbiden node after placing Start and End nodes
• Left Click to place Start, then End, then Obstacles
• Right Click to remove Start, End, Forbbiden nodes, 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

• Start: where the search algorithm will start
• End: where the search algorithm is trying to get to
• Obstacle: a position the algorithms avoid
• Forbidden: a position certain algorithms avoid (a different type of obstacle)
• Check/Uncheck: markup for visualizing the algorithm
• Path: markup for visualizing the found path
• Default: a position that can be traversed

Currently implemented algorithms (17/33):

- A*
- Beam Search
- Bellman Ford's Algorithm
- Best First Search
- Bidirectional search
- 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)
- Lexicographic BFS
- Random Walk
- Theta*

Currently looking at:

- None

Planned algorithms (Going to look at them):

- α–β pruning

- Branch & bound

- Concurrent Dijkstra

- Fast Iterative Method
- Fast Marching Method
- Fast Sweeping Method
- Fringe search

- Johnson's
- Jump Point Search (JPS)

- Kruskal's

- Lifelong Planning A* (LPA*)

- SMA*
- SSS*
- SUB

- Viterbi algorithm

- Yen's k-Shortest Paths