What you're building
A astar(grid, start, end) function that finds the shortest path on a 2-D grid using the A algorithm* — a heuristic-guided search that outperforms BFS on large grids.
A* is BFS with a priority queue and a heuristic:
f(n) = g(n) + h(n)
g(n) = actual cost from start to n
h(n) = estimated cost from n to end (Manhattan distance)
Requirements
- Accept the same interface as the BFS lesson:
grid(array of strings),startandendas[row, col]. - Return the shortest path as
[[row,col], ...](inclusive of start and end), ornullif unreachable. - Use Manhattan distance as the heuristic:
|r1-r2| + |c1-c2|. - Move in 4 directions only (up, down, left, right).
- Walls are
"#"; all other cells are open, each with a movement cost of 1.
Stretch goals
- Support diagonal movement (cost
√2for diagonals, 1 for cardinal). - Support weighted tiles (e.g.
"~"= cost 3 for swamp). - Visualise the open/closed sets at each step.
What this proves
A* is the industry standard for game pathfinding (Unity NavMesh, Unreal AI), robotics motion planning, and any domain where you need guaranteed-shortest paths faster than BFS. Implementing it shows you understand heuristics, priority queues, and the trade-off between exploration breadth and goal-directedness.
⚡ 60 XP
solution.jsRuns in your browser
Loading editor…
Tests4 to pass
finds path in open grid
returns null when fully blocked
single-step path
shortest path length matches BFS
Run your code to check these.