Collision detection optimized 2d datastructure for usage in games
npm install 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
> npm install hashbounds@5
``js
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
* Properties
* BoundsMM
* Properties
* Bounds
* Entry
* EntryCache
* ForEachCallback
* Parameters
* EveryCallback
* Parameters
* HashBounds
* Parameters
* getQueryID
* setupLog2
* createLevels
* initializeArea
* Parameters
* init
* clear
* prune
* update
* Parameters
* getLevel
* Parameters
* insert
* Parameters
* remove
* Parameters
* contains
* Parameters
* getHashCache
* Parameters
* toArray
* Parameters
* every
* Parameters
* forEach
* Parameters
* boundsFitsInHash
* Parameters
* mmToPS
* Parameters
* psToMM
* Parameters
* boundsOverlap
* Parameters
* boundsContains
* Parameters
* truncateBounds
* Parameters
* convertBounds
* Parameters
* HashGrid
* Parameters
* initializeArea
* Parameters
* deleteBucket
* Parameters
* setBucket
* Parameters
* getBucket
* Parameters
* createBucket
* Parameters
* prune
* pruneBucket
* Parameters
* update
* Parameters
* insert
* Parameters
* remove
* Parameters
* every
* Parameters
* TreeBucket
* Parameters
* updateQuadCache
* add
* subtract
* getQuad
* Parameters
* \_every
* Parameters
* every
* Parameters
* everyAll
* Parameters
* remove
* Parameters
* set
* Parameters
A 2d bounding box represented by a point and sizes.
Type: Object
* x number y
* number width
* number height
* number
A 2d bounding box represented by min/max points.
Type: Object
* minX number minY
* number maxX
* number maxY
* number
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
* entry Entry Entry
Callback function used in .every() calls
Type: Function
* entry Entry 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.
* minSize number The size of the smallest grid cell.levelCount
* number 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.initialBounds
* Bounds? Optionally specifies the bounds used to pre-initilize the datastructure. These bounds are not enforced.id
* number? 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
#### Parameters
* 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.
#### Parameters
* entry Entry The entry to update.bounds
* Bounds The 2d bounding box of the entry.
* 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.
#### Parameters
* bounds Bounds The 2d bounding box of the entry.entryCache
* EntryCache Cache object
Returns number The index of the level.
Inserts a entry with a specified 2d bounding box.
#### Parameters
* entry Entry The entry to insert.bounds
* Bounds The 2d bounding box of the entry.
* Throws any Will throw an error if the entry is already present.
Removes an entry.
#### Parameters
* entry Entry The entry to remove.
* Throws any Will throw an error if the entry is not present.
Returns true if the entry is present.
#### Parameters
* entry Entry
Returns Boolean
Returns the cache object from a entry
#### Parameters
* entry Entry
Returns EntryCache
Retrieves an array of unique entries that may overlap with a 2d bounding box.
#### Parameters
* bounds Bounds? 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
#### Parameters
* bounds Bounds? A 2d bounding box to search.call
* EveryCallback 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
#### Parameters
* bounds Bounds? A 2d bounding box to search.call
* ForEachCallback A callback function with the first argument indicating the entry.
Check if bounds exceeds the pre-initialized size of the datastructure
#### Parameters
* bounds Bounds
Returns boolean
Converts a min-max 2d bound to pos-size format in place
#### Parameters
* bounds Bounds
Converts a pos-size 2d bound to min-max format in place
#### Parameters
* bounds Bounds
Checks if two 2d bounding boxes are overlapping.
#### Parameters
* bounds1 Bounds bounds2
* Bounds
Returns boolean
Checks if one 2d bounding box is fully contained in another.
#### Parameters
* bounds1 Bounds Inner boxbounds2
* Bounds Outer box
Returns boolean
Truncates bounds to fit a certain area
#### Parameters
* bounds Bounds minX
* number minY
* number maxX
* number maxY
* number
* Throws any Will throw error if bounds are unformatted.
Formats/converts 2d bounding boxes.
#### Parameters
* bounds Bounds
* 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).
* bucketSize number The size of the bucketslevel
* number 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.
#### Parameters
* initialBounds Bounds Bounds to initialize area with.
Deletes a bucket from the bucket grid.
#### Parameters
* bucketX number bucketY
* number
Inserts a bucket into the bucket grid.
#### Parameters
* bucketX number bucketY
* number bucket
* TreeBucket
Gets a bucket from the bucket grid
#### Parameters
* bucketX number bucketY
* number
Returns TreeBucket
Creates, initializes, and returns a bucket at a certain position. Any parent buckets will be created.
#### Parameters
* bucketX number bucketY
* number
Returns TreeBucket
Prunes empty buckets.
Prunes an empty bucket and its empty parents.
#### Parameters
* bucket TreeBucket
Updates a entry.
#### Parameters
* entry Entry bounds
* Bounds entryCache
* EntryCache
Returns boolean Returns true if there was a change.
Inserts a entry.
#### Parameters
* entry Entry bounds
* Bounds entryCache
* EntryCache k1x
* number? k1y
* number? k2x
* number? k2y
* number?
Removes a entry.
#### Parameters
* entryCache EntryCache
Iterates entries that may overlap with bounds. Cancellable.
Similar to Array.every()
#### Parameters
* bounds (Bounds | undefined) call
* EveryCallback QID
* number
Returns boolean
TreeBucket.
The class that actually contains the data
* bucketX number bucketY
* number bucketSize
* number
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.
#### Parameters
* bounds Bounds
Returns number
Internal method that iterates through the items contained in the bucket while filtering non-unique entries.
Similar to Array.every();
#### Parameters
* call EveryCallback QID
* number
Returns boolean
Recursive method that iterates through entries that may collide with the specified bounds.
#### Parameters
* bounds Bounds call
* EveryCallback QID
* number
Returns boolean
Recursive method that iterates through all entries contained in this bucket and its children.
#### Parameters
* call EveryCallback QID
* number
Returns boolean
Removes a entry
#### Parameters
* entryCache EntryCache indexKey
* number
Sets a entry
#### Parameters
* entry Entry entryCache
* EntryCache indexKey` number
*