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]
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.
34 @property 35 @abstractmethod 36 def area(self) -> float: 37 """The ground covered, in square game units."""
The ground covered, in square game units.
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.
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.
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.
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.
Each tile's cheapest path's length, inf where no path reaches; read-only. On a grid of bools, the costs.
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)
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
At once: the circle holds its whole value out to its edge, and none beyond, so it takes no width.
Evenly, by t: a constant slope across the band, which turns at once where the band begins and ends.
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.
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.
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)
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.
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.
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.
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.
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.
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.
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.
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.
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)
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.
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.
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.
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.
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.
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.
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.
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.
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.
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
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)
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.
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.
93 @property 94 def width(self) -> int: 95 """The number of tiles across.""" 96 return self._data.shape[0]
The number of tiles across.
98 @property 99 def height(self) -> int: 100 """The number of tiles up.""" 101 return self._data.shape[1]
The number of tiles up.
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.
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.
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
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)
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.
145 @property 146 def readonly(self) -> bool: 147 """Whether the grid refuses writes.""" 148 return self._readonly
Whether the grid refuses writes.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Tiles kept free beside a footprint: as many on every side, or so many on its left, right, bottom and top.
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.
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.
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.
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.
203 @property 204 def right(self) -> float: 205 """The upper x edge.""" 206 return self.x + self.width
The upper x edge.
208 @property 209 def top(self) -> float: 210 """The upper y edge.""" 211 return self.y + self.height
The upper y edge.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
331 def bounding_rectangle(self) -> Rectangle: 332 """The rectangle itself.""" 333 self._raise_if_empty("bounding rectangle") 334 return self
The rectangle itself.
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.
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.
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.
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.
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.
147 def clear(self) -> None: 148 """Remove every circle, keeping the spacing.""" 149 self._sources.clear()
Remove every circle, keeping the spacing.
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.
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.
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.
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))
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.
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.
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.
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.
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.
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.
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.
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.
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))
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.