sc2nachos.geometry

Geometry primitives in the game's coordinate space.

 1"""Geometry primitives in the game's coordinate space."""
 2
 3from sc2nachos.geometry._area import Area
 4from sc2nachos.geometry._circle import Circle
 5from sc2nachos.geometry._direction import Direction
 6from sc2nachos.geometry._edge import Edge
 7from sc2nachos.geometry._field import Field
 8from sc2nachos.geometry._footprint import Footprint, Margin
 9from sc2nachos.geometry._grid import CheapestPaths, Grid
10from sc2nachos.geometry._point import POINT_PRECISION, Point, Point3D, PointLike
11from sc2nachos.geometry._shapes import Rectangle, Tile, TileSet
12from sc2nachos.geometry._source_field import CircleSource, SourceField
13from sc2nachos.geometry._tile_path import TilePath
14
15__all__ = [
16    "POINT_PRECISION",
17    "Area",
18    "CheapestPaths",
19    "Circle",
20    "CircleSource",
21    "Direction",
22    "Edge",
23    "Field",
24    "Footprint",
25    "Grid",
26    "Margin",
27    "Point",
28    "Point3D",
29    "PointLike",
30    "Rectangle",
31    "SourceField",
32    "Tile",
33    "TilePath",
34    "TileSet",
35]
POINT_PRECISION = 0.000244140625
class Area(abc.ABC):
19class Area(ABC):
20    """A patch of ground: somewhere to attack, to scout, or to filter positions by.
21
22    An area may be empty. `center`, `random_point`, `closest_point_to` and `bounding_rectangle` raise `ValueError` on
23    an empty area; the rest work normally.
24    """
25
26    # Without this every subclass carries a __dict__, whatever slots it declares itself.
27    __slots__ = ()
28
29    @property
30    @abstractmethod
31    def center(self) -> Point:
32        """The middle of the area."""
33
34    @property
35    @abstractmethod
36    def area(self) -> float:
37        """The ground covered, in square game units."""
38
39    @abstractmethod
40    def random_point(self, *, rng: random.Random | None = None) -> Point:
41        """A point drawn uniformly from the area, by `rng`, or if none is given by the `random` module's own
42        generator, which the whole process shares: always one the area holds, as `in` has it."""
43
44    @abstractmethod
45    def __contains__(self, point: PointLike | Tile) -> bool:
46        """Whether `point` lies inside, a `Tile` read as its center. Raises `TypeError` on anything but a point or a
47        tile."""
48
49    @abstractmethod
50    def translated(self, offset: PointLike) -> Self:
51        """The area shifted by `offset`, keeping its shape. Raises `TypeError` for a `Tile`, and `ValueError` for an
52        offset with a height."""
53
54    @abstractmethod
55    def closest_point_to(self, point: PointLike) -> tuple[Point, float]:
56        """The point of the area nearest to `point`, and the distance to it: always one the area holds, as `in` has
57        it, so on an edge the area leaves out, the least a float can move inside it."""
58
59    @abstractmethod
60    def bounding_rectangle(self) -> Rectangle:
61        """The smallest rectangle containing the area."""
62
63    @abstractmethod
64    def tiles(self) -> TileSet:
65        """Every tile whose center lies in the area."""
66
67    @abstractmethod
68    def _contains_each(self, xs: ndarray, ys: ndarray) -> ndarray:
69        """Whether each point lies inside, as `in` has it, their x and y given as arrays that broadcast together."""
70
71    @abstractmethod
72    def _overlapped_tile_mask(self) -> TileMask:
73        """Every tile whose inside the area overlaps, a tile it only touches at an edge or a corner left out. An empty
74        area holds none."""
75
76    def _tile_mask(self, within: Rectangle | None = None) -> TileMask:
77        """Every tile whose center lies in the area, as `tiles` gives them, of those that lie `within` a rectangle on
78        whole tiles, if one is given."""
79        return self.tiles()._tile_mask(within)

A patch of ground: somewhere to attack, to scout, or to filter positions by.

An area may be empty. center, random_point, closest_point_to and bounding_rectangle raise ValueError on an empty area; the rest work normally.

center: Point
29    @property
30    @abstractmethod
31    def center(self) -> Point:
32        """The middle of the area."""

The middle of the area.

area: float
34    @property
35    @abstractmethod
36    def area(self) -> float:
37        """The ground covered, in square game units."""

The ground covered, in square game units.

@abstractmethod
def random_point( self, *, rng: random.Random | None = None) -> Point:
39    @abstractmethod
40    def random_point(self, *, rng: random.Random | None = None) -> Point:
41        """A point drawn uniformly from the area, by `rng`, or if none is given by the `random` module's own
42        generator, which the whole process shares: always one the area holds, as `in` has it."""

A point drawn uniformly from the area, by rng, or if none is given by the random module's own generator, which the whole process shares: always one the area holds, as in has it.

@abstractmethod
def translated(self, offset: 'PointLike') -> Self:
49    @abstractmethod
50    def translated(self, offset: PointLike) -> Self:
51        """The area shifted by `offset`, keeping its shape. Raises `TypeError` for a `Tile`, and `ValueError` for an
52        offset with a height."""

The area shifted by offset, keeping its shape. Raises TypeError for a Tile, and ValueError for an offset with a height.

@abstractmethod
def closest_point_to( self, point: 'PointLike') -> tuple[Point, float]:
54    @abstractmethod
55    def closest_point_to(self, point: PointLike) -> tuple[Point, float]:
56        """The point of the area nearest to `point`, and the distance to it: always one the area holds, as `in` has
57        it, so on an edge the area leaves out, the least a float can move inside it."""

The point of the area nearest to point, and the distance to it: always one the area holds, as in has it, so on an edge the area leaves out, the least a float can move inside it.

@abstractmethod
def bounding_rectangle(self) -> Rectangle:
59    @abstractmethod
60    def bounding_rectangle(self) -> Rectangle:
61        """The smallest rectangle containing the area."""

The smallest rectangle containing the area.

@abstractmethod
def tiles(self) -> TileSet:
63    @abstractmethod
64    def tiles(self) -> TileSet:
65        """Every tile whose center lies in the area."""

Every tile whose center lies in the area.

@final
@dataclass(frozen=True, slots=True, eq=False)
class CheapestPaths:
712@final
713@dataclass(frozen=True, slots=True, eq=False)
714class CheapestPaths:
715    """The cheapest path from one tile to every tile of a grid, which on a grid of bools is a shortest one; of several
716    equally cheap paths to a tile, one of them."""
717
718    costs: Grid[float]
719    """Each tile's cheapest path's cost, `inf` where no path reaches; read-only."""
720    distances: Grid[float]
721    """Each tile's cheapest path's length, `inf` where no path reaches; read-only. On a grid of bools, the costs."""
722    _found: semita.CheapestPaths = field(repr=False)
723    """What the search found, by the grid's indices."""
724
725    def path_to(self, end: PointLike | Tile) -> TilePath | None:
726        """The cheapest path to the tile holding `end`, whose cost and length are `costs` and `distances` there, or
727        `None` if no path reaches it. Raises `IndexError` for a point the grid does not cover, even where `costs` reads
728        a value beyond it.
729        """
730        found = self._found.path_to(self.costs.index_of(end))
731        return None if found is None else _semita_path_to_tile_path(found, self.costs.origin)

The cheapest path from one tile to every tile of a grid, which on a grid of bools is a shortest one; of several equally cheap paths to a tile, one of them.

CheapestPaths( costs: Grid[float], distances: Grid[float], _found: semita.CheapestPaths)
costs: Grid[float]

Each tile's cheapest path's cost, inf where no path reaches; read-only.

distances: Grid[float]

Each tile's cheapest path's length, inf where no path reaches; read-only. On a grid of bools, the costs.

def path_to( self, end: 'PointLike | Tile') -> TilePath | None:
725    def path_to(self, end: PointLike | Tile) -> TilePath | None:
726        """The cheapest path to the tile holding `end`, whose cost and length are `costs` and `distances` there, or
727        `None` if no path reaches it. Raises `IndexError` for a point the grid does not cover, even where `costs` reads
728        a value beyond it.
729        """
730        found = self._found.path_to(self.costs.index_of(end))
731        return None if found is None else _semita_path_to_tile_path(found, self.costs.origin)

The cheapest path to the tile holding end, whose cost and length are costs and distances there, or None if no path reaches it. Raises IndexError for a point the grid does not cover, even where costs reads a value beyond it.

@final
class Circle(sc2nachos.geometry.Area):
 23@final
 24class Circle(Area):
 25    """Every point within `radius` of a center, boundary included."""
 26
 27    # Not a dataclass: `Area.center` is a property, and a field cannot override one.
 28    __slots__ = ("_center", "_radius")
 29
 30    _center: Point
 31    _radius: float
 32
 33    def __init__(self, center: PointLike, radius: float) -> None:
 34        """A circle of `radius` around `center`."""
 35        if radius <= 0:
 36            raise ValueError("a circle must have a positive radius")
 37        self._center = Point(center[:2])
 38        self._radius = radius
 39
 40    @property
 41    def center(self) -> Point:
 42        """The point the circle is drawn around."""
 43        return self._center
 44
 45    @property
 46    def radius(self) -> float:
 47        """The distance from the center to the boundary."""
 48        return self._radius
 49
 50    @property
 51    def area(self) -> float:
 52        """The ground covered, in square game units."""
 53        return math.pi * self._radius**2
 54
 55    @property
 56    def perimeter(self) -> float:
 57        """The length of the boundary."""
 58        return 2 * math.pi * self._radius
 59
 60    def __contains__(self, point: PointLike | Tile) -> bool:
 61        """Whether `point` lies in the circle, boundary included."""
 62        position = coordinates_or_tile_center(point)
 63        dx = position[0] - self._center[0]
 64        dy = position[1] - self._center[1]
 65        return dx * dx + dy * dy <= self._radius**2
 66
 67    def _contains_each(self, xs: ndarray, ys: ndarray) -> ndarray:
 68        """Whether each point lies in the circle, boundary included."""
 69        dx = xs - self._center[0]
 70        dy = ys - self._center[1]
 71        return dx * dx + dy * dy <= self._radius**2
 72
 73    def translated(self, offset: PointLike) -> Circle:
 74        """The circle shifted by `offset`, keeping its radius. Raises `ValueError` for an offset with a height."""
 75        return Circle(self._center + checked_ground_offset(offset), self._radius)
 76
 77    def random_point(self, *, rng: random.Random | None = None) -> Point:
 78        """A point drawn uniformly from the circle, by `rng` or the `random` module's own generator."""
 79        random_fraction = random.random if rng is None else rng.random
 80        # sqrt, because a uniform radius would crowd the points toward the center.
 81        distance = self._radius * math.sqrt(random_fraction())
 82        angle = 2 * math.pi * random_fraction()
 83        drawn = Point((self._center[0] + distance * math.cos(angle), self._center[1] + distance * math.sin(angle)))
 84        return self._stepped_inside(drawn)
 85
 86    def closest_point_to(self, point: PointLike) -> tuple[Point, float]:
 87        """The point of the circle nearest to `point`, and the distance to it.
 88
 89        A point inside the circle is its own nearest point, at distance zero. For one outside, the point on the edge
 90        is moved toward the center by as little as rounding needs for the circle to hold it.
 91        """
 92        position = Point(point[:2])
 93        offset = position - self._center
 94        distance = offset.length
 95        if distance <= self._radius:
 96            return position, 0.0
 97        return self._stepped_inside(self._center + offset * (self._radius / distance)), distance - self._radius
 98
 99    def _stepped_inside(self, point: Point) -> Point:
100        """`point`, on or near the edge, moved toward the center by as little as rounding needs for the circle to hold
101        it."""
102        # Rounding leaves about half the points worked out on the edge just outside, almost always by a step of each
103        # coordinate.
104        center_x, center_y = self._center
105        while point not in self:
106            point = Point((math.nextafter(point[0], center_x), math.nextafter(point[1], center_y)))
107        return point
108
109    def bounding_rectangle(self) -> Rectangle:
110        """The smallest rectangle containing the circle."""
111        diameter = 2 * self._radius
112        return Rectangle(self._center[0] - self._radius, self._center[1] - self._radius, diameter, diameter)
113
114    def tiles(self) -> TileSet:
115        """Every tile whose center lies in the circle."""
116        tiles_in_circle = self._tile_mask()
117        return TileSet._from_mask(tiles_in_circle.origin, tiles_in_circle.mask)
118
119    def _tile_mask(self, within: Rectangle | None = None) -> TileMask:
120        """The tiles whose center lies in the circle and that lie `within` a rectangle on whole tiles, if one is
121        given."""
122        # Derived from the circle, not from its bounding rectangle: that rectangle is half-open, so it would
123        # drop a tile center sitting exactly on the circle's rightmost or topmost point.
124        center_x, center_y = self._center[0], self._center[1]
125        first_x = math.ceil(center_x - self._radius - 0.5)
126        first_y = math.ceil(center_y - self._radius - 0.5)
127        last_x = math.floor(center_x + self._radius - 0.5)
128        last_y = math.floor(center_y + self._radius - 0.5)
129        if within is not None:
130            first_x, first_y = max(first_x, int(within.x)), max(first_y, int(within.y))
131            last_x = min(last_x, int(within.x + within.width) - 1)
132            last_y = min(last_y, int(within.y + within.height) - 1)
133        offsets_x = numpy.arange(first_x, last_x + 1) + 0.5 - center_x
134        offsets_y = numpy.arange(first_y, last_y + 1) + 0.5 - center_y
135        tiles_in_circle = offsets_x[:, None] ** 2 + offsets_y[None, :] ** 2 <= self._radius**2
136        return TileMask(Tile(first_x, first_y), tiles_in_circle)
137
138    def _overlapped_tile_mask(self) -> TileMask:
139        """Every tile whose inside the circle overlaps: those whose nearest point lies nearer the center than the
140        radius."""
141        center_x, center_y = self._center[0], self._center[1]
142        radius = self._radius
143        first_x = math.floor(center_x - radius)
144        first_y = math.floor(center_y - radius)
145        columns = math.ceil(center_x + radius) - first_x
146        overlapped = numpy.zeros((columns, math.ceil(center_y + radius) - first_y), dtype=bool)
147        # Column by column, a run of rows: up to a radius of about 10, faster than numpy over the whole box.
148        for column in range(columns):
149            left = first_x + column
150            gap_x = max(left - center_x, center_x - left - 1, 0.0)
151            reach_squared = radius * radius - gap_x * gap_x
152            if reach_squared > 0:
153                reach = math.sqrt(reach_squared)
154                lowest_row = math.floor(center_y - reach) - first_y
155                overlapped[column, lowest_row : math.ceil(center_y + reach) - first_y] = True
156        return TileMask(Tile(first_x, first_y), overlapped)
157
158    def intersections_with(self, other: Circle) -> tuple[Point, ...]:
159        """The points where the two boundaries cross: two, one where the circles touch, none otherwise.
160
161        Concentric circles, the same circle included, report none.
162        """
163        offset = other.center - self._center
164        distance_squared = offset[0] ** 2 + offset[1] ** 2
165        if distance_squared > (self._radius + other.radius) ** 2:
166            return ()
167        if distance_squared < (self._radius - other.radius) ** 2 or distance_squared == 0:
168            return ()
169        distance = math.sqrt(distance_squared)
170        along = (self._radius**2 - other.radius**2 + distance_squared) / (2 * distance)
171        midpoint = self._center + offset * (along / distance)
172        across_squared = self._radius**2 - along**2
173        if across_squared <= 0:
174            return (midpoint,)
175        across = math.sqrt(across_squared) / distance
176        perpendicular = Point((offset[1] * across, -offset[0] * across))
177        return midpoint + perpendicular, midpoint - perpendicular
178
179    def __eq__(self, other: object) -> bool:
180        if not isinstance(other, Circle):
181            return NotImplemented
182        return self._center == other.center and self._radius == other.radius
183
184    def __hash__(self) -> int:
185        return hash((self._center, self._radius))
186
187    def __repr__(self) -> str:
188        return f"Circle({self._center!r}, {self._radius})"

Every point within radius of a center, boundary included.

Circle(center: 'PointLike', radius: float)
33    def __init__(self, center: PointLike, radius: float) -> None:
34        """A circle of `radius` around `center`."""
35        if radius <= 0:
36            raise ValueError("a circle must have a positive radius")
37        self._center = Point(center[:2])
38        self._radius = radius

A circle of radius around center.

center: Point
40    @property
41    def center(self) -> Point:
42        """The point the circle is drawn around."""
43        return self._center

The point the circle is drawn around.

radius: float
45    @property
46    def radius(self) -> float:
47        """The distance from the center to the boundary."""
48        return self._radius

The distance from the center to the boundary.

area: float
50    @property
51    def area(self) -> float:
52        """The ground covered, in square game units."""
53        return math.pi * self._radius**2

The ground covered, in square game units.

perimeter: float
55    @property
56    def perimeter(self) -> float:
57        """The length of the boundary."""
58        return 2 * math.pi * self._radius

The length of the boundary.

def translated(self, offset: 'PointLike') -> Circle:
73    def translated(self, offset: PointLike) -> Circle:
74        """The circle shifted by `offset`, keeping its radius. Raises `ValueError` for an offset with a height."""
75        return Circle(self._center + checked_ground_offset(offset), self._radius)

The circle shifted by offset, keeping its radius. Raises ValueError for an offset with a height.

def random_point( self, *, rng: random.Random | None = None) -> Point:
77    def random_point(self, *, rng: random.Random | None = None) -> Point:
78        """A point drawn uniformly from the circle, by `rng` or the `random` module's own generator."""
79        random_fraction = random.random if rng is None else rng.random
80        # sqrt, because a uniform radius would crowd the points toward the center.
81        distance = self._radius * math.sqrt(random_fraction())
82        angle = 2 * math.pi * random_fraction()
83        drawn = Point((self._center[0] + distance * math.cos(angle), self._center[1] + distance * math.sin(angle)))
84        return self._stepped_inside(drawn)

A point drawn uniformly from the circle, by rng or the random module's own generator.

def closest_point_to( self, point: 'PointLike') -> tuple[Point, float]:
86    def closest_point_to(self, point: PointLike) -> tuple[Point, float]:
87        """The point of the circle nearest to `point`, and the distance to it.
88
89        A point inside the circle is its own nearest point, at distance zero. For one outside, the point on the edge
90        is moved toward the center by as little as rounding needs for the circle to hold it.
91        """
92        position = Point(point[:2])
93        offset = position - self._center
94        distance = offset.length
95        if distance <= self._radius:
96            return position, 0.0
97        return self._stepped_inside(self._center + offset * (self._radius / distance)), distance - self._radius

The point of the circle nearest to point, and the distance to it.

A point inside the circle is its own nearest point, at distance zero. For one outside, the point on the edge is moved toward the center by as little as rounding needs for the circle to hold it.

def bounding_rectangle(self) -> Rectangle:
109    def bounding_rectangle(self) -> Rectangle:
110        """The smallest rectangle containing the circle."""
111        diameter = 2 * self._radius
112        return Rectangle(self._center[0] - self._radius, self._center[1] - self._radius, diameter, diameter)

The smallest rectangle containing the circle.

def tiles(self) -> TileSet:
114    def tiles(self) -> TileSet:
115        """Every tile whose center lies in the circle."""
116        tiles_in_circle = self._tile_mask()
117        return TileSet._from_mask(tiles_in_circle.origin, tiles_in_circle.mask)

Every tile whose center lies in the circle.

def intersections_with( self, other: Circle) -> tuple[Point, ...]:
158    def intersections_with(self, other: Circle) -> tuple[Point, ...]:
159        """The points where the two boundaries cross: two, one where the circles touch, none otherwise.
160
161        Concentric circles, the same circle included, report none.
162        """
163        offset = other.center - self._center
164        distance_squared = offset[0] ** 2 + offset[1] ** 2
165        if distance_squared > (self._radius + other.radius) ** 2:
166            return ()
167        if distance_squared < (self._radius - other.radius) ** 2 or distance_squared == 0:
168            return ()
169        distance = math.sqrt(distance_squared)
170        along = (self._radius**2 - other.radius**2 + distance_squared) / (2 * distance)
171        midpoint = self._center + offset * (along / distance)
172        across_squared = self._radius**2 - along**2
173        if across_squared <= 0:
174            return (midpoint,)
175        across = math.sqrt(across_squared) / distance
176        perpendicular = Point((offset[1] * across, -offset[0] * across))
177        return midpoint + perpendicular, midpoint - perpendicular

The points where the two boundaries cross: two, one where the circles touch, none otherwise.

Concentric circles, the same circle included, report none.

@final
@dataclass(frozen=True, slots=True)
class CircleSource:
29@final
30@dataclass(frozen=True, slots=True)
31class CircleSource:
32    """A circle a `SourceField` holds: `value` held throughout `circle` with a sharp `edge`; with a linear or a smooth
33    one, held out to half of `edge_width` inside the circle's edge, falling across the band of that width centered on
34    the edge, to half the value on it and 0 half the width beyond it, as `Edge` says. So the field reaches past `circle`
35    by half the width. It is checked as it is made: raises `TypeError` for a `circle` that is not a `Circle`, and
36    `ValueError` for a radius not above 0, a width given a sharp edge, and a linear or smooth edge's width not above 0.
37    Being frozen, a changed one is made with `dataclasses.replace`, and checked again."""
38
39    circle: Circle
40    value: float
41    edge: Edge = Edge.SHARP
42    edge_width: float = 0.0
43    _x: float = dataclass_field(init=False, repr=False, compare=False)
44    _y: float = dataclass_field(init=False, repr=False, compare=False)
45    _reach: float = dataclass_field(init=False, repr=False, compare=False)
46    """How far from the center the circle's value reaches: the radius and half the edge's width."""
47    _reach_squared: float = dataclass_field(init=False, repr=False, compare=False)
48    _full_within_squared: float = dataclass_field(init=False, repr=False, compare=False)
49    """The square of how far from the center the circle holds its whole value, where its edge begins, or -1 where the
50    edge is wider than the circle and no point holds it."""
51
52    def __post_init__(self) -> None:
53        """Check the circle and its edge, and keep what the reads compare as floats of their own."""
54        if not isinstance(self.circle, Circle):
55            raise TypeError(f"a circle source holds a Circle, not a {type(self.circle).__name__}")
56        radius = float(self.circle.radius)
57        if not radius > 0:
58            raise ValueError(f"a circle's radius lies above 0, got {radius}")
59        if self.edge is Edge.SHARP:
60            if self.edge_width:
61                raise ValueError(f"a sharp edge takes no width, got {self.edge_width}")
62        elif not self.edge_width > 0:
63            raise ValueError(f"a {self.edge.value} edge's width lies above 0, got {self.edge_width}")
64        half_width = self.edge_width / 2.0
65        reach = radius + half_width
66        full_within = radius - half_width
67        center = self.circle.center
68        set_field = object.__setattr__
69        set_field(self, "value", float(self.value))
70        set_field(self, "edge_width", float(self.edge_width))
71        set_field(self, "_x", float(center[0]))
72        set_field(self, "_y", float(center[1]))
73        set_field(self, "_reach", reach)
74        set_field(self, "_reach_squared", reach * reach)
75        set_field(self, "_full_within_squared", full_within * full_within if full_within >= 0 else -1.0)
76
77    def _with_value(self, value: float) -> CircleSource:
78        """The circle holding `value` in place of its own, made as `dataclasses.replace` would make it, at about half
79        the cost."""
80        return CircleSource(self.circle, value, self.edge, self.edge_width)
81
82    def _values_at_distances_squared(self, distances_squared: ndarray) -> ndarray:
83        """The value the circle holds at each of `distances_squared` from its center, worked out as
84        `SourceField.value_at` works out one, to the last bit."""
85        if not self.edge_width:
86            return numpy.where(distances_squared <= self._reach_squared, self.value, 0.0)
87        depths = (self._reach - numpy.sqrt(distances_squared)) / self.edge_width
88        weights = depths * depths * (3.0 - 2.0 * depths) if self.edge is Edge.SMOOTH else depths
89        falling = numpy.where(distances_squared <= self._reach_squared, self.value * weights, 0.0)
90        return numpy.where(distances_squared <= self._full_within_squared, self.value, falling)

