How would you implement A* on a weighted grid?

1. Problem

Implement aStar(grid, start, goal). A cell is blocked or has a positive traversal cost. Moves are four-directional; entering a neighbor adds that neighbor's cost. Return the path and total cost, or NO_PATH when the goal is unreachable.

2. Constraints and clarifications

• Coordinates are integer (row, column) pairs inside the grid; start and goal must be traversable.
• A heuristic must never overestimate the remaining cost if the result must be optimal. With four-way movement and minimum cell cost m, Manhattan distance times m is admissible.
• Use a min-heap ordered by f, then a deterministic coordinate tie-breaker. The heap may contain stale entries after a better g score is found.
• Negative cell costs are invalid. A single-threaded implementation is enough; concurrent grid updates require a snapshot or version check.

3. Core approach

Keep gScore for the cheapest known cost to each cell and cameFrom for reconstruction. Push (f, g, cell) whenever a relaxation improves gScore. On pop, skip the node if its stored g is greater than the current gScore; this lazy approach avoids an arbitrary heap decrease-key operation.

For a consistent heuristic, the first non-stale pop of the goal is optimal. If the heuristic is only admissible, permit a closed node to be reopened when a cheaper g is discovered. Red Blob Games describes this priority-queue pattern and the effect of heuristic quality on work performed.

4. Reference implementation

aStar(grid, start, goal):
  require traversable(start) and traversable(goal)
  gScore = map(default=INFINITY)
  cameFrom = map()
  gScore[start] = 0
  open = minHeap((heuristic(start, goal), 0, start))

  while open is not empty:
    (f, queuedG, current) = open.pop()
    if queuedG != gScore[current]: continue   // stale entry
    if current == goal:
      return reconstruct(cameFrom, goal), gScore[goal]

    for next in traversableNeighbors(current):
      tentative = gScore[current] + grid[next].cost
      if tentative < gScore[next]:
        gScore[next] = tentative
        cameFrom[next] = current
        open.push((tentative + h(next, goal), tentative, next))

  return NO_PATH

reconstruct follows cameFrom from goal to start and reverses the collected cells. The priority queue only schedules candidates; gScore remains the source of truth.

5. Complexity and trade-offs

With V reachable cells and E neighbor edges, a binary heap gives O((V + E) log V) time and O(V) space in the lazy-entry implementation. On a four-neighbor grid, E is O(V). A stronger consistent heuristic usually reduces expanded cells without changing the worst-case bound. An exact decrease-key heap can reduce duplicate entries but adds implementation complexity.

6. Verification and observability

• Test start equals goal, blocked endpoints, an empty grid, a wall with a gap, weighted detours, and an unreachable goal.
• Compare returned cost with Dijkstra using h=0 on randomized non-negative grids.
• Assert every returned step is adjacent and traversable, and recompute the path cost independently.
• Track expanded cells, stale pops, maximum heap size, and heuristic violations; a stale-pop spike may indicate duplicate scheduling or a poor data structure boundary.

7. Common mistakes

• Marking a node permanently closed on first discovery instead of on a valid pop.
• Using Euclidean distance for four-way unit movement without scaling or checking admissibility.
• Adding the current cell cost instead of the cost of entering the neighbor.
• Returning a path when the goal was popped from a stale heap record.
• Forgetting to handle start == goal or allowing blocked endpoints.

8. Follow-up questions

When is Manhattan distance admissible?

For four-way movement with non-negative costs and minimum traversal cost m, each required horizontal or vertical step costs at least m; Manhattan distance times m cannot exceed the true remaining cost.

How do diagonal moves change the heuristic?

Use an octile or Chebyshev-style lower bound that matches diagonal and straight movement costs. The formula must reflect the cheapest legal combination and remain a lower bound.

What if the grid changes during the search?

Search a versioned snapshot and validate the path before use, or restart when the grid version changes. Mixing costs from different versions can invalidate both optimality and safety.