A* and heuristic search — search you can afford

W, H = 48, 28
rng = random.Random(11)
grid = [[0]*W for _ in range(H)]
for _ in range(16):                       # sparse walls, with gaps to walk through
    if rng.random() < .5:
        r = rng.randrange(H); c0 = rng.randrange(W-13)
        for c in range(c0, c0+13):
            if rng.random() > .22: grid[r][c] = 1
    else:
        c = rng.randrange(W); r0 = rng.randrange(max(1, H-10))
        for r in range(r0, min(H, r0+10)):
            if rng.random() > .22: grid[r][c] = 1
START, GOAL = (H-1, 0), (0, W-1)
grid[START[0]][START[1]] = grid[GOAL[0]][GOAL[1]] = 0

def neighbours(rc):
    r, c = rc
    for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
        nr, nc = r+dr, c+dc
        if 0 <= nr < H and 0 <= nc < W and grid[nr][nc] == 0:
            yield (nr, nc)
record('map_cells', f'{W*H:,}')
record('map_walls', f'{sum(sum(r) for r in grid):,}')

def bfs():
    seen = {START: None}; q = deque([START]); order = []
    while q:
        cur = q.popleft(); order.append(cur)
        if cur == GOAL: break
        for n in neighbours(cur):
            if n not in seen:
                seen[n] = cur; q.append(n)
    path, cur = [], GOAL
    while cur: path.append(cur); cur = seen.get(cur)
    return order, path[::-1]

bfs_order, bfs_path = bfs()
record('bfs_explored', f'{len(bfs_order):,}')
record('bfs_path_len', f'{len(bfs_path):,}')

def astar():
    def h(rc): return abs(rc[0]-GOAL[0]) + abs(rc[1]-GOAL[1])
    seen = {START: None}; g = {START: 0}; order = []
    # (total guess, then how far is left) — the second term is a TIE-BREAK.
    # Without it, every monotone route across an open grid scores the same
    # total, A* has no reason to prefer any of them, and it degenerates
    # into breadth-first. Prefer the cell closest to the goal and it commits.
    pq = [(h(START), h(START), 0, START)]
    while pq:
        _, _, gc, cur = heapq.heappop(pq)
        order.append(cur)
        if cur == GOAL: break
        for n in neighbours(cur):
            ng = gc + 1
            if ng < g.get(n, 10**9):
                g[n] = ng; seen[n] = cur
                heapq.heappush(pq, (ng + h(n), h(n), ng, n))
    path, cur = [], GOAL
    while cur: path.append(cur); cur = seen.get(cur)
    return order, path[::-1]

ast_order, ast_path = astar()
record('astar_explored', f'{len(ast_order):,}')
record('astar_path_len', f'{len(ast_path):,}')
record('same_length', 'yes' if len(ast_path) == len(bfs_path) else 'NO')
record('astar_factor', f'{len(bfs_order)/len(ast_order):.1f}')
record('astar_saved_pct', f'{100*(1-len(ast_order)/len(bfs_order)):.0f}%')

# Rectangles, not imshow. imshow embeds the grid as a base64 PNG inside the
# SVG, and lib/blocks/svg.ts refuses any <image> — so the figure would have
# been replaced by its alt text on the page. The test suite caught it.
#
# Adjacent cells in a row are then merged into ONE rectangle. Drawing 1,200
# separate squares produced a 254 KB SVG, which is inlined into the page
# twice (light and dark); runs bring it under 30 KB and look identical.
from matplotlib.patches import Rectangle
from matplotlib.collections import PatchCollection

WALL     = (0.55, 0.53, 0.50, 0.55)
EXPLORED = (0.91, 0.41, 0.25, 0.30)
PATH     = (0.91, 0.41, 0.25, 1.00)

def runs(coords):
    """(row, col) cells -> (row, col_start, width) horizontal runs."""
    by_row = {}
    for r, c in coords: by_row.setdefault(r, []).append(c)
    out = []
    for r, cs in by_row.items():
        cs.sort(); start = prev = cs[0]
        for c in cs[1:]:
            if c == prev + 1: prev = c; continue
            out.append((r, start, prev - start + 1)); start = prev = c
        out.append((r, start, prev - start + 1))
    return out