A circle a SourceField holds: value held throughout circle with a sharp edge; with a linear or a smooth one, held out to half of edge_width inside the circle's edge, falling across the band of that width centered on the edge, to half the value on it and 0 half the width beyond it, as Edge says. So the field reaches past circle by half the width. It is checked as it is made: raises TypeError for a circle that is not a Circle, and ValueError for a radius not above 0, a width given a sharp edge, and a linear or smooth edge's width not above 0. Being frozen, a changed one is made with dataclasses.replace, and checked again.

CircleSource( circle: Circle, value: float, edge: Edge = <Edge.SHARP: 'sharp'>, edge_width: float = 0.0)
circle: Circle
value: float
edge: Edge
edge_width: float
class Direction(enum.Enum):
14class Direction(Enum):
15    """One of the eight ways from a tile to a neighbor, valued as its step in x and y. North is +y, as the game's y
16    grows upward."""
17
18    EAST = (1, 0)
19    NORTH_EAST = (1, 1)
20    NORTH = (0, 1)
21    NORTH_WEST = (-1, 1)
22    WEST = (-1, 0)
23    SOUTH_WEST = (-1, -1)
24    SOUTH = (0, -1)
25    SOUTH_EAST = (1, -1)
26
27    @property
28    def is_diagonal(self) -> bool:
29        """Whether the direction lies between two axes, such as north-east."""
30        step_x, step_y = self.value
31        return step_x != 0 and step_y != 0
32
33    @classmethod
34    def closest(cls, vector: PointLike) -> Direction:
35        """The direction whose line lies nearest by angle to the line along `vector`. Raises `ValueError` for a vector
36        of no length, which points nowhere."""
37        vector_x, vector_y = vector[0], vector[1]
38        if vector_x == 0 and vector_y == 0:
39            raise ValueError("a vector of no length has no direction")
40        # The members run counterclockwise from east, an eighth of a turn apart; a half rounds up, as NachOS rounds.
41        eighths_counterclockwise_of_east = math.floor(math.atan2(vector_y, vector_x) / (math.pi / 4) + 0.5) % 8
42        return tuple(cls)[eighths_counterclockwise_of_east]

One of the eight ways from a tile to a neighbor, valued as its step in x and y. North is +y, as the game's y grows upward.

EAST = <Direction.EAST: (1, 0)>
NORTH_EAST = <Direction.NORTH_EAST: (1, 1)>
NORTH = <Direction.NORTH: (0, 1)>
NORTH_WEST = <Direction.NORTH_WEST: (-1, 1)>
WEST = <Direction.WEST: (-1, 0)>
SOUTH_WEST = <Direction.SOUTH_WEST: (-1, -1)>
SOUTH = <Direction.SOUTH: (0, -1)>
SOUTH_EAST = <Direction.SOUTH_EAST: (1, -1)>
is_diagonal: bool
27    @property
28    def is_diagonal(self) -> bool:
29        """Whether the direction lies between two axes, such as north-east."""
30        step_x, step_y = self.value
31        return step_x != 0 and step_y != 0

Whether the direction lies between two axes, such as north-east.

@classmethod
def closest(cls, vector: 'PointLike') -> Direction:
33    @classmethod
34    def closest(cls, vector: PointLike) -> Direction:
35        """The direction whose line lies nearest by angle to the line along `vector`. Raises `ValueError` for a vector
36        of no length, which points nowhere."""
37        vector_x, vector_y = vector[0], vector[1]
38        if vector_x == 0 and vector_y == 0:
39            raise ValueError("a vector of no length has no direction")
40        # The members run counterclockwise from east, an eighth of a turn apart; a half rounds up, as NachOS rounds.
41        eighths_counterclockwise_of_east = math.floor(math.atan2(vector_y, vector_x) / (math.pi / 4) + 0.5) % 8
42        return tuple(cls)[eighths_counterclockwise_of_east]

The direction whose line lies nearest by angle to the line along vector. Raises ValueError for a vector of no length, which points nowhere.

class Edge(enum.Enum):
 7class Edge(Enum):
 8    """How a `SourceField`'s circle falls from its value to 0 at its edge: at once, or across a band of `edge_width`
 9    centered on the edge, by a point's depth `t` in the band, how far it lies from the band's outer end in band widths:
10    1 where the band begins, half the edge's width inside the circle, ½ on the circle's edge, and 0 half the width
11    beyond it. A band wider than the circle leaves no point holding the whole value, and the center holds what its depth
12    gives."""
13
14    SHARP = "sharp"
15    """At once: the circle holds its whole value out to its edge, and none beyond, so it takes no width."""
16    LINEAR = "linear"
17    """Evenly, by `t`: a constant slope across the band, which turns at once where the band begins and ends."""
18    SMOOTH = "smooth"
19    """By the smoothstep `t²(3 − 2t)`: its slope eases to 0 where the band begins and ends, so that the field has no
20    kink there and its gradient no jump."""

How a SourceField's circle falls from its value to 0 at its edge: at once, or across a band of edge_width centered on the edge, by a point's depth t in the band, how far it lies from the band's outer end in band widths: 1 where the band begins, half the edge's width inside the circle, ½ on the circle's edge, and 0 half the width beyond it. A band wider than the circle leaves no point holding the whole value, and the center holds what its depth gives.

SHARP = <Edge.SHARP: 'sharp'>

At once: the circle holds its whole value out to its edge, and none beyond, so it takes no width.

LINEAR = <Edge.LINEAR: 'linear'>

Evenly, by t: a constant slope across the band, which turns at once where the band begins and ends.

SMOOTH = <Edge.SMOOTH: 'smooth'>

By the smoothstep t²(3 − 2t): its slope eases to 0 where the band begins and ends, so that the field has no kink there and its gradient no jump.

class Field(typing.Protocol, typing.Generic[T]):
17class Field[T: float](Protocol):
18    """A value at every position on the map, such as a threat or a mask: read at a point, as the smallest or the
19    largest over an area and where it lies, or as its slope. `Grid` holds one value per tile, and `SourceField` adds up
20    circles.
21
22    A point or an area the field does not cover raises `IndexError`, and an empty area `ValueError`.
23    """
24
25    def value_at(self, point: PointLike) -> T:
26        """The value at `point`."""
27        ...
28
29    def values_at(self, points: Sequence[PointLike] | ndarray) -> ndarray:
30        """The value at each of `points`, a sequence of points or an array of them, a point a row, as `value_at` reads
31        it, through numpy: an array, a value a point, in order."""
32        ...
33
34    def min(self, *, within: Area) -> T:
35        """The smallest value anywhere in `within`."""
36        ...
37
38    def max(self, *, within: Area) -> T:
39        """The largest value anywhere in `within`."""
40        ...
41
42    def argmin(self, *, within: Area) -> Point:
43        """A point where the value within `within` is smallest. A grid answers the center of that tile, which
44        `within` may not hold, and a source field one of the points it reads, which `within` holds."""
45        ...
46
47    def argmax(self, *, within: Area) -> Point:
48        """A point where the value within `within` is largest, as `argmin` answers one."""
49        ...
50
51    def gradient_at(self, point: PointLike) -> tuple[float, float]:
52        """How fast the value rises at `point`, per map unit, along x and along y, together pointing the way it rises
53        fastest. Raises `TypeError` for a field of booleans."""
54        ...

A value at every position on the map, such as a threat or a mask: read at a point, as the smallest or the largest over an area and where it lies, or as its slope. Grid holds one value per tile, and SourceField adds up circles.

A point or an area the field does not cover raises IndexError, and an empty area ValueError.

Field(*args, **kwargs)
1739def _no_init_or_replace_init(self, *args, **kwargs):
1740    cls = type(self)
1741
1742    if cls._is_protocol:
1743        raise TypeError('Protocols cannot be instantiated')
1744
1745    # Already using a custom `__init__`. No need to calculate correct
1746    # `__init__` to call. This can lead to RecursionError. See bpo-45121.
1747    if cls.__init__ is not _no_init_or_replace_init:
1748        return
1749
1750    # Initially, `__init__` of a protocol subclass is set to `_no_init_or_replace_init`.
1751    # The first instantiation of the subclass will call `_no_init_or_replace_init` which
1752    # searches for a proper new `__init__` in the MRO. The new `__init__`
1753    # replaces the subclass' old `__init__` (ie `_no_init_or_replace_init`). Subsequent
1754    # instantiation of the protocol subclass will thus use the new
1755    # `__init__` and no longer call `_no_init_or_replace_init`.
1756    for base in cls.__mro__:
1757        init = base.__dict__.get('__init__', _no_init_or_replace_init)
1758        if init is not _no_init_or_replace_init:
1759            cls.__init__ = init
1760            break
1761    else:
1762        # should not happen
1763        cls.__init__ = object.__init__
1764
1765    cls.__init__(self, *args, **kwargs)
def value_at(self, point: 'PointLike') -> 'T':
25    def value_at(self, point: PointLike) -> T:
26        """The value at `point`."""
27        ...

The value at point.

def values_at(self, points: 'Sequence[PointLike] | ndarray') -> numpy.ndarray:
29    def values_at(self, points: Sequence[PointLike] | ndarray) -> ndarray:
30        """The value at each of `points`, a sequence of points or an array of them, a point a row, as `value_at` reads
31        it, through numpy: an array, a value a point, in order."""
32        ...

The value at each of points, a sequence of points or an array of them, a point a row, as value_at reads it, through numpy: an array, a value a point, in order.

def min(self, *, within: Area) -> 'T':
34    def min(self, *, within: Area) -> T:
35        """The smallest value anywhere in `within`."""
36        ...

The smallest value anywhere in within.

def max(self, *, within: Area) -> 'T':
38    def max(self, *, within: Area) -> T:
39        """The largest value anywhere in `within`."""
40        ...

The largest value anywhere in within.

def argmin( self, *, within: Area) -> Point:
42    def argmin(self, *, within: Area) -> Point:
43        """A point where the value within `within` is smallest. A grid answers the center of that tile, which
44        `within` may not hold, and a source field one of the points it reads, which `within` holds."""
45        ...

A point where the value within within is smallest. A grid answers the center of that tile, which within may not hold, and a source field one of the points it reads, which within holds.

def argmax( self, *, within: Area) -> Point:
47    def argmax(self, *, within: Area) -> Point:
48        """A point where the value within `within` is largest, as `argmin` answers one."""
49        ...

A point where the value within within is largest, as argmin answers one.

def gradient_at(self, point: 'PointLike') -> tuple[float, float]:
51    def gradient_at(self, point: PointLike) -> tuple[float, float]:
52        """How fast the value rises at `point`, per map unit, along x and along y, together pointing the way it rises
53        fastest. Raises `TypeError` for a field of booleans."""
54        ...

How fast the value rises at point, per map unit, along x and along y, together pointing the way it rises fastest. Raises TypeError for a field of booleans.

@final
class Footprint:
 21@final
 22class Footprint:
 23    """The tiles a structure covers, as a mask laid around its center.
 24
 25    Along a side of odd length the mask centers on the tile holding the center, and along a side of even length on the
 26    tile corner nearest it, as the game snaps a structure: a 3x3 barracks stands on a tile center, a 2x2 depot on a
 27    tile corner, and a 2x1 mineral field on the edge between two tiles. A grid says where a footprint fits on it.
 28    """
 29
 30    __slots__ = ("_mask",)
 31
 32    _mask: ndarray
 33
 34    def __init__(self, mask: ndarray) -> None:
 35        """A footprint covering the true entries of `mask`, indexed `[x, y]` from its lower left tile. A mask with no
 36        entries is the empty footprint, whatever its shape."""
 37        if mask.ndim != 2:
 38            raise ValueError(f"a footprint is two-dimensional, got {mask.ndim} dimensions")
 39        self._mask = numpy.array(mask, dtype=bool) if mask.size else numpy.zeros((0, 0), dtype=bool)
 40        self._mask.flags.writeable = False
 41
 42    @classmethod
 43    def from_rows(cls, *rows: str) -> Footprint:
 44        """The footprint `rows` draw, the top row first: `#` covered, `.` not. No rows cover nothing. Raises
 45        `ValueError` for rows of different lengths, or with any other character."""
 46        if len({len(row) for row in rows}) > 1:
 47            raise ValueError(f"the rows of a footprint are all as long, got {rows}")
 48        if set("".join(rows)) - {"#", "."}:
 49            raise ValueError(f"a footprint's rows hold only '#' and '.', got {rows}")
 50        width = len(rows[0]) if rows else 0
 51        mask = numpy.array([[row[x] == "#" for row in reversed(rows)] for x in range(width)], dtype=bool)
 52        return cls(mask.reshape(width, len(rows)))
 53
 54    @classmethod
 55    def empty(cls) -> Footprint:
 56        """A footprint covering no tile, as a Xel'Naga healing shrine's does."""
 57        return cls(numpy.zeros((0, 0), dtype=bool))
 58
 59    @classmethod
 60    def rectangle(cls, width: int, height: int, *, cut_corners: int = 0) -> Footprint:
 61        """A footprint covering a rectangle `width` tiles across and `height` up, less, at each corner, the tiles
 62        fewer than `cut_corners` steps from it, counting each step across or up: the corner tile for 1, and the two
 63        beside it too for 2. Raises `ValueError` for a side shorter than 1 or a negative `cut_corners`."""
 64        if width < 1 or height < 1 or cut_corners < 0:
 65            raise ValueError(
 66                f"a rectangle is at least 1x1 with no negative corner cut, got {width}x{height}, {cut_corners}"
 67            )
 68        steps_from_side_x = numpy.minimum(numpy.arange(width), numpy.arange(width)[::-1])[:, numpy.newaxis]
 69        steps_from_side_y = numpy.minimum(numpy.arange(height), numpy.arange(height)[::-1])[numpy.newaxis, :]
 70        return cls(steps_from_side_x + steps_from_side_y >= cut_corners)
 71
 72    @classmethod
 73    def square(cls, side: int, *, cut_corners: int = 0) -> Footprint:
 74        """A footprint covering a square `side` tiles across, less its corners as `rectangle` cuts them."""
 75        return cls.rectangle(side, side, cut_corners=cut_corners)
 76
 77    @property
 78    def mask(self) -> ndarray:
 79        """Whether the footprint covers each tile of its bounding box, indexed `[x, y]` from its lower left tile."""
 80        return self._mask
 81
 82    @property
 83    def width(self) -> int:
 84        """The number of tiles across its bounding box."""
 85        return self._mask.shape[0]
 86
 87    @property
 88    def height(self) -> int:
 89        """The number of tiles up its bounding box."""
 90        return self._mask.shape[1]
 91
 92    def bounding_box(self, *, at: PointLike) -> Rectangle:
 93        """The tiles `mask` spans, with the footprint placed at `at` and centered as the game snaps it. The footprint
 94        covers some of them, or all."""
 95        left, bottom = self._lower_left_tile(at=at)
 96        return Rectangle(left, bottom, self.width, self.height)
 97
 98    def snapped_center(self, *, at: PointLike) -> Point:
 99        """Where the footprint centers when placed at `at`, as the game snaps a structure: for the empty footprint,
100        the tile corner nearest `at`."""
101        left, bottom = self._lower_left_tile(at=at)
102        return Point((left + self.width / 2, bottom + self.height / 2))
103
104    def _lower_left_tile(self, *, at: PointLike) -> tuple[int, int]:
105        """The lower left tile of `mask`, with the footprint placed at `at` and centered as the game snaps it."""
106        x, y = at[0], at[1]
107        return rounded_half_up(x - self.width / 2), rounded_half_up(y - self.height / 2)
108
109    def tiles(self, *, at: PointLike) -> TileSet:
110        """The tiles the footprint covers, placed at `at` and centered as the game snaps it."""
111        left, bottom = self._lower_left_tile(at=at)
112        return TileSet._from_mask(Tile(left, bottom), self._mask)
113
114    def center_in_tile(self, tile: Tile) -> Point:
115        """Where the footprint is centered when its center lies in `tile`: the tile's center along a side of odd
116        length, and its lower left corner along a side of even length."""
117        return Point((tile.x + 0.5 * (self.width % 2), tile.y + 0.5 * (self.height % 2)))
118
119    def _grown(self, sides: tuple[int, int, int, int]) -> Footprint:
120        """This footprint and every tile within `sides` of a tile it covers: so many to the left and right of one, and
121        so many below and above it. Its own mask lies at `[left:, bottom:]` of the grown one."""
122        left, right, bottom, top = sides
123        width, height = self.width, self.height
124        grown = numpy.zeros((width + left + right, height + bottom + top), dtype=bool)
125        for dx in range(left + right + 1):
126            for dy in range(bottom + top + 1):
127                grown[dx : dx + width, dy : dy + height] |= self._mask
128        return Footprint(grown)
129
130    def _grown_by(self, margin: Margin, *, at: PointLike) -> tuple[Footprint, PointLike]:
131        """This footprint with every tile within `margin` of one it covers, and where that centers so that this
132        footprint stays centered at `at`. Raises as `_margin_sides` does."""
133        if not any(sides := _margin_sides(margin)):
134            return self, at
135        left, _, bottom, _ = sides
136        lower_left_x, lower_left_y = self._lower_left_tile(at=at)
137        grown = self._grown(sides)
138        # Centered so that its lower left tile lies `left` and `bottom` beyond this footprint's.
139        return grown, (lower_left_x - left + grown.width / 2, lower_left_y - bottom + grown.height / 2)
140
141    def __eq__(self, other: object) -> bool:
142        return isinstance(other, Footprint) and numpy.array_equal(self._mask, other._mask)
143
144    def __hash__(self) -> int:
145        return hash((self._mask.shape, self._mask.tobytes()))
146
147    def __repr__(self) -> str:
148        return f"Footprint({self.width}x{self.height}, {numpy.count_nonzero(self._mask)} tiles)"

The tiles a structure covers, as a mask laid around its center.

Along a side of odd length the mask centers on the tile holding the center, and along a side of even length on the tile corner nearest it, as the game snaps a structure: a 3x3 barracks stands on a tile center, a 2x2 depot on a tile corner, and a 2x1 mineral field on the edge between two tiles. A grid says where a footprint fits on it.

Footprint(mask: numpy.ndarray)
34    def __init__(self, mask: ndarray) -> None:
35        """A footprint covering the true entries of `mask`, indexed `[x, y]` from its lower left tile. A mask with no
36        entries is the empty footprint, whatever its shape."""
37        if mask.ndim != 2:
38            raise ValueError(f"a footprint is two-dimensional, got {mask.ndim} dimensions")
39        self._mask = numpy.array(mask, dtype=bool) if mask.size else numpy.zeros((0, 0), dtype=bool)
40        self._mask.flags.writeable = False

A footprint covering the true entries of mask, indexed [x, y] from its lower left tile. A mask with no entries is the empty footprint, whatever its shape.

@classmethod
def from_rows(cls, *rows: str) -> Footprint:
42    @classmethod
43    def from_rows(cls, *rows: str) -> Footprint:
44        """The footprint `rows` draw, the top row first: `#` covered, `.` not. No rows cover nothing. Raises
45        `ValueError` for rows of different lengths, or with any other character."""
46        if len({len(row) for row in rows}) > 1:
47            raise ValueError(f"the rows of a footprint are all as long, got {rows}")
48        if set("".join(rows)) - {"#", "."}:
49            raise ValueError(f"a footprint's rows hold only '#' and '.', got {rows}")
50        width = len(rows[0]) if rows else 0
51        mask = numpy.array([[row[x] == "#" for row in reversed(rows)] for x in range(width)], dtype=bool)
52        return cls(mask.reshape(width, len(rows)))

The footprint rows draw, the top row first: # covered, . not. No rows cover nothing. Raises ValueError for rows of different lengths, or with any other character.

@classmethod
def empty(cls) -> Footprint:
54    @classmethod
55    def empty(cls) -> Footprint:
56        """A footprint covering no tile, as a Xel'Naga healing shrine's does."""
57        return cls(numpy.zeros((0, 0), dtype=bool))

A footprint covering no tile, as a Xel'Naga healing shrine's does.

@classmethod
def rectangle( cls, width: int, height: int, *, cut_corners: int = 0) -> Footprint:
59    @classmethod
60    def rectangle(cls, width: int, height: int, *, cut_corners: int = 0) -> Footprint:
61        """A footprint covering a rectangle `width` tiles across and `height` up, less, at each corner, the tiles
62        fewer than `cut_corners` steps from it, counting each step across or up: the corner tile for 1, and the two
63        beside it too for 2. Raises `ValueError` for a side shorter than 1 or a negative `cut_corners`."""
64        if width < 1 or height < 1 or cut_corners < 0:
65            raise ValueError(
66                f"a rectangle is at least 1x1 with no negative corner cut, got {width}x{height}, {cut_corners}"
67            )
68        steps_from_side_x = numpy.minimum(numpy.arange(width), numpy.arange(width)[::-1])[:, numpy.newaxis]
69        steps_from_side_y = numpy.minimum(numpy.arange(height), numpy.arange(height)[::-1])[numpy.newaxis, :]
70        return cls(steps_from_side_x + steps_from_side_y >= cut_corners)

A footprint covering a rectangle width tiles across and height up, less, at each corner, the tiles fewer than cut_corners steps from it, counting each step across or up: the corner tile for 1, and the two beside it too for 2. Raises ValueError for a side shorter than 1 or a negative cut_corners.

