Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Hierarchical Spatial Hash Grid: extremely efficient spatial hashing for collision detection between objects of any size! This is an implementation in JS as described in http://www10.informatik.uni-erlangen.de/~schornbaum/hierarchical_hash_grids.pdf
// The only thing HSHG expects a collidable object to have is a getAABB() method that
// returns an object with two properties, min and max, that should both have a single
// array with two numbers as coordinates. For example, an object at 10, 10 and
// height/width of 100 would return { min: [10, 10], max: [110, 110] }
function Vertex(args /*x, y, radius*/){
var argProp;
for(argProp in args){
if(args.hasOwnProperty(argProp)){
this[ argProp ] = args[argProp];
}
}
}
Vertex.prototype.getAABB = function(){
var rad = this.radius
,x = this.x
,y = this.y;
return this.aabb = {
min: [ x - rad, y - rad ]
,max: [ x + rad, y + rad ]
};
}
var grid = new HSHG()
,v1 = new Vertex({ x: 0, y: 0, radius: 20 })
// size is of no concern to the HSHG, it dynamically creates the necessary structures!
,v2 = new Vertex({ x: 10, y: 10, radius: 200 });
grid.addObject(v1);
grid.addObject(v2);
// obviously use something more robust than setTimeout
setTimeout(function(){
grid.update();
// the queryForCollisionPairs method can also accept a callback that will be used as a
// broad overlap test. By default, it uses a quick AABB intersection. The method must
// return true or false.
var pairs = grid.queryForCollisionPairs();
// do something with all the pairs!
});
// Hierarchical Spatial Hash Grid: HSHG
(function(root, undefined){
//---------------------------------------------------------------------
// GLOBAL FUNCTIONS
//---------------------------------------------------------------------
/**
* Updates every object's position in the grid, but only if
* the hash value for that object has changed.
* This method DOES NOT take into account object expansion or
* contraction, just position, and does not attempt to change
* the grid the object is currently in; it only (possibly) changes
* the cell.
*
* If the object has significantly changed in size, the best bet is to
* call removeObject() and addObject() sequentially, outside of the
* normal update cycle of HSHG.
*
* @return void desc
*/
function update_RECOMPUTE(){
var i
,obj
,grid
,meta
,objAABB
,newObjHash;
// for each object
for(i = 0; i < this._globalObjects.length; i++){
obj = this._globalObjects[i];
meta = obj.HSHG;
grid = meta.grid;
// recompute hash
objAABB = obj.getAABB();
newObjHash = grid.toHash(objAABB.min[0], objAABB.min[1]);
if(newObjHash !== meta.hash){
// grid position has changed, update!
grid.removeObject(obj);
grid.addObject(obj, newObjHash);
}
}
}
// not implemented yet :)
function update_REMOVEALL(){
}
function testAABBOverlap(objA, objB){
var a = objA.getAABB()
,b = objB.getAABB();
//if(a.min[0] > b.max[0] || a.min[1] > b.max[1] || a.min[2] > b.max[2]
//|| a.max[0] < b.min[0] || a.max[1] < b.min[1] || a.max[2] < b.min[2]){
if(a.min[0] > b.max[0] || a.min[1] > b.max[1]
|| a.max[0] < b.min[0] || a.max[1] < b.min[1]){
return false;
} else {
return true;
}
}
function getLongestAABBEdge(min, max){
return Math.max(
Math.abs(max[0] - min[0])
,Math.abs(max[1] - min[1])
//,Math.abs(max[2] - min[2])
);
}
//---------------------------------------------------------------------
// ENTITIES
//---------------------------------------------------------------------
function HSHG(){
this.MAX_OBJECT_CELL_DENSITY = 1/8 // objects / cells
this.INITIAL_GRID_LENGTH = 256 // 16x16
this.HIERARCHY_FACTOR = 2
this.HIERARCHY_FACTOR_SQRT = Math.SQRT2
this.UPDATE_METHOD = update_RECOMPUTE // or update_REMOVEALL
this._grids = [];
this._globalObjects = [];
}
//HSHG.prototype.init = function(){
// this._grids = [];
// this._globalObjects = [];
//}
HSHG.prototype.addObject = function(obj){
var x ,i
,cellSize
,objAABB = obj.getAABB()
,objSize = getLongestAABBEdge(objAABB.min, objAABB.max)
,oneGrid, newGrid;
// for HSHG metadata
obj.HSHG = {
globalObjectsIndex: this._globalObjects.length
};
// add to global object array
this._globalObjects.push(obj);
if(this._grids.length == 0) {
// no grids exist yet
cellSize = objSize * this.HIERARCHY_FACTOR_SQRT;
newGrid = new Grid(cellSize, this.INITIAL_GRID_LENGTH, this);
newGrid.initCells();
newGrid.addObject(obj);
this._grids.push(newGrid);
} else {
x = 0;
// grids are sorted by cellSize, smallest to largest
for(i = 0; i < this._grids.length; i++){
oneGrid = this._grids[i];
x = oneGrid.cellSize;
if(objSize < x){
x = x / this.HIERARCHY_FACTOR;
if(objSize < x) {
// find appropriate size
while( objSize < x ) {
x = x / this.HIERARCHY_FACTOR;
}
newGrid = new Grid(x * this.HIERARCHY_FACTOR, this.INITIAL_GRID_LENGTH, this);
newGrid.initCells();
// assign obj to grid
newGrid.addObject(obj)
// insert grid into list of grids directly before oneGrid
this._grids.splice(i, 0, newGrid);
} else {
// insert obj into grid oneGrid
oneGrid.addObject(obj);
}
return;
}
}
while( objSize >= x ){
x = x * this.HIERARCHY_FACTOR;
}
newGrid = new Grid(x, this.INITIAL_GRID_LENGTH, this);
newGrid.initCells();
// insert obj into grid
newGrid.addObject(obj)
// add newGrid as last element in grid list
this._grids.push(newGrid);
}
}
HSHG.prototype.removeObject = function(obj){
var meta = obj.HSHG
,globalObjectsIndex
,replacementObj;
if(meta === undefined){
throw Error( obj + ' was not in the HSHG.' );
return;
}
// remove object from global object list
globalObjectsIndex = meta.globalObjectsIndex
if(globalObjectsIndex === this._globalObjects.length - 1){
this._globalObjects.pop();
} else {
replacementObj = this._globalObjects.pop();
replacementObj.HSHG.globalObjectsIndex = globalObjectsIndex;
this._globalObjects[ globalObjectsIndex ] = replacementObj;
}
meta.grid.removeObject(obj);
// remove meta data
delete obj.HSHG;
}
HSHG.prototype.update = function(){
this.UPDATE_METHOD.call(this);
}
HSHG.prototype.queryForCollisionPairs = function(broadOverlapTestCallback){
var i, j, k, l, c
,grid
,cell
,objA
,objB
,offset
,adjacentCell
,biggerGrid
,objAAABB
,objAHashInBiggerGrid
,possibleCollisions = []
// default broad test to internal aabb overlap test
broadOverlapTest = broadOverlapTestCallback || testAABBOverlap;
// for all grids ordered by cell size ASC
for(i = 0; i < this._grids.length; i++){
grid = this._grids[i];
// for each cell of the grid that is occupied
for(j = 0; j < grid.occupiedCells.length; j++){
cell = grid.occupiedCells[j];
// collide all objects within the occupied cell
for(k = 0; k < cell.objectContainer.length; k++){
objA = cell.objectContainer[k];
for(l = k+1; l < cell.objectContainer.length; l++){
objB = cell.objectContainer[l];
if(broadOverlapTest(objA, objB) === true){
possibleCollisions.push( [ objA, objB ] );
}
}
}
// for the first half of all adjacent cells (offset 4 is the current cell)
for(c = 0; c < 4; c++){
offset = cell.neighborOffsetArray[c];
//if(offset === null) { continue; }
adjacentCell = grid.allCells[ cell.allCellsIndex + offset ];
// collide all objects in cell with adjacent cell
for(k = 0; k < cell.objectContainer.length; k++){
objA = cell.objectContainer[k];
for(l = 0; l < adjacentCell.objectContainer.length; l++){
objB = adjacentCell.objectContainer[l];
if(broadOverlapTest(objA, objB) === true){
possibleCollisions.push( [ objA, objB ] );
}
}
}
}
}
// forall objects that are stored in this grid
for(j = 0; j < grid.allObjects.length; j++){
objA = grid.allObjects[j];
objAAABB = objA.getAABB();
// for all grids with cellsize larger than grid
for(k = i + 1; k < this._grids.length; k++){
biggerGrid = this._grids[k];
objAHashInBiggerGrid = biggerGrid.toHash(objAAABB.min[0], objAAABB.min[1]);
cell = biggerGrid.allCells[objAHashInBiggerGrid];
// check objA against every object in all cells in offset array of cell
// for all adjacent cells...
for(c = 0; c < cell.neighborOffsetArray.length; c++){
offset = cell.neighborOffsetArray[c];
//if(offset === null) { continue; }
adjacentCell = biggerGrid.allCells[ cell.allCellsIndex + offset ];
// for all objects in the adjacent cell...
for(l = 0; l < adjacentCell.objectContainer.length; l++){
objB = adjacentCell.objectContainer[l];
// test against object A
if(broadOverlapTest(objA, objB) === true){
possibleCollisions.push( [ objA, objB ] );
}
}
}
}
}
}
// return list of object pairs
return possibleCollisions;
}
HSHG.update_RECOMPUTE = update_RECOMPUTE;
HSHG.update_REMOVEALL = update_REMOVEALL;
/**
* Grid
*
* @constructor
* @param int cellSize the pixel size of each cell of the grid
* @param int cellCount the total number of cells for the grid (width x height)
* @param HSHG parentHierarchy the HSHG to which this grid belongs
* @return void
*/
function Grid(cellSize, cellCount, parentHierarchy){
this.cellSize = cellSize;
this.inverseCellSize = 1/cellSize;
this.rowColumnCount = ~~Math.sqrt(cellCount);
this.xyHashMask = this.rowColumnCount - 1;
this.occupiedCells = [];
this.allCells = Array(this.rowColumnCount*this.rowColumnCount);
this.allObjects = [];
this.sharedInnerOffsets = [];
this._parentHierarchy = parentHierarchy || null;
}
Grid.prototype.initCells = function(){
// TODO: inner/unique offset rows 0 and 2 may need to be
// swapped due to +y being "down" vs "up"
var i, gridLength = this.allCells.length
,x, y
,wh = this.rowColumnCount
,isOnRightEdge, isOnLeftEdge, isOnTopEdge, isOnBottomEdge
,innerOffsets = [
// y+ down offsets
//-1 + -wh, -wh, -wh + 1,
//-1, 0, 1,
//wh - 1, wh, wh + 1
// y+ up offsets
wh - 1, wh, wh + 1,
-1, 0, 1,
-1 + -wh, -wh, -wh + 1
]
,leftOffset, rightOffset, topOffset, bottomOffset
,uniqueOffsets = []
,cell;
this.sharedInnerOffsets = innerOffsets;
// init all cells, creating offset arrays as needed
for(i = 0; i < gridLength; i++){
cell = new Cell();
// compute row (y) and column (x) for an index
y = ~~(i / this.rowColumnCount);
x = ~~(i - (y*this.rowColumnCount));
// reset / init
isOnRightEdge = false;
isOnLeftEdge = false;
isOnTopEdge = false;
isOnBottomEdge = false;
// right or left edge cell
if((x+1) % this.rowColumnCount == 0){ isOnRightEdge = true; }
else if(x % this.rowColumnCount == 0){ isOnLeftEdge = true; }
// top or bottom edge cell
if((y+1) % this.rowColumnCount == 0){ isOnTopEdge = true; }
else if(y % this.rowColumnCount == 0){ isOnBottomEdge = true; }
// if cell is edge cell, use unique offsets, otherwise use inner offsets
if(isOnRightEdge || isOnLeftEdge || isOnTopEdge || isOnBottomEdge){
// figure out cardinal offsets first
rightOffset = isOnRightEdge === true ? -wh + 1 : 1;
leftOffset = isOnLeftEdge === true ? wh - 1 : -1;
topOffset = isOnTopEdge === true ? -gridLength + wh : wh;
bottomOffset = isOnBottomEdge === true ? gridLength - wh : -wh;
// diagonals are composites of the cardinals
uniqueOffsets = [
// y+ down offset
//leftOffset + bottomOffset, bottomOffset, rightOffset + bottomOffset,
//leftOffset, 0, rightOffset,
//leftOffset + topOffset, topOffset, rightOffset + topOffset
// y+ up offset
leftOffset + topOffset, topOffset, rightOffset + topOffset,
leftOffset, 0, rightOffset,
leftOffset + bottomOffset, bottomOffset, rightOffset + bottomOffset
];
cell.neighborOffsetArray = uniqueOffsets;
} else {
cell.neighborOffsetArray = this.sharedInnerOffsets;
}
cell.allCellsIndex = i;
this.allCells[i] = cell;
}
}
Grid.prototype.toHash = function(x, y, z){
var i, xHash, yHash, zHash;
if(x < 0){
i = (-x) * this.inverseCellSize;
xHash = this.rowColumnCount - 1 - ( ~~i & this.xyHashMask );
} else {
i = x * this.inverseCellSize;
xHash = ~~i & this.xyHashMask;
}
if(y < 0){
i = (-y) * this.inverseCellSize;
yHash = this.rowColumnCount - 1 - ( ~~i & this.xyHashMask );
} else {
i = y * this.inverseCellSize;
yHash = ~~i & this.xyHashMask;
}
//if(z < 0){
// i = (-z) * this.inverseCellSize;
// zHash = this.rowColumnCount - 1 - ( ~~i & this.xyHashMask );
//} else {
// i = z * this.inverseCellSize;
// zHash = ~~i & this.xyHashMask;
//}
return xHash + yHash * this.rowColumnCount
//+ zHash * this.rowColumnCount * this.rowColumnCount;
}
Grid.prototype.addObject = function(obj, hash){
var objAABB
,objHash
,targetCell;
// technically, passing this in this should save some computational effort when updating objects
if(hash !== undefined){
objHash = hash;
} else {
objAABB = obj.getAABB()
objHash = this.toHash(objAABB.min[0], objAABB.min[1])
}
targetCell = this.allCells[objHash];
if(targetCell.objectContainer.length === 0){
// insert this cell into occupied cells list
targetCell.occupiedCellsIndex = this.occupiedCells.length;
this.occupiedCells.push(targetCell);
}
// add meta data to obj, for fast update/removal
obj.HSHG.objectContainerIndex = targetCell.objectContainer.length;
obj.HSHG.hash = objHash;
obj.HSHG.grid = this;
obj.HSHG.allGridObjectsIndex = this.allObjects.length;
// add obj to cell
targetCell.objectContainer.push(obj);
// we can assume that the targetCell is already a member of the occupied list
// add to grid-global object list
this.allObjects.push(obj);
// do test for grid density
if(this.allObjects.length / this.allCells.length > this._parentHierarchy.MAX_OBJECT_CELL_DENSITY){
// grid must be increased in size
this.expandGrid();
}
}
Grid.prototype.removeObject = function(obj){
var meta = obj.HSHG
,hash
,containerIndex
,allGridObjectsIndex
,cell
,replacementCell
,replacementObj;
hash = meta.hash;
containerIndex = meta.objectContainerIndex;
allGridObjectsIndex = meta.allGridObjectsIndex;
cell = this.allCells[hash];
// remove object from cell object container
if(cell.objectContainer.length === 1){
// this is the last object in the cell, so reset it
cell.objectContainer.length = 0;
// remove cell from occupied list
if(cell.occupiedCellsIndex === this.occupiedCells.length - 1){
// special case if the cell is the newest in the list
this.occupiedCells.pop();
} else {
replacementCell = this.occupiedCells.pop();
replacementCell.occupiedCellsIndex = cell.occupiedCellsIndex;
this.occupiedCells[ cell.occupiedCellsIndex ] = replacementCell;
}
cell.occupiedCellsIndex = null;
} else {
// there is more than one object in the container
if(containerIndex === cell.objectContainer.length - 1){
// special case if the obj is the newest in the container
cell.objectContainer.pop();
} else {
replacementObj = cell.objectContainer.pop();
replacementObj.HSHG.objectContainerIndex = containerIndex;
cell.objectContainer[ containerIndex ] = replacementObj;
}
}
// remove object from grid object list
if(allGridObjectsIndex === this.allObjects.length - 1){
this.allObjects.pop();
} else {
replacementObj = this.allObjects.pop();
replacementObj.HSHG.allGridObjectsIndex = allGridObjectsIndex;
this.allObjects[ allGridObjectsIndex ] = replacementObj;
}
}
Grid.prototype.expandGrid = function(){
var i, j
,currentCellCount = this.allCells.length
,currentRowColumnCount = this.rowColumnCount
,currentXYHashMask = this.xyHashMask
,newCellCount = currentCellCount * 4 // double each dimension
,newRowColumnCount = ~~Math.sqrt(newCellCount)
,newXYHashMask = newRowColumnCount - 1
,allObjects = this.allObjects.slice(0) // duplicate array, not objects contained
,aCell
,push = Array.prototype.push;
// remove all objects
for(i = 0; i < allObjects.length; i++){
this.removeObject(allObjects[i]);
}
// reset grid values, set new grid to be 4x larger than last
this.rowColumnCount = newRowColumnCount;
this.allCells = Array(this.rowColumnCount*this.rowColumnCount);
this.xyHashMask = newXYHashMask;
// initialize new cells
this.initCells();
// re-add all objects to grid
for(i = 0; i < allObjects.length; i++){
this.addObject(allObjects[i]);
}
}
/**
* A cell of the grid
*
* @constructor
* @return void desc
*/
function Cell(){
this.objectContainer = [];
this.neighborOffsetArray;
this.occupiedCellsIndex = null;
this.allCellsIndex = null;
}
//---------------------------------------------------------------------
// EXPORTS
//---------------------------------------------------------------------
root['HSHG'] = HSHG;
HSHG._private = {
Grid: Grid,
Cell: Cell,
testAABBOverlap: testAABBOverlap,
getLongestAABBEdge: getLongestAABBEdge
};
})(this);
Copyright 2012 Andrew Petersen
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.