Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Python A-star grid search: use an admissible lower bound for shortest paths

Last updated: 30 Sept 20264 min read
tutorial
IntermediateBy AITrove Editorial

A-star expands candidate paths by current cost plus a heuristic lower bound on remaining cost.

Download Python source kit

Operation contract

The bounded grid allows unit-cost orthogonal moves. Manhattan distance never overestimates the remaining cost under those rules. The center cell is blocked, so the route from the top-left to the bottom-right goes around it with four moves. A priority queue keeps frontier states; the best-known cost map discards stale heap entries.

Failure and ownership boundary

A heuristic that overestimates or ignores a cheaper movement mode can break optimality. For weighted or diagonal moves, choose a matching lower bound or fall back to zero, which gives Dijkstra behavior. Python Dijkstra: nonnegative weights and stale heap entries, Python graph BFS: mark a vertex when it enters the queue and Python Floyd-Warshall: all-pairs costs with negative-cycle rejection make the assumptions visible.

Working program

python
from heapq import heappop, heappush

def grid_cost(width, height, blocked, start, goal):
    if type(width) is not int or type(height) is not int or not 1 <= width <= 10 or not 1 <= height <= 10 or type(blocked) is not set or any(type(cell) is not tuple or len(cell) != 2 or any(type(value) is not int for value in cell) for cell in blocked) or any(type(cell) is not tuple or len(cell) != 2 or any(type(value) is not int for value in cell) for cell in (start, goal)):
        raise ValueError("grid bounds")
    valid = lambda cell: 0 <= cell[0] < width and 0 <= cell[1] < height and cell not in blocked
    if not valid(start) or not valid(goal):
        raise ValueError("endpoint")
    estimate = lambda cell: abs(cell[0] - goal[0]) + abs(cell[1] - goal[1])
    best = {start: 0}
    frontier = [(estimate(start), 0, start)]
    while frontier:
        _, cost, cell = heappop(frontier)
        if cost != best[cell]:
            continue
        if cell == goal:
            return cost
        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            neighbor = (cell[0] + dx, cell[1] + dy)
            if valid(neighbor) and cost + 1 < best.get(neighbor, float("inf")):
                best[neighbor] = cost + 1
                heappush(frontier, (cost + 1 + estimate(neighbor), cost + 1, neighbor))
    return None

print(grid_cost(3, 3, {(1, 1)}, (0, 0), (2, 2)))
print(grid_cost(2, 1, {(1, 0)}, (0, 0), (0, 0)))

Output

Output
4
0

Costs and limits

For V reachable cells and E possible moves, heap operations give O((V+E) log V) time with O(V) retained state in this bounded implementation. The heuristic may reduce expansions but does not improve the worst-case guarantee.

Common Mistakes

  • A heuristic must be a lower bound under the actual movement costs.
  • Reject blocked or out-of-range endpoints before search.

Connected lessons

Python Dijkstra: nonnegative weights and stale heap entries, Python graph BFS: mark a vertex when it enters the queue, Python Floyd-Warshall: all-pairs costs with negative-cycle rejection.

python
a-star-grid
Storage details