hashbounds

    5.0.3 • Public • Published

    NPM Demo

    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

    src/HashBounds.js:72-72

    A 2d bounding box represented by a point and sizes.

    Type: Object

    Properties

    BoundsMM

    src/HashBounds.js:72-72

    A 2d bounding box represented by min/max points.

    Type: Object

    Properties

    Bounds

    src/HashBounds.js:72-72

    An object representing a 2d bounding box.

    Type: (BoundsPS | BoundsMM)

    Entry

    src/HashBounds.js:72-72

    Represents an entry

    Type: Object

    EntryCache

    src/HashBounds.js:72-72

    Represents an entry's cache object

    Type: Object

    ForEachCallback

    src/HashBounds.js:72-72

    Callback function used in .forEach() calls

    Type: Function

    Parameters

    EveryCallback

    src/HashBounds.js:72-72

    Callback function used in .every() calls

    Type: Function

    Parameters

    Returns boolean Return true to continue iteration, false to cancel.

    HashBounds

    src/HashBounds.js:80-361

    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

    • 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.

    getQueryID

    src/HashBounds.js:113-119

    Returns an incremented number used to filter non-unique entries during search queries.

    Returns number

    setupLog2

    src/HashBounds.js:124-131

    Initializes a dictionary of ceiled log2 values that are frequently used by the data structure

    createLevels

    src/HashBounds.js:136-150

    Initializes the basic hierarchical structure of levels.

    initializeArea

    src/HashBounds.js:155-157

    Pre-initializes an area according to some bounds

    Parameters

    • initialBounds

    init

    src/HashBounds.js:162-165

    Initializes the data structure and pre-initializes area if applicable

    clear

    src/HashBounds.js:170-174

    Clear the data structure and reinitialize it.

    prune

    src/HashBounds.js:179-181

    Removes empty buckets.

    update

    src/HashBounds.js:191-207

    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

    getLevel

    src/HashBounds.js:216-229

    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.

    insert

    src/HashBounds.js:238-264

    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.

    remove

    src/HashBounds.js:272-277

    Removes an entry.

    Parameters

    • entry Entry The entry to remove.
    • Throws any Will throw an error if the entry is not present.

    contains

    src/HashBounds.js:284-286

    Returns true if the entry is present.

    Parameters

    Returns Boolean

    getHashCache

    src/HashBounds.js:293-295

    Returns the cache object from a entry

    Parameters

    Returns EntryCache

    toArray

    src/HashBounds.js:302-312

    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.

    every

    src/HashBounds.js:323-330

    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.

    forEach

    src/HashBounds.js:340-350

    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.

    boundsFitsInHash

    src/HashBounds.js:357-360

    Check if bounds exceeds the pre-initialized size of the datastructure

    Parameters

    Returns boolean

    mmToPS

    src/HashBounds.js:368-373

    Converts a min-max 2d bound to pos-size format in place

    Parameters

    psToMM

    src/HashBounds.js:379-385

    Converts a pos-size 2d bound to min-max format in place

    Parameters

    boundsOverlap

    src/HashBounds.js:393-395

    Checks if two 2d bounding boxes are overlapping.

    Parameters

    Returns boolean

    boundsContains

    src/HashBounds.js:403-405

    Checks if one 2d bounding box is fully contained in another.

    Parameters

    Returns boolean

    truncateBounds

    src/HashBounds.js:416-435

    Truncates bounds to fit a certain area

    Parameters

    • Throws any Will throw error if bounds are unformatted.

    convertBounds

    src/HashBounds.js:442-458

    Formats/converts 2d bounding boxes.

    Parameters

    • Throws any Error if invalid

    HashGrid

    src/HashGrid.js:34-302

    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

    • bucketSize number The size of the buckets
    • level number The level/index of the grid. Higher levels have double the bucketSize than the preceding.

    initializeArea

    src/HashGrid.js:53-64

    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.

    deleteBucket

    src/HashGrid.js:71-77

    Deletes a bucket from the bucket grid.

    Parameters

    setBucket

    src/HashGrid.js:85-92

    Inserts a bucket into the bucket grid.

    Parameters

    getBucket

    src/HashGrid.js:100-103

    Gets a bucket from the bucket grid

    Parameters

    Returns TreeBucket

    createBucket

    src/HashGrid.js:111-135

    Creates, initializes, and returns a bucket at a certain position. Any parent buckets will be created.

    Parameters

    Returns TreeBucket

    prune

    src/HashGrid.js:140-150

    Prunes empty buckets.

    pruneBucket

    src/HashGrid.js:156-169

    Prunes an empty bucket and its empty parents.

    Parameters

    update

    src/HashGrid.js:178-196

    Updates a entry.

    Parameters

    Returns boolean Returns true if there was a change.

    insert

    src/HashGrid.js:208-239

    Inserts a entry.

    Parameters

    remove

    src/HashGrid.js:245-257

    Removes a entry.

    Parameters

    every

    src/HashGrid.js:268-301

    Iterates entries that may overlap with bounds. Cancellable.

    Similar to Array.every()

    Parameters

    Returns boolean

    TreeBucket

    src/TreeBucket.js:31-221

    TreeBucket.

    The class that actually contains the data

    Parameters

    updateQuadCache

    src/TreeBucket.js:64-76

    Update QuadCache with appropriate child buckets.

    add

    src/TreeBucket.js:81-84

    Increments a counter and propagates it upwards.

    subtract

    src/TreeBucket.js:89-92

    Decrements a counter and propagates it upwards.

    getQuad

    src/TreeBucket.js:99-135

    Returns the quads that collide with the bounding box. Returns -1 if bounds is completely enclosing bucket.

    Parameters

    Returns number

    _every

    src/TreeBucket.js:145-153

    Internal method that iterates through the items contained in the bucket while filtering non-unique entries.

    Similar to Array.every();

    Parameters

    Returns boolean

    every

    src/TreeBucket.js:162-173

    Recursive method that iterates through entries that may collide with the specified bounds.

    Parameters

    Returns boolean

    everyAll

    src/TreeBucket.js:181-189

    Recursive method that iterates through all entries contained in this bucket and its children.

    Parameters

    Returns boolean

    remove

    src/TreeBucket.js:196-207

    Removes a entry

    Parameters

    set

    src/TreeBucket.js:215-220

    Sets a entry

    Parameters

    Install

    npm i hashbounds

    DownloadsWeekly Downloads

    9

    Version

    5.0.3

    License

    MIT

    Unpacked Size

    61.1 kB

    Total Files

    7

    Last publish

    Collaborators

    • andrews54757