Skip to content

A Star Search

Problem

Given a 2D grid where each cell has a non-negative traversal cost, find the shortest (least-cost) path from a start cell to a goal cell using A* search with Manhattan distance heuristic.

Approach

Priority queue ordered by f(n) = g(n) + h(n), where g is the cost so far and h is the Manhattan distance heuristic. Expand the node with lowest f; skip already-settled nodes.

When to Use

Shortest path when you have a good heuristic (estimated distance to goal). Better than Dijkstra when goal is known — avoids exploring irrelevant nodes. ASI relevance: flight route optimization with destination-aware pruning. Use Manhattan distance for grids, great-circle distance for geospatial.

Complexity
Time O(E log V) with a good heuristic (grid: E ~ 4V)
Space O(V)

Implementation

A* pathfinding on a weighted grid.

Problem

Given a 2D grid where each cell has a non-negative traversal cost, find the shortest (least-cost) path from a start cell to a goal cell using A* search with Manhattan distance heuristic.

Approach

Priority queue ordered by f(n) = g(n) + h(n), where g is the cost so far and h is the Manhattan distance heuristic. Expand the node with lowest f; skip already-settled nodes.

When to use

Shortest path when you have a good heuristic (estimated distance to goal). Better than Dijkstra when goal is known — avoids exploring irrelevant nodes. ASI relevance: flight route optimization with destination-aware pruning. Use Manhattan distance for grids, great-circle distance for geospatial.

Complexity

Time: O(E log V) with a good heuristic (grid: E ~ 4V) Space: O(V)

a_star 

a_star(
    grid: list[list[int]],
    start: tuple[int, int],
    goal: tuple[int, int],
) -> list[tuple[int, int]] | None

Return the shortest path from start to goal on grid.

grid[r][c] is the cost to enter cell (r, c). Returns a list of (row, col) coordinates from start to goal inclusive, or None if no path exists.

a_star([[1, 1, 1], [1, 1, 1], [1, 1, 1]], (0, 0), (2, 2)) [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)]

Source code in src/algo/graphs/a_star_search.py 
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
def a_star(
    grid: list[list[int]],
    start: tuple[int, int],
    goal: tuple[int, int],
) -> list[tuple[int, int]] | None:
    """Return the shortest path from *start* to *goal* on *grid*.

    *grid[r][c]* is the cost to enter cell (r, c). Returns a list of
    (row, col) coordinates from start to goal inclusive, or ``None`` if
    no path exists.

    >>> a_star([[1, 1, 1], [1, 1, 1], [1, 1, 1]], (0, 0), (2, 2))
    [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)]
    """
    if not grid or not grid[0]:
        return None

    rows, cols = len(grid), len(grid[0])
    sr, sc = start
    gr, gc = goal

    if not (0 <= sr < rows and 0 <= sc < cols):
        return None
    if not (0 <= gr < rows and 0 <= gc < cols):
        return None

    open_heap: list[tuple[int, int, int, int]] = [
        (manhattan_distance(start, goal), 0, sr, sc),
    ]
    came_from: dict[tuple[int, int], tuple[int, int]] = {}
    g_score: dict[tuple[int, int], int] = {start: 0}

    while open_heap:
        _f, g, r, c = heapq.heappop(open_heap)
        if (r, c) == goal:
            return _reconstruct_path(came_from, goal)

        if g > g_score.get((r, c), float("inf")):
            continue

        for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                ng = g + grid[nr][nc]
                if ng < g_score.get((nr, nc), float("inf")):
                    g_score[(nr, nc)] = ng
                    f = ng + manhattan_distance((nr, nc), goal)
                    heapq.heappush(open_heap, (f, ng, nr, nc))
                    came_from[(nr, nc)] = (r, c)

    return None

manhattan_distance 

manhattan_distance(
    a: tuple[int, int], b: tuple[int, int]
) -> int

Return the Manhattan distance between two grid points.

Source code in src/algo/graphs/a_star_search.py 
27
28
29
def manhattan_distance(a: tuple[int, int], b: tuple[int, int]) -> int:
    """Return the Manhattan distance between two grid points."""
    return abs(a[0] - b[0]) + abs(a[1] - b[1])
tests/graphs/test_a_star_search.py
"""Tests for A* search on weighted grids."""

from algo.graphs.a_star_search import a_star, manhattan_distance


class TestManhattanDistance:
    def test_same_point(self) -> None:
        assert manhattan_distance((0, 0), (0, 0)) == 0

    def test_basic(self) -> None:
        assert manhattan_distance((0, 0), (3, 4)) == 7