@classmethod
def square( cls, side: int, *, cut_corners: int = 0) -> Footprint:
72    @classmethod
73    def square(cls, side: int, *, cut_corners: int = 0) -> Footprint:
74        """A footprint covering a square `side` tiles across, less its corners as `rectangle` cuts them."""
75        return cls.rectangle(side, side, cut_corners=cut_corners)

A footprint covering a square side tiles across, less its corners as rectangle cuts them.

mask: numpy.ndarray
77    @property
78    def mask(self) -> ndarray:
79        """Whether the footprint covers each tile of its bounding box, indexed `[x, y]` from its lower left tile."""
80        return self._mask

Whether the footprint covers each tile of its bounding box, indexed [x, y] from its lower left tile.

width: int
82    @property
83    def width(self) -> int:
84        """The number of tiles across its bounding box."""
85        return self._mask.shape[0]

The number of tiles across its bounding box.

height: int
87    @property
88    def height(self) -> int:
89        """The number of tiles up its bounding box."""
90        return self._mask.shape[1]

The number of tiles up its bounding box.

def bounding_box(self, *, at: 'PointLike') -> Rectangle:
92    def bounding_box(self, *, at: PointLike) -> Rectangle:
93        """The tiles `mask` spans, with the footprint placed at `at` and centered as the game snaps it. The footprint
94        covers some of them, or all."""
95        left, bottom = self._lower_left_tile(at=at)
96        return Rectangle(left, bottom, self.width, self.height)

The tiles mask spans, with the footprint placed at at and centered as the game snaps it. The footprint covers some of them, or all.

def snapped_center(self, *, at: 'PointLike') -> Point:
 98    def snapped_center(self, *, at: PointLike) -> Point:
 99        """Where the footprint centers when placed at `at`, as the game snaps a structure: for the empty footprint,
100        the tile corner nearest `at`."""
101        left, bottom = self._lower_left_tile(at=at)
102        return Point((left + self.width / 2, bottom + self.height / 2))

Where the footprint centers when placed at at, as the game snaps a structure: for the empty footprint, the tile corner nearest at.

def tiles(self, *, at: 'PointLike') -> TileSet:
109    def tiles(self, *, at: PointLike) -> TileSet:
110        """The tiles the footprint covers, placed at `at` and centered as the game snaps it."""
111        left, bottom = self._lower_left_tile(at=at)
112        return TileSet._from_mask(Tile(left, bottom), self._mask)

The tiles the footprint covers, placed at at and centered as the game snaps it.

def center_in_tile( self, tile: Tile) -> Point:
114    def center_in_tile(self, tile: Tile) -> Point:
115        """Where the footprint is centered when its center lies in `tile`: the tile's center along a side of odd
116        length, and its lower left corner along a side of even length."""
117        return Point((tile.x + 0.5 * (self.width % 2), tile.y + 0.5 * (self.height % 2)))

Where the footprint is centered when its center lies in tile: the tile's center along a side of odd length, and its lower left corner along a side of even length.

@final
class Grid(typing.Generic[T]):
 39@final
 40class Grid[T: float]:
 41    """A grid of per-tile values, addressed by map position rather than by array index.
 42
 43    `origin` is the tile at the grid's lower left corner, so a grid can cover the playable area alone. An area
 44    reaching past the edge is clipped to the tiles the grid holds; a point outside it raises `IndexError`.
 45
 46    A grid the library shares, such as the map's, and the grids of `CheapestPaths` are `readonly` and refuse every
 47    write. `copy()` gives a writable one, as does every other grid derived from one.
 48    """
 49
 50    __slots__ = ("_data", "_origin", "_outside", "_readonly")
 51
 52    _data: ndarray
 53    _origin: Tile
 54    _outside: T | None
 55    _readonly: bool
 56
 57    # --- Construction
 58
 59    def __init__(
 60        self, data: ndarray, *, origin: Tile = _ORIGIN, outside: T | None = None, readonly: bool = False
 61    ) -> None:
 62        """A grid holding `data`, whose `[0, 0]` entry is the tile at `origin`.
 63
 64        `outside` is what a read beyond the grid returns; without it such a read raises. A write beyond the grid
 65        always raises, and a `readonly` grid refuses every write.
 66        """
 67        if data.ndim != 2:
 68            raise ValueError(f"a grid is two-dimensional, got {data.ndim} dimensions")
 69        self._data = data
 70        self._origin = origin
 71        self._outside = outside
 72        self._readonly = readonly
 73
 74    @classmethod
 75    def zeros(
 76        cls, width: int, height: int, *, origin: Tile = _ORIGIN, dtype: type[T] = float, outside: T | None = None
 77    ) -> Grid[T]:
 78        """A grid of `width` by `height` tiles, filled with zeros."""
 79        return Grid(numpy.zeros((width, height), dtype=dtype), origin=origin, outside=outside)
 80
 81    @classmethod
 82    def like[U: float](cls, other: Grid[U], *, dtype: type[T] = float, outside: T | None = None) -> Grid[T]:
 83        """A grid of zeros covering the same tiles as `other`."""
 84        return Grid(numpy.zeros(other._data.shape, dtype=dtype), origin=other._origin, outside=outside)
 85
 86    # --- The ground it covers
 87
 88    @property
 89    def origin(self) -> Tile:
 90        """The tile at the grid's lower left corner."""
 91        return self._origin
 92
 93    @property
 94    def width(self) -> int:
 95        """The number of tiles across."""
 96        return self._data.shape[0]
 97
 98    @property
 99    def height(self) -> int:
100        """The number of tiles up."""
101        return self._data.shape[1]
102
103    @property
104    def bounds(self) -> Rectangle:
105        """The ground the grid covers."""
106        return Rectangle(self._origin.x, self._origin.y, self.width, self.height)
107
108    @property
109    def values(self) -> ndarray:
110        """A read-only view of the grid, indexed `[x, y]` from `origin`."""
111        view = self._data.view()
112        view.flags.writeable = False
113        return view
114
115    def index_of(self, point: PointLike | Tile) -> tuple[int, int]:
116        """The index into `values` of the tile holding `point`, a tile reading as itself.
117
118        Raises `IndexError` for a point the grid does not cover, whatever `outside` is.
119        """
120        if (index := self._index_if_covered(point)) is None:
121            raise IndexError(f"{Tile.at(point)!r} lies outside {self.bounds!r}")
122        return index
123
124    def _index_if_covered(self, point: PointLike | Tile) -> tuple[int, int] | None:
125        """The index into `values` of the tile holding `point`, or `None` for a point the grid does not cover."""
126        tile_x, tile_y = Tile._address_at(point)
127        x = tile_x - self._origin.x
128        y = tile_y - self._origin.y
129        if 0 <= x < self._data.shape[0] and 0 <= y < self._data.shape[1]:
130            return x, y
131        return None
132
133    def tile_at(self, index: tuple[int, int]) -> Tile:
134        """The tile an index into `values` addresses. The inverse of `index_of`."""
135        x, y = index
136        if not (0 <= x < self._data.shape[0] and 0 <= y < self._data.shape[1]):
137            raise IndexError(f"{index} lies outside a {self.width} by {self.height} grid")
138        return self._origin.shifted(x, y)
139
140    @property
141    def outside(self) -> T | None:
142        """What a read beyond the grid returns, or `None` if one raises."""
143        return self._outside
144
145    @property
146    def readonly(self) -> bool:
147        """Whether the grid refuses writes."""
148        return self._readonly
149
150    def with_outside(self, value: T | None) -> Grid[T]:
151        """The same grid, reading `value` beyond its edge.
152
153        It shares the data rather than copying it, and stays read-only if this grid is.
154        """
155        return Grid(self._data, origin=self._origin, outside=value, readonly=self._readonly)
156
157    def value_at(self, point: PointLike | Tile) -> T:
158        """The value at `point`, a tile reading as itself, or `outside` beyond the grid, which raises `IndexError` if
159        that is `None`."""
160        if (index := self._index_if_covered(point)) is not None:
161            return self._data.item(index)
162        if self._outside is None:
163            raise IndexError(f"{Tile.at(point)!r} lies outside {self.bounds!r}")
164        return self._outside
165
166    def values_at(self, points: Sequence[PointLike] | ndarray) -> ndarray:
167        """The value at each of `points`, a sequence of points or an array of them, a point a row, as `value_at` reads
168        it, in one numpy pass: an array of the grid's values, a value a point, in order, `outside` beyond the grid.
169        Raises `IndexError` for a point beyond the grid where it reads no `outside`. A sequence of points first becomes
170        an array, which takes most of the time: the pass pays off most on points already in an array."""
171        xs, ys = coordinate_arrays_of(points)
172        columns = numpy.floor(xs).astype(numpy.intp) - self._origin.x
173        rows = numpy.floor(ys).astype(numpy.intp) - self._origin.y
174        width, height = self._data.shape
175        covered = (columns >= 0) & (columns < width) & (rows >= 0) & (rows < height)
176        if covered.all():
177            return self._data[columns, rows]
178        if self._outside is None:
179            first_beyond = int(numpy.argmin(covered))
180            point = (xs[first_beyond].item(), ys[first_beyond].item())
181            raise IndexError(f"{Tile.at(point)!r} lies outside {self.bounds!r}")
182        values = numpy.full(len(xs), self._outside, dtype=numpy.result_type(self._data.dtype, self._outside))
183        values[covered] = self._data[columns[covered], rows[covered]]
184        return values
185
186    def _aligned(self, other: Grid) -> ndarray:
187        """The values of `other`, which must cover the same tiles as this grid."""
188        if not isinstance(other, Grid):
189            raise TypeError(f"expected a grid, got {type(other).__name__}")
190        if other._data.shape != self._data.shape or other._origin != self._origin:
191            raise ValueError(f"{other!r} does not cover the same tiles as {self!r}")
192        return other._data
193
194    # --- Reading and writing
195
196    # `Tile` is an `Area`, and the only one that addresses a single tile, so it must be matched first. The overlap
197    # is real: a key typed `Area` that holds a `Tile` is annotated `ndarray` but returns a scalar.
198    @overload
199    def __getitem__(self, key: Tile) -> T: ...  # pyright: ignore[reportOverlappingOverload]
200
201    @overload
202    def __getitem__(self, key: Rectangle | Area | Grid[bool]) -> ndarray: ...
203    @overload
204    def __getitem__(self, key: PointLike) -> T: ...
205
206    def __getitem__(self, key: PointLike | Area | Grid[bool]) -> T | ndarray:
207        """The value at a point, the values over an area, or the values a mask selects. The values over a rectangle
208        are a view, read-only when the grid is; the others are a copy, by ascending x, then y."""
209        # Points first, checked as tuples, then a tile, which addresses a single tile like any point. A miss here is
210        # cheap; a miss against an `Area` subclass is not.
211        if isinstance(key, tuple) or type(key) is Tile:
212            return self.value_at(key)
213        if isinstance(key, Rectangle):
214            view = self._data[self._slices(key)]
215            if self._readonly:
216                view.flags.writeable = False
217            return view
218        if isinstance(key, Area):
219            grid_slices, area_mask_on_grid = self._slices_and_mask_for_area(key)
220            return self._data[grid_slices][area_mask_on_grid]
221        if isinstance(key, Grid):
222            return self._data[self._mask(key)]
223        return self.value_at(key)
224
225    def __setitem__(self, key: PointLike | Area | Grid[bool], value: T | ndarray) -> None:
226        """Writes a value at a point, over an area, or over the tiles a mask selects."""
227        self._refuse_readonly()
228        if isinstance(key, tuple) or type(key) is Tile:
229            self._data[self.index_of(key)] = value
230        elif isinstance(key, Rectangle):
231            self._data[self._slices(key)] = value
232        elif isinstance(key, Area):
233            grid_slices, area_mask_on_grid = self._slices_and_mask_for_area(key)
234            self._data[grid_slices][area_mask_on_grid] = value
235        elif isinstance(key, Grid):
236            self._data[self._mask(key)] = value
237        else:
238            self._data[self.index_of(key)] = value
239
240    def fill(self, value: T) -> None:
241        """Sets every tile to `value`."""
242        self._refuse_readonly()
243        self._data[:] = value
244
245    def fill_footprint(self, footprint: Footprint, *, at: PointLike, value: T, margin: Margin = 0) -> None:
246        """Sets every tile `footprint` covers, centered at `at`, to `value`, and with `margin`, every tile within it of
247        one the footprint covers, as `fits_footprint` takes it, skipping those beyond the grid. Raises `ValueError` for
248        a negative margin."""
249        self._refuse_readonly()
250        footprint, at = footprint._grown_by(margin, at=at)
251        grid_slices, mask_slices = self._slices_for_footprint(footprint, at)
252        self._data[grid_slices][footprint.mask[mask_slices]] = value
253
254    def fits_footprint(self: Grid[bool], footprint: Footprint, *, at: PointLike, margin: Margin = 0) -> bool:
255        """Whether every tile `footprint` covers, centered at `at`, is true, and with `margin`, every tile within it of
256        one the footprint covers: as many on every side, or so many on its left, right, bottom and top. A tile beyond
257        the grid reads `outside`, and raises `IndexError` if that is `None`. Raises `ValueError` for a negative
258        margin."""
259        footprint, at = footprint._grown_by(margin, at=at)
260        grid_slices, mask_slices = self._slices_for_footprint(footprint, at)
261        covered_on_grid = footprint.mask[mask_slices]
262        if numpy.count_nonzero(covered_on_grid) < numpy.count_nonzero(footprint.mask):
263            if self._outside is None:
264                raise IndexError(f"{footprint!r} centered at {at} reaches past {self.bounds!r}")
265            if not self._outside:
266                return False
267        return bool((self._data[grid_slices].astype(bool, copy=False) | ~covered_on_grid).all())
268
269    def _refuse_readonly(self) -> None:
270        """Raises unless this grid can be written to."""
271        if self._readonly:
272            raise TypeError(f"{self!r} is read-only, because it is shared; copy() it to change it")
273
274    def _slices_for_footprint(
275        self, footprint: Footprint, center: PointLike
276    ) -> tuple[tuple[slice, slice], tuple[slice, slice]]:
277        """The slices that line `footprint`, centered at `center`, up with the grid: first those of the grid's values
278        under its bounding box, clipped to the grid, then those of its mask over the same tiles. A 3x3 footprint
279        centered on the grid's lower left tile meets the values in `[0:2, 0:2]` with its mask's `[1:3, 1:3]`. Both are
280        empty where it lies wholly beyond the grid."""
281        left, bottom = footprint._lower_left_tile(at=center)
282        return self._slices_for_mask(left, bottom, footprint.mask.shape)
283
284    def _slices_and_mask_for_area(self, area: Area) -> tuple[tuple[slice, slice], ndarray]:
285        """The slices of the grid's values over the tiles `area` covers, clipped to the grid, and the mask of those
286        tiles over the same slices."""
287        area_tiles = area._tile_mask(self.bounds)
288        grid_slices, mask_slices = self._slices_for_tile_mask(area_tiles)
289        return grid_slices, area_tiles.mask[mask_slices]
290
291    def _slices_for_tile_mask(self, tiles: TileMask) -> tuple[tuple[slice, slice], tuple[slice, slice]]:
292        """The slices that line `tiles` up with the grid, as `_slices_for_mask` gives them."""
293        return self._slices_for_mask(tiles.origin.x, tiles.origin.y, tiles.mask.shape)
294
295    def _slices_for_mask(
296        self, left: int, bottom: int, shape: tuple[int, ...]
297    ) -> tuple[tuple[slice, slice], tuple[slice, slice]]:
298        """The slices that line a mask of `shape`, whose `[0, 0]` entry is the tile at `left` and `bottom`, up with the
299        grid: first those of the grid's values under it, clipped to the grid, then those of the mask over the same
300        tiles. Both are empty where it lies wholly beyond the grid."""
301        width, height = self._data.shape
302        mask_x, mask_y = left - self._origin.x, bottom - self._origin.y
303        x = min(max(mask_x, 0), width)
304        y = min(max(mask_y, 0), height)
305        stop_x = min(max(mask_x + shape[0], x), width)
306        stop_y = min(max(mask_y + shape[1], y), height)
307        grid_slices = (slice(x, stop_x), slice(y, stop_y))
308        return grid_slices, (slice(x - mask_x, stop_x - mask_x), slice(y - mask_y, stop_y - mask_y))
309
310    def _slices(self, rectangle: Rectangle) -> tuple[slice, slice]:
311        """The array slices covering the tiles of `rectangle`, clipped to the grid."""
312        x_range, y_range = rectangle.tile_range()
313        grid_slices, _ = self._slices_for_mask(x_range.start, y_range.start, (len(x_range), len(y_range)))
314        return grid_slices
315
316    def _mask(self, mask: Grid[bool]) -> ndarray:
317        """The values of `mask`, which must cover the same tiles and hold booleans; numpy would read any other dtype
318        as row indices."""
319        values = self._aligned(mask)
320        if values.dtype != bool:
321            raise TypeError(f"a grid used as a mask must hold booleans, got {values.dtype}")
322        return values
323
324    # --- Derived grids
325
326    def copy(self) -> Grid[T]:
327        """An independent grid holding the same values."""
328        return Grid(self._data.copy(), origin=self._origin, outside=self._outside)
329
330    def as_readonly(self) -> Grid[T]:
331        """The same grid, refusing writes. It shares the values, so a write to this grid shows in it."""
332        return Grid(self.values, origin=self._origin, outside=self._outside, readonly=True)
333
334    def where_footprint_fits(self: Grid[bool], footprint: Footprint, *, margin: Margin = 0) -> Grid[bool]:
335        """Where `footprint` fits, with `margin` as `fits_footprint` takes it, by the tile holding its center: true
336        where every tile it covers, centered as `footprint.center_in_tile` says, is true, which is this grid eroded by
337        the footprint. A tile beyond the grid reads `outside`, or false if that is `None`. The result covers the same
338        tiles as this grid and reads false beyond them. Raises `ValueError` for a negative margin."""
339        values = self._data.astype(bool, copy=False)
340        if any(sides := _margin_sides(margin)):
341            return Grid(self._where_grown_fits(values, footprint, sides), origin=self._origin, outside=False)
342        if not footprint.mask.any():
343            return Grid(numpy.ones_like(values), origin=self._origin, outside=False)
344        # The structure's own center, index `side // 2` along each axis, is where `center_in_tile` centers a footprint.
345        fitting = scipy.ndimage.binary_erosion(values, structure=footprint.mask, border_value=int(bool(self._outside)))
346        return Grid(fitting, origin=self._origin, outside=False)
347
348    def _where_grown_fits(self, values: ndarray, footprint: Footprint, sides: tuple[int, int, int, int]) -> ndarray:
349        """Where `footprint` fits on `values` with `sides` free beside it, by the tile holding its center."""
350        left, _, bottom, _ = sides
351        grown = footprint._grown(sides)
352        if not grown.mask.any():
353            return numpy.ones_like(values)
354        # Padded so that every center on the grid has its grown footprint's center on the padding or the grid.
355        pad = max(sides)
356        border = bool(self._outside)
357        padded = numpy.pad(values, pad, constant_values=border)
358        fitting = scipy.ndimage.binary_erosion(padded, structure=grown.mask, border_value=int(border))
359        # The tile holding the footprint's center lies this far from the one holding the grown footprint's.
360        dx = left + footprint.width // 2 - grown.width // 2
361        dy = bottom + footprint.height // 2 - grown.height // 2
362        width, height = values.shape
363        return fitting[pad - dx : pad - dx + width, pad - dy : pad - dy + height]
364
365    def where(self, condition: Grid[bool], other: T | Grid[T]) -> Grid[T]:
366        """This grid where `condition` holds, and `other` everywhere else."""
367        values = self._aligned(other) if isinstance(other, Grid) else other
368        # `_aligned` runs before `_where_outside`: it rejects a condition that is not a grid, and `_where_outside`
369        # reads `condition._outside`, which needs that check to have passed.
370        chosen = numpy.where(self._aligned(condition), self._data, values)
371        return Grid(chosen, origin=self._origin, outside=self._where_outside(condition, other))
372
373    def _where_outside(self, condition: Grid[bool], other: T | Grid[T]) -> T | None:
374        """The off-grid value of whichever operand the condition picks off-grid, or `None` if it has none."""
375        if condition._outside is None:
376            return None
377        if condition._outside:
378            return self._outside
379        return other._outside if isinstance(other, Grid) else other
380
381    def minimum(self, other: Grid[T]) -> Grid[T]:
382        """The smaller of the two values on each tile."""
383        return self._combine(other, numpy.minimum)
384
385    def maximum(self, other: Grid[T]) -> Grid[T]:
386        """The larger of the two values on each tile."""
387        return self._combine(other, numpy.maximum)
388
389    def cropped(self, rectangle: Rectangle) -> Grid[T]:
390        """An independent grid over the tiles `rectangle` covers, clipped to the ones this grid holds."""
391        x, y = self._slices(rectangle)
392        origin = self._origin.shifted(x.start, y.start)
393        return Grid(self._data[x, y].copy(), origin=origin, outside=self._outside)
394
395    def distance_from(self, point: PointLike, *, outside: float | None = None) -> Grid[float]:
396        """The distance from each tile's center to `point`."""
397        xs = numpy.arange(self.width) + self._origin.x + 0.5 - point[0]
398        ys = numpy.arange(self.height) + self._origin.y + 0.5 - point[1]
399        return Grid(numpy.hypot(xs[:, None], ys[None, :]), origin=self._origin, outside=outside)
400
401    def distance_transform(self: Grid[bool], *, outside: float | None = None) -> Grid[float]:
402        """For each true tile, the distance from its center to the nearest false tile's; zero on a false tile. Where
403        this grid reads false beyond its edge, the tiles beyond it count as false; where no false tile is found, every
404        distance is `inf`."""
405        if self._outside is not None and not self._outside:
406            padded = numpy.pad(self._data, 1, constant_values=False)
407            distances = numpy.asarray(scipy.ndimage.distance_transform_edt(padded, return_indices=False))[1:-1, 1:-1]
408        elif self._data.all():
409            distances = numpy.full(self._data.shape, math.inf)
410        else:
411            distances = numpy.asarray(scipy.ndimage.distance_transform_edt(self._data, return_indices=False))
412        return Grid(distances, origin=self._origin, outside=outside)
413
414    def cheapest_path(self, start: PointLike | Tile, end: PointLike | Tile) -> TilePath | None:
415        """The cheapest path from the tile holding `start` to the tile holding `end`, or `None` if there is none. Of
416        several equally cheap paths it is one, but which is not part of the contract.
417
418        Each tile's value is the cost of moving one unit of distance across it, and 0 and `inf` block it, so on a grid
419        of bools, where true costs 1 and false blocks, the cheapest path is a shortest one. A negative or NaN value
420        raises `ValueError`. A step goes to a tile sharing a side or a corner, 1 or sqrt(2) long, and costs its length
421        times the mean of the two tiles' values; a diagonal step needs both tiles sharing a side with the two passable,
422        so no path cuts a corner. The start is a path to itself even on a blocked tile, but no path leaves one. Raises
423        `IndexError` for a point the grid does not cover.
424        """
425        start_index = self.index_of(start)
426        end_index = self.index_of(end)
427        with self._bad_cost_named_by_its_tile():
428            found = semita.cheapest_path(self._data, start_index, end_index)
429        return None if found is None else _semita_path_to_tile_path(found, self._origin)
430
431    def cheapest_paths_from(self, start: PointLike | Tile, *, outside: float | None = None) -> CheapestPaths:
432        """The cheapest path from the tile holding `start` to every tile, over the steps `cheapest_path` takes, found in
433        one search: their costs, their lengths and each one's tiles. `outside` is what the costs and the lengths read
434        beyond the grid. Raises as `cheapest_path` does.
435        """
436        start_index = self.index_of(start)
437        with self._bad_cost_named_by_its_tile():
438            found = semita.cheapest_paths_from(self._data, start_index)
439        costs = Grid(found.costs, origin=self._origin, outside=outside, readonly=True)
440        distances = Grid(found.distances, origin=self._origin, outside=outside, readonly=True)
441        return CheapestPaths(costs, distances, found)
442
443    @contextlib.contextmanager
444    def _bad_cost_named_by_its_tile(self) -> Iterator[None]:
445        """Within it, the `ValueError` a search raises for a negative or NaN cost names the cost's tile rather than its
446        index into `values`."""
447        try:
448            yield
449        except ValueError as error:
450            bad_costs = numpy.argwhere(~(self._data >= 0))
451            if not len(bad_costs):
452                raise
453            index = (int(bad_costs[0][0]), int(bad_costs[0][1]))
454            tile = self.tile_at(index)
455            cost = self._data.item(index)
456            message = f"the cost at {tile!r} is {cost!r}; a tile's cost is positive, or 0 or inf to block it"
457            raise ValueError(message) from error
458
459    def smoothed(self, sigma: float, *, within: Grid[bool] | None = None, outside: float | None = None) -> Grid[float]:
460        """A Gaussian blur of the values, `sigma` measured in tiles.
461
462        Given `within`, only those tiles contribute and the result is renormalized, so values near the edge
463        of the region are not dragged down by the tiles outside it. A tile no contributor reaches keeps its
464        own value.
465        """
466        values = self._data.astype(float)
467        if within is None:
468            return Grid(scipy.ndimage.gaussian_filter(values, sigma=sigma), origin=self._origin, outside=outside)
469        weights = self._mask(within).astype(float)
470        numerator = scipy.ndimage.gaussian_filter(values * weights, sigma=sigma)
471        denominator = scipy.ndimage.gaussian_filter(weights, sigma=sigma)
472        blurred = values.copy()
473        numpy.divide(numerator, denominator, out=blurred, where=denominator > 0)
474        return Grid(blurred, origin=self._origin, outside=outside)
475
476    # --- Summaries
477
478    def min(self, *, within: Area | None = None) -> T:
479        """The smallest value, or with `within`, the smallest of every tile the area overlaps, a tile it only touches at
480        an edge or a corner left out. A tile beyond the grid reads `outside`, and raises `IndexError` if that is
481        `None`. Raises `ValueError` for an empty area."""
482        if within is None:
483            return self._data.min().item()
484        return self._values_of_tiles_held(within._overlapped_tile_mask(), within).min().item()
485
486    def max(self, *, within: Area | None = None) -> T:
487        """The largest value, or with `within`, the largest of every tile the area overlaps, as `min` takes them."""
488        if within is None:
489            return self._data.max().item()
490        return self._values_of_tiles_held(within._overlapped_tile_mask(), within).max().item()
491
492    def argmin(self, *, within: Area | None = None) -> Point:
493        """The center of the tile `argmin_tile` gives, which `within` may not hold."""
494        return self.argmin_tile(within=within).center
495
496    def argmax(self, *, within: Area | None = None) -> Point:
497        """The center of the tile `argmax_tile` gives, which `within` may not hold."""
498        return self.argmax_tile(within=within).center
499
500    def argmin_tile(self, *, within: Area | None = None) -> Tile:
501        """The tile with the smallest value, or with `within`, the one with the smallest of those the area overlaps,
502        as `min` takes them; the lowest address if several tie."""
503        if within is None:
504            return self._tile_at(int(numpy.argmin(self._data)))
505        return self._extreme_tile(within, largest=False)
506
507    def argmax_tile(self, *, within: Area | None = None) -> Tile:
508        """The tile with the largest value, or with `within`, the one with the largest of those the area overlaps, as
509        `argmin_tile` picks one."""
510        if within is None:
511            return self._tile_at(int(numpy.argmax(self._data)))
512        return self._extreme_tile(within, largest=True)
513
514    def _extreme_tile(self, area: Area, *, largest: bool) -> Tile:
515        """The tile `area` overlaps with the largest value, or the smallest, the lowest address if several tie."""
516        overlapped = area._overlapped_tile_mask()
517        values = self._values_of_tiles_held(overlapped, area)
518        picked = numpy.argmax(values) if largest else numpy.argmin(values)
519        x, y = numpy.unravel_index(int(numpy.flatnonzero(overlapped.mask)[picked]), overlapped.mask.shape)
520        return overlapped.origin.shifted(int(x), int(y))
521
522    def _values_of_tiles_held(self, tiles: TileMask, area: Area) -> ndarray:
523        """The values of the tiles `tiles` holds, by ascending x, then y, `outside` for one beyond the grid. Raises
524        `IndexError` for one beyond the grid if `outside` is `None`, and `ValueError` if it holds none, naming `area`,
525        whose tiles they are."""
526        grid_slices, mask_slices = self._slices_for_tile_mask(tiles)
527        under_mask = self._data[grid_slices]
528        if under_mask.shape != tiles.mask.shape:
529            under_mask = self._padded_with_outside(under_mask, tiles.mask, mask_slices, area)
530        values = under_mask[tiles.mask]
531        if not len(values):
532            raise ValueError(f"{area!r} is empty, so it has no smallest or largest value")
533        return values
534
535    def _padded_with_outside(
536        self, on_grid: ndarray, mask: ndarray, mask_slices: tuple[slice, slice], area: Area
537    ) -> ndarray:
538        """`on_grid`, the values under the part of `mask` on the grid, laid out over the whole of `mask`, `outside`
539        beyond the grid. Raises `IndexError` where `mask` holds a tile beyond the grid and `outside` is `None`."""
540        if self._outside is None:
541            if numpy.count_nonzero(mask[mask_slices]) < numpy.count_nonzero(mask):
542                raise IndexError(f"{area!r} reaches past {self.bounds!r}")
543            # Beyond the grid, the mask holds no tile, so these zeros are never read.
544            padded = numpy.zeros(mask.shape, dtype=self._data.dtype)
545        else:
546            padded = numpy.full(mask.shape, self._outside, dtype=self._data.dtype)
547        padded[mask_slices] = on_grid
548        return padded
549
550    def gradient_at(self, point: PointLike) -> tuple[float, float]:
551        """How fast the values rise at `point`, per map unit, along x and along y, together pointing the way they rise
552        fastest: along each axis, the difference between the neighbors on either side of the tile holding it, over the
553        two units between them. A
554        neighbor beyond the grid reads `outside`; where that is `None`, the difference is taken on the side the grid
555        holds, over one unit, and is 0 along an axis the grid is one tile across. Raises `IndexError` for a point
556        beyond the grid when `outside` is `None`, and `TypeError` for a grid of booleans."""
557        if self._data.dtype == bool:
558            raise TypeError(f"{self!r} holds booleans, which have no gradient")
559        value_here = self.value_at(point)
560        tile_x, tile_y = Tile._address_at(point)
561        slope_x = _finite_difference(
562            self._value_or_outside_at(tile_x - 1, tile_y), value_here, self._value_or_outside_at(tile_x + 1, tile_y)
563        )
564        slope_y = _finite_difference(
565            self._value_or_outside_at(tile_x, tile_y - 1), value_here, self._value_or_outside_at(tile_x, tile_y + 1)
566        )
567        return slope_x, slope_y
568
569    def _value_or_outside_at(self, tile_x: int, tile_y: int) -> T | None:
570        """The value of the tile at `tile_x` and `tile_y`, or `outside` beyond the grid, which may be `None`."""
571        x = tile_x - self._origin.x
572        y = tile_y - self._origin.y
573        if 0 <= x < self._data.shape[0] and 0 <= y < self._data.shape[1]:
574            return self._data.item(x, y)
575        return self._outside
576
577    @overload
578    def sum(self: Grid[bool]) -> int: ...
579    @overload
580    def sum(self) -> T: ...
581
582    def sum(self) -> T | int:
583        """The total over every tile; for a boolean grid, the number of true ones."""
584        return self._data.sum().item()
585
586    def _tile_at(self, flat_index: int) -> Tile:
587        """The tile addressed by a flat index into the grid."""
588        x, y = numpy.unravel_index(flat_index, self._data.shape)
589        return self.tile_at((int(x), int(y)))
590
591    # --- Operators
592
593    def _combine(self, other: object, op: Callable[..., ndarray], *, flip: bool = False) -> Grid:
594        """`op` applied against a scalar, or tilewise against a grid covering the same tiles."""
595        if isinstance(other, Grid):
596            values = self._aligned(other)
597        elif isinstance(other, SCALAR_TYPES):
598            values = other
599        else:
600            return NotImplemented
601        left, right = (values, self._data) if flip else (self._data, values)
602        return Grid(op(left, right), origin=self._origin, outside=self._combine_outside(other, op, flip=flip))
603
604    def _combine_outside(self, other: object, op: Callable[..., ndarray], *, flip: bool) -> T | None:
605        """`op` applied to both operands' off-grid values, or `None` if either has none."""
606        if self._outside is None:
607            return None
608        if isinstance(other, Grid):
609            if other._outside is None:
610                return None
611            value = other._outside
612        else:
613            value = other
614        left, right = (value, self._outside) if flip else (self._outside, value)
615        return op(left, right).item()
616
617    def __add__(self, other: Grid[T] | T) -> Grid[T]:
618        return self._combine(other, numpy.add)
619
620    def __radd__(self, other: T) -> Grid[T]:
621        return self._combine(other, numpy.add, flip=True)
622
623    def __sub__(self, other: Grid[T] | T) -> Grid[T]:
624        return self._combine(other, numpy.subtract)
625
626    def __rsub__(self, other: T) -> Grid[T]:
627        return self._combine(other, numpy.subtract, flip=True)
628
629    def __mul__(self, other: Grid[T] | T) -> Grid[T]:
630        return self._combine(other, numpy.multiply)
631
632    def __rmul__(self, other: T) -> Grid[T]:
633        return self._combine(other, numpy.multiply, flip=True)
634
635    def __truediv__(self, other: Grid[T] | T) -> Grid[float]:
636        return self._combine(other, numpy.divide)
637
638    def __neg__(self) -> Grid[T]:
639        # Negating a `T` bound to float widens to float; at runtime the type is unchanged.
640        outside = None if self._outside is None else cast("T", -self._outside)
641        return Grid(-self._data, origin=self._origin, outside=outside)
642
643    def __abs__(self) -> Grid[T]:
644        outside = None if self._outside is None else cast("T", abs(self._outside))
645        return Grid(abs(self._data), origin=self._origin, outside=outside)
646
647    def __invert__(self: Grid[bool]) -> Grid[bool]:
648        return Grid(
649            numpy.logical_not(self._data),
650            origin=self._origin,
651            outside=None if self._outside is None else not self._outside,
652        )
653
654    def __and__(self: Grid[bool], other: Grid[bool] | bool) -> Grid[bool]:
655        return self._combine(other, numpy.logical_and)
656
657    def __rand__(self: Grid[bool], other: bool) -> Grid[bool]:
658        return self._combine(other, numpy.logical_and, flip=True)
659
660    def __or__(self: Grid[bool], other: Grid[bool] | bool) -> Grid[bool]:
661        return self._combine(other, numpy.logical_or)
662
663    def __ror__(self: Grid[bool], other: bool) -> Grid[bool]:
664        return self._combine(other, numpy.logical_or, flip=True)
665
666    # --- Comparisons
667
668    def equals(self, other: object) -> bool:
669        """Whether `other` is a grid covering the same tiles and holding the same values."""
670        return (
671            isinstance(other, Grid)
672            and self._origin == other._origin
673            and self._data.shape == other._data.shape
674            and numpy.array_equal(self._data, other._data)
675        )
676
677    def __eq__(self, other: Grid[T] | T) -> Grid[bool]:  # pyright: ignore[reportIncompatibleMethodOverride]
678        """Whether each tile equals `other`; `equals` compares grids as wholes."""
679        return self._combine(other, numpy.equal)
680
681    def __ne__(self, other: Grid[T] | T) -> Grid[bool]:  # pyright: ignore[reportIncompatibleMethodOverride]
682        return self._combine(other, numpy.not_equal)
683
684    def __lt__(self, other: Grid[T] | T) -> Grid[bool]:
685        return self._combine(other, numpy.less)
686
687    def __le__(self, other: Grid[T] | T) -> Grid[bool]:
688        return self._combine(other, numpy.less_equal)
689
690    def __gt__(self, other: Grid[T] | T) -> Grid[bool]:
691        return self._combine(other, numpy.greater)
692
693    def __ge__(self, other: Grid[T] | T) -> Grid[bool]:
694        return self._combine(other, numpy.greater_equal)
695
696    def __bool__(self) -> bool:
697        """Raises `TypeError`: a grid has no truth value. `any` and `all` say whether any tile is true, or every one."""
698        raise TypeError("a grid has no truth value; use .any() or .all()")
699
700    def any(self) -> bool:
701        """Whether any tile is true."""
702        return bool(self._data.any())
703
704    def all(self) -> bool:
705        """Whether every tile is true."""
706        return bool(self._data.all())
707
708    def __repr__(self) -> str:
709        return f"Grid({self.width}x{self.height} of {self._data.dtype} at {self._origin!r})"

