nodes/grid.py

Part of Tiny Yurts.

  1"""Grid state: path graph, farms, yurts, and BFS pathfinder.
  2
  3The original Tiny Yurts uses a per-edge graph where each path tile is a
  4single grid-edge between two adjacent cells (4-way + 4-diagonal). Settlers
  5traverse the graph via BFS from yurt cell to any of the farm's cells.
  6
  7This mirrors that model. Paths are tracked as bidirectional edges between
  8two cells; cells can be queried for neighbours via :meth:`Grid.neighbours`.
  9"""
 10
 11from __future__ import annotations
 12
 13from collections import deque
 14from dataclasses import dataclass, field
 15
 16from . import iso
 17
 18# 8-way adjacency offsets (matches original Tiny Yurts)
 19ADJ8 = (
 20    (1, 0),
 21    (-1, 0),
 22    (0, 1),
 23    (0, -1),
 24    (1, 1),
 25    (1, -1),
 26    (-1, 1),
 27    (-1, -1),
 28)
 29
 30
 31@dataclass
 32class Farm:
 33    """An animal source. Tile size is 1x1 in this simplified port."""
 34
 35    kind: str  # "ox" | "goat" | "fish"
 36    cell: tuple[int, int]
 37    demand: float = 0.0
 38    capacity: float = 6.0  # max demand before unfed-loss triggers
 39    colour: tuple[float, float, float, float] = (1.0, 1.0, 1.0, 1.0)
 40
 41
 42@dataclass
 43class Yurt:
 44    """A consumer for one farm kind."""
 45
 46    kind: str
 47    cell: tuple[int, int]
 48    settlers: list[object] = field(default_factory=list)
 49
 50
 51class Grid:
 52    """Mutable grid state: path edges + entity placement + BFS routing."""
 53
 54    def __init__(self) -> None:
 55        # Edges as unordered cell pairs frozenset of two tuples
 56        self.edges: set[frozenset[tuple[int, int]]] = set()
 57        # Adjacency map for fast lookup
 58        self.adj: dict[tuple[int, int], set[tuple[int, int]]] = {}
 59        self.farms: list[Farm] = []
 60        self.yurts: list[Yurt] = []
 61        # Cells that block path drawing (occupied by farm/yurt body) -- but
 62        # they are still valid endpoints for paths.
 63        self.blocked: set[tuple[int, int]] = set()
 64
 65    # ---------- Path edges ----------
 66
 67    def add_edge(self, a: tuple[int, int], b: tuple[int, int]) -> bool:
 68        """Add a bidirectional edge between two adjacent cells."""
 69        if not iso.in_bounds(*a) or not iso.in_bounds(*b):
 70            return False
 71        di, dj = b[0] - a[0], b[1] - a[1]
 72        if (di, dj) not in ADJ8:
 73            return False
 74        key = frozenset((a, b))
 75        if key in self.edges:
 76            return False
 77        self.edges.add(key)
 78        self.adj.setdefault(a, set()).add(b)
 79        self.adj.setdefault(b, set()).add(a)
 80        return True
 81
 82    def remove_edge(self, a: tuple[int, int], b: tuple[int, int]) -> bool:
 83        key = frozenset((a, b))
 84        if key not in self.edges:
 85            return False
 86        self.edges.discard(key)
 87        self.adj.get(a, set()).discard(b)
 88        self.adj.get(b, set()).discard(a)
 89        return True
 90
 91    def has_edge(self, a: tuple[int, int], b: tuple[int, int]) -> bool:
 92        return frozenset((a, b)) in self.edges
 93
 94    @property
 95    def path_count(self) -> int:
 96        return len(self.edges)
 97
 98    # ---------- Entities ----------
 99
100    def add_farm(self, farm: Farm) -> None:
101        self.farms.append(farm)
102        self.blocked.add(farm.cell)
103
104    def add_yurt(self, yurt: Yurt) -> None:
105        self.yurts.append(yurt)
106        self.blocked.add(yurt.cell)
107
108    # ---------- Pathfinding ----------
109
110    def neighbours(self, cell: tuple[int, int]):
111        return self.adj.get(cell, ())
112
113    def find_route(
114        self,
115        start: tuple[int, int],
116        targets: set[tuple[int, int]],
117    ) -> list[tuple[int, int]]:
118        """BFS along path edges. Returns shortest cell list start..goal,
119        or an empty list if unreachable.
120        """
121        if start in targets:
122            return [start]
123        if start not in self.adj:
124            return []
125        prev: dict[tuple[int, int], tuple[int, int] | None] = {start: None}
126        q: deque[tuple[int, int]] = deque([start])
127        while q:
128            n = q.popleft()
129            for nb in self.adj.get(n, ()):
130                if nb in prev:
131                    continue
132                prev[nb] = n
133                if nb in targets:
134                    # Reconstruct
135                    path = [nb]
136                    cur: tuple[int, int] | None = n
137                    while cur is not None:
138                        path.append(cur)
139                        cur = prev[cur]
140                    path.reverse()
141                    return path
142                q.append(nb)
143        return []