# @tiptap/grid@0.1.0 **Spec §7.1: `@tiptap/grid`** — tile maps, and the things you can only do once terrain is data. §7.1 calls this "the highest-value new work in the list", for two reasons that are worth keeping separate. **A\* is what gives an ARPG monsters.** Not pathfinding in the abstract — a monster that walks into a wall and stays there is the difference between a genre and a tech demo, and no amount of collision solves it. **A mutable tile bitmask is what makes destructible terrain possible at all.** §7.2's argument: under the old design geometry lived in immutable config and the platform owned collision, so Worms was impossible — not hard, impossible. Here the terrain is a bitmask in creator state, mutable by definition, and collision is a function the creator calls against it. [`TileMap::carve`] is a two-line method and it is the whole unlock. ## Determinism is the entire difficulty Every routine here is a search, and a search has ties. Two paths of equal length, two frontier nodes with equal cost, two neighbours at equal distance — and if the tie is broken by anything that varies between machines, two clients send their monsters down different corridors and the room desyncs with no bad packet in it. So: | Routine | Where the tie is | How it is broken | |---|---|---| | [`TileMap::path`] | equal `f` in the open set | by tile index, ascending — a total order, so the heap has no freedom | | [`TileMap::flood`] | which neighbour to visit first | fixed [`ORTHOGONAL`] order, FIFO queue | | [`TileMap::line_of_sight`] | which side of an exact diagonal | the `x` step first — and the walk always runs from the lexicographically smaller endpoint, so `los(a,b) == los(b,a)` by construction | No hash maps, no floats, no iteration over anything unordered. The costs are integers (`10` orthogonal, `14` diagonal — `√2` to two places) because a fixed-point heuristic that rounded differently at the seventh bit would break admissibility on one platform and not the other. ## Bounded, because a creator will ask for the impossible A monster told to path to an unreachable tile explores every reachable tile before admitting defeat. On a 256×256 map that is 65,536 expansions, on a phone, inside a rollback that may run it ten times in one frame. [`MAX_STEPS`] caps it and [`Path::Exhausted`] says so, because §11.5's rule is bounded time and "the creator should not have done that" is not a bound. ## Types ```rust pub struct TileMap ``` A rectangular tile map with a solid/open bit per tile. ## Enums ```rust pub enum MapError ``` Why a map could not be built. ```rust pub enum Path ``` How a path search ended. ## Constants ```rust pub const MAX_TILES: usize = 1 << 16 ``` The most tiles a map may have — 256×256. The bitmask is one bit per tile, so this is 8 KB of terrain. The limit is not the memory, it is [`MAX_STEPS`]: a search over more tiles than this cannot finish inside a tick budget that also has to run the rest of the game. ```rust pub const MAX_STEPS: usize = 4096 ``` The most nodes one [`TileMap::path`] call will expand. Four thousand. Generous for a monster with line of sight to a player, and far short of exploring a full map — which is exactly the intent: a reachable goal is found, an unreachable one is given up on quickly rather than correctly. ```rust pub const MAX_PATH: usize = 512 ``` The most tiles a returned path may contain. ```rust pub const COST_ORTHO: u32 = 10 ``` Cost of an orthogonal step. Integers, so two platforms cannot round it apart. ```rust pub const COST_DIAG: u32 = 14 ``` Cost of a diagonal step — `√2 × 10`, to two places. ```rust pub const ORTHOGONAL: [(i32, i32); 4] = [(0, -1), (-1, 0), (1, 0), (0, 1)] ``` Neighbour offsets, in the order every routine here visits them. The order is part of the contract, not an implementation detail: it is what breaks the tie when two neighbours are equally good, and changing it changes which corridor a monster picks. ```rust pub const DIAGONAL: [(i32, i32); 4] = [(-1, -1), (1, -1), (-1, 1), (1, 1)] ``` The four diagonals, visited after [`ORTHOGONAL`]. ## Functions ```rust pub fn TileMap::new(w: usize, h: usize, tile: Fixed, origin: Vec2) -> Result ``` An empty map: every tile open. ```rust pub fn is_solid(&self, x: i32, y: i32) -> bool ``` Solid, or **out of bounds**. Outside-is-solid is the useful default and the safe one: every caller here is asking "can I move here", and a map whose edge was open would let a monster walk out of the world and a raycast run to the horizon. ```rust pub fn carve(&mut self, centre: Vec2, radius: Fixed) -> usize ``` Blast a circle open — §7.2's destructible terrain, in one call. Returns how many tiles changed, so a caller can skip the work of rebuilding anything derived when nothing moved. ```rust pub fn fill(&mut self, centre: Vec2, radius: Fixed) -> usize ``` The inverse — build terrain up. ```rust pub fn tile_at(&self, p: Vec2) -> (i32, i32) ``` Which tile a world point is in. Not clamped — may be outside the map. ```rust pub fn tile_centre(&self, x: i32, y: i32) -> Vec2 ``` The world position of a tile's centre — where a monster walking the path should aim. ```rust pub fn tile_bounds(&self, x: i32, y: i32) -> Aabb ``` The world-space box of one tile — hand straight to `collide2d`. ```rust pub fn overlaps_solid(&self, box_: Aabb) -> bool ``` Does this box touch solid terrain? The cheap query a character controller wants every tick, before doing anything more expensive. ```rust pub fn solid_near(&self, box_: Aabb, mut sink: impl FnMut(i32, i32, Aabb)) ``` Every solid tile touching `box_`, as world boxes, ascending by index. Ascending for the same reason `broadphase` sorts: the caller resolves these in the order given, and an order that depended on the traversal would make depenetration depend on it too. ```rust pub fn line_of_sight(&self, a: (i32, i32), b: (i32, i32)) -> bool ``` Can these two tiles see each other? **A solid endpoint is never visible**, and only tiles *strictly between* block. Both halves of that were decided by the tests rather than chosen up front, and the first draft had neither: it allowed a shot to land on the wall it was aimed at, which sounds reasonable until you notice it also let a monster see a player standing inside a rock. A supercover walk — every tile the segment touches, not the thin Bresenham line — because a monster that shoots through the join where two walls meet is a bug players find in about a minute. # Symmetry is structural, not emergent Walking from `a` steps `x` first where walking from `b` would step `y` first, so a line passing exactly through a lattice corner is blocked one way and open the other — and an asymmetric line of sight means one monster shoots a player who cannot see it back. So the walk is always run from the **lexicographically smaller endpoint**, which costs a comparison and makes `los(a, b) == los(b, a)` true by construction rather than by testing. ```rust pub fn flood(&self, start: (i32, i32), limit: usize, mut sink: impl FnMut(i32, i32)) -> usize ``` Every open tile reachable from `start`, in breadth-first order. Deterministic: a FIFO queue and [`ORTHOGONAL`]'s fixed neighbour order, so two clients enumerate a cavern identically. Four-way rather than eight, because a flood fill that leaks diagonally through a corner joins two rooms a player can see are separate. ```rust pub fn path( ``` A\* from `start` to `goal`, written into `out` as tiles, start first. Eight-way, with corner-cutting refused: a diagonal is only allowed when **both** adjacent orthogonals are open. Without that a monster slips through the join between two wall tiles, which looks like the collision is broken rather than the pathing. Deterministic in the way that matters: the open set is ordered by `(f, tile index)`, a total order, so two nodes of equal cost can only ever come out one way round.