A grid of per-tile values, addressed by map position rather than by array index.

origin is the tile at the grid's lower left corner, so a grid can cover the playable area alone. An area reaching past the edge is clipped to the tiles the grid holds; a point outside it raises IndexError.

A grid the library shares, such as the map's, and the grids of CheapestPaths are readonly and refuse every write. copy() gives a writable one, as does every other grid derived from one.

Grid( data: numpy.ndarray, *, origin: Tile = Tile(0, 0), outside: 'T | None' = None, readonly: bool = False)
59    def __init__(
60        self, data: ndarray, *, origin: Tile = _ORIGIN, outside: T | None = None, readonly: bool = False
61    ) -> None:
62        """A grid holding `data`, whose `[0, 0]` entry is the tile at `origin`.
63
64        `outside` is what a read beyond the grid returns; without it such a read raises. A write beyond the grid
65        always raises, and a `readonly` grid refuses every write.
66        """
67        if data.ndim != 2:
68            raise ValueError(f"a grid is two-dimensional, got {data.ndim} dimensions")
69        self._data = data
70        self._origin = origin
71        self._outside = outside
72        self._readonly = readonly

A grid holding data, whose [0, 0] entry is the tile at origin.

outside is what a read beyond the grid returns; without it such a read raises. A write beyond the grid always raises, and a readonly grid refuses every write.

@classmethod
def zeros( cls, width: int, height: int, *, origin: Tile = Tile(0, 0), dtype: 'type[T]' = <class 'float'>, outside: 'T | None' = None) -> 'Grid[T]':
74    @classmethod
75    def zeros(
76        cls, width: int, height: int, *, origin: Tile = _ORIGIN, dtype: type[T] = float, outside: T | None = None
77    ) -> Grid[T]:
78        """A grid of `width` by `height` tiles, filled with zeros."""
79        return Grid(numpy.zeros((width, height), dtype=dtype), origin=origin, outside=outside)

A grid of width by height tiles, filled with zeros.

@classmethod
def like( cls, other: 'Grid[U]', *, dtype: 'type[T]' = <class 'float'>, outside: 'T | None' = None) -> 'Grid[T]':
81    @classmethod
82    def like[U: float](cls, other: Grid[U], *, dtype: type[T] = float, outside: T | None = None) -> Grid[T]:
83        """A grid of zeros covering the same tiles as `other`."""
84        return Grid(numpy.zeros(other._data.shape, dtype=dtype), origin=other._origin, outside=outside)

A grid of zeros covering the same tiles as other.

origin: Tile
88    @property
89    def origin(self) -> Tile:
90        """The tile at the grid's lower left corner."""
91        return self._origin

The tile at the grid's lower left corner.

width: int
93    @property
94    def width(self) -> int:
95        """The number of tiles across."""
96        return self._data.shape[0]

The number of tiles across.

height: int
 98    @property
 99    def height(self) -> int:
100        """The number of tiles up."""
101        return self._data.shape[1]

The number of tiles up.

bounds: Rectangle
103    @property
104    def bounds(self) -> Rectangle:
105        """The ground the grid covers."""
106        return Rectangle(self._origin.x, self._origin.y, self.width, self.height)

The ground the grid covers.

values: numpy.ndarray
108    @property
109    def values(self) -> ndarray:
110        """A read-only view of the grid, indexed `[x, y]` from `origin`."""
111        view = self._data.view()
112        view.flags.writeable = False
113        return view

A read-only view of the grid, indexed [x, y] from origin.

def index_of(self, point: 'PointLike | Tile') -> tuple[int, int]:
115    def index_of(self, point: PointLike | Tile) -> tuple[int, int]:
116        """The index into `values` of the tile holding `point`, a tile reading as itself.
117
118        Raises `IndexError` for a point the grid does not cover, whatever `outside` is.
119        """
120        if (index := self._index_if_covered(point)) is None:
121            raise IndexError(f"{Tile.at(point)!r} lies outside {self.bounds!r}")
122        return index

The index into values of the tile holding point, a tile reading as itself.

Raises IndexError for a point the grid does not cover, whatever outside is.

def tile_at(self, index: tuple[int, int]) -> Tile:
133    def tile_at(self, index: tuple[int, int]) -> Tile:
134        """The tile an index into `values` addresses. The inverse of `index_of`."""
135        x, y = index
136        if not (0 <= x < self._data.shape[0] and 0 <= y < self._data.shape[1]):
137            raise IndexError(f"{index} lies outside a {self.width} by {self.height} grid")
138        return self._origin.shifted(x, y)

The tile an index into values addresses. The inverse of index_of.

outside: 'T | None'
140    @property
141    def outside(self) -> T | None:
142        """What a read beyond the grid returns, or `None` if one raises."""
143        return self._outside

What a read beyond the grid returns, or None if one raises.

readonly: bool
145    @property
146    def readonly(self) -> bool:
147        """Whether the grid refuses writes."""
148        return self._readonly

Whether the grid refuses writes.

def with_outside(self, value: 'T | None') -> 'Grid[T]':
150    def with_outside(self, value: T | None) -> Grid[T]:
151        """The same grid, reading `value` beyond its edge.
152
153        It shares the data rather than copying it, and stays read-only if this grid is.
154        """
155        return Grid(self._data, origin=self._origin, outside=value, readonly=self._readonly)

The same grid, reading value beyond its edge.

It shares the data rather than copying it, and stays read-only if this grid is.

def value_at(self, point: 'PointLike | Tile') -> 'T':
157    def value_at(self, point: PointLike | Tile) -> T:
158        """The value at `point`, a tile reading as itself, or `outside` beyond the grid, which raises `IndexError` if
159        that is `None`."""
160        if (index := self._index_if_covered(point)) is not None:
161            return self._data.item(index)
162        if self._outside is None:
163            raise IndexError(f"{Tile.at(point)!r} lies outside {self.bounds!r}")
164        return self._outside

The value at point, a tile reading as itself, or outside beyond the grid, which raises IndexError if that is None.

def values_at(self, points: 'Sequence[PointLike] | ndarray') -> numpy.ndarray:
166    def values_at(self, points: Sequence[PointLike] | ndarray) -> ndarray:
167        """The value at each of `points`, a sequence of points or an array of them, a point a row, as `value_at` reads
168        it, in one numpy pass: an array of the grid's values, a value a point, in order, `outside` beyond the grid.
169        Raises `IndexError` for a point beyond the grid where it reads no `outside`. A sequence of points first becomes
170        an array, which takes most of the time: the pass pays off most on points already in an array."""
171        xs, ys = coordinate_arrays_of(points)
172        columns = numpy.floor(xs).astype(numpy.intp) - self._origin.x
173        rows = numpy.floor(ys).astype(numpy.intp) - self._origin.y
174        width, height = self._data.shape
175        covered = (columns >= 0) & (columns < width) & (rows >= 0) & (rows < height)
176        if covered.all():
177            return self._data[columns, rows]
178        if self._outside is None:
179            first_beyond = int(numpy.argmin(covered))
180            point = (xs[first_beyond].item(), ys[first_beyond].item())
181            raise IndexError(f"{Tile.at(point)!r} lies outside {self.bounds!r}")
182        values = numpy.full(len(xs), self._outside, dtype=numpy.result_type(self._data.dtype, self._outside))
183        values[covered] = self._data[columns[covered], rows[covered]]
184        return values

The value at each of points, a sequence of points or an array of them, a point a row, as value_at reads it, in one numpy pass: an array of the grid's values, a value a point, in order, outside beyond the grid. Raises IndexError for a point beyond the grid where it reads no outside. A sequence of points first becomes an array, which takes most of the time: the pass pays off most on points already in an array.

def fill(self, value: 'T') -> None:
240    def fill(self, value: T) -> None:
241        """Sets every tile to `value`."""
242        self._refuse_readonly()
243        self._data[:] = value

Sets every tile to value.

def fill_footprint( self, footprint: Footprint, *, at: 'PointLike', value: 'T', margin: Margin = 0) -> None:
245    def fill_footprint(self, footprint: Footprint, *, at: PointLike, value: T, margin: Margin = 0) -> None:
246        """Sets every tile `footprint` covers, centered at `at`, to `value`, and with `margin`, every tile within it of
247        one the footprint covers, as `fits_footprint` takes it, skipping those beyond the grid. Raises `ValueError` for
248        a negative margin."""
249        self._refuse_readonly()
250        footprint, at = footprint._grown_by(margin, at=at)
251        grid_slices, mask_slices = self._slices_for_footprint(footprint, at)
252        self._data[grid_slices][footprint.mask[mask_slices]] = value

Sets every tile footprint covers, centered at at, to value, and with margin, every tile within it of one the footprint covers, as fits_footprint takes it, skipping those beyond the grid. Raises ValueError for a negative margin.

