SpatialHash
A node.js implementation of a 2D spatial hash.
Documentation
Item requirements
Example of an item:
var item = range: x: 0 y: 0 w: 100 h: 150 __b: undefined;
- Item must contain a
.range
object. The.range
object also must havex
,y
,w
andh
variables/properties. - Item must not have a
.__b
item defined. - Functionality is not guaranteed if requirements are not met.
Constructor
const SpatialHash = ;var hash = rangeObj bucketSize;
rangeObj
An object containing x
, y
, w
and h
variables/properties. The same functionality as item.range
object.
x: /* X center */ y: /* Y center */ w: /* Half-width */ h: /* Half-height */
bucketSize
A number that represents the size of a bucket.
bucketSize
is used to create the spatial hashes. The hashes are in a dimension of a square and have a half-width of bucketSize
.
Variables
.bucketSize
The second argument passed in the constructor. Changing it will create problems unless proceeded with a .init()
call.
.itemCount
The amount of items currently in the map.
The maximum item count is 900 000 000 000 000.
.hashes
The map. See remarks for more info.
.horizontalBuckets
Amount of horizontal buckets in the map. See remarks for more info.
.verticalBuckets
Amount of vertical buckets in the map. See remarks for more info.
.bucketCount
Amount of buckets in the map. Basically .horizontalBuckets * .verticalBuckets
.
Functions
.init()
Initializes the spatial hash arrays. Automatically called in the constructor.
Can be called to remove all items.
.insert(item)
Inserts an item.
See item requirements that need to be met. Functionality is not guaranteed if requirements are not met.
The maximum item count is 900 000 000 000 000.
The .insert(item)
function creates a .__b
object in the item
.
.remove(item)
Removes an item.
The .remove(item)
function will not remove items that do not have a .__b
object inside them.
.update(item)
Removes then inserts the item.
Items that are moving need to be updated.
Calls .remove(item)
and .insert(item)
.
.query(rangeObj, [selector])
Searches the map for items in a specified rangeObj
then returns an array of found items.
If any item is found to be intersecting the rangeObj
, the class will call selector(item)
if selector
is provided.
If selector(item)
returns false
the array will not include the item.
.any(rangeObj)
Searches the map for items in a specified rangeObj
.
Returns a boolean whether an item was found or not.
If any item is found to be intersecting the rangeObj
, it will immediately return true
. Otherwise returns false
.
.find(rangeObj, [callback])
Searches the map for items in a specified rangeObj
.
If any item is found to be intersecting the rangeObj
, the class will call callback(item)
if callback
is provided.
Remarks
This implementation's map is a two-dimensional array-like object.
var hash = x: 0 y: 0 w: 200 h: 200 100;console;
returns
'0': '0': '1': '2': '-2': '-1': '1': '0': '1': '2': '-2': '-1': '2': '0': '1': '2': '-2': '-1': '-2': '0': '1': '2': '-2': '-1': '-1': '0': '1': '2': '-2': '-1':
The map goes horizontally then vertically, and at the end is an array that will contain objects.
.insert(item)
can insert an item into the map multiple times.
This is because an item can be larger than the bucket size and will sometimes not be found when searching.
This requires for an ID, and that's why there is a maximum item count, 900 000 000 000 000, to ensure integer stability.
item.__b.id number may overlap with some other id.
This is due to the class just adding 1 to the next number.
This is fixable but very performance-costly.
Also this problem will appear only if you add 1 800 000 000 000 000 or more objects into the map and then remove it.
Which will take a few hours to come to.