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

example.js

// 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!
});

hshg.js

// 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);

LICENSE

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.