# @tiptap/broadphase@0.1.0 **Spec §7.1: `@tiptap/broadphase`** — which pairs are worth testing properly. One of two packages in the initial catalogue that is new code rather than extraction, and the reason it is in the catalogue at all is arithmetic: narrow phase is `O(n²)`. Forty bodies is 780 pairs and nobody notices; two hundred monsters is 19,900, and under rollback that is 19,900 pairs **per re-simulated tick**, ten times a tick on a bad link. §7.1 says this "gates the ARPG", and that is why. ## Why a dense grid and not a hash map Because a hash map iterates in an order nobody controls, and this crate's output feeds `step`. Two clients whose hash seeds differ would resolve the same two overlapping monsters in a different order, apply the same impulses in a different order, and end up in different worlds — a desync with no bad packet anywhere in it, which is the hardest kind to find. So: a dense `Vec` of cells over a bounded arena, and **every query returns ascending ids**. Determinism here is not "we were careful", it is a sort, and [`Grid::query`]'s contract says so. See [`tests::insertion_order_cannot_change_what_comes_out`]. ## Why it is bounded and refuses rather than grows §11.5: the bodies come from a config a stranger wrote and the arena bounds do too. A grid that sized itself from `bounds / cell_size` would let a config with a large arena and a small cell allocate gigabytes on a phone, from one validated-looking pair of numbers. [`Grid::new`] refuses past [`MAX_CELLS`], and the refusal carries the numbers so `validate_config` can say which one was wrong. ## What it deliberately does not do It does not test anything. A broadphase that returned "these two overlap" is a narrow phase with an index attached, and it would need to know about circles, capsules, convex hulls and whatever comes next. This returns *candidates* and `collide2d` decides. ## Types ```rust pub struct Grid ``` A uniform grid over a fixed region. Rebuilt every tick: [`clear`](Grid::clear), then [`insert`](Grid::insert) per body, then query. Rebuilding rather than incrementally updating is not laziness — under rollback the world jumps backwards several ticks at a time, and an incremental structure would have to be rewound too, which is a second copy of the hardest part of §17 for no measured gain at these body counts. ## Enums ```rust pub enum GridError ``` Why a grid could not be built. ## Constants ```rust pub const MAX_CELLS: usize = 1 << 16 ``` The most cells a grid may allocate. 65,536 — a 256×256 grid, or 4 KB of `u32` offsets plus the entry list. Past this the config is wrong rather than ambitious: an arena needing more cells than this at a sensible cell size is larger than any room §4.2 admits. ```rust pub const MAX_BODIES: usize = u16::MAX as usize ``` The most bodies one grid may hold. `u16` ids, minus one so [`NONE`] is available. Well past `MAX_SIM_BODY`, and the point is that the id type is small: the entry list is the hot allocation and a body in nine cells is nine entries. ## Functions ```rust pub fn Grid::new(bounds: Aabb, cell_size: Fixed) -> Result ``` Build a grid covering `bounds` with square cells of `cell_size`. A good `cell_size` is about the diameter of the largest common body. Too small and a body spans many cells (insertion cost); too large and every query returns the whole arena (the `O(n²)` this exists to avoid). ```rust pub fn clear(&mut self) ``` Empty it, keeping every allocation. ```rust pub fn insert(&mut self, body: u16, bounds: Aabb) ``` Add a body, under every cell its bounds touch. Ignored if `body` is past [`MAX_BODIES`] — a silently-dropped body is a missed collision, so callers with untrusted counts should bound them first; this is the last line rather than the check. ```rust pub fn query(&mut self, bounds: Aabb, mut sink: impl FnMut(u16)) ``` Every body whose cells overlap `bounds`, **ascending, without repeats**. Ascending is the contract, not a coincidence of the implementation. A caller that resolves overlaps in the order it is handed them — which is every caller — would otherwise get an order that depends on cell layout and insertion sequence, and two clients that inserted in different orders would resolve the same pair differently and desync. Candidates, not hits: cells are coarser than bodies, so a returned body may not overlap at all. `collide2d` decides. ```rust pub fn pairs(&mut self, bodies: &[(u16, Aabb)], mut sink: impl FnMut(u16, u16)) ``` Every candidate pair, each once, as `(low, high)` with `low < high`. The all-versus-all case — the ARPG's monsters against each other. Emitted per body rather than per cell, because a pair sharing four cells must be offered once and a cell-major walk would offer it four times.