Bidirectional A*

1import heapq
2
3def bidirectional_astar(grid: list[list[int]], start: tuple[int, int], end: tuple[int, int]) -> list[tuple[int, int]] | None:
4    """Bidirectional A* search from both start and end."""
5    rows, cols = len(grid), len(grid[0])
6    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
7
8    # Forward search state
9    g_fwd = {start: 0}
10    parent_fwd = {start: None}
11    open_fwd = [(heuristic(start, end), start)]
12    closed_fwd = set()
13
14    # Backward search state
15    g_bwd = {end: 0}
16    parent_bwd = {end: None}
17    open_bwd = [(heuristic(end, start), end)]
18    closed_bwd = set()
19
20    best_path = None
21    best_cost = float('inf')
22
23    while open_fwd and open_bwd:
24        # Expand forward
25        if open_fwd:
26            _, curr = heapq.heappop(open_fwd)
27            if curr not in closed_fwd:
28                closed_fwd.add(curr)
29
30                if curr in closed_bwd:
31                    cost = g_fwd[curr] + g_bwd[curr]
32                    if cost < best_cost:
33                        best_cost = cost
34                        best_path = _reconstruct(curr, parent_fwd, parent_bwd)
35
36                for dr, dc in directions:
37                    nr, nc = curr[0] + dr, curr[1] + dc
38                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
39                        neighbor = (nr, nc)
40                        tentative_g = g_fwd[curr] + 1
41                        if neighbor not in g_fwd or tentative_g < g_fwd[neighbor]:
42                            g_fwd[neighbor] = tentative_g
43                            parent_fwd[neighbor] = curr
44                            f = tentative_g + heuristic(neighbor, end)
45                            heapq.heappush(open_fwd, (f, neighbor))
46
47        # Expand backward (similar logic)
48        if open_bwd:
49            _, curr = heapq.heappop(open_bwd)
50            if curr not in closed_bwd:
51                closed_bwd.add(curr)
52
53                if curr in closed_fwd:
54                    cost = g_fwd[curr] + g_bwd[curr]
55                    if cost < best_cost:
56                        best_cost = cost
57                        best_path = _reconstruct(curr, parent_fwd, parent_bwd)
58
59                for dr, dc in directions:
60                    nr, nc = curr[0] + dr, curr[1] + dc
61                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
62                        neighbor = (nr, nc)
63                        tentative_g = g_bwd[curr] + 1
64                        if neighbor not in g_bwd or tentative_g < g_bwd[neighbor]:
65                            g_bwd[neighbor] = tentative_g
66                            parent_bwd[neighbor] = curr
67                            f = tentative_g + heuristic(neighbor, start)
68                            heapq.heappush(open_bwd, (f, neighbor))
69
70    return best_path
71
72def _reconstruct(meeting, parent_fwd, parent_bwd):
73    path_fwd = []
74    curr = meeting
75    while curr:
76        path_fwd.append(curr)
77        curr = parent_fwd[curr]
78    path_fwd.reverse()
79
80    path_bwd = []
81    curr = parent_bwd[meeting]
82    while curr:
83        path_bwd.append(curr)
84        curr = parent_bwd[curr]
85
86    return path_fwd + path_bwd