nereid_spatialHashGrid.js
import { Component } from "../components/component.js";
/**
* Validates finite number.
* @param {number} value
* @param {string} name
* @returns {number}
*/
function finiteNumber(value, name) {
if (typeof value !== "number" || !Number.isFinite(value)) {
throw new TypeError(`${name} must be a finite number`);
}
return value;
}
/**
* 2D Spatial Hash Grid broadphase partitioning space into uniform buckets.
* Supports efficient range queries, AABB queries, teleportation, dynamic updates,
* and robust handling of negative coordinates and oversized colliders.
*/
export class SpatialHashGrid extends Component {
/**
* @param {Object} [config]
* @param {number} [config.cellSize=64] Width and height of each spatial cell
* @param {number} [config.maxCellSpan=32] Maximum cells an oversized object can span across one dimension
*/
constructor({ cellSize = 64, maxCellSpan = 32 } = {}) {
super();
finiteNumber(cellSize, "cellSize");
if (cellSize <= 0) throw new RangeError("cellSize must be a positive number");
this.cellSize = cellSize;
this.maxCellSpan = Math.max(2, maxCellSpan);
this.cells = new Map(); // key `${cellX},${cellY}` -> Set of entries
this.entryCells = new Map(); // entry -> Set of cell keys
this.entryBounds = new Map(); // entry -> { left, right, top, bottom }
this._nextId = 1;
this._ids = new WeakMap();
}
_id(entry) {
if (!this._ids.has(entry)) {
this._ids.set(entry, this._nextId++);
}
return this._ids.get(entry);
}
/**
* Convert world coordinate to cell coordinate index.
* Uses Math.floor to correctly handle negative coordinates.
* @param {number} coord
* @returns {number}
*/
worldToCell(coord) {
return Math.floor(coord / this.cellSize);
}
/**
* Compute set of cell keys covered by an AABB.
* Handles negative cells and clamps huge colliders to maxCellSpan.
* @param {Object} bounds { left, right, top, bottom }
* @returns {Set<string>}
*/
getCellKeysForBounds(bounds) {
if (!bounds || !Number.isFinite(bounds.left) || !Number.isFinite(bounds.right) ||
!Number.isFinite(bounds.top) || !Number.isFinite(bounds.bottom)) {
throw new TypeError("Bounds must contain finite left, right, top, bottom");
}
const minCellX = this.worldToCell(Math.min(bounds.left, bounds.right));
const maxCellX = this.worldToCell(Math.max(bounds.left, bounds.right));
const minCellY = this.worldToCell(Math.min(bounds.top, bounds.bottom));
const maxCellY = this.worldToCell(Math.max(bounds.top, bounds.bottom));
const spanX = Math.min(maxCellX - minCellX, this.maxCellSpan);
const spanY = Math.min(maxCellY - minCellY, this.maxCellSpan);
const keys = new Set();
for (let cx = minCellX; cx <= minCellX + spanX; cx++) {
for (let cy = minCellY; cy <= minCellY + spanY; cy++) {
keys.add(`${cx},${cy}`);
}
}
return keys;
}
/**
* Insert an entry into the spatial grid.
* @param {Object} entry Object identifier (collider, entity, etc.)
* @param {Object} bounds { left, right, top, bottom }
*/
insert(entry, bounds) {
if (!entry) throw new TypeError("entry cannot be null or undefined");
if (this.entryCells.has(entry)) {
this.remove(entry);
}
const keys = this.getCellKeysForBounds(bounds);
this.entryCells.set(entry, keys);
this.entryBounds.set(entry, { ...bounds });
for (const key of keys) {
let bucket = this.cells.get(key);
if (!bucket) {
bucket = new Set();
this.cells.set(key, bucket);
}
bucket.add(entry);
}
}
/**
* Update an entry's position and bounding box.
* If the cell coverage did not change, avoids bucket re-insertions.
* @param {Object} entry
* @param {Object} newBounds
* @returns {boolean} Whether spatial bucket assignment changed
*/
update(entry, newBounds) {
if (!this.entryCells.has(entry)) {
this.insert(entry, newBounds);
return true;
}
const currentKeys = this.entryCells.get(entry);
const newKeys = this.getCellKeysForBounds(newBounds);
// Check if sets are equal
let changed = currentKeys.size !== newKeys.size;
if (!changed) {
for (const key of currentKeys) {
if (!newKeys.has(key)) {
changed = true;
break;
}
}
}
this.entryBounds.set(entry, { ...newBounds });
if (!changed) return false;
// Remove from old keys not in new keys
for (const key of currentKeys) {
if (!newKeys.has(key)) {
const bucket = this.cells.get(key);
if (bucket) {
bucket.delete(entry);
if (bucket.size === 0) this.cells.delete(key);
}
}
}
// Add to new keys not in old keys
for (const key of newKeys) {
if (!currentKeys.has(key)) {
let bucket = this.cells.get(key);
if (!bucket) {
bucket = new Set();
this.cells.set(key, bucket);
}
bucket.add(entry);
}
}
this.entryCells.set(entry, newKeys);
return true;
}
/**
* Teleport an entry instantly to new bounds.
* @param {Object} entry
* @param {Object} newBounds
*/
teleport(entry, newBounds) {
this.update(entry, newBounds);
}
/**
* Remove an entry from all cells.
* @param {Object} entry
* @returns {boolean} Whether entry was present and removed
*/
remove(entry) {
const keys = this.entryCells.get(entry);
if (!keys) return false;
for (const key of keys) {
const bucket = this.cells.get(key);
if (bucket) {
bucket.delete(entry);
if (bucket.size === 0) {
this.cells.delete(key);
}
}
}
this.entryCells.delete(entry);
this.entryBounds.delete(entry);
return true;
}
/**
* Query all unique entries whose bounding box overlaps the given AABB.
* @param {Object} bounds { left, right, top, bottom }
* @returns {Array<Object>}
*/
queryAABB(bounds) {
const keys = this.getCellKeysForBounds(bounds);
const candidateEntries = new Set();
for (const key of keys) {
const bucket = this.cells.get(key);
if (bucket) {
for (const entry of bucket) {
candidateEntries.add(entry);
}
}
}
const results = [];
for (const entry of candidateEntries) {
const b = this.entryBounds.get(entry);
if (!b) continue;
// Precise AABB overlap test
if (b.left < bounds.right && b.right > bounds.left &&
b.top < bounds.bottom && b.bottom > bounds.top) {
results.push(entry);
}
}
return results;
}
/**
* Query all unique entries within a circular radius of a point.
* @param {number} x Center X
* @param {number} y Center Y
* @param {number} radius Search radius
* @returns {Array<Object>}
*/
queryRadius(x, y, radius) {
finiteNumber(x, "x");
finiteNumber(y, "y");
finiteNumber(radius, "radius");
if (radius < 0) throw new RangeError("radius must be non-negative");
const aabb = {
left: x - radius,
right: x + radius,
top: y - radius,
bottom: y + radius
};
const candidates = this.queryAABB(aabb);
const radiusSq = radius * radius;
const results = [];
for (const entry of candidates) {
const b = this.entryBounds.get(entry);
if (!b) continue;
// Closest point on AABB to circle center
const closestX = Math.max(b.left, Math.min(x, b.right));
const closestY = Math.max(b.top, Math.min(y, b.bottom));
const distSq = ((x - closestX) ** 2) + ((y - closestY) ** 2);
if (distSq <= radiusSq) {
results.push(entry);
}
}
return results;
}
/**
* Generate unique potential collision pairs across all cells.
* Returns an array of [entryA, entryB] pairs with deterministic ordering.
* @returns {Array<Array>}
*/
getPotentialCollisionPairs() {
const seenPairs = new Set();
const pairs = [];
for (const bucket of this.cells.values()) {
if (bucket.size < 2) continue;
const entries = [...bucket];
for (let i = 0; i < entries.length; i++) {
const a = entries[i];
const idA = this._id(a);
for (let j = i + 1; j < entries.length; j++) {
const b = entries[j];
const idB = this._id(b);
const pairKey = idA < idB ? `${idA}:${idB}` : `${idB}:${idA}`;
if (!seenPairs.has(pairKey)) {
seenPairs.add(pairKey);
// Check precise bounding overlap
const boundsA = this.entryBounds.get(a);
const boundsB = this.entryBounds.get(b);
if (boundsA && boundsB &&
boundsA.left < boundsB.right && boundsA.right > boundsB.left &&
boundsA.top < boundsB.bottom && boundsA.bottom > boundsB.top) {
pairs.push(idA < idB ? [a, b] : [b, a]);
}
}
}
}
}
return pairs;
}
/**
* Clear all cells and entries (e.g. on scene unload).
*/
clear() {
this.cells.clear();
this.entryCells.clear();
this.entryBounds.clear();
}
/**
* Get the count of tracked entries.
* @returns {number}
*/
get size() {
return this.entryCells.size;
}
}