class TestAStar:
    def test_simple_grid(self) -> None:
        grid = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
        path = a_star(grid, (0, 0), (2, 2))
        assert path is not None
        assert path[0] == (0, 0)
        assert path[-1] == (2, 2)
        assert len(path) == 5  # Manhattan distance + 1

    def test_start_equals_goal(self) -> None:
        grid = [[1, 1], [1, 1]]
        path = a_star(grid, (0, 0), (0, 0))
        assert path == [(0, 0)]

    def test_obstacle_avoidance(self) -> None:
        grid = [
            [1, 999, 1],
            [1, 999, 1],
            [1, 1, 1],
        ]
        path = a_star(grid, (0, 0), (0, 2))
        assert path is not None
        assert path[0] == (0, 0)
        assert path[-1] == (0, 2)
        # Should go around the wall
        total_cost = sum(grid[r][c] for r, c in path[1:])
        assert total_cost < 999

    def test_empty_grid(self) -> None:
        assert a_star([], (0, 0), (0, 0)) is None

    def test_out_of_bounds(self) -> None:
        grid = [[1, 1], [1, 1]]
        assert a_star(grid, (5, 5), (0, 0)) is None

    def test_weighted_preference(self) -> None:
        grid = [
            [1, 1, 1],
            [1, 10, 1],
            [1, 1, 1],
        ]
        path = a_star(grid, (0, 0), (2, 2))
        assert path is not None
        # Should not go through (1,1) since weight 10
        assert (1, 1) not in path

Implement it yourself

Run: just challenge graphs a_star_search

Then implement the functions to make all tests pass. Use just study graphs for watch mode.

Reveal Solution

A* pathfinding on a weighted grid.

Problem

Given a 2D grid where each cell has a non-negative traversal cost, find the shortest (least-cost) path from a start cell to a goal cell using A* search with Manhattan distance heuristic.

Approach

Priority queue ordered by f(n) = g(n) + h(n), where g is the cost so far and h is the Manhattan distance heuristic. Expand the node with lowest f; skip already-settled nodes.

When to use

Shortest path when you have a good heuristic (estimated distance to goal). Better than Dijkstra when goal is known — avoids exploring irrelevant nodes. ASI relevance: flight route optimization with destination-aware pruning. Use Manhattan distance for grids, great-circle distance for geospatial.

Complexity

Time: O(E log V) with a good heuristic (grid: E ~ 4V) Space: O(V)

a_star 

a_star(
    grid: list[list[int]],
    start: tuple[int, int],
    goal: tuple[int, int],
) -> list[tuple[int, int]] | None

Return the shortest path from start to goal on grid.

grid[r][c] is the cost to enter cell (r, c). Returns a list of (row, col) coordinates from start to goal inclusive, or None if no path exists.

a_star([[1, 1, 1], [1, 1, 1], [1, 1, 1]], (0, 0), (2, 2)) [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)]

Source code in src/algo/graphs/a_star_search.py 
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
def a_star(
    grid: list[list[int]],
    start: tuple[int, int],
    goal: tuple[int, int],
) -> list[tuple[int, int]] | None:
    """Return the shortest path from *start* to *goal* on *grid*.

    *grid[r][c]* is the cost to enter cell (r, c). Returns a list of
    (row, col) coordinates from start to goal inclusive, or ``None`` if
    no path exists.

    >>> a_star([[1, 1, 1], [1, 1, 1], [1, 1, 1]], (0, 0), (2, 2))
    [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)]
    """
    if not grid or not grid[0]:
        return None

    rows, cols = len(grid), len(grid[0])
    sr, sc = start
    gr, gc = goal

    if not (0 <= sr < rows and 0 <= sc < cols):
        return None
    if not (0 <= gr < rows and 0 <= gc < cols):
        return None

    open_heap: list[tuple[int, int, int, int]] = [
        (manhattan_distance(start, goal), 0, sr, sc),
    ]
    came_from: dict[tuple[int, int], tuple[int, int]] = {}
    g_score: dict[tuple[int, int], int] = {start: 0}

    while open_heap:
        _f, g, r, c = heapq.heappop(open_heap)
        if (r, c) == goal:
            return _reconstruct_path(came_from, goal)

        if g > g_score.get((r, c), float("inf")):
            continue

        for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                ng = g + grid[nr][nc]
                if ng < g_score.get((nr, nc), float("inf")):
                    g_score[(nr, nc)] = ng
                    f = ng + manhattan_distance((nr, nc), goal)
                    heapq.heappush(open_heap, (f, ng, nr, nc))
                    came_from[(nr, nc)] = (r, c)

    return None

manhattan_distance 

manhattan_distance(
    a: tuple[int, int], b: tuple[int, int]
) -> int

Return the Manhattan distance between two grid points.

Source code in src/algo/graphs/a_star_search.py 
27
28
29
def manhattan_distance(a: tuple[int, int], b: tuple[int, int]) -> int:
    """Return the Manhattan distance between two grid points."""
    return abs(a[0] - b[0]) + abs(a[1] - b[1])