nodes/pathfinder.py

Part of Tanks of Freedom.

  1"""Pathfinding + flood-fill helpers.
  2
  3Both queries are hand-rolled breadth-first searches over the 12x12 grid.
  4Every step costs exactly one AP, and the two callbacks (``passable`` for
  5terrain, ``blocked`` for occupancy) are re-evaluated per query because the
  6answer changes with the selected unit: helicopters fly over water and
  7forest, and a friendly unit blocks a tile only for someone else. Diagonal
  8movement is disabled (matches upstream).
  9"""
 10
 11from __future__ import annotations
 12
 13from collections import deque
 14
 15from .data import MAP_H, MAP_W
 16
 17
 18def neighbours4(x: int, y: int):
 19    """4-directional neighbours within map bounds."""
 20    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
 21        nx, ny = x + dx, y + dy
 22        if 0 <= nx < MAP_W and 0 <= ny < MAP_H:
 23            yield nx, ny
 24
 25
 26def reachable_cells(start: tuple[int, int], ap: int, *, passable, blocked):
 27    """BFS flood fill: cells reachable from ``start`` within ``ap`` AP.
 28
 29    Args:
 30        start: (x, y) start cell.
 31        ap: action-points budget (each step costs 1 here; future refinements
 32            could read ``terrain.cost_for(unit)``).
 33        passable: callable (x, y) -> bool, terrain alone passable for unit.
 34        blocked: callable (x, y) -> bool, there's a unit/obstacle in the way.
 35
 36    Returns:
 37        Dict ``{(x, y): cost}`` of cells reachable at ``cost <= ap``.
 38        ``start`` is always included with cost 0.
 39    """
 40    seen = {start: 0}
 41    q: deque[tuple[int, int]] = deque([start])
 42    while q:
 43        x, y = q.popleft()
 44        c = seen[(x, y)]
 45        if c >= ap:
 46            continue
 47        for nx, ny in neighbours4(x, y):
 48            if (nx, ny) in seen:
 49                continue
 50            if not passable(nx, ny):
 51                continue
 52            if blocked(nx, ny):
 53                continue
 54            seen[(nx, ny)] = c + 1
 55            q.append((nx, ny))
 56    return seen
 57
 58
 59def find_path(
 60    start: tuple[int, int],
 61    goal: tuple[int, int],
 62    *,
 63    passable,
 64    blocked,
 65):
 66    """Return list of cells [start, ..., goal] or [] if unreachable.
 67
 68    Uses BFS for unit-cost grids: simple, matches the on-screen ``ap`` budget
 69    and stays predictable for the AI.
 70    """
 71    if start == goal:
 72        return [start]
 73    parents: dict[tuple[int, int], tuple[int, int]] = {start: start}
 74    q: deque[tuple[int, int]] = deque([start])
 75    while q:
 76        cell = q.popleft()
 77        if cell == goal:
 78            break
 79        x, y = cell
 80        for nx, ny in neighbours4(x, y):
 81            n = (nx, ny)
 82            if n in parents:
 83                continue
 84            if not passable(nx, ny):
 85                continue
 86            # Allow the goal cell even if blocked (target/attack square).
 87            if blocked(nx, ny) and n != goal:
 88                continue
 89            parents[n] = cell
 90            q.append(n)
 91    if goal not in parents:
 92        return []
 93    # Trace back
 94    path = [goal]
 95    cur = goal
 96    while cur != start:
 97        cur = parents[cur]
 98        path.append(cur)
 99    path.reverse()
100    return path
101
102
103def cells_within_range(cell: tuple[int, int], rng: int):
104    """All cells within Chebyshev range ``rng`` (4-dir Manhattan for our case)."""
105    cx, cy = cell
106    out = []
107    for dy in range(-rng, rng + 1):
108        for dx in range(-rng, rng + 1):
109            if dx == 0 and dy == 0:
110                continue
111            if abs(dx) + abs(dy) > rng:
112                continue
113            x, y = cx + dx, cy + dy
114            if 0 <= x < MAP_W and 0 <= y < MAP_H:
115                out.append((x, y))
116    return out