def cells(coords, colour, ax):
    if not coords: return
    ax.add_collection(PatchCollection(
        [Rectangle((c, r), w, 1) for r, c, w in runs(coords)],
        facecolor=colour, edgecolor='none'))

def draw(order, path, ax):
    walls = [(r, c) for r in range(H) for c in range(W) if grid[r][c]]
    seen  = [(r, c) for (r, c) in order if not grid[r][c]]
    cells(seen, EXPLORED, ax)
    cells(walls, WALL, ax)
    cells(path, PATH, ax)
    ax.set_xlim(0, W); ax.set_ylim(H, 0)
    ax.set_aspect('equal'); ax.set_xticks([]); ax.set_yticks([])
    for s in ax.spines.values(): s.set_visible(False)
    record('draw_runs_' + ('bfs' if len(order) > 500 else 'astar'), f'{len(runs(seen)):,}')

save_fig('flood-bfs', lambda ax: draw(bfs_order, bfs_path, ax), figsize=(7, 4.2))

save_fig('beam-astar', lambda ax: draw(ast_order, ast_path, ax), figsize=(7, 4.0))

def plot(ax):
    bars = ax.bar(['look everywhere\n(breadth-first)', 'look towards the goal\n(A*)'],
                  [len(bfs_order), len(ast_order)])
    bars[1].set_alpha(.55)
    for b_, v in zip(bars, [len(bfs_order), len(ast_order)]):
        ax.text(b_.get_x()+b_.get_width()/2, v*1.04, f'{v:,}', ha='center', fontsize=10)
    ax.set_ylabel('cells examined')
    ax.set_ylim(0, len(bfs_order)*1.18)
save_fig('cells-compared', plot, figsize=(7, 3.4))

LINES = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)]
EMPTY = (None,)*9
def winner(b):
    for i,j,k in LINES:
        if b[i] is not None and b[i]==b[j]==b[k]: return b[i]
    return None
def moves(b): return [i for i,c in enumerate(b) if c is None]
def play(b,i,m): return b[:i]+(m,)+b[i+1:]

def guess(b, me):                       # a two-line evaluation function
    them = 'O' if me=='X' else 'X'
    s = 0
    for i,j,k in LINES:
        line = [b[i],b[j],b[k]]
        if them not in line: s += line.count(me)
        if me   not in line: s -= line.count(them)
    return s / 24

def limited(b, mark, me, depth, counter):
    counter[0] += 1
    w = winner(b)
    if w: return 1.0 if w==me else -1.0
    if not moves(b): return 0.0
    if depth == 0: return guess(b, me)
    vals = [limited(play(b,m,mark), 'O' if mark=='X' else 'X', me, depth-1, counter)
            for m in moves(b)]
    return max(vals) if mark==me else min(vals)

def move_limited(b, mark, depth, counter):
    scored = [(limited(play(b,m,mark),'O' if mark=='X' else 'X',mark,depth-1,counter), m)
              for m in moves(b)]
    return max(scored)[1]

rng2 = random.Random(5)
for depth, key in ((2,'d2'), (9,'d9')):
    res = {'win':0,'draw':0,'loss':0}; c = [0]
    for game in range(400):
        ai = 'X' if game % 2 == 0 else 'O'
        b, mark = EMPTY, 'X'
        while winner(b) is None and moves(b):
            m = move_limited(b, mark, depth, c) if mark == ai else rng2.choice(moves(b))
            b = play(b, m, mark); mark = 'O' if mark=='X' else 'X'
        w = winner(b)
        res['draw' if w is None else 'win' if w==ai else 'loss'] += 1
    record(f'{key}_losses', f"{res['loss']:,}")
    record(f'{key}_wins', f"{res['win']:,}")
    record(f'{key}_nodes', f'{c[0]:,}')
    record(f'{key}_nodes_per_game', f'{c[0]/400:,.0f}')