Rereading my pathfinding visualiser: A*, Dijkstra, and an RRT that never arrives

One of my first projects at Monash (for FIT1045) was a 2D pathfinding visualiser: draw obstacles on a grid, pick start and end points, and watch an algorithm find a path. It's back online at pathfinding.vrp2206.com as part of putting old projects back online.

Before linking it from my portfolio, I reread the code and, for the first time, benchmarked it properly.

What it does

Built with Streamlit and Plotly, it offers three algorithms:

• Dijkstra: expands outward in order of distance from the start. Guaranteed shortest path.
• A*: Dijkstra plus a heuristic that estimates the remaining distance to the goal, so it explores towards the goal first. Also guaranteed shortest, if the heuristic never overestimates.
• RRT (Rapidly-exploring Random Tree): a sampling-based planner from robotics. It grows a tree towards random points until a branch happens to get near the goal. No guarantee of the shortest path, or of any path.

The grid is 8-connected: you can move diagonally, and a diagonal step costs √2 ≈ 1.414 instead of 1.

The README describes the wrong heuristic

The README says A* uses Manhattan distance. The code uses Euclidean distance:

def distance(self, pos1, pos2):
    return np.sqrt(sum((a - b) ** 2 for a, b in zip(pos1, pos2)))

That's a lucky mismatch, because the code is the right one. A* is only guaranteed to find the shortest path if its heuristic is admissible: it must never overestimate the real remaining cost.

A worked example. Going from (0, 0) to (3, 3) on this grid:

	Estimate or cost
Real cheapest path: 3 diagonal steps	3 × √2 ≈ 4.24
Euclidean heuristic: √(3² + 3²)	≈ 4.24, never more than the real cost ✓
Manhattan heuristic: 3 + 3	6, an overestimate ✗

With diagonal moves, Manhattan distance overestimates, and A* could return a path that isn't the shortest. (The textbook choice for 8-connected grids is the octile distance, which is exact on an empty grid. Euclidean is admissible too, just a little less sharp.) So the code is correct and the README needed fixing.

The benchmark

The app has a comparison mode, but it times a single grid once. I wrote a small script that runs the project's own AStar, Dijkstra and RRT classes on 40 random grids per setting, from the top-left corner to the bottom-right, skipping grids with no possible path:

Grid	Algorithm	Found a path	Cells explored	Time	Path cost
15×15, 20% walls	A*	40 / 40	46	1.1 ms	20.71
	Dijkstra	40 / 40	184	1.8 ms	20.71
	RRT	39 / 40	104	36 ms	24.62
50×50, 20% walls	A*	40 / 40	357	9.1 ms	71.51
	Dijkstra	40 / 40	2,048	21.9 ms	71.51
	RRT	0 / 40	304	163 ms	none
50×50, 30% walls	A*	36 / 36	462	11.7 ms	72.91
	Dijkstra	36 / 36	1,852	19.1 ms	72.91
	RRT	0 / 36	225	128 ms	none

Averages per grid. Path cost counts a diagonal step as √2. Times are from one Python run and only comparable within the table.

What the numbers say

A and Dijkstra always agree on the path cost.* That's the check that matters most: both are supposed to be optimal, and on 116 grids they never disagreed.

A does the same job with far less searching.* On 50×50 grids it explored about 5.7× fewer cells than Dijkstra (357 vs 2,048). That gap is the whole point of a heuristic: Dijkstra spreads out in a circle, while A* leans towards the goal.

The time gap is smaller than the cell gap. A* explores 5.7× fewer cells but is only about 2.4× faster, because each A* step also computes the heuristic. "Cells explored" is the fairer measure. Wall-clock time in Python measures the interpreter as much as the algorithm.

RRT never reaches the goal on a 50×50 grid. Three reasons, all visible in the code:

1. It stops after 500 iterations. On a 15×15 grid that's plenty. On 50×50 the tree needs to grow about 70 cells' worth of distance through obstacles, while most random samples pull it in other directions.
2. It only grows one cell at a time towards each random point, so progress is slow.
3. Finding the nearest tree node is a linear scan over the whole tree every iteration, so it gets slower as the tree grows. That's why RRT is the slowest of the three, despite exploring fewer cells than Dijkstra.

Even when it succeeds on small grids, its paths cost about 19% more than the optimum (24.62 vs 20.71). RRT shines in continuous, high-dimensional spaces such as robot arms, where you can't list every cell. On a small 2D grid, A* is better in every way.

What I'd change now

• Fix the README to say Euclidean, and explain why Manhattan would be wrong here.
• Report path cost, not path length. The app's "Path Length" counts cells, so ten diagonal steps and ten straight steps look the same, even though the diagonal path costs about 41% more.
• Skip stale queue entries in A*. It pushes a cell again when it finds a better route, and later pops the old entry and expands it again. That's harmless for correctness here, but wasted work. One if current in closed: continue fixes it, the same way the Dijkstra code already does.
• Give RRT a fair chance: scale the iteration limit with the grid size, take longer steps, and add goal bias (aim straight at the goal some fraction of the time).
• Benchmark many grids, not one. A single run tells you very little. Forty runs per setting made every pattern above obvious.

The code I wrote in first year was mostly right. The parts that were wrong were the claims around it: the README, the metric names and the comparison. That's what rereading old code is good for.