def fits_footprint( self: Grid[bool], footprint: Footprint, *, at: 'PointLike', margin: Margin = 0) -> bool:
254    def fits_footprint(self: Grid[bool], footprint: Footprint, *, at: PointLike, margin: Margin = 0) -> bool:
255        """Whether every tile `footprint` covers, centered at `at`, is true, and with `margin`, every tile within it of
256        one the footprint covers: as many on every side, or so many on its left, right, bottom and top. A tile beyond
257        the grid reads `outside`, and raises `IndexError` if that is `None`. Raises `ValueError` for a negative
258        margin."""
259        footprint, at = footprint._grown_by(margin, at=at)
260        grid_slices, mask_slices = self._slices_for_footprint(footprint, at)
261        covered_on_grid = footprint.mask[mask_slices]
262        if numpy.count_nonzero(covered_on_grid) < numpy.count_nonzero(footprint.mask):
263            if self._outside is None:
264                raise IndexError(f"{footprint!r} centered at {at} reaches past {self.bounds!r}")
265            if not self._outside:
266                return False
267        return bool((self._data[grid_slices].astype(bool, copy=False) | ~covered_on_grid).all())

Whether every tile footprint covers, centered at at, is true, and with margin, every tile within it of one the footprint covers: as many on every side, or so many on its left, right, bottom and top. A tile beyond the grid reads outside, and raises IndexError if that is None. Raises ValueError for a negative margin.

def copy(self) -> 'Grid[T]':
326    def copy(self) -> Grid[T]:
327        """An independent grid holding the same values."""
328        return Grid(self._data.copy(), origin=self._origin, outside=self._outside)

An independent grid holding the same values.

def as_readonly(self) -> 'Grid[T]':
330    def as_readonly(self) -> Grid[T]:
331        """The same grid, refusing writes. It shares the values, so a write to this grid shows in it."""
332        return Grid(self.values, origin=self._origin, outside=self._outside, readonly=True)

The same grid, refusing writes. It shares the values, so a write to this grid shows in it.

def where_footprint_fits( self: Grid[bool], footprint: Footprint, *, margin: Margin = 0) -> Grid[bool]:
334    def where_footprint_fits(self: Grid[bool], footprint: Footprint, *, margin: Margin = 0) -> Grid[bool]:
335        """Where `footprint` fits, with `margin` as `fits_footprint` takes it, by the tile holding its center: true
336        where every tile it covers, centered as `footprint.center_in_tile` says, is true, which is this grid eroded by
337        the footprint. A tile beyond the grid reads `outside`, or false if that is `None`. The result covers the same
338        tiles as this grid and reads false beyond them. Raises `ValueError` for a negative margin."""
339        values = self._data.astype(bool, copy=False)
340        if any(sides := _margin_sides(margin)):
341            return Grid(self._where_grown_fits(values, footprint, sides), origin=self._origin, outside=False)
342        if not footprint.mask.any():
343            return Grid(numpy.ones_like(values), origin=self._origin, outside=False)
344        # The structure's own center, index `side // 2` along each axis, is where `center_in_tile` centers a footprint.
345        fitting = scipy.ndimage.binary_erosion(values, structure=footprint.mask, border_value=int(bool(self._outside)))
346        return Grid(fitting, origin=self._origin, outside=False)

Where footprint fits, with margin as fits_footprint takes it, by the tile holding its center: true where every tile it covers, centered as footprint.center_in_tile says, is true, which is this grid eroded by the footprint. A tile beyond the grid reads outside, or false if that is None. The result covers the same tiles as this grid and reads false beyond them. Raises ValueError for a negative margin.

def where( self, condition: Grid[bool], other: 'T | Grid[T]') -> 'Grid[T]':
365    def where(self, condition: Grid[bool], other: T | Grid[T]) -> Grid[T]:
366        """This grid where `condition` holds, and `other` everywhere else."""
367        values = self._aligned(other) if isinstance(other, Grid) else other
368        # `_aligned` runs before `_where_outside`: it rejects a condition that is not a grid, and `_where_outside`
369        # reads `condition._outside`, which needs that check to have passed.
370        chosen = numpy.where(self._aligned(condition), self._data, values)
371        return Grid(chosen, origin=self._origin, outside=self._where_outside(condition, other))

This grid where condition holds, and other everywhere else.

def minimum(self, other: 'Grid[T]') -> 'Grid[T]':
381    def minimum(self, other: Grid[T]) -> Grid[T]:
382        """The smaller of the two values on each tile."""
383        return self._combine(other, numpy.minimum)

The smaller of the two values on each tile.

def maximum(self, other: 'Grid[T]') -> 'Grid[T]':
385    def maximum(self, other: Grid[T]) -> Grid[T]:
386        """The larger of the two values on each tile."""
387        return self._combine(other, numpy.maximum)

The larger of the two values on each tile.

def cropped(self, rectangle: Rectangle) -> 'Grid[T]':
389    def cropped(self, rectangle: Rectangle) -> Grid[T]:
390        """An independent grid over the tiles `rectangle` covers, clipped to the ones this grid holds."""
391        x, y = self._slices(rectangle)
392        origin = self._origin.shifted(x.start, y.start)
393        return Grid(self._data[x, y].copy(), origin=origin, outside=self._outside)

An independent grid over the tiles rectangle covers, clipped to the ones this grid holds.

def distance_from( self, point: 'PointLike', *, outside: float | None = None) -> Grid[float]:
395    def distance_from(self, point: PointLike, *, outside: float | None = None) -> Grid[float]:
396        """The distance from each tile's center to `point`."""
397        xs = numpy.arange(self.width) + self._origin.x + 0.5 - point[0]
398        ys = numpy.arange(self.height) + self._origin.y + 0.5 - point[1]
399        return Grid(numpy.hypot(xs[:, None], ys[None, :]), origin=self._origin, outside=outside)

The distance from each tile's center to point.

def distance_transform( self: Grid[bool], *, outside: float | None = None) -> Grid[float]:
401    def distance_transform(self: Grid[bool], *, outside: float | None = None) -> Grid[float]:
402        """For each true tile, the distance from its center to the nearest false tile's; zero on a false tile. Where
403        this grid reads false beyond its edge, the tiles beyond it count as false; where no false tile is found, every
404        distance is `inf`."""
405        if self._outside is not None and not self._outside:
406            padded = numpy.pad(self._data, 1, constant_values=False)
407            distances = numpy.asarray(scipy.ndimage.distance_transform_edt(padded, return_indices=False))[1:-1, 1:-1]
408        elif self._data.all():
409            distances = numpy.full(self._data.shape, math.inf)
410        else:
411            distances = numpy.asarray(scipy.ndimage.distance_transform_edt(self._data, return_indices=False))
412        return Grid(distances, origin=self._origin, outside=outside)

For each true tile, the distance from its center to the nearest false tile's; zero on a false tile. Where this grid reads false beyond its edge, the tiles beyond it count as false; where no false tile is found, every distance is inf.

def cheapest_path( self, start: 'PointLike | Tile', end: 'PointLike | Tile') -> TilePath | None:
414    def cheapest_path(self, start: PointLike | Tile, end: PointLike | Tile) -> TilePath | None:
415        """The cheapest path from the tile holding `start` to the tile holding `end`, or `None` if there is none. Of
416        several equally cheap paths it is one, but which is not part of the contract.
417
418        Each tile's value is the cost of moving one unit of distance across it, and 0 and `inf` block it, so on a grid
419        of bools, where true costs 1 and false blocks, the cheapest path is a shortest one. A negative or NaN value
420        raises `ValueError`. A step goes to a tile sharing a side or a corner, 1 or sqrt(2) long, and costs its length
421        times the mean of the two tiles' values; a diagonal step needs both tiles sharing a side with the two passable,
422        so no path cuts a corner. The start is a path to itself even on a blocked tile, but no path leaves one. Raises
423        `IndexError` for a point the grid does not cover.
424        """
425        start_index = self.index_of(start)
426        end_index = self.index_of(end)
427        with self._bad_cost_named_by_its_tile():
428            found = semita.cheapest_path(self._data, start_index, end_index)
429        return None if found is None else _semita_path_to_tile_path(found, self._origin)

The cheapest path from the tile holding start to the tile holding end, or None if there is none. Of several equally cheap paths it is one, but which is not part of the contract.

Each tile's value is the cost of moving one unit of distance across it, and 0 and inf block it, so on a grid of bools, where true costs 1 and false blocks, the cheapest path is a shortest one. A negative or NaN value raises ValueError. A step goes to a tile sharing a side or a corner, 1 or sqrt(2) long, and costs its length times the mean of the two tiles' values; a diagonal step needs both tiles sharing a side with the two passable, so no path cuts a corner. The start is a path to itself even on a blocked tile, but no path leaves one. Raises IndexError for a point the grid does not cover.

def cheapest_paths_from( self, start: 'PointLike | Tile', *, outside: float | None = None) -> CheapestPaths:
431    def cheapest_paths_from(self, start: PointLike | Tile, *, outside: float | None = None) -> CheapestPaths:
432        """The cheapest path from the tile holding `start` to every tile, over the steps `cheapest_path` takes, found in
433        one search: their costs, their lengths and each one's tiles. `outside` is what the costs and the lengths read
434        beyond the grid. Raises as `cheapest_path` does.
435        """
436        start_index = self.index_of(start)
437        with self._bad_cost_named_by_its_tile():
438            found = semita.cheapest_paths_from(self._data, start_index)
439        costs = Grid(found.costs, origin=self._origin, outside=outside, readonly=True)
440        distances = Grid(found.distances, origin=self._origin, outside=outside, readonly=True)
441        return CheapestPaths(costs, distances, found)

The cheapest path from the tile holding start to every tile, over the steps cheapest_path takes, found in one search: their costs, their lengths and each one's tiles. outside is what the costs and the lengths read beyond the grid. Raises as cheapest_path does.

def smoothed( self, sigma: float, *, within: Optional[Grid[bool]] = None, outside: float | None = None) -> Grid[float]:
459    def smoothed(self, sigma: float, *, within: Grid[bool] | None = None, outside: float | None = None) -> Grid[float]:
460        """A Gaussian blur of the values, `sigma` measured in tiles.
461
462        Given `within`, only those tiles contribute and the result is renormalized, so values near the edge
463        of the region are not dragged down by the tiles outside it. A tile no contributor reaches keeps its
464        own value.
465        """
466        values = self._data.astype(float)
467        if within is None:
468            return Grid(scipy.ndimage.gaussian_filter(values, sigma=sigma), origin=self._origin, outside=outside)
469        weights = self._mask(within).astype(float)
470        numerator = scipy.ndimage.gaussian_filter(values * weights, sigma=sigma)
471        denominator = scipy.ndimage.gaussian_filter(weights, sigma=sigma)
472        blurred = values.copy()
473        numpy.divide(numerator, denominator, out=blurred, where=denominator > 0)
474        return Grid(blurred, origin=self._origin, outside=outside)

A Gaussian blur of the values, sigma measured in tiles.

Given within, only those tiles contribute and the result is renormalized, so values near the edge of the region are not dragged down by the tiles outside it. A tile no contributor reaches keeps its own value.

def min(self, *, within: Area | None = None) -> 'T':
478    def min(self, *, within: Area | None = None) -> T:
479        """The smallest value, or with `within`, the smallest of every tile the area overlaps, a tile it only touches at
480        an edge or a corner left out. A tile beyond the grid reads `outside`, and raises `IndexError` if that is
481        `None`. Raises `ValueError` for an empty area."""
482        if within is None:
483            return self._data.min().item()
484        return self._values_of_tiles_held(within._overlapped_tile_mask(), within).min().item()

The smallest value, or with within, the smallest of every tile the area overlaps, a tile it only touches at an edge or a corner left out. A tile beyond the grid reads outside, and raises IndexError if that is None. Raises ValueError for an empty area.

def max(self, *, within: Area | None = None) -> 'T':
486    def max(self, *, within: Area | None = None) -> T:
487        """The largest value, or with `within`, the largest of every tile the area overlaps, as `min` takes them."""
488        if within is None:
489            return self._data.max().item()
490        return self._values_of_tiles_held(within._overlapped_tile_mask(), within).max().item()

The largest value, or with within, the largest of every tile the area overlaps, as min takes them.

def argmin( self, *, within: Area | None = None) -> Point:
492    def argmin(self, *, within: Area | None = None) -> Point:
493        """The center of the tile `argmin_tile` gives, which `within` may not hold."""
494        return self.argmin_tile(within=within).center

The center of the tile argmin_tile gives, which within may not hold.

def argmax( self, *, within: Area | None = None) -> Point:
496    def argmax(self, *, within: Area | None = None) -> Point:
497        """The center of the tile `argmax_tile` gives, which `within` may not hold."""
498        return self.argmax_tile(within=within).center

The center of the tile argmax_tile gives, which within may not hold.

def argmin_tile( self, *, within: Area | None = None) -> Tile:
500    def argmin_tile(self, *, within: Area | None = None) -> Tile:
501        """The tile with the smallest value, or with `within`, the one with the smallest of those the area overlaps,
502        as `min` takes them; the lowest address if several tie."""
503        if within is None:
504            return self._tile_at(int(numpy.argmin(self._data)))
505        return self._extreme_tile(within, largest=False)

The tile with the smallest value, or with within, the one with the smallest of those the area overlaps, as min takes them; the lowest address if several tie.

def argmax_tile( self, *, within: Area | None = None) -> Tile:
507    def argmax_tile(self, *, within: Area | None = None) -> Tile:
508        """The tile with the largest value, or with `within`, the one with the largest of those the area overlaps, as
509        `argmin_tile` picks one."""
510        if within is None:
511            return self._tile_at(int(numpy.argmax(self._data)))
512        return self._extreme_tile(within, largest=True)

The tile with the largest value, or with within, the one with the largest of those the area overlaps, as argmin_tile picks one.

def gradient_at(self, point: 'PointLike') -> tuple[float, float]:
550    def gradient_at(self, point: PointLike) -> tuple[float, float]:
551        """How fast the values rise at `point`, per map unit, along x and along y, together pointing the way they rise
552        fastest: along each axis, the difference between the neighbors on either side of the tile holding it, over the
553        two units between them. A
554        neighbor beyond the grid reads `outside`; where that is `None`, the difference is taken on the side the grid
555        holds, over one unit, and is 0 along an axis the grid is one tile across. Raises `IndexError` for a point
556        beyond the grid when `outside` is `None`, and `TypeError` for a grid of booleans."""
557        if self._data.dtype == bool:
558            raise TypeError(f"{self!r} holds booleans, which have no gradient")
559        value_here = self.value_at(point)
560        tile_x, tile_y = Tile._address_at(point)
561        slope_x = _finite_difference(
562            self._value_or_outside_at(tile_x - 1, tile_y), value_here, self._value_or_outside_at(tile_x + 1, tile_y)
563        )
564        slope_y = _finite_difference(
565            self._value_or_outside_at(tile_x, tile_y - 1), value_here, self._value_or_outside_at(tile_x, tile_y + 1)
566        )
567        return slope_x, slope_y

How fast the values rise at point, per map unit, along x and along y, together pointing the way they rise fastest: along each axis, the difference between the neighbors on either side of the tile holding it, over the two units between them. A neighbor beyond the grid reads outside; where that is None, the difference is taken on the side the grid holds, over one unit, and is 0 along an axis the grid is one tile across. Raises IndexError for a point beyond the grid when outside is None, and TypeError for a grid of booleans.

def sum(self) -> 'T | int':
582    def sum(self) -> T | int:
583        """The total over every tile; for a boolean grid, the number of true ones."""
584        return self._data.sum().item()

The total over every tile; for a boolean grid, the number of true ones.

def equals(self, other: object) -> bool:
668    def equals(self, other: object) -> bool:
669        """Whether `other` is a grid covering the same tiles and holding the same values."""
670        return (
671            isinstance(other, Grid)
672            and self._origin == other._origin
673            and self._data.shape == other._data.shape
674            and numpy.array_equal(self._data, other._data)
675        )

Whether other is a grid covering the same tiles and holding the same values.

def any(self) -> bool:
700    def any(self) -> bool:
701        """Whether any tile is true."""
702        return bool(self._data.any())

Whether any tile is true.

def all(self) -> bool:
704    def all(self) -> bool:
705        """Whether every tile is true."""
706        return bool(self._data.all())

Whether every tile is true.

type Margin = int | tuple[int, int, int, int]

Tiles kept free beside a footprint: as many on every side, or so many on its left, right, bottom and top.

@final
class Point(sc2nachos.geometry._point._PointND, tuple[float, float]):
274@final
275class Point(_PointND, tuple[float, float]):
276    """An immutable 2D point, constructed from an iterable of exactly two coordinates: `Point((3, 4))`. The count is
277    not checked, so a `Point3D` becomes a `Point` through its `ground`, never through `Point(point3d)`.
278
279    A tuple subclass, so it unpacks, hashes and compares like `(x, y)` and works as a dict key. A numpy array combines
280    with a point only through `numpy.asarray(point)`: `positions - point` raises `TypeError`.
281    """
282
283    __slots__ = ()
284
285    @classmethod
286    def _from_proto(cls, data: common_pb2.Point2D | common_pb2.PointI) -> Self:
287        """Read a point from the game's 2D point message."""
288        return cls((data.x, data.y))
289
290    @classmethod
291    def _rounded_to_float32(cls, point: PointLike) -> Self:
292        """`point` on the ground as the protocol carries it: its height dropped, and each coordinate cut to a 32-bit
293        float."""
294        return cls((float(numpy.float32(point[0])), float(numpy.float32(point[1]))))
295
296    def with_height(self, z: float = 0.0) -> Point3D:
297        """The point lifted to height `z`."""
298        return Point3D((self[0], self[1], z))
299
300    # Two-coordinate fast paths, quicker than the general implementation and used in per-unit loops.
301
302    def __add__(self, other: PointLike | float) -> Point:  # pyright: ignore[reportIncompatibleMethodOverride]
303        if isinstance(other, tuple) and len(other) == 2:
304            return Point((self[0] + other[0], self[1] + other[1]))
305        return super().__add__(other)
306
307    def __sub__(self, other: PointLike | float) -> Point:
308        if isinstance(other, tuple) and len(other) == 2:
309            return Point((self[0] - other[0], self[1] - other[1]))
310        return super().__sub__(other)

An immutable 2D point, constructed from an iterable of exactly two coordinates: Point((3, 4)). The count is not checked, so a Point3D becomes a Point through its ground, never through Point(point3d).

A tuple subclass, so it unpacks, hashes and compares like (x, y) and works as a dict key. A numpy array combines with a point only through numpy.asarray(point): positions - point raises TypeError.

def with_height(self, z: float = 0.0) -> Point3D:
296    def with_height(self, z: float = 0.0) -> Point3D:
297        """The point lifted to height `z`."""
298        return Point3D((self[0], self[1], z))

The point lifted to height z.

@final
class Point3D(sc2nachos.geometry._point._PointND, tuple[float, float, float]):
313@final
314class Point3D(_PointND, tuple[float, float, float]):
315    """An immutable 3D point, used for terrain height and debug drawing."""
316
317    __slots__ = ()
318
319    @property
320    def z(self) -> float:
321        """The height coordinate."""
322        return self[2]
323
324    @property
325    def ground(self) -> Point:
326        """The point projected onto the ground plane, dropping its height."""
327        return Point((self[0], self[1]))

An immutable 3D point, used for terrain height and debug drawing.

z: float
319    @property
320    def z(self) -> float:
321        """The height coordinate."""
322        return self[2]

The height coordinate.

ground: Point
324    @property
325    def ground(self) -> Point:
326        """The point projected onto the ground plane, dropping its height."""
327        return Point((self[0], self[1]))

The point projected onto the ground plane, dropping its height.

PointLike = typing.Union[ForwardRef('Point'), ForwardRef('Point3D'), tuple[float, float], tuple[float, float, float]]
@final
@dataclass(frozen=True, slots=True)
class Rectangle(sc2nachos.geometry.Area):
163@final
164@dataclass(frozen=True, slots=True)
165class Rectangle(Area):
166    """An axis-aligned rectangle, anchored at its lower left corner.
167
168    `y` grows upward, as in the game, so `top` is the higher edge. A rectangle with no width or no height covers
169    nothing: it is empty, as `Area` has it.
170    """
171
172    x: float
173    y: float
174    width: float
175    height: float
176
177    def __post_init__(self) -> None:
178        """Rejects a negative extent."""
179        # Two negatives cancel in `area`, so such a rectangle would report a plausible size while covering nothing.
180        if self.width < 0 or self.height < 0:
181            raise ValueError(f"a rectangle cannot have a negative extent, got {self.width} x {self.height}")
182
183    @classmethod
184    def from_center(cls, center: PointLike, width: float, height: float) -> Rectangle:
185        """The rectangle of the given size centered on a point."""
186        return cls(center[0] - width / 2, center[1] - height / 2, width, height)
187
188    @classmethod
189    def _from_proto(cls, data: common_pb2.RectangleI) -> Rectangle:
190        """Read a rectangle from the game's `RectangleI`, which holds opposite corners rather than a size."""
191        return cls(data.p0.x, data.p0.y, data.p1.x - data.p0.x, data.p1.y - data.p0.y)
192
193    @property
194    def left(self) -> float:
195        """The lower x edge."""
196        return self.x
197
198    @property
199    def bottom(self) -> float:
200        """The lower y edge."""
201        return self.y
202
203    @property
204    def right(self) -> float:
205        """The upper x edge."""
206        return self.x + self.width
207
208    @property
209    def top(self) -> float:
210        """The upper y edge."""
211        return self.y + self.height
212
213    @property
214    def center(self) -> Point:
215        """The midpoint."""
216        self._raise_if_empty("center")
217        return Point((self.x + self.width / 2, self.y + self.height / 2))
218
219    @property
220    def _is_empty(self) -> bool:
221        """Whether the rectangle has no width or no height, and so covers nothing."""
222        return not self.width or not self.height
223
224    def _raise_if_empty(self, what: str) -> None:
225        """Raises `ValueError`, naming `what` it lacks, if the rectangle is empty."""
226        if self._is_empty:
227            raise ValueError(f"{self!r} covers no ground, so it has no {what}")
228
229    @property
230    def size(self) -> tuple[float, float]:
231        """The extent along each axis."""
232        return self.width, self.height
233
234    @property
235    def area(self) -> float:
236        """The ground covered, in square game units."""
237        return self.width * self.height
238
239    @property
240    def perimeter(self) -> float:
241        """The distance around the edge."""
242        return 2 * (self.width + self.height)
243
244    @property
245    def corners(self) -> tuple[Point, Point, Point, Point]:
246        """The four corners, counter-clockwise from the bottom left."""
247        return (
248            Point((self.left, self.bottom)),
249            Point((self.right, self.bottom)),
250            Point((self.right, self.top)),
251            Point((self.left, self.top)),
252        )
253
254    def __contains__(self, point: PointLike | Tile) -> bool:
255        """Whether a point lies inside, on the lower edges but not the upper ones."""
256        position = coordinates_or_tile_center(point)
257        # The fields rather than the edge properties, a call each; the arithmetic is the same as `right` and `top`.
258        x, y = self.x, self.y
259        return x <= position[0] < x + self.width and y <= position[1] < y + self.height
260
261    def _contains_each(self, xs: ndarray, ys: ndarray) -> ndarray:
262        """Whether each point lies inside, on the lower edges but not the upper ones."""
263        x, y = self.x, self.y
264        return (x <= xs) & (xs < x + self.width) & (y <= ys) & (ys < y + self.height)
265
266    def encloses(self, other: Rectangle) -> bool:
267        """Whether the whole of `other` lies inside."""
268        return (
269            self.left <= other.left
270            and self.bottom <= other.bottom
271            and self.right >= other.right
272            and self.top >= other.top
273        )
274
275    def translated(self, offset: PointLike) -> Rectangle:
276        """The rectangle shifted by `offset`, keeping its size. Raises `ValueError` for an offset with a height."""
277        ground_offset = checked_ground_offset(offset)
278        return Rectangle(self.x + ground_offset[0], self.y + ground_offset[1], self.width, self.height)
279
280    def intersects(self, other: Rectangle) -> bool:
281        """Whether the two rectangles share any ground: never when either is empty."""
282        if self._is_empty or other._is_empty:
283            return False
284        return not (
285            self.right <= other.left or self.left >= other.right or self.top <= other.bottom or self.bottom >= other.top
286        )
287
288    def intersection(self, other: Rectangle) -> Rectangle | None:
289        """The ground both rectangles cover; `None` if they do not overlap."""
290        left = max(self.left, other.left)
291        bottom = max(self.bottom, other.bottom)
292        right = min(self.right, other.right)
293        top = min(self.top, other.top)
294        if right <= left or top <= bottom:
295            return None
296        return Rectangle(left, bottom, right - left, top - bottom)
297
298    def rounded_out(self) -> Rectangle:
299        """The smallest rectangle on integer coordinates that contains this one."""
300        left = math.floor(self.left)
301        bottom = math.floor(self.bottom)
302        return Rectangle(left, bottom, math.ceil(self.right) - left, math.ceil(self.top) - bottom)
303
304    def rounded_in(self) -> Rectangle | None:
305        """The largest rectangle on integer coordinates that fits inside this one, `None` if none fits."""
306        left = math.ceil(self.left)
307        bottom = math.ceil(self.bottom)
308        right = math.floor(self.right)
309        top = math.floor(self.top)
310        if right <= left or top <= bottom:
311            return None
312        return Rectangle(left, bottom, right - left, top - bottom)
313
314    def random_point(self, *, rng: random.Random | None = None) -> Point:
315        """A point drawn uniformly from the rectangle, by `rng` or the `random` module's own generator."""
316        self._raise_if_empty("points to draw from")
317        uniform = random.uniform if rng is None else rng.uniform
318        x, y = self.x, self.y
319        drawn_x = x + uniform(0, self.width)
320        drawn_y = y + uniform(0, self.height)
321        return _nearest_point_held_within(drawn_x, drawn_y, x, y, x + self.width, y + self.height)
322
323    def closest_point_to(self, point: PointLike) -> tuple[Point, float]:
324        """The point of the rectangle nearest to `point`, and the distance to it, kept off the upper edges as `Area`
325        has it."""
326        self._raise_if_empty("closest point")
327        x, y = self.x, self.y
328        closest = _nearest_point_held_within(point[0], point[1], x, y, x + self.width, y + self.height)
329        return closest, closest.distance_to(point)
330
331    def bounding_rectangle(self) -> Rectangle:
332        """The rectangle itself."""
333        self._raise_if_empty("bounding rectangle")
334        return self
335
336    def tile_range(self) -> tuple[range, range]:
337        """The x and y addresses of the tiles the rectangle covers."""
338        return (
339            range(math.ceil(self.left - 0.5), math.ceil(self.right - 0.5)),
340            range(math.ceil(self.bottom - 0.5), math.ceil(self.top - 0.5)),
341        )
342
343    def tile_centers(self, *, offset: PointLike = (0.0, 0.0)) -> ndarray:
344        """The center of every tile the rectangle covers, as an array of shape `(x, y, 2)`.
345
346        Laid out like the tiles themselves, so a mask over the same region indexes it directly. `offset`
347        shifts every point without changing which tiles are covered.
348        """
349        x_range, y_range = self.tile_range()
350        xs = numpy.arange(x_range.start, x_range.stop) + 0.5 + offset[0]
351        ys = numpy.arange(y_range.start, y_range.stop) + 0.5 + offset[1]
352        return numpy.stack(numpy.meshgrid(xs, ys, indexing="ij"), axis=-1)
353
354    def tiles(self) -> TileSet:
355        """Every tile whose center the rectangle contains."""
356        x_range, y_range = self.tile_range()
357        return TileSet._from_addresses((x, y) for x in x_range for y in y_range)
358
359    def _overlapped_tile_mask(self) -> TileMask:
360        """Every tile whose inside the rectangle overlaps."""
361        first_x = math.floor(self.x)
362        first_y = math.floor(self.y)
363        if self._is_empty:
364            return TileMask(Tile(first_x, first_y), numpy.zeros((0, 0), dtype=bool))
365        columns = math.ceil(self.right) - first_x
366        rows = math.ceil(self.top) - first_y
367        return TileMask(Tile(first_x, first_y), numpy.ones((columns, rows), dtype=bool))

An axis-aligned rectangle, anchored at its lower left corner.

y grows upward, as in the game, so top is the higher edge. A rectangle with no width or no height covers nothing: it is empty, as Area has it.

Rectangle(x: float, y: float, width: float, height: float)
x: float
y: float
width: float
height: float
@classmethod
def from_center( cls, center: 'PointLike', width: float, height: float) -> Rectangle:
183    @classmethod
184    def from_center(cls, center: PointLike, width: float, height: float) -> Rectangle:
185        """The rectangle of the given size centered on a point."""
186        return cls(center[0] - width / 2, center[1] - height / 2, width, height)

The rectangle of the given size centered on a point.

left: float
193    @property
194    def left(self) -> float:
195        """The lower x edge."""
196        return self.x

The lower x edge.

bottom: float
198    @property
199    def bottom(self) -> float:
200        """The lower y edge."""
201        return self.y

The lower y edge.

right: float
203    @property
204    def right(self) -> float:
205        """The upper x edge."""
206        return self.x + self.width

The upper x edge.

top: float
208    @property
209    def top(self) -> float:
210        """The upper y edge."""
211        return self.y + self.height

The upper y edge.

center: Point
213    @property
214    def center(self) -> Point:
215        """The midpoint."""
216        self._raise_if_empty("center")
217        return Point((self.x + self.width / 2, self.y + self.height / 2))

The midpoint.

size: tuple[float, float]
229    @property
230    def size(self) -> tuple[float, float]:
231        """The extent along each axis."""
232        return self.width, self.height

The extent along each axis.

area: float
234    @property
235    def area(self) -> float:
236        """The ground covered, in square game units."""
237        return self.width * self.height

The ground covered, in square game units.

perimeter: float
239    @property
240    def perimeter(self) -> float:
241        """The distance around the edge."""
242        return 2 * (self.width + self.height)

The distance around the edge.

corners: tuple[Point, Point, Point, Point]
244    @property
245    def corners(self) -> tuple[Point, Point, Point, Point]:
246        """The four corners, counter-clockwise from the bottom left."""
247        return (
248            Point((self.left, self.bottom)),
249            Point((self.right, self.bottom)),
250            Point((self.right, self.top)),
251            Point((self.left, self.top)),
252        )

The four corners, counter-clockwise from the bottom left.

def encloses(self, other: Rectangle) -> bool:
266    def encloses(self, other: Rectangle) -> bool:
267        """Whether the whole of `other` lies inside."""
268        return (
269            self.left <= other.left
270            and self.bottom <= other.bottom
271            and self.right >= other.right
272            and self.top >= other.top
273        )

Whether the whole of other lies inside.

def translated(self, offset: 'PointLike') -> Rectangle:
275    def translated(self, offset: PointLike) -> Rectangle:
276        """The rectangle shifted by `offset`, keeping its size. Raises `ValueError` for an offset with a height."""
277        ground_offset = checked_ground_offset(offset)
278        return Rectangle(self.x + ground_offset[0], self.y + ground_offset[1], self.width, self.height)

The rectangle shifted by offset, keeping its size. Raises ValueError for an offset with a height.

def intersects(self, other: Rectangle) -> bool:
280    def intersects(self, other: Rectangle) -> bool:
281        """Whether the two rectangles share any ground: never when either is empty."""
282        if self._is_empty or other._is_empty:
283            return False
284        return not (
285            self.right <= other.left or self.left >= other.right or self.top <= other.bottom or self.bottom >= other.top
286        )

Whether the two rectangles share any ground: never when either is empty.

def intersection( self, other: Rectangle) -> Rectangle | None:
288    def intersection(self, other: Rectangle) -> Rectangle | None:
289        """The ground both rectangles cover; `None` if they do not overlap."""
290        left = max(self.left, other.left)
291        bottom = max(self.bottom, other.bottom)
292        right = min(self.right, other.right)
293        top = min(self.top, other.top)
294        if right <= left or top <= bottom:
295            return None
296        return Rectangle(left, bottom, right - left, top - bottom)

The ground both rectangles cover; None if they do not overlap.

def rounded_out(self) -> Rectangle:
298    def rounded_out(self) -> Rectangle:
299        """The smallest rectangle on integer coordinates that contains this one."""
300        left = math.floor(self.left)
301        bottom = math.floor(self.bottom)
302        return Rectangle(left, bottom, math.ceil(self.right) - left, math.ceil(self.top) - bottom)

The smallest rectangle on integer coordinates that contains this one.

def rounded_in(self) -> Rectangle | None:
304    def rounded_in(self) -> Rectangle | None:
305        """The largest rectangle on integer coordinates that fits inside this one, `None` if none fits."""
306        left = math.ceil(self.left)
307        bottom = math.ceil(self.bottom)
308        right = math.floor(self.right)
309        top = math.floor(self.top)
310        if right <= left or top <= bottom:
311            return None
312        return Rectangle(left, bottom, right - left, top - bottom)

The largest rectangle on integer coordinates that fits inside this one, None if none fits.

def random_point( self, *, rng: random.Random | None = None) -> Point:
314    def random_point(self, *, rng: random.Random | None = None) -> Point:
315        """A point drawn uniformly from the rectangle, by `rng` or the `random` module's own generator."""
316        self._raise_if_empty("points to draw from")
317        uniform = random.uniform if rng is None else rng.uniform
318        x, y = self.x, self.y
319        drawn_x = x + uniform(0, self.width)
320        drawn_y = y + uniform(0, self.height)
321        return _nearest_point_held_within(drawn_x, drawn_y, x, y, x + self.width, y + self.height)

A point drawn uniformly from the rectangle, by rng or the random module's own generator.

def closest_point_to( self, point: 'PointLike') -> tuple[Point, float]:
323    def closest_point_to(self, point: PointLike) -> tuple[Point, float]:
324        """The point of the rectangle nearest to `point`, and the distance to it, kept off the upper edges as `Area`
325        has it."""
326        self._raise_if_empty("closest point")
327        x, y = self.x, self.y
328        closest = _nearest_point_held_within(point[0], point[1], x, y, x + self.width, y + self.height)
329        return closest, closest.distance_to(point)

The point of the rectangle nearest to point, and the distance to it, kept off the upper edges as Area has it.

def bounding_rectangle(self) -> Rectangle:
331    def bounding_rectangle(self) -> Rectangle:
332        """The rectangle itself."""
333        self._raise_if_empty("bounding rectangle")
334        return self

The rectangle itself.

def tile_range(self) -> tuple[range, range]:
336    def tile_range(self) -> tuple[range, range]:
337        """The x and y addresses of the tiles the rectangle covers."""
338        return (
339            range(math.ceil(self.left - 0.5), math.ceil(self.right - 0.5)),
340            range(math.ceil(self.bottom - 0.5), math.ceil(self.top - 0.5)),
341        )

The x and y addresses of the tiles the rectangle covers.

def tile_centers(self, *, offset: 'PointLike' = (0.0, 0.0)) -> numpy.ndarray:
343    def tile_centers(self, *, offset: PointLike = (0.0, 0.0)) -> ndarray:
344        """The center of every tile the rectangle covers, as an array of shape `(x, y, 2)`.
345
346        Laid out like the tiles themselves, so a mask over the same region indexes it directly. `offset`
347        shifts every point without changing which tiles are covered.
348        """
349        x_range, y_range = self.tile_range()
350        xs = numpy.arange(x_range.start, x_range.stop) + 0.5 + offset[0]
351        ys = numpy.arange(y_range.start, y_range.stop) + 0.5 + offset[1]
352        return numpy.stack(numpy.meshgrid(xs, ys, indexing="ij"), axis=-1)

The center of every tile the rectangle covers, as an array of shape (x, y, 2).

Laid out like the tiles themselves, so a mask over the same region indexes it directly. offset shifts every point without changing which tiles are covered.

def tiles(self) -> TileSet:
354    def tiles(self) -> TileSet:
355        """Every tile whose center the rectangle contains."""
356        x_range, y_range = self.tile_range()
357        return TileSet._from_addresses((x, y) for x in x_range for y in y_range)

Every tile whose center the rectangle contains.

@final
class SourceField:
 93@final
 94class SourceField:
 95    """A `Field` of floats made of circles, each adding its value over the ground it covers, its edge included, such as
 96    a threat around each enemy, and 0 beyond every circle's reach. A circle with a sharp `Edge`, the default, holds
 97    its value throughout, so a mask is circles of 1.0; one with a linear or a smooth edge falls from its value to 0,
 98    evenly or smoothly, across a band of `edge_width` centered on its edge, half the value on the edge, so it reaches
 99    half the width beyond the circle. Where circles overlap, their values add up. The field covers every point, so no
100    read raises `IndexError`.
101
102    `min`, `max`, `argmin` and `argmax` read the field at points at most `spacing` apart, along x and along y, over
103    the area, and at the area's point nearest the center of each circle that reaches it. So where every circle's value
104    is positive, whether `max` reads above 0 is exact, and so is the largest value where one circle reaches the area
105    alone. Anything else may be off by as much as the field changes over the spacing, and a value held only on a patch
106    narrower than that may be missed.
107
108    A field holds `CircleSource`s, built from them or circle by circle with `add_circle`. `len` counts them, and
109    iterating over the field hands them out, in the order added. Fields add up and subtract, a sum holding the circles
110    of both, a number scales one, and `transformed` remakes each circle, each a new field. Like a grid, a field has no
111    truth value.
112    """
113
114    __slots__ = ("_sources", "_spacing")
115
116    _sources: list[CircleSource]
117    _spacing: float
118
119    def __init__(self, sources: Iterable[CircleSource] = (), *, spacing: float = 0.25) -> None:
120        """A field holding `sources`, whose reads over an area take points at most `spacing` apart:
121        `SourceField(other)` holds another field's circles. Raises `ValueError` for a spacing that is not positive, and
122        `TypeError` for a source that is not a `CircleSource`."""
123        if spacing <= 0:
124            raise ValueError(f"a source field reads points a positive spacing apart, got {spacing}")
125        self._sources = []
126        self._spacing = spacing
127        for source in sources:
128            if not isinstance(source, CircleSource):
129                raise TypeError(f"a source field holds CircleSources, not a {type(source).__name__}")
130            self._sources.append(source)
131
132    @property
133    def spacing(self) -> float:
134        """How far apart, at most, along x and along y, `min`, `max`, `argmin` and `argmax` read the field."""
135        return self._spacing
136
137    def add_circle(
138        self, center: PointLike, radius: float, value: float, *, edge: Edge = Edge.SHARP, edge_width: float = 0.0
139    ) -> None:
140        """Add a circle of `radius` around `center`, holding `value`: throughout, with a sharp `edge`, or with a linear
141        or a smooth one, falling across a band of `edge_width` centered on its edge, to half the value on it and 0 half
142        the width beyond it, so that an edge as wide as the circle makes a cone, or a smooth one a bump, reaching twice
143        the radius. Raises `ValueError` as a `Circle` and a `CircleSource` do: for a radius not above 0, for a width
144        given a sharp edge, and for a linear or smooth edge's width not above 0."""
145        self._sources.append(CircleSource(Circle(center, radius), value, edge, edge_width))
146
147    def clear(self) -> None:
148        """Remove every circle, keeping the spacing."""
149        self._sources.clear()
150
151    def copy(self) -> SourceField:
152        """A new field holding the same circles and reading at the same spacing, which a circle added to either leaves
153        out of the other."""
154        return SourceField(self._sources, spacing=self._spacing)
155
156    def __len__(self) -> int:
157        """The number of circles added."""
158        return len(self._sources)
159
160    def __iter__(self) -> Iterator[CircleSource]:
161        """Each circle the field holds, in the order added."""
162        return iter(self._sources)
163
164    def __bool__(self) -> bool:
165        """Raises `TypeError`, as a grid's does: whether a field holds a circle and whether it reads anything differ,
166        for circles of 0 or ones that cancel out. `len` says the one, and `max` within an area the other."""
167        raise TypeError("a source field has no truth value; len() says whether it holds a circle")
168
169    # --- Arithmetic
170
171    def __add__(self, other: SourceField) -> SourceField:
172        """A new field holding this field's circles and then `other`'s, so that its value is the sum of theirs
173        everywhere, reading at the finer of their spacings."""
174        if not isinstance(other, SourceField):
175            return NotImplemented
176        return SourceField([*self._sources, *other._sources], spacing=min(self._spacing, other._spacing))
177
178    def __sub__(self, other: SourceField) -> SourceField:
179        """A new field holding this field's circles and then `other`'s with their values negated, so that its value is
180        the difference of theirs everywhere, reading at the finer of their spacings."""
181        if not isinstance(other, SourceField):
182            return NotImplemented
183        return self + -other
184
185    def __neg__(self) -> SourceField:
186        """A new field of the same circles, each with its value negated."""
187        return self.transformed(lambda source: source._with_value(-source.value))
188
189    def __mul__(self, factor: float) -> SourceField:
190        """A new field of the same circles, each with its value multiplied by `factor`, a number."""
191        if not isinstance(factor, numbers.Real):
192            return NotImplemented
193        return self.transformed(lambda source: source._with_value(source.value * factor))
194
195    def __rmul__(self, factor: float) -> SourceField:
196        """A new field of the same circles, each with its value multiplied by `factor`, a number."""
197        return self.__mul__(factor)
198
199    def __truediv__(self, divisor: float) -> SourceField:
200        """A new field of the same circles, each with its value divided by `divisor`, a number. Raises
201        `ZeroDivisionError` for 0."""
202        if not isinstance(divisor, numbers.Real):
203            return NotImplemented
204        return self.transformed(lambda source: source._with_value(source.value / divisor))
205
206    def transformed(self, transformation: Callable[[CircleSource], CircleSource]) -> SourceField:
207        """A new field of each circle as `transformation` remakes it, a `CircleSource` from a `CircleSource`, in the
208        same order and reading at the same spacing: its value, its circle or its edge, through `dataclasses.replace`.
209        Raises `TypeError` for anything but a `CircleSource` made, which was checked as it was made."""
210        return SourceField((transformation(source) for source in self._sources), spacing=self._spacing)
211
212    # --- Reads
213
214    def sources_reaching(self, area: Area) -> list[CircleSource]:
215        """Each circle reaching `area`, as a `CircleSource`, in the order it was added: those whose values the reads
216        over the area take, those it reaches within its radius and half its edge's width, so not one touching only an
217        edge the area leaves out. An empty area has none."""
218        if not area.area:
219            return []
220        sources = self._sources_near(area.bounding_rectangle())
221        return [source for source, _ in _sources_reaching(area, sources)]
222
223    def values_at(self, points: Sequence[PointLike] | ndarray) -> ndarray:
224        """The value at each of `points`, a sequence of points or an array of them, a point a row, as `value_at` reads
225        it to the last bit, in a numpy pass a circle: an array of floats, a value a point, in order. It pays off from
226        about a hundred points; for a few, `value_at` in a loop is quicker."""
227        xs, ys = coordinate_arrays_of(points)
228        if not len(xs):
229            return numpy.zeros(0)
230        left = xs.min().item()
231        bottom = ys.min().item()
232        bounds = Rectangle(left, bottom, xs.max().item() - left, ys.max().item() - bottom)
233        return _values_at(xs, ys, self._sources_near(bounds))
234
235    def value_at(self, point: PointLike) -> float:
236        """The value at `point`: the sum of the values of the circles covering it."""
237        x = point[0]
238        y = point[1]
239        total = 0.0
240        for source in self._sources:
241            dx = x - source._x
242            dy = y - source._y
243            distance_squared = dx * dx + dy * dy
244            if distance_squared <= source._full_within_squared:
245                total += source.value
246            elif distance_squared <= source._reach_squared:
247                depth = (source._reach - math.sqrt(distance_squared)) / source.edge_width
248                weight = depth * depth * (3.0 - 2.0 * depth) if source.edge is Edge.SMOOTH else depth
249                total += source.value * weight
250        return total
251
252    def min(self, *, within: Area) -> float:
253        """The smallest value read in `within`, as the class says. Raises `ValueError` for an empty area."""
254        return self._extreme_value(within, largest=False)
255
256    def max(self, *, within: Area) -> float:
257        """The largest value read in `within`, as the class says. Raises `ValueError` for an empty area."""
258        return self._extreme_value(within, largest=True)
259
260    def argmin(self, *, within: Area) -> Point:
261        """The point, of those read in `within` as the class says, with the smallest value, the lowest x, then y, where
262        several tie: always one `within` holds. Raises `ValueError` for an empty area."""
263        return self._extreme_point(within, largest=False)
264
265    def argmax(self, *, within: Area) -> Point:
266        """The point, of those read in `within` as the class says, with the largest value, as `argmin` picks one."""
267        return self._extreme_point(within, largest=True)
268
269    def _extreme_value(self, area: Area, *, largest: bool) -> float:
270        """The largest value read in `area`, or the smallest."""
271        _check_not_empty(area)
272        if not self._sources:
273            return 0.0
274        bounds = area.bounding_rectangle()
275        sources = self._sources_near(bounds)
276        reaching = _sources_reaching(area, sources)
277        if not reaching:
278            return 0.0
279        if len(reaching) == 1 and largest == (reaching[0][0].value > 0):
280            # A circle reaching the area alone holds its value farthest from 0 at the area's point nearest its center,
281            # which is one of the points read, and the others near reach none of them.
282            return self.value_at(reaching[0][1])
283        xs, ys = self._points_to_read(area, bounds, [point for _, point in reaching])
284        values = _values_at(xs, ys, sources)
285        return (values.max() if largest else values.min()).item()
286
287    def _extreme_point(self, area: Area, *, largest: bool) -> Point:
288        """The point read in `area` with the largest value, or the smallest, the lowest x, then y, where several tie."""
289        _check_not_empty(area)
290        bounds = area.bounding_rectangle()
291        sources = self._sources_near(bounds)
292        xs, ys = self._points_to_read(area, bounds, [point for _, point in _sources_reaching(area, sources)])
293        values = _values_at(xs, ys, sources)
294        tied = numpy.flatnonzero(values == (values.max() if largest else values.min()))
295        picked = tied[numpy.lexsort((ys[tied], xs[tied]))[0]]
296        return Point((xs[picked].item(), ys[picked].item()))
297
298    def _sources_near(self, bounds: Rectangle) -> list[CircleSource]:
299        """The circles that may reach into `bounds`, an area's bounding rectangle: every one that does, and some that
300        only come near."""
301        left, bottom = bounds.x, bounds.y
302        right, top = bounds.right, bounds.top
303        return [
304            source
305            for source in self._sources
306            if source._x - source._reach <= right
307            and source._x + source._reach >= left
308            and source._y - source._reach <= top
309            and source._y + source._reach >= bottom
310        ]
311
312    def _points_to_read(self, area: Area, bounds: Rectangle, nearest_points: list[Point]) -> tuple[ndarray, ndarray]:
313        """The x and the y of the points to read in `area`, whose bounding rectangle is `bounds`: those `spacing` apart,
314        by ascending x, then y, then `nearest_points`, the area's point nearest each reaching circle's center."""
315        xs, ys = _points_spaced_over(area, bounds, self._spacing)
316        if not nearest_points:
317            return xs, ys
318        nearest = numpy.array(nearest_points)
319        return numpy.concatenate((xs, nearest[:, 0])), numpy.concatenate((ys, nearest[:, 1]))
320
321    def gradient_at(self, point: PointLike) -> tuple[float, float]:
322        """How fast the value rises at `point`, per map unit, along x and along y, together pointing the way it rises
323        fastest. Exact: a circle slopes across its edge's band, beyond where that begins and out to where it ends, where
324        a linear edge slopes too and a smooth one is flat, and is flat elsewhere, at its center too, where an edge wider
325        than the circle meets itself in a peak."""
326        x = point[0]
327        y = point[1]
328        slope_x = 0.0
329        slope_y = 0.0
330        for source in self._sources:
331            dx = x - source._x
332            dy = y - source._y
333            distance_squared = dx * dx + dy * dy
334            if source._full_within_squared < distance_squared <= source._reach_squared and distance_squared > 0.0:
335                distance = math.sqrt(distance_squared)
336                slope_per_offset = -source.value / (source.edge_width * distance)
337                if source.edge is Edge.SMOOTH:
338                    depth = (source._reach - distance) / source.edge_width
339                    slope_per_offset *= 6.0 * depth * (1.0 - depth)
340                slope_x += slope_per_offset * dx
341                slope_y += slope_per_offset * dy
342        return slope_x, slope_y
343
344    def to_grid(self, rectangle: Rectangle, *, outside: float | None = None) -> Grid[float]:
345        """A grid over the tiles `rectangle` covers, as `Grid.cropped` takes them, each holding the field's value at
346        its center, as `value_at` reads it, so that paths and a grid's arithmetic can take the field. A circle that
347        covers no tile's center, as a small one may, leaves no mark on the grid. `outside` is what the grid reads
348        beyond its edge, as `Grid` takes it."""
349        x_range, y_range = rectangle.tile_range()
350        values = numpy.zeros((len(x_range), len(y_range)))
351        for source in self._sources:
352            # The tiles the circle's bounding box overlaps, of those the grid holds.
353            left = max(x_range.start, math.floor(source._x - source._reach))
354            right = min(x_range.stop, math.floor(source._x + source._reach) + 1)
355            bottom = max(y_range.start, math.floor(source._y - source._reach))
356            top = min(y_range.stop, math.floor(source._y + source._reach) + 1)
357            if left >= right or bottom >= top:
358                continue
359            dx = (numpy.arange(left, right) + 0.5) - source._x
360            dy = (numpy.arange(bottom, top) + 0.5) - source._y
361            block = values[left - x_range.start : right - x_range.start, bottom - y_range.start : top - y_range.start]
362            block += source._values_at_distances_squared((dx * dx)[:, None] + (dy * dy)[None, :])
363        return Grid(values, origin=Tile(x_range.start, y_range.start), outside=outside)
364
365    def __repr__(self) -> str:
366        return f"SourceField({len(self._sources)} circles)"

A Field of floats made of circles, each adding its value over the ground it covers, its edge included, such as a threat around each enemy, and 0 beyond every circle's reach. A circle with a sharp Edge, the default, holds its value throughout, so a mask is circles of 1.0; one with a linear or a smooth edge falls from its value to 0, evenly or smoothly, across a band of edge_width centered on its edge, half the value on the edge, so it reaches half the width beyond the circle. Where circles overlap, their values add up. The field covers every point, so no read raises IndexError.

min, max, argmin and argmax read the field at points at most spacing apart, along x and along y, over the area, and at the area's point nearest the center of each circle that reaches it. So where every circle's value is positive, whether max reads above 0 is exact, and so is the largest value where one circle reaches the area alone. Anything else may be off by as much as the field changes over the spacing, and a value held only on a patch narrower than that may be missed.

A field holds CircleSources, built from them or circle by circle with add_circle. len counts them, and iterating over the field hands them out, in the order added. Fields add up and subtract, a sum holding the circles of both, a number scales one, and transformed remakes each circle, each a new field. Like a grid, a field has no truth value.

SourceField( sources: Iterable[CircleSource] = (), *, spacing: float = 0.25)
119    def __init__(self, sources: Iterable[CircleSource] = (), *, spacing: float = 0.25) -> None:
120        """A field holding `sources`, whose reads over an area take points at most `spacing` apart:
121        `SourceField(other)` holds another field's circles. Raises `ValueError` for a spacing that is not positive, and
122        `TypeError` for a source that is not a `CircleSource`."""
123        if spacing <= 0:
124            raise ValueError(f"a source field reads points a positive spacing apart, got {spacing}")
125        self._sources = []
126        self._spacing = spacing
127        for source in sources:
128            if not isinstance(source, CircleSource):
129                raise TypeError(f"a source field holds CircleSources, not a {type(source).__name__}")
130            self._sources.append(source)

A field holding sources, whose reads over an area take points at most spacing apart: SourceField(other) holds another field's circles. Raises ValueError for a spacing that is not positive, and TypeError for a source that is not a CircleSource.

spacing: float
132    @property
133    def spacing(self) -> float:
134        """How far apart, at most, along x and along y, `min`, `max`, `argmin` and `argmax` read the field."""
135        return self._spacing

How far apart, at most, along x and along y, min, max, argmin and argmax read the field.

def add_circle( self, center: 'PointLike', radius: float, value: float, *, edge: Edge = <Edge.SHARP: 'sharp'>, edge_width: float = 0.0) -> None:
137    def add_circle(
138        self, center: PointLike, radius: float, value: float, *, edge: Edge = Edge.SHARP, edge_width: float = 0.0
139    ) -> None:
140        """Add a circle of `radius` around `center`, holding `value`: throughout, with a sharp `edge`, or with a linear
141        or a smooth one, falling across a band of `edge_width` centered on its edge, to half the value on it and 0 half
142        the width beyond it, so that an edge as wide as the circle makes a cone, or a smooth one a bump, reaching twice
143        the radius. Raises `ValueError` as a `Circle` and a `CircleSource` do: for a radius not above 0, for a width
144        given a sharp edge, and for a linear or smooth edge's width not above 0."""
145        self._sources.append(CircleSource(Circle(center, radius), value, edge, edge_width))

Add a circle of radius around center, holding value: throughout, with a sharp edge, or with a linear or a smooth one, falling across a band of edge_width centered on its edge, to half the value on it and 0 half the width beyond it, so that an edge as wide as the circle makes a cone, or a smooth one a bump, reaching twice the radius. Raises ValueError as a Circle and a CircleSource do: for a radius not above 0, for a width given a sharp edge, and for a linear or smooth edge's width not above 0.

def clear(self) -> None:
147    def clear(self) -> None:
148        """Remove every circle, keeping the spacing."""
149        self._sources.clear()

Remove every circle, keeping the spacing.

def copy(self) -> SourceField:
151    def copy(self) -> SourceField:
152        """A new field holding the same circles and reading at the same spacing, which a circle added to either leaves
153        out of the other."""
154        return SourceField(self._sources, spacing=self._spacing)

A new field holding the same circles and reading at the same spacing, which a circle added to either leaves out of the other.

def transformed( self, transformation: Callable[[CircleSource], CircleSource]) -> SourceField:
206    def transformed(self, transformation: Callable[[CircleSource], CircleSource]) -> SourceField:
207        """A new field of each circle as `transformation` remakes it, a `CircleSource` from a `CircleSource`, in the
208        same order and reading at the same spacing: its value, its circle or its edge, through `dataclasses.replace`.
209        Raises `TypeError` for anything but a `CircleSource` made, which was checked as it was made."""
210        return SourceField((transformation(source) for source in self._sources), spacing=self._spacing)

A new field of each circle as transformation remakes it, a CircleSource from a CircleSource, in the same order and reading at the same spacing: its value, its circle or its edge, through dataclasses.replace. Raises TypeError for anything but a CircleSource made, which was checked as it was made.

def sources_reaching( self, area: Area) -> list[CircleSource]:
214    def sources_reaching(self, area: Area) -> list[CircleSource]:
215        """Each circle reaching `area`, as a `CircleSource`, in the order it was added: those whose values the reads
216        over the area take, those it reaches within its radius and half its edge's width, so not one touching only an
217        edge the area leaves out. An empty area has none."""
218        if not area.area:
219            return []
220        sources = self._sources_near(area.bounding_rectangle())
221        return [source for source, _ in _sources_reaching(area, sources)]

Each circle reaching area, as a CircleSource, in the order it was added: those whose values the reads over the area take, those it reaches within its radius and half its edge's width, so not one touching only an edge the area leaves out. An empty area has none.

def values_at(self, points: 'Sequence[PointLike] | ndarray') -> numpy.ndarray:
223    def values_at(self, points: Sequence[PointLike] | ndarray) -> ndarray:
224        """The value at each of `points`, a sequence of points or an array of them, a point a row, as `value_at` reads
225        it to the last bit, in a numpy pass a circle: an array of floats, a value a point, in order. It pays off from
226        about a hundred points; for a few, `value_at` in a loop is quicker."""
227        xs, ys = coordinate_arrays_of(points)
228        if not len(xs):
229            return numpy.zeros(0)
230        left = xs.min().item()
231        bottom = ys.min().item()
232        bounds = Rectangle(left, bottom, xs.max().item() - left, ys.max().item() - bottom)
233        return _values_at(xs, ys, self._sources_near(bounds))

The value at each of points, a sequence of points or an array of them, a point a row, as value_at reads it to the last bit, in a numpy pass a circle: an array of floats, a value a point, in order. It pays off from about a hundred points; for a few, value_at in a loop is quicker.

def value_at(self, point: 'PointLike') -> float:
235    def value_at(self, point: PointLike) -> float:
236        """The value at `point`: the sum of the values of the circles covering it."""
237        x = point[0]
238        y = point[1]
239        total = 0.0
240        for source in self._sources:
241            dx = x - source._x
242            dy = y - source._y
243            distance_squared = dx * dx + dy * dy
244            if distance_squared <= source._full_within_squared:
245                total += source.value
246            elif distance_squared <= source._reach_squared:
247                depth = (source._reach - math.sqrt(distance_squared)) / source.edge_width
248                weight = depth * depth * (3.0 - 2.0 * depth) if source.edge is Edge.SMOOTH else depth
249                total += source.value * weight
250        return total

The value at point: the sum of the values of the circles covering it.

def min(self, *, within: Area) -> float:
252    def min(self, *, within: Area) -> float:
253        """The smallest value read in `within`, as the class says. Raises `ValueError` for an empty area."""
254        return self._extreme_value(within, largest=False)

The smallest value read in within, as the class says. Raises ValueError for an empty area.

def max(self, *, within: Area) -> float:
256    def max(self, *, within: Area) -> float:
257        """The largest value read in `within`, as the class says. Raises `ValueError` for an empty area."""
258        return self._extreme_value(within, largest=True)

The largest value read in within, as the class says. Raises ValueError for an empty area.

def argmin( self, *, within: Area) -> Point:
260    def argmin(self, *, within: Area) -> Point:
261        """The point, of those read in `within` as the class says, with the smallest value, the lowest x, then y, where
262        several tie: always one `within` holds. Raises `ValueError` for an empty area."""
263        return self._extreme_point(within, largest=False)

The point, of those read in within as the class says, with the smallest value, the lowest x, then y, where several tie: always one within holds. Raises ValueError for an empty area.

def argmax( self, *, within: Area) -> Point:
265    def argmax(self, *, within: Area) -> Point:
266        """The point, of those read in `within` as the class says, with the largest value, as `argmin` picks one."""
267        return self._extreme_point(within, largest=True)

The point, of those read in within as the class says, with the largest value, as argmin picks one.

def gradient_at(self, point: 'PointLike') -> tuple[float, float]:
321    def gradient_at(self, point: PointLike) -> tuple[float, float]:
322        """How fast the value rises at `point`, per map unit, along x and along y, together pointing the way it rises
323        fastest. Exact: a circle slopes across its edge's band, beyond where that begins and out to where it ends, where
324        a linear edge slopes too and a smooth one is flat, and is flat elsewhere, at its center too, where an edge wider
325        than the circle meets itself in a peak."""
326        x = point[0]
327        y = point[1]
328        slope_x = 0.0
329        slope_y = 0.0
330        for source in self._sources:
331            dx = x - source._x
332            dy = y - source._y
333            distance_squared = dx * dx + dy * dy
334            if source._full_within_squared < distance_squared <= source._reach_squared and distance_squared > 0.0:
335                distance = math.sqrt(distance_squared)
336                slope_per_offset = -source.value / (source.edge_width * distance)
337                if source.edge is Edge.SMOOTH:
338                    depth = (source._reach - distance) / source.edge_width
339                    slope_per_offset *= 6.0 * depth * (1.0 - depth)
340                slope_x += slope_per_offset * dx
341                slope_y += slope_per_offset * dy
342        return slope_x, slope_y

How fast the value rises at point, per map unit, along x and along y, together pointing the way it rises fastest. Exact: a circle slopes across its edge's band, beyond where that begins and out to where it ends, where a linear edge slopes too and a smooth one is flat, and is flat elsewhere, at its center too, where an edge wider than the circle meets itself in a peak.

def to_grid( self, rectangle: Rectangle, *, outside: float | None = None) -> Grid[float]:
344    def to_grid(self, rectangle: Rectangle, *, outside: float | None = None) -> Grid[float]:
345        """A grid over the tiles `rectangle` covers, as `Grid.cropped` takes them, each holding the field's value at
346        its center, as `value_at` reads it, so that paths and a grid's arithmetic can take the field. A circle that
347        covers no tile's center, as a small one may, leaves no mark on the grid. `outside` is what the grid reads
348        beyond its edge, as `Grid` takes it."""
349        x_range, y_range = rectangle.tile_range()
350        values = numpy.zeros((len(x_range), len(y_range)))
351        for source in self._sources:
352            # The tiles the circle's bounding box overlaps, of those the grid holds.
353            left = max(x_range.start, math.floor(source._x - source._reach))
354            right = min(x_range.stop, math.floor(source._x + source._reach) + 1)
355            bottom = max(y_range.start, math.floor(source._y - source._reach))
356            top = min(y_range.stop, math.floor(source._y + source._reach) + 1)
357            if left >= right or bottom >= top:
358                continue
359            dx = (numpy.arange(left, right) + 0.5) - source._x
360            dy = (numpy.arange(bottom, top) + 0.5) - source._y
361            block = values[left - x_range.start : right - x_range.start, bottom - y_range.start : top - y_range.start]
362            block += source._values_at_distances_squared((dx * dx)[:, None] + (dy * dy)[None, :])
363        return Grid(values, origin=Tile(x_range.start, y_range.start), outside=outside)

A grid over the tiles rectangle covers, as Grid.cropped takes them, each holding the field's value at its center, as value_at reads it, so that paths and a grid's arithmetic can take the field. A circle that covers no tile's center, as a small one may, leaves no mark on the grid. outside is what the grid reads beyond its edge, as Grid takes it.

@final
@dataclass(frozen=True, slots=True, order=True, init=False)
class Tile(sc2nachos.geometry.Area):
 29@final
 30@dataclass(frozen=True, slots=True, order=True, init=False)
 31class Tile(Area):
 32    """One square of the map, addressed by the integer coordinates of its lower left corner. An area's `in`, a grid's
 33    index and `Tile.at` take a tile where they take a point; anything else that wants a point takes its
 34    `center`. Tiles sort by `x`, then `y`."""
 35
 36    x: int
 37    """The left edge."""
 38    y: int
 39    """The bottom edge."""
 40
 41    def __init__(self, x: int, y: int) -> None:
 42        """The tile whose lower left corner is at `x` and `y`, each an integer, a numpy one included, which becomes an
 43        `int`. Raises `TypeError` for any other coordinate, a float among them."""
 44        object.__setattr__(self, "x", operator.index(x))
 45        object.__setattr__(self, "y", operator.index(y))
 46
 47    @classmethod
 48    def at(cls, point: PointLike | Tile) -> Self:
 49        """The tile a point falls in, or the tile itself."""
 50        x, y = Tile._address_at(point)
 51        return cls(x, y)
 52
 53    @staticmethod
 54    def _address_at(point: PointLike | Tile) -> tuple[int, int]:
 55        """The x and y of the tile `point` falls in, or of the tile itself. Raises `TypeError` on anything but a point
 56        or a tile."""
 57        # Points first: this runs for every lookup of a tile set and a grid.
 58        if isinstance(point, tuple):
 59            return math.floor(point[0]), math.floor(point[1])
 60        if type(point) is Tile:
 61            return point.x, point.y
 62        raise not_a_point_error(point)
 63
 64    @property
 65    def center(self) -> Point:
 66        """The middle of the tile, where a unit on it stands."""
 67        return Point((self.x + 0.5, self.y + 0.5))
 68
 69    @property
 70    def area(self) -> float:
 71        """The ground covered: one square game unit."""
 72        return 1.0
 73
 74    def random_point(self, *, rng: random.Random | None = None) -> Point:
 75        """A point drawn uniformly from the tile, by `rng` or the `random` module's own generator."""
 76        random_fraction = random.random if rng is None else rng.random
 77        x, y = self.x, self.y
 78        return _nearest_point_held_within(x + random_fraction(), y + random_fraction(), x, y, x + 1, y + 1)
 79
 80    @property
 81    def neighbors4(self) -> tuple[Tile, Tile, Tile, Tile]:
 82        """The four orthogonally adjacent tiles."""
 83        x, y = self.x, self.y
 84        return (Tile(x, y + 1), Tile(x, y - 1), Tile(x + 1, y), Tile(x - 1, y))
 85
 86    @property
 87    def neighbors8(self) -> tuple[Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile]:
 88        """The eight adjacent tiles, diagonals included."""
 89        x, y = self.x, self.y
 90        return (
 91            *self.neighbors4,
 92            Tile(x + 1, y + 1),
 93            Tile(x + 1, y - 1),
 94            Tile(x - 1, y + 1),
 95            Tile(x - 1, y - 1),
 96        )
 97
 98    def __contains__(self, point: PointLike | Tile) -> bool:
 99        """Whether a point falls on this tile, on the lower edges but not the upper ones, a tile reading as itself.
100        Raises `TypeError` on anything but a point or a tile."""
101        return Tile._address_at(point) == (self.x, self.y)
102
103    def _contains_each(self, xs: ndarray, ys: ndarray) -> ndarray:
104        """Whether each point falls on this tile, on the lower edges but not the upper ones."""
105        x, y = self.x, self.y
106        return (x <= xs) & (xs < x + 1) & (y <= ys) & (ys < y + 1)
107
108    def shifted(self, dx: int, dy: int) -> Tile:
109        """The tile `dx` across and `dy` up from this one. Raises `TypeError` for a shift that is not a whole number."""
110        return Tile(self.x + dx, self.y + dy)
111
112    def translated(self, offset: PointLike) -> Tile:
113        """The tile reached by shifting this one's center by `offset`. Raises `ValueError` for an offset with a
114        height."""
115        ground_offset = checked_ground_offset(offset)
116        return Tile.at((self.x + 0.5 + ground_offset[0], self.y + 0.5 + ground_offset[1]))
117
118    def closest_point_to(self, point: PointLike) -> tuple[Point, float]:
119        """The point of the tile nearest to `point`, and the distance to it, kept off the upper edges as `Area` has
120        it."""
121        x, y = self.x, self.y
122        closest = _nearest_point_held_within(point[0], point[1], x, y, x + 1, y + 1)
123        return closest, closest.distance_to(point)
124
125    def bounding_rectangle(self) -> Rectangle:
126        """The tile as a unit rectangle."""
127        return Rectangle(self.x, self.y, 1, 1)
128
129    def tiles(self) -> TileSet:
130        """A set of this tile alone."""
131        return TileSet._from_addresses([(self.x, self.y)])
132
133    def _overlapped_tile_mask(self) -> TileMask:
134        """The tile alone."""
135        return TileMask(self, numpy.ones((1, 1), dtype=bool))
136
137    def __repr__(self) -> str:
138        return f"Tile({self.x}, {self.y})"

One square of the map, addressed by the integer coordinates of its lower left corner. An area's in, a grid's index and Tile.at take a tile where they take a point; anything else that wants a point takes its center. Tiles sort by x, then y.

Tile(x: int, y: int)
41    def __init__(self, x: int, y: int) -> None:
42        """The tile whose lower left corner is at `x` and `y`, each an integer, a numpy one included, which becomes an
43        `int`. Raises `TypeError` for any other coordinate, a float among them."""
44        object.__setattr__(self, "x", operator.index(x))
45        object.__setattr__(self, "y", operator.index(y))

The tile whose lower left corner is at x and y, each an integer, a numpy one included, which becomes an int. Raises TypeError for any other coordinate, a float among them.

x: int

The left edge.

y: int

The bottom edge.

@classmethod
def at(cls, point: 'PointLike | Tile') -> Self:
47    @classmethod
48    def at(cls, point: PointLike | Tile) -> Self:
49        """The tile a point falls in, or the tile itself."""
50        x, y = Tile._address_at(point)
51        return cls(x, y)

The tile a point falls in, or the tile itself.

center: Point
64    @property
65    def center(self) -> Point:
66        """The middle of the tile, where a unit on it stands."""
67        return Point((self.x + 0.5, self.y + 0.5))

The middle of the tile, where a unit on it stands.

area: float
69    @property
70    def area(self) -> float:
71        """The ground covered: one square game unit."""
72        return 1.0

The ground covered: one square game unit.

def random_point( self, *, rng: random.Random | None = None) -> Point:
74    def random_point(self, *, rng: random.Random | None = None) -> Point:
75        """A point drawn uniformly from the tile, by `rng` or the `random` module's own generator."""
76        random_fraction = random.random if rng is None else rng.random
77        x, y = self.x, self.y
78        return _nearest_point_held_within(x + random_fraction(), y + random_fraction(), x, y, x + 1, y + 1)

A point drawn uniformly from the tile, by rng or the random module's own generator.

neighbors4: tuple[Tile, Tile, Tile, Tile]
80    @property
81    def neighbors4(self) -> tuple[Tile, Tile, Tile, Tile]:
82        """The four orthogonally adjacent tiles."""
83        x, y = self.x, self.y
84        return (Tile(x, y + 1), Tile(x, y - 1), Tile(x + 1, y), Tile(x - 1, y))

The four orthogonally adjacent tiles.

neighbors8: tuple[Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile]
86    @property
87    def neighbors8(self) -> tuple[Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile]:
88        """The eight adjacent tiles, diagonals included."""
89        x, y = self.x, self.y
90        return (
91            *self.neighbors4,
92            Tile(x + 1, y + 1),
93            Tile(x + 1, y - 1),
94            Tile(x - 1, y + 1),
95            Tile(x - 1, y - 1),
96        )

The eight adjacent tiles, diagonals included.

def shifted(self, dx: int, dy: int) -> Tile:
108    def shifted(self, dx: int, dy: int) -> Tile:
109        """The tile `dx` across and `dy` up from this one. Raises `TypeError` for a shift that is not a whole number."""
110        return Tile(self.x + dx, self.y + dy)

The tile dx across and dy up from this one. Raises TypeError for a shift that is not a whole number.

def translated(self, offset: 'PointLike') -> Tile:
112    def translated(self, offset: PointLike) -> Tile:
113        """The tile reached by shifting this one's center by `offset`. Raises `ValueError` for an offset with a
114        height."""
115        ground_offset = checked_ground_offset(offset)
116        return Tile.at((self.x + 0.5 + ground_offset[0], self.y + 0.5 + ground_offset[1]))

The tile reached by shifting this one's center by offset. Raises ValueError for an offset with a height.

def closest_point_to( self, point: 'PointLike') -> tuple[Point, float]:
118    def closest_point_to(self, point: PointLike) -> tuple[Point, float]:
119        """The point of the tile nearest to `point`, and the distance to it, kept off the upper edges as `Area` has
120        it."""
121        x, y = self.x, self.y
122        closest = _nearest_point_held_within(point[0], point[1], x, y, x + 1, y + 1)
123        return closest, closest.distance_to(point)

The point of the tile nearest to point, and the distance to it, kept off the upper edges as Area has it.

def bounding_rectangle(self) -> Rectangle:
125    def bounding_rectangle(self) -> Rectangle:
126        """The tile as a unit rectangle."""
127        return Rectangle(self.x, self.y, 1, 1)

The tile as a unit rectangle.

def tiles(self) -> TileSet:
129    def tiles(self) -> TileSet:
130        """A set of this tile alone."""
131        return TileSet._from_addresses([(self.x, self.y)])

A set of this tile alone.

@final
class TilePath(collections.abc.Sequence[sc2nachos.geometry._shapes.Tile]):
 20@final
 21class TilePath(Sequence[Tile]):
 22    """An ordered walk of tiles.
 23
 24    A path may be empty. An empty path is falsy, and `start` and `end` raise `ValueError` on it.
 25    """
 26
 27    __slots__ = ("_distance", "_tiles")
 28
 29    _tiles: tuple[Tile, ...]
 30    _distance: float | None
 31
 32    def __init__(self, tiles: Iterable[Tile], distance: float | None = None) -> None:
 33        """A path along `tiles`, `distance` game units end to end, measured on first use if not given."""
 34        self._tiles = tuple(tiles)
 35        if distance is not None and (not math.isfinite(distance) or distance < 0):
 36            raise ValueError(f"a path cannot be {distance} game units long")
 37        self._distance = distance
 38
 39    @property
 40    def distance(self) -> float:
 41        """The length from the first tile to the last, center to center."""
 42        if self._distance is None:
 43            self._distance = math.fsum(
 44                one.center.distance_to(following.center) for one, following in itertools.pairwise(self._tiles)
 45            )
 46        return self._distance
 47
 48    @property
 49    def start(self) -> Tile:
 50        """The first tile."""
 51        if not self._tiles:
 52            raise ValueError("an empty path has no start")
 53        return self._tiles[0]
 54
 55    @property
 56    def end(self) -> Tile:
 57        """The last tile."""
 58        if not self._tiles:
 59            raise ValueError("an empty path has no end")
 60        return self._tiles[-1]
 61
 62    @overload
 63    def __getitem__(self, index: int) -> Tile: ...
 64
 65    @overload
 66    def __getitem__(self, index: slice) -> TilePath: ...
 67
 68    def __getitem__(self, index: int | slice) -> Tile | TilePath:
 69        """The tile at `index`, or the stretch a slice selects.
 70
 71        A stretch's distance is measured afresh, as straight lines between the tiles it keeps.
 72        """
 73        if isinstance(index, slice):
 74            return TilePath(self._tiles[index])
 75        return self._tiles[index]
 76
 77    def __len__(self) -> int:
 78        return len(self._tiles)
 79
 80    def __iter__(self) -> Iterator[Tile]:
 81        return iter(self._tiles)
 82
 83    def __reversed__(self) -> Iterator[Tile]:
 84        return reversed(self._tiles)
 85
 86    def index(self, value: PointLike | Tile, start: int = 0, stop: int = sys.maxsize) -> int:
 87        """The position of the first tile from `start`, and before `stop`, that holds the point `value`, a tile
 88        reading as itself. Raises `ValueError` if none does, and `TypeError` on anything but a point or a tile."""
 89        return self._tiles.index(Tile.at(value), start, stop)
 90
 91    def count(self, value: PointLike | Tile) -> int:
 92        """How many of the path's tiles hold the point `value`, a tile reading as itself. Raises `TypeError` on
 93        anything but a point or a tile."""
 94        return self._tiles.count(Tile.at(value))
 95
 96    def __contains__(self, point: object) -> bool:
 97        """Whether the path covers the tile holding `point`, a tile reading as itself. Raises `TypeError` on anything
 98        but a point or a tile.
 99
100        This scans the path; build a `TileSet` from it to test many points.
101        """
102        return Tile.at(cast("PointLike | Tile", point)) in self._tiles
103
104    def __eq__(self, other: object) -> bool:
105        if not isinstance(other, TilePath):
106            return NotImplemented
107        return self._tiles == other._tiles
108
109    def __hash__(self) -> int:
110        return hash(self._tiles)
111
112    def __repr__(self) -> str:
113        if not self._tiles:
114            return "TilePath(empty)"
115        return f"TilePath({self.start!r} to {self.end!r}, {len(self._tiles)} tiles, {self.distance:.2f} long)"

An ordered walk of tiles.

A path may be empty. An empty path is falsy, and start and end raise ValueError on it.

TilePath( tiles: Iterable[Tile], distance: float | None = None)
32    def __init__(self, tiles: Iterable[Tile], distance: float | None = None) -> None:
33        """A path along `tiles`, `distance` game units end to end, measured on first use if not given."""
34        self._tiles = tuple(tiles)
35        if distance is not None and (not math.isfinite(distance) or distance < 0):
36            raise ValueError(f"a path cannot be {distance} game units long")
37        self._distance = distance

A path along tiles, distance game units end to end, measured on first use if not given.

distance: float
39    @property
40    def distance(self) -> float:
41        """The length from the first tile to the last, center to center."""
42        if self._distance is None:
43            self._distance = math.fsum(
44                one.center.distance_to(following.center) for one, following in itertools.pairwise(self._tiles)
45            )
46        return self._distance

The length from the first tile to the last, center to center.

start: Tile
48    @property
49    def start(self) -> Tile:
50        """The first tile."""
51        if not self._tiles:
52            raise ValueError("an empty path has no start")
53        return self._tiles[0]

The first tile.

end: Tile
55    @property
56    def end(self) -> Tile:
57        """The last tile."""
58        if not self._tiles:
59            raise ValueError("an empty path has no end")
60        return self._tiles[-1]

The last tile.

def index( self, value: 'PointLike | Tile', start: int = 0, stop: int = 9223372036854775807) -> int:
86    def index(self, value: PointLike | Tile, start: int = 0, stop: int = sys.maxsize) -> int:
87        """The position of the first tile from `start`, and before `stop`, that holds the point `value`, a tile
88        reading as itself. Raises `ValueError` if none does, and `TypeError` on anything but a point or a tile."""
89        return self._tiles.index(Tile.at(value), start, stop)

The position of the first tile from start, and before stop, that holds the point value, a tile reading as itself. Raises ValueError if none does, and TypeError on anything but a point or a tile.

def count(self, value: 'PointLike | Tile') -> int:
91    def count(self, value: PointLike | Tile) -> int:
92        """How many of the path's tiles hold the point `value`, a tile reading as itself. Raises `TypeError` on
93        anything but a point or a tile."""
94        return self._tiles.count(Tile.at(value))

How many of the path's tiles hold the point value, a tile reading as itself. Raises TypeError on anything but a point or a tile.

@final
class TileSet(sc2nachos.geometry.Area):
380@final
381class TileSet(Area):
382    """An area of any shape, held as the set of map tiles it covers.
383
384    Build one from positions with `Tile.at`. An empty tile set is falsy.
385    """
386
387    _addresses: frozenset[tuple[int, int]]
388
389    def __init__(self, tiles: Iterable[Tile]) -> None:
390        """A tile set covering `tiles`. Raises `TypeError` for anything else among them."""
391        try:
392            self._addresses = frozenset((tile.x, tile.y) for tile in tiles)
393        except AttributeError as error:
394            raise TypeError("a tile set is built of tiles; Tile.at gives the one a point falls in") from error
395
396    @classmethod
397    def _from_addresses(cls, addresses: Iterable[tuple[int, int]]) -> TileSet:
398        """A tile set covering the tiles at `addresses`, each an x and a y."""
399        tile_set = cls.__new__(cls)
400        tile_set._addresses = frozenset(addresses)
401        return tile_set
402
403    @classmethod
404    def _from_mask(cls, origin: Tile, mask: ndarray) -> TileSet:
405        """A tile set covering the true entries of `mask`, indexed `[x, y]`, whose `[0, 0]` entry is the tile at
406        `origin`."""
407        xs, ys = numpy.nonzero(mask)
408        return cls._from_addresses(zip((xs + origin.x).tolist(), (ys + origin.y).tolist(), strict=True))
409
410    @property
411    def center(self) -> Point:
412        """The mean of the covered tile centers."""
413        return self._centroid
414
415    @cached_property
416    def _centroid(self) -> Point:
417        """The mean position, computed on first use."""
418        if not self._addresses:
419            raise ValueError("an empty tile set has no center")
420        sum_x = sum_y = 0
421        for x, y in self._addresses:
422            sum_x += x
423            sum_y += y
424        count = len(self._addresses)
425        return Point((sum_x / count + 0.5, sum_y / count + 0.5))
426
427    @property
428    def area(self) -> float:
429        """The ground covered, in square game units: one per tile."""
430        return float(len(self._addresses))
431
432    def __len__(self) -> int:
433        return len(self._addresses)
434
435    @cached_property
436    def _ordered(self) -> tuple[Tile, ...]:
437        """The covered tiles by ascending x then y, sorted on first use."""
438        # Keep the sort: a set built by difference iterates in a different order from one built directly, which
439        # reaches `random_point` and makes a seeded game unreproducible.
440        return tuple(Tile(x, y) for x, y in sorted(self._addresses))
441
442    def __iter__(self) -> Iterator[Tile]:
443        yield from self._ordered
444
445    def __contains__(self, point: PointLike | Tile) -> bool:
446        """Whether the tile containing `point` is covered."""
447        return Tile._address_at(point) in self._addresses
448
449    def _contains_each(self, xs: ndarray, ys: ndarray) -> ndarray:
450        """Whether the tile containing each point is covered."""
451        covered_tiles = self._mask_over_bounds
452        columns = numpy.floor(xs).astype(int) - covered_tiles.origin.x
453        rows = numpy.floor(ys).astype(int) - covered_tiles.origin.y
454        columns, rows = numpy.broadcast_arrays(columns, rows)
455        width, height = covered_tiles.mask.shape
456        on_mask = (columns >= 0) & (columns < width) & (rows >= 0) & (rows < height)
457        contained = numpy.zeros(columns.shape, dtype=bool)
458        contained[on_mask] = covered_tiles.mask[columns[on_mask], rows[on_mask]]
459        return contained
460
461    @cached_property
462    def _spatial_index(self) -> tuple[KDTree, list[Tile]]:
463        """A KD-tree over the tile centers, with the tiles in the order it indexes them, built on first use."""
464        tiles = list(self._ordered)
465        return KDTree(numpy.array([(tile.x + 0.5, tile.y + 0.5) for tile in tiles])), tiles
466
467    def closest_point_to(self, point: PointLike) -> tuple[Point, float]:
468        """The point of the covered ground nearest to `point`, and the distance to it."""
469        if not self._addresses:
470            raise ValueError("an empty tile set has no closest point")
471        position = Point(point[:2])
472        if Tile._address_at(position) in self._addresses:
473            return position, 0.0
474        tree, tiles = self._spatial_index
475        nearest_center_distance, _ = tree.query(position)
476        # A tile's nearest point lies between 1/2 and sqrt(1/2) nearer than its center, so a tile can beat the one
477        # whose center is nearest only if its own center lies within this distance.
478        farthest_center_that_can_be_nearer = nearest_center_distance + math.sqrt(0.5) - 0.5
479        candidates = tree.query_ball_point(position, farthest_center_that_can_be_nearer, return_sorted=True)
480        return min((tiles[index].closest_point_to(position) for index in candidates), key=operator.itemgetter(1))
481
482    def random_point(self, *, rng: random.Random | None = None) -> Point:
483        """A point drawn uniformly from the covered ground, by `rng` or the `random` module's own generator."""
484        if not self._addresses:
485            raise ValueError("an empty tile set has no points to draw from")
486        choice = random.choice if rng is None else rng.choice
487        return choice(self._ordered).random_point(rng=rng)
488
489    def bounding_rectangle(self) -> Rectangle:
490        """The smallest rectangle containing every covered tile."""
491        if not self._addresses:
492            raise ValueError("an empty tile set has no bounding rectangle")
493        lowest_x, lowest_y, highest_x, highest_y = self._address_bounds
494        return Rectangle(lowest_x, lowest_y, highest_x - lowest_x + 1, highest_y - lowest_y + 1)
495
496    def tiles(self) -> TileSet:
497        """The tile set itself."""
498        return self
499
500    def _tile_mask(self, within: Rectangle | None = None) -> TileMask:
501        """The covered tiles that lie `within` a rectangle on whole tiles, if one is given, masked over their bounding
502        rectangle: an empty mask at `Tile(0, 0)` for none."""
503        xs, ys = self._address_arrays
504        if within is None or not len(xs) or self._lies_within(within):
505            # Kept once built: its size is at most that of `within`, or of the set's own bounds if none was given.
506            return self._mask_over_bounds
507        left, bottom = int(within.x), int(within.y)
508        right, top = left + int(within.width), bottom + int(within.height)
509        kept = (xs >= left) & (xs < right) & (ys >= bottom) & (ys < top)
510        return _mask_of_addresses(xs[kept], ys[kept])
511
512    def _overlapped_tile_mask(self) -> TileMask:
513        """The covered tiles."""
514        return self._mask_over_bounds
515
516    def _lies_within(self, within: Rectangle) -> bool:
517        """Whether every covered tile lies within `within`, a rectangle on whole tiles. The set is not empty."""
518        lowest_x, lowest_y, highest_x, highest_y = self._address_bounds
519        return (
520            within.x <= lowest_x
521            and highest_x < within.x + within.width
522            and within.y <= lowest_y
523            and highest_y < within.y + within.height
524        )
525
526    @cached_property
527    def _address_bounds(self) -> tuple[int, int, int, int]:
528        """The lowest x and y and the highest x and y of the covered tiles, found on first use. The set is not
529        empty."""
530        xs, ys = self._address_arrays
531        return int(xs.min()), int(ys.min()), int(xs.max()), int(ys.max())
532
533    @cached_property
534    def _address_arrays(self) -> tuple[ndarray, ndarray]:
535        """The x and the y of every covered tile, as two arrays, built on first use."""
536        address_rows = numpy.array(tuple(self._addresses), dtype=int).reshape(-1, 2)
537        address_rows.flags.writeable = False
538        return address_rows[:, 0], address_rows[:, 1]
539
540    @cached_property
541    def _mask_over_bounds(self) -> TileMask:
542        """What `_tile_mask` returns for every covered tile, built on first use."""
543        covered_tiles = _mask_of_addresses(*self._address_arrays)
544        covered_tiles.mask.flags.writeable = False
545        return covered_tiles
546
547    def translated(self, offset: PointLike) -> TileSet:
548        """The tiles shifted by `offset`, snapped back onto the tile grid, as `Tile.translated` shifts each. Raises
549        `ValueError` for an offset with a height."""
550        ground_offset = checked_ground_offset(offset)
551        offset_x, offset_y = ground_offset[0], ground_offset[1]
552        return TileSet._from_addresses(
553            (math.floor(x + 0.5 + offset_x), math.floor(y + 0.5 + offset_y)) for x, y in self._addresses
554        )
555
556    def filter(self, predicate: Callable[[Tile], bool]) -> TileSet:
557        """The tiles satisfying `predicate`."""
558        return TileSet(tile for tile in self._ordered if predicate(tile))
559
560    def __add__(self, other: Area) -> TileSet:
561        if not isinstance(other, Area):
562            return NotImplemented
563        return TileSet._from_addresses(self._addresses | other.tiles()._addresses)
564
565    def __sub__(self, other: Area) -> TileSet:
566        if not isinstance(other, Area):
567            return NotImplemented
568        return TileSet._from_addresses(self._addresses - other.tiles()._addresses)
569
570    def __eq__(self, other: object) -> bool:
571        if not isinstance(other, TileSet):
572            return NotImplemented
573        return self._addresses == other._addresses
574
575    def __hash__(self) -> int:
576        return hash(self._addresses)
577
578    def __repr__(self) -> str:
579        if not self._addresses:
580            return "TileSet(empty)"
581        return f"TileSet({len(self._addresses)} tiles around {self.center})"

An area of any shape, held as the set of map tiles it covers.

Build one from positions with Tile.at. An empty tile set is falsy.

TileSet(tiles: Iterable[Tile])
389    def __init__(self, tiles: Iterable[Tile]) -> None:
390        """A tile set covering `tiles`. Raises `TypeError` for anything else among them."""
391        try:
392            self._addresses = frozenset((tile.x, tile.y) for tile in tiles)
393        except AttributeError as error:
394            raise TypeError("a tile set is built of tiles; Tile.at gives the one a point falls in") from error

A tile set covering tiles. Raises TypeError for anything else among them.

center: Point
410    @property
411    def center(self) -> Point:
412        """The mean of the covered tile centers."""
413        return self._centroid

The mean of the covered tile centers.

area: float
427    @property
428    def area(self) -> float:
429        """The ground covered, in square game units: one per tile."""
430        return float(len(self._addresses))

The ground covered, in square game units: one per tile.

def closest_point_to( self, point: 'PointLike') -> tuple[Point, float]:
467    def closest_point_to(self, point: PointLike) -> tuple[Point, float]:
468        """The point of the covered ground nearest to `point`, and the distance to it."""
469        if not self._addresses:
470            raise ValueError("an empty tile set has no closest point")
471        position = Point(point[:2])
472        if Tile._address_at(position) in self._addresses:
473            return position, 0.0
474        tree, tiles = self._spatial_index
475        nearest_center_distance, _ = tree.query(position)
476        # A tile's nearest point lies between 1/2 and sqrt(1/2) nearer than its center, so a tile can beat the one
477        # whose center is nearest only if its own center lies within this distance.
478        farthest_center_that_can_be_nearer = nearest_center_distance + math.sqrt(0.5) - 0.5
479        candidates = tree.query_ball_point(position, farthest_center_that_can_be_nearer, return_sorted=True)
480        return min((tiles[index].closest_point_to(position) for index in candidates), key=operator.itemgetter(1))

The point of the covered ground nearest to point, and the distance to it.

def random_point( self, *, rng: random.Random | None = None) -> Point:
482    def random_point(self, *, rng: random.Random | None = None) -> Point:
483        """A point drawn uniformly from the covered ground, by `rng` or the `random` module's own generator."""
484        if not self._addresses:
485            raise ValueError("an empty tile set has no points to draw from")
486        choice = random.choice if rng is None else rng.choice
487        return choice(self._ordered).random_point(rng=rng)

A point drawn uniformly from the covered ground, by rng or the random module's own generator.

def bounding_rectangle(self) -> Rectangle:
489    def bounding_rectangle(self) -> Rectangle:
490        """The smallest rectangle containing every covered tile."""
491        if not self._addresses:
492            raise ValueError("an empty tile set has no bounding rectangle")
493        lowest_x, lowest_y, highest_x, highest_y = self._address_bounds
494        return Rectangle(lowest_x, lowest_y, highest_x - lowest_x + 1, highest_y - lowest_y + 1)

The smallest rectangle containing every covered tile.

def tiles(self) -> TileSet:
496    def tiles(self) -> TileSet:
497        """The tile set itself."""
498        return self

The tile set itself.

def translated(self, offset: 'PointLike') -> TileSet:
547    def translated(self, offset: PointLike) -> TileSet:
548        """The tiles shifted by `offset`, snapped back onto the tile grid, as `Tile.translated` shifts each. Raises
549        `ValueError` for an offset with a height."""
550        ground_offset = checked_ground_offset(offset)
551        offset_x, offset_y = ground_offset[0], ground_offset[1]
552        return TileSet._from_addresses(
553            (math.floor(x + 0.5 + offset_x), math.floor(y + 0.5 + offset_y)) for x, y in self._addresses
554        )

The tiles shifted by offset, snapped back onto the tile grid, as Tile.translated shifts each. Raises ValueError for an offset with a height.

def filter( self, predicate: Callable[[Tile], bool]) -> TileSet:
556    def filter(self, predicate: Callable[[Tile], bool]) -> TileSet:
557        """The tiles satisfying `predicate`."""
558        return TileSet(tile for tile in self._ordered if predicate(tile))

The tiles satisfying predicate.