← Back to problems Anduril • ground path planning

Grid A*

AeroSpace • Manhattan heuristic • obstacle grid

A* on a small 4-connected grid with obstacles (1 = blocked). Use f = g + h with Manhattan distance heuristic; reconstruct path from parent pointers when goal is popped.

TimeO(V log V)

SpaceO(V)

Step0/0

Ready

Press Play or Step. Start (0,0) → goal (5,4) on a 6×5 grid.

Speed:

⌨ Type It

Python: def astar(grid, start, goal) -> list of (r,c) from start to goal, or [] if unreachable.

═══ GRID A* ═══

① Priority queue by f = g + manhattan

② Skip walls; relax 4-neighbors

③ Reconstruct via parent map

Verify: