Tracing A* on a Grid

Search a small grid with obstacles using A*, combining path cost and a heuristic to find the shortest route efficiently.

Problem

A* finds shortest paths using the cost so far g plus an admissible heuristic h that estimates remaining cost. By expanding nodes in order of f = g + h it explores far fewer nodes than Dijkstra while still returning the optimal path, provided h never overestimates.

Grid and heuristic

On a 4x4 grid moving in four directions, with a wall blocking part of the middle, the Manhattan distance is an admissible heuristic. Start at (0,0), goal at (3,3).

import heapq
W,H=4,4; walls={(1,1),(1,2),(2,1)}
def nbr(p):
    for dx,dy in((1,0),(-1,0),(0,1),(0,-1)):
        q=(p[0]+dx,p[1]+dy)
        if 0<=q[0]<W and 0<=q[1]<H and q not in walls: yield q
h=lambda p:abs(3-p[0])+abs(3-p[1])
start,goal=(0,0),(3,3)
pq=[(h(start),0,start)]; g={start:0}; came={}
while pq:
    f,gc,u=heapq.heappop(pq)
    if u==goal: break
    for v in nbr(u):
        ng=gc+1
        if v not in g or ng<g[v]:
            g[v]=ng; came[v]=u; heapq.heappush(pq,(ng+h(v),ng,v))
print('path length',g[goal])  # 6

Result

A* returns a path of length 6, the shortest way around the wall, while expanding only the nodes that lie roughly along the route toward the goal. The heuristic steers the search: nodes pointing away from the goal get a high f and are deprioritized. If the heuristic were zero, A* would degenerate into Dijkstra and expand many more nodes.

• Admissibility (never overestimating) guarantees A* returns an optimal path.
• A more informed heuristic expands fewer nodes but must stay admissible to keep optimality.
• Grid path-planning of this kind supports Kronos maintenance-robot and cabling-route layout studies.