Collision detection optimized 2d datastructure for usage in games. Particularily useful when:
- Objects have varying sizes
- Objects are continually moving
- Map size is not determinable/fixed at start
npm install hashbounds@5
const HashBounds = require("hashbounds");
// Initialize hashbounds with min grid size of 16 and 3 levels and pre-initialize buckets in 1000x1000 map.
let myData = new HashBounds(16, 3, {
x: 0,
y: 0,
width: 1000,
height: 1000
});
// You don't have to pre-initialize buckets
myData = new HashBounds(16, 3);
// An entry is some sort of object
const entry = {
foo: "bar"
}
// Insert an entry
myData.insert(entry, {
x: 0,
y: 0,
width: 10,
height: 10
});
// Get array at bounds
myData.toArray({ x: 0, y: 0, width: 5, height: 5 }).length // 1
// Iterate at bounds
myData.forEach({ x: 0, y: 0, width: 5, height: 5 }, (item)=>{
});
// Iterate at bounds cancellable
myData.every({ x: 0, y: 0, width: 5, height: 5 }, (item)=>{
return true; // True to continue iteration
});
// Update the entry's bounds
myData.update(entry, {
x: 10,
y: 10,
width: 3,
height: 4
});
// You can also use min/max format for all bounds.
myData.update(entry, {
minX: 10,
minY: 10,
maxX: 13,
maxY: 14
});
// Remove entry
myData.remove(entry);- BoundsPS
- BoundsMM
- Bounds
- Entry
- EntryCache
- ForEachCallback
- EveryCallback
- HashBounds
- HashGrid
- TreeBucket
A 2d bounding box represented by a point and sizes.
Type: Object
A 2d bounding box represented by min/max points.
Type: Object
An object representing a 2d bounding box.
Represents an entry
Type: Object
Represents an entry's cache object
Type: Object
Callback function used in .forEach() calls
Type: Function
entryEntry Entry
Callback function used in .every() calls
Type: Function
entryEntry Entry
Returns boolean Return true to continue iteration, false to cancel.
HashBounds
Stores/Organizes arbitrary objects with 2d bounding box data in the form of a spatial grid tree that is quick to query. It is particularily efficient when objects have varying sizes. Constant time insertion and removal, and n log n search.
minSizenumber The size of the smallest grid cell.levelCountnumber Specifies the number of levels/depth. Each additional level has a grid size twice as large then the previous in one axis, 4x size in area.initialBoundsBounds? Optionally specifies the bounds used to pre-initilize the datastructure. These bounds are not enforced.idnumber? Optionally specify a unique ID of the hash.
Returns an incremented number used to filter non-unique entries during search queries.
Returns number
Initializes a dictionary of ceiled log2 values that are frequently used by the data structure
Initializes the basic hierarchical structure of levels.
Pre-initializes an area according to some bounds
initialBounds
Initializes the data structure and pre-initializes area if applicable
Clear the data structure and reinitialize it.
Removes empty buckets.
Updates the entry when its bounds have changed.
- Throws any Will throw an error if the entry is not present.
Returns boolean A boolean value that is true to indicate something has changed
Gets the level index the entry should belong to with the appropriate bounding box.
boundsBounds The 2d bounding box of the entry.entryCacheEntryCache Cache object
Returns number The index of the level.
Inserts a entry with a specified 2d bounding box.
- Throws any Will throw an error if the entry is already present.
Removes an entry.
entryEntry The entry to remove.
- Throws any Will throw an error if the entry is not present.
Returns true if the entry is present.
entryEntry
Returns Boolean
Returns the cache object from a entry
entryEntry
Returns EntryCache
Retrieves an array of unique entries that may overlap with a 2d bounding box.
boundsBounds? A 2d bounding box to search.
Returns Array An array of entries.
Iterates through unique entries that may overlap with a 2d bounding box. Iteration may be stopped.
Similar to Array.every
boundsBounds? A 2d bounding box to search.callEveryCallback A callback function with the first argument indicating the entry. Return true to continue iteration, return false to stop.
Returns boolean Returns false if cancelled.
Iterates through unique entries that may overlap with a 2d bounding box. Iteration cannot be stopped.
Similar to Array.forEach
boundsBounds? A 2d bounding box to search.callForEachCallback A callback function with the first argument indicating the entry.
Check if bounds exceeds the pre-initialized size of the datastructure
boundsBounds
Returns boolean
Converts a min-max 2d bound to pos-size format in place
boundsBounds
Converts a pos-size 2d bound to min-max format in place
boundsBounds
Checks if two 2d bounding boxes are overlapping.
Returns boolean
Checks if one 2d bounding box is fully contained in another.
Returns boolean
Truncates bounds to fit a certain area
- Throws any Will throw error if bounds are unformatted.
Formats/converts 2d bounding boxes.
boundsBounds
- Throws any Error if invalid
HashGrid.
A doubly linked 2d spatial hash/grid which stores TreeBuckets. Multiple grids are typically used by HashBounds. Allows for constant time insertion and deletion by using Math.floor(X / gridSize).
bucketSizenumber The size of the bucketslevelnumber The level/index of the grid. Higher levels have double the bucketSize than the preceding.
Pre-initializes buckets in a 2d bounding box. While these bounds are not strictly enforced for entries, pre-initialization will increase performance.
initialBoundsBounds Bounds to initialize area with.
Deletes a bucket from the bucket grid.
Inserts a bucket into the bucket grid.
bucketXnumberbucketYnumberbucketTreeBucket
Gets a bucket from the bucket grid
Returns TreeBucket
Creates, initializes, and returns a bucket at a certain position. Any parent buckets will be created.
Returns TreeBucket
Prunes empty buckets.
Prunes an empty bucket and its empty parents.
bucketTreeBucket
Updates a entry.
entryEntryboundsBoundsentryCacheEntryCache
Returns boolean Returns true if there was a change.
Inserts a entry.
Removes a entry.
entryCacheEntryCache
Iterates entries that may overlap with bounds. Cancellable.
Similar to Array.every()
bounds(Bounds | undefined)callEveryCallbackQIDnumber
Returns boolean
TreeBucket.
The class that actually contains the data
Update QuadCache with appropriate child buckets.
Increments a counter and propagates it upwards.
Decrements a counter and propagates it upwards.
Returns the quads that collide with the bounding box. Returns -1 if bounds is completely enclosing bucket.
boundsBounds
Returns number
Internal method that iterates through the items contained in the bucket while filtering non-unique entries.
Similar to Array.every();
callEveryCallbackQIDnumber
Returns boolean
Recursive method that iterates through entries that may collide with the specified bounds.
boundsBoundscallEveryCallbackQIDnumber
Returns boolean
Recursive method that iterates through all entries contained in this bucket and its children.
callEveryCallbackQIDnumber
Returns boolean
Removes a entry
entryCacheEntryCacheindexKeynumber
Sets a entry
entryEntryentryCacheEntryCacheindexKeynumber