A-Star Algorithm
Interactive A* path planner for grid navigation with obstacle placement and route replay
Problem to result
Who had the problem, what I built, the hardest part, and what it achieved.
The coursework path planner was marked on execution speed, and my first version slowed down on large grids because every step scanned the whole list of open nodes.
A grid path planner with an interactive window: place obstacles, pick a start and goal, and watch the shortest route being found and replayed.
Making it fast with no imports allowed. The specification banned imports, so Python's heap module was off-limits. I wrote my own binary min-heap with lazy deletion, so each step costs O(log n) instead of O(n).
Each search step from O(n) to O(log n); the planner grew from 143 to about 600 lines, with every design choice documented against the lecture material and Hart, Nilsson & Raphael (1968).
A* Path Planner Simulation
Interactive A-star visualization for obstacle-aware routing.
Problems & Fixes
What went wrong while building it, and how each problem was solved.
From the "Updates based on Coursework Results" commit (16 March); the planner went from 143 lines to about 600. The input checks (empty grid, start or goal out of bounds, start or goal on an obstacle, start equal to goal) were already right in the first version and stayed the same, and gui.py has not changed since the first commit.
Choosing the next node was slow
Cause: My first version kept the open list as a plain Python list. Every iteration it scanned the whole list for the lowest f-cost, so each step cost O(n), which is slow on large grids
Wrote my own binary min-heap (_heap_push with sift-up, _heap_pop with sift-down), so each step now costs O(log n). The code comments link this to the execution-speed mark
Source Code
GitHub repositories for this project.
A-Star Algorithm Repository
Access the complete source code on GitHub.