A-Star Algorithm

Interactive A* path planner for grid navigation with obstacle placement and route replay

Algorithms
# overview

Problem to result

Who had the problem, what I built, the hardest part, and what it achieved.

01 · The problem

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.

02 · What I built

A grid path planner with an interactive window: place obstacles, pick a start and goal, and watch the shortest route being found and replayed.

03 · The hardest part, and how I solved it

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).

04 · The results

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).

# simulation

A* Path Planner Simulation

Interactive A-star visualization for obstacle-aware routing.

No messages yet.
# challenges

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.

A* planner (commit 3576a2a)01 / 05

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

How it was fixed

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

# repositories

Source Code

GitHub repositories for this project.

A-Star Algorithm Repository

Access the complete source code on GitHub.

Quick Start
$ git clone https://github.com/prathapselvakumar/AMR-Coursework-2
$ cd AMR-Coursework-2
$ python -m venv .venv
$ . .venv/bin/activate
$ pip install -r requirements.txt
$ python a_star_algorithm.py