Overview

A minimal, zero-dependency TypeScript library implementing a high-performance 2D spatial partitioning structure: HashGrid. Developed for strict data-oriented design (DoD), zero runtime memory allocations, and high cache locality via contiguous TypedArray memory blocks.

Requirements: Node.js >= 22.19.0 Installation: npm install @zeitfall/spatial

Mathematical & Algorithmic Properties

| Operation / Metric | HashGrid | | --- | --- | | Insertion | O(1) | | Removal | O(1) | | Update (Position) | O(1) | | Query (Rect / Circle) | O(k) | | Space Complexity | O(n + m) |

Note 1: k represents the number of elements within the overlapping spatial cells. The average case approaches O(1) for evenly distributed datasets.

Note 2: n represents the maxEntityCount and m represents the tableSize (bucket count) pre-allocated in memory.

API Reference

HashGrid

The primary structural class representing a flattened spatial grid mapped to linear memory.

• Constructor constructor(tableSize: number, cellSize: number, maxEntityCount: number) Initializes a pre-allocated spatial grid. tableSize must be a strict power of two.
• insert(entityX: number, entityY: number, entityIndex: number): this Maps an entity to a spatial cell. Throws an error if the entity is already present in the grid or if the index exceeds bounds.
• remove(entityIndex: number): void Detaches an entity from the grid's internal linked-list structures.
• update(entityIndex: number, newEntityX: number, newEntityY: number): void Updates an entity's coordinates. Bypasses structural re-insertion if the entity's movement keeps it within the boundaries of its current spatial cell.
• queryRect(left: number, right: number, top: number, bottom: number, candidateBucket: Uint32Array): number Populates the provided buffer with entity indices that strictly reside within the defined Axis-Aligned Bounding Box (AABB). Spatial boundaries are automatically normalized. Returns the total number of populated candidates.
• queryCircle(x: number, y: number, radius: number, candidateBucket: Uint32Array): number Populates the provided buffer with entity indices that strictly reside within the specified circle. Returns the total number of populated candidates.
• clear(): void Executes a fast O(m) wipe of the grid.

Operational Context (Behavioral Notes)

• Zero-Allocation Runtime: Post-instantiation, all structural operations (insert, update, remove, queryRect, queryCircle) execute without utilizing the new keyword or generating implicit objects/arrays. This guarantees zero GC (Garbage Collector) pauses during critical execution loops.
• Struct-of-Arrays (SoA) & Data Locality: Entity coordinates and linked-list traversal pointers are stored in flat, unboxed typed arrays (Int32Array, Float32Array). This design maximizes CPU L1/L2 cache efficiency during sequential spatial queries.
• Early Exit & Overflow Protection: Query methods evaluate the capacity of the candidateBucket (Uint32Array) directly inside the traversal loop. Iteration immediately halts if the buffer reaches maximum capacity, eliminating redundant cycles.
• Hash Collision Safety: The class utilizes an internal query state array (#entityQuery) to guarantee that entities residing in different cells with identical hashes (collisions) are never evaluated or yielded multiple times within a single query execution.
• Fast Bitwise Hashing: Spatial coordinates are hashed using integer multiplication (Math.imul) and bitwise masking. The tableSize is strictly validated as a power of two during instantiation to support the hash & hashMask bitwise operation, bypassing slower modulo arithmetic.

Usage Example

import { HashGrid } from '@zeitfall/spatial';

// Initialize a grid with 1024 cells (must be power of two), 
// 50px cell size, and a strict limit of 10,000 entities.
const grid = new HashGrid(1024, 50, 10000);

// Pre-allocate a buffer for query results to ensure zero-allocation runtime.
const resultBuffer = new Uint32Array(64);

// Insert entities (x, y, entityIndex)
grid.insert(120.5, 300.0, 0);
grid.insert(135.0, 310.5, 1);
grid.insert(900.0, 800.0, 2);

// Update entity 0's position during a game loop
grid.update(0, 122.0, 305.0);

// --- Radius Query (e.g., Explosion / Aggro Range) ---
const radiusFound = grid.queryCircle(125.0, 305.0, 25.0, resultBuffer);

for (let i = 0; i < radiusFound; i++) {
    const entityId = resultBuffer[i];
    console.log(`Entity ${entityId} is within the radius.`);
}

// --- Rect/AABB Query (e.g., RTS Mouse Selection / Frustum Culling) ---
const rectFound = grid.queryRect(100.0, 200.0, 250.0, 350.0, resultBuffer);

for (let i = 0; i < rectFound; i++) {
    const entityId = resultBuffer[i];
    console.log(`Entity ${entityId} is inside the rectangle.`);
}

// Optional: Fast structural wipe between independent simulation phases
grid.clear();