Pathfinding Algorithm Comparison Tool
The software is an interactive Pygame application for visualizing and benchmarking four classic pathfinding algorithms - BFS, DFS, A-star, and Greedy Best-First Search (GBFS) - on randomly generated mazes with variable terrain costs and maze density. Run a single side-by-side trial or a large-scale multi-trial statistical comparison, it can then export the results to a polished PDF report on a large scale.
Features
Four algorithms run on identical 100 by 100 grid mazes for fair, apples-to-apples comparison: BFS, DFS, A-star, and GBFS. Terrain costs: in addition to walls (impassable), mazes include sand (cost 3) and water (cost 5) tiles that affect path cost calculations. Manual maze editing: draw walls, sand, or water directly on the grid with the mouse. Random maze generation with an adjustable wall density slider. Single Trial mode: run all four algorithms once on the same maze and step through each result (path found, nodes expanded, path cost, efficiency) with Previous/Next navigation. Multi-Trial mode: run up to 1000 trials with random start/end positions and mazes, automatically retrying failed attempts, and aggregate success rate, average nodes expanded, and average path cost per algorithm. Best performer highlights: automatically flags the most efficient, lowest-cost, and highest success-rate algorithm after a multi-trial run. PDF report export: generates a formatted report (via ReportLab) with a per-trial breakdown table, averaged statistics table, and an overall best performers summary. The PDF opens automatically after export on macOS, Windows, and Linux.
Requirements
Python 3.8 or newer Pygame ReportLab
Installation
pip install pygame reportlab
Usage
python pathfinding_comparison.py
A window will open with a control panel on the left and a maze grid on the right.
Controls
Draw a wall: left-click and drag on the grid. Draw sand, cost 3: hold Ctrl and left-click or drag. Draw water, cost 5: hold Shift and left-click or drag. Generate a random maze: use the Generate Maze button. Clear walls and terrain: use the Clear Walls/Terrain button. Adjust wall density: use the Wall Density slider. Set number of trials: use the Number of Trials slider.
Buttons
RUN SINGLE TRIAL: runs BFS, DFS, A-star, and GBFS once on a freshly generated maze. Use the Previous and Next arrows below the grid to page through each algorithm's result and stats. RUN MULTI-TRIAL: runs the selected number of successful trials, each with a random maze and random start/end position, skipping and retrying attempts where no path exists, and displays aggregated statistics for all four algorithms. Export to PDF: available after a multi-trial run. Generates a timestamped PDF report, named pathfinding_multitrial_ followed by the date and time, in the working directory, and attempts to open it automatically.
Algorithms Compared
BFS, Breadth-First Search: uninformed search; guarantees the shortest path by unweighted step count.
DFS, Depth-First Search: uninformed search; does not guarantee the shortest path.
A-star: informed search using heuristic plus cost; guarantees the shortest path when the heuristic is admissible.
GBFS, Greedy Best-First Search: informed search using heuristic only; does not guarantee the shortest path.
All algorithms use Manhattan distance as the heuristic where applicable and respect terrain costs. Logically walls are impassable.
PDF Report Contents
Each generated report includes the following:
Run configuration: wall density, grid size, trial and attempt counts. A per-trial results table showing status, nodes expanded, path cost, and efficiency for up to 1000 sampled trials. Aggregated average performance per algorithm across all successful trials. A summary section highlighting the most efficient, lowest-cost, and highest-success-rate algorithm.
Project Structure
The main application lives in pathfinding_comparison.py. Generated PDF reports, named pathfinding_multitrial_ followed by a timestamp, are created at runtime in the same directory.
License
This project is provided as-is for educational and experimental purposes. Feel free to fork, modify, and use it in your own projects.