Starship Survivors Wiki

spatial-grid

6 min read

spatial-grid.ts

PURPOSE

Spatial hash grid that reduces broad-phase collision lookups from O(n^2) to O(n * k), where k is the average number of entities in a queried cell neighborhood. Divides the world into fixed-size square cells; entities are inserted into every cell their position+radius overlaps; queries return the union of entities in the cells intersected by the query area. Exports a SpatialGrid class plus a singleton enemyGrid used as the canonical broad-phase index for alive, tangible enemies.

OWNS

  • class SpatialGrid — the grid data structure.
    • cellSize (readonly) — world units per cell, supplied at construction.
    • invCellSize (readonly) — precomputed reciprocal of cellSize, used to replace division with multiplication in the hot path.
    • cells — Map<number, any[]> from packed cell key to the array of entities currently in that cell.
    • arrayPool — pool of reusable arrays so per-frame clear() does not allocate fresh arrays each frame.
    • cellKey(cx, cy) — packs two 16-bit signed cell coordinates into a single integer key: (cx & 0xFFFF) | ((cy & 0xFFFF) << 16).
    • getCell(cx, cy) — private; returns the cell array for (cx, cy), creating one from the pool (or []) if missing.
    • clear() — empties every cell, returns the cleared arrays to arrayPool, then clears the cells map.
    • insert(entity, x, y, radius) — adds entity to every cell whose footprint overlaps the AABB [x-r, x+r] x [y-r, y+r].
    • insertPoint(entity, x, y) — adds entity to the single cell containing (x, y) with no radius expansion; intended for entities whose radius < cellSize/4.
    • query(x, y, radius) — broad-phase: returns candidates in every cell overlapping the AABB around (x, y, radius). Uses a shared module-level result array.
    • countNear(x, y, radius) — returns the total entity count across the cells overlapping the AABB; does not allocate or expose entities.
  • Module-level _queryResults: any[] — singleton, pre-allocated result buffer reused by every query() call across every SpatialGrid instance.
  • Module-level enemyGrid = new SpatialGrid(CFG.GRID_CELL_SIZE) — exported singleton grid used by combat, weapons, bullets, artifacts, effects, and AI separation.

READS FROM

  • ./config — imports CFG and reads CFG.GRID_CELL_SIZE when constructing the enemyGrid singleton.
  • Entity inputs supplied by callers: only (x, y) coordinates and a radius scalar. The grid does not inspect any other entity field; entities can be any object shape (any).

PUSHES TO

  • Stores entity references inside its internal cells map. Returns aliases to those references via query().
  • query() returns the shared _queryResults array directly; the buffer is reused on the next query() call on any SpatialGrid instance.
  • Does not emit events, mutate entities, or write to other systems.

DOES NOT

  • Does not perform precise (narrow-phase) collision tests. Returned candidates may be outside the query radius; callers must do an exact distance check.
  • Does not deduplicate. An entity inserted via insert() into multiple cells will appear multiple times in query() results if those cells fall inside the query AABB. Callers that need uniqueness rely on their own bookkeeping (for example, the bullet.hits Set in collision-resolver).
  • Does not update positions automatically. The grid is rebuilt from scratch each frame; there is no move() or remove(entity) API.
  • Does not own or run an update loop. clear() + insert() calls are driven externally (currently by collision-resolver.ts).
  • Does not support concurrent queries. The shared _queryResults array assumes one query is consumed before the next begins.
  • Does not validate cell coordinate bounds. Coordinates outside the 16-bit signed range will alias with other cells because cellKey masks with 0xFFFF.
  • Does not handle the bulletGrid use case in code — the file’s header comment notes a future-use bulletGrid slot, but only enemyGrid is instantiated and exported.

Signals

None. The grid produces no events or telemetry. All output is via return values from query() and countNear().

Entry points

  • new SpatialGrid(cellSize) — construct a grid with a chosen cell size.
  • grid.clear() — call once per frame before re-inserting.
  • grid.insert(entity, x, y, radius) — radius-aware insertion, places entity in every overlapping cell.
  • grid.insertPoint(entity, x, y) — single-cell point insertion, no radius expansion.
  • grid.query(x, y, radius) — broad-phase lookup of candidate entities near a point.
  • grid.countNear(x, y, radius) — density count without returning entity references.
  • enemyGrid (exported singleton) — the project-wide broad-phase index for enemies; consumed by combat/collision-resolver.ts, combat/damage.ts, weapons/weapons.ts, weapons/bullets.ts, world/artifacts.ts, effects/custom-handlers.ts, and bridge.ts.

Pattern notes

  • Cell size. enemyGrid uses CFG.GRID_CELL_SIZE (currently 200 world units). The header notes the heuristic that cellSize should be at least twice the largest entity radius so most entities fall in a single cell.
  • Packed integer keys. Cell coordinates are folded into a single 32-bit integer (cx in the low 16 bits, cy in the high 16 bits) so the cell map can be keyed by a primitive number rather than a string.
  • Inverse cell size cached. invCellSize = 1 / cellSize is computed once in the constructor; insert/query/count all multiply by invCellSize instead of dividing by cellSize in their inner loops.
  • AABB cell range. Both insert() and query() compute [minCx..maxCx] x [minCy..maxCy] from Math.floor((coord +/- radius) * invCellSize) and iterate that 2D range. For an entity small relative to cellSize, this typically reduces to a single cell on insert and a 3x3 block on query.
  • Per-frame rebuild contract. Lifecycle is clear() → many insert() → many query() → clear() on the next frame. The grid has no incremental update path; callers must rebuild after entity movement.
  • Allocation discipline. Two pooling strategies avoid per-frame garbage: clear() recycles emptied cell arrays via arrayPool, and query() writes into the module-level _queryResults buffer instead of allocating a new array.
  • Shared result buffer. query() returns a reference to _queryResults, which is reused by every grid instance. Callers must consume (read or copy) the result before calling query() again; otherwise the prior result is overwritten.
  • Duplicates by design. An entity inserted into multiple cells (radius spanning more than one) will appear multiple times if the query AABB covers more than one of its cells. The header documents this and notes that callers using bullet.hits Set already handle it naturally.
  • Broad-phase only. The grid eliminates candidates by cell-membership; precise circle/circle or circle/segment tests stay in the caller (collision-resolver.ts, damage.ts, bullets.ts, etc.).
  • any-typed entities. The grid is intentionally untyped on the entity payload to avoid coupling to enemy / bullet / pickup shapes; the only requirement is that the caller supplies (x, y, radius) numbers at insert and query time.
  • Singletons live with the class. enemyGrid is constructed at module load using CFG.GRID_CELL_SIZE. The header reserves a bulletGrid slot for future use; no bulletGrid is currently instantiated.

Graph View

Backlinks