Skip to main content
🧩 Algorithm Projects

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), start and end as [row, col].
  • Return the shortest path as [[row,col], ...] (inclusive of start and end), or null if 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 √2 for 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.