Pathfinding Visualizer

An interactive pathfinding visualizer built with Python and Pygame that demonstrates and compares Breadth-First Search (BFS) and A* search on a grid.

The visualizer allows users to build custom maps, load preset layouts, watch each algorithm explore the grid, compare their performance, and dynamically modify the environment while the program recalculates routes.

• Breadth-First Search (BFS)
• A* Search using Manhatten Distance
• Animated search exploration
• Final shortest-path visualization
• BFS vs. A* performance comparison
• A* g, h, and f score inspection
• Adjustable animation speed
• Pause and step through controls
• Dynamic path rerouting
• Click and drag wall drawing
• Click and drag wall erasing
• Moveable start and destination cells
• Search statistics including:
  • Expanded Cells
  • Path length
  • Runtime
  • Whether or not a path was found
• Multiple map presets
• Adjustable random map wall density

Breadth-First Search explores the grid layer by layer from the starting position. Because every movement in the visualizer has the same cost, BFS is guaranteed to find a shortest path when one exists.

A* uses the following evaluation function:

f(n) = g(n) + h(n)

Where:

• g(n) is the known cost from the start to the current cell.
• h(n) is the estimated distance from the current cell to the destination
• f(n) is the estimated total cost of a path through that cell.

The visualizer uses Manhatten distance for its heuristic:

|row1 - row2| + |column1 - column2|

This works well for the four directional grid because movement is only limited to up, down, left, and right.

When A* is selected, hovering over cells that were evaluated by the algorithm displays their g, h, and f scores.

Dynamic rerouting can be toggled with D

When enabled, modifying the map automatically runs the currently selected algorithm again after the edit is completed.

For example, a wall can be drawn across the current path and the visualizer will calculate and animate a new route around the obstacle.

Dynamic rerouting also works when:

• Removing walls
• Moving the start position
• Moving the destination

The visualizer includes several built-in layouts:

0 - Custom

Starts with an empty grid so the user can create their own map.

1 - Warehouse

A structured layout that contains rows of obstacles with aisles between them

2 - Dungeon

A room based layout with walls, corridors, and doorways

3 - Backrooms Generates a randomized map using an adjustable slider.

The random preset places the start and destination far enough apart to create an actual meaningful search and generates a guaranteed route between them.

Comparison mode runs BFS and A* on the same map and displays statistics for both algorithms.

The comparison includes:

• Expanded cells
• Path length
• Runtime
• Whether a path was found

On an unweighted grid, both algorithms can produce a shortest path of the same length, but A* can often explore fewer cells by using its heuristic to guide the search toward the destination.

Runtime measurements on small grids can vary between runs, so the number of expanded cells is generally a more useful way to visualize the difference between the algorithms.

• Python 3
• pygame-ce

Clone the repository:

git clone <repository-url>
cd A-Star