HashBounds
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
Usage
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);API
Table of Contents
- BoundsPS
- BoundsMM
- Bounds
- Entry
- EntryCache
- ForEachCallback
- EveryCallback
- HashBounds
- HashGrid
- TreeBucket
BoundsPS
A 2d bounding box represented by a point and sizes.
Type: Object
Properties
BoundsMM
A 2d bounding box represented by min/max points.
Type: Object
Properties
Bounds
An object representing a 2d bounding box.
Entry
Represents an entry
Type: Object
EntryCache
Represents an entry's cache object
Type: Object
ForEachCallback
Callback function used in .forEach() calls
Type: Function
Parameters
-
entryEntry Entry
EveryCallback
Callback function used in .every() calls
Type: Function
Parameters
-
entryEntry Entry
Returns boolean Return true to continue iteration, false to cancel.
HashBounds
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.
Parameters
-
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.
getQueryID
Returns an incremented number used to filter non-unique entries during search queries.
Returns number
setupLog2
Initializes a dictionary of ceiled log2 values that are frequently used by the data structure
createLevels
Initializes the basic hierarchical structure of levels.
initializeArea
Pre-initializes an area according to some bounds
Parameters
initialBounds
init
Initializes the data structure and pre-initializes area if applicable
clear
Clear the data structure and reinitialize it.
prune
Removes empty buckets.
update
Updates the entry when its bounds have changed.
Parameters
- 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
getLevel
Gets the level index the entry should belong to with the appropriate bounding box.
Parameters
-
boundsBounds The 2d bounding box of the entry. -
entryCacheEntryCache Cache object
Returns number The index of the level.
insert
Inserts a entry with a specified 2d bounding box.
Parameters
- Throws any Will throw an error if the entry is already present.
remove
Removes an entry.
Parameters
-
entryEntry The entry to remove.
- Throws any Will throw an error if the entry is not present.
contains
Returns true if the entry is present.
Parameters
-
entryEntry
Returns Boolean
getHashCache
Returns the cache object from a entry
Parameters
-
entryEntry
Returns EntryCache
toArray
Retrieves an array of unique entries that may overlap with a 2d bounding box.
Parameters
-
boundsBounds? A 2d bounding box to search.
Returns Array An array of entries.
every
Iterates through unique entries that may overlap with a 2d bounding box. Iteration may be stopped.
Similar to Array.every
Parameters
-
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.
forEach
Iterates through unique entries that may overlap with a 2d bounding box. Iteration cannot be stopped.
Similar to Array.forEach
Parameters
-
boundsBounds? A 2d bounding box to search. -
callForEachCallback A callback function with the first argument indicating the entry.
boundsFitsInHash
Check if bounds exceeds the pre-initialized size of the datastructure
Parameters
-
boundsBounds
Returns boolean
mmToPS
Converts a min-max 2d bound to pos-size format in place
Parameters
-
boundsBounds
psToMM
Converts a pos-size 2d bound to min-max format in place
Parameters
-
boundsBounds
boundsOverlap
Checks if two 2d bounding boxes are overlapping.
Parameters
Returns boolean
boundsContains
Checks if one 2d bounding box is fully contained in another.
Parameters
Returns boolean
truncateBounds
Truncates bounds to fit a certain area
Parameters
- Throws any Will throw error if bounds are unformatted.
convertBounds
Formats/converts 2d bounding boxes.
Parameters
-
boundsBounds
- Throws any Error if invalid
HashGrid
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).
Parameters
-
bucketSizenumber The size of the buckets -
levelnumber The level/index of the grid. Higher levels have double the bucketSize than the preceding.
initializeArea
Pre-initializes buckets in a 2d bounding box. While these bounds are not strictly enforced for entries, pre-initialization will increase performance.
Parameters
-
initialBoundsBounds Bounds to initialize area with.
deleteBucket
Deletes a bucket from the bucket grid.
Parameters
setBucket
Inserts a bucket into the bucket grid.
Parameters
-
bucketXnumber -
bucketYnumber -
bucketTreeBucket
getBucket
Gets a bucket from the bucket grid
Parameters
Returns TreeBucket
createBucket
Creates, initializes, and returns a bucket at a certain position. Any parent buckets will be created.
Parameters
Returns TreeBucket
prune
Prunes empty buckets.
pruneBucket
Prunes an empty bucket and its empty parents.
Parameters
-
bucketTreeBucket
update
Updates a entry.
Parameters
-
entryEntry -
boundsBounds -
entryCacheEntryCache
Returns boolean Returns true if there was a change.
insert
Inserts a entry.
Parameters
remove
Removes a entry.
Parameters
-
entryCacheEntryCache
every
Iterates entries that may overlap with bounds. Cancellable.
Similar to Array.every()
Parameters
-
bounds(Bounds | undefined) -
callEveryCallback -
QIDnumber
Returns boolean
TreeBucket
TreeBucket.
The class that actually contains the data
Parameters
updateQuadCache
Update QuadCache with appropriate child buckets.
add
Increments a counter and propagates it upwards.
subtract
Decrements a counter and propagates it upwards.
getQuad
Returns the quads that collide with the bounding box. Returns -1 if bounds is completely enclosing bucket.
Parameters
-
boundsBounds
Returns number
_every
Internal method that iterates through the items contained in the bucket while filtering non-unique entries.
Similar to Array.every();
Parameters
-
callEveryCallback -
QIDnumber
Returns boolean
every
Recursive method that iterates through entries that may collide with the specified bounds.
Parameters
-
boundsBounds -
callEveryCallback -
QIDnumber
Returns boolean
everyAll
Recursive method that iterates through all entries contained in this bucket and its children.
Parameters
-
callEveryCallback -
QIDnumber
Returns boolean
remove
Removes a entry
Parameters
-
entryCacheEntryCache -
indexKeynumber
set
Sets a entry
Parameters
-
entryEntry -
entryCacheEntryCache -
indexKeynumber