As3 Spatial Hash

When I wrote the Playchilla Physics Engine last summer I needed a broad phase algorithm to reduce the number of collisions to check. There are several ways to do this using spatial partitioning for example Grids, Spatial Hashing, Trees and Sweep and Prune. After reviewing them I decided to go with something called Spatial Hashing due to its simplicity and efficiency.

Spatial hashing

Most people are familiar with uniform grids, for 2d this is a matrix with rows and columns where each cell has a list of objects. Objects are mapped to this structure from world space as a function of the cell size. Instead of having a sparse matrix (memory consuming) we can use a hash function to map the cell to a dense 1d structure. So every time an object is added its 2d cell position is run through a hash function to produce a key that identifies a bucket. This bucket is a vector that can contain multiple objects. An object can overlap many cells and hence exist in more than one bucket at a time.

About the code

The code below may contain bugs, please let me know if so. The class SpatialHashValue is basically a container with for a Axis Align Bounding Box (AABB) and a time stamp. Cordinates (x1, y1) corresponds to the top left positions of the AABB and (x2, y2) to the bottom right position.

Adding an object

Map world coordinates to grid coordinates and add the object into the cells corresponding bucket

public function add(shv:SpatialHashValue):void
{
	shv.cx1 = shv.x1 / _cellSize;
	shv.cy1 = shv.y1 / _cellSize;
	shv.cx2 = shv.x2 / _cellSize;
	shv.cy2 = shv.y2 / _cellSize;
	for (var cy:int = shv.cy1; cy <= shv.cy2; ++cy)
		for (var cx:int = shv.cx1; cx <= shv.cx2; ++cx)
			_addToBucket(shv, cx, cy);
}

then we can add the objects cells into some kind of dictionary based on their keys

private function _addToBucket(shv:SpatialHashValue, cx:int, cy:int):void
{
	const key:uint = _getKey(cx, cy);
	var bucket:Vector.<SpatialHashValue> = _hash[key];
	if (bucket == null)
	{
		bucket = new Vector.<SpatialHashValue>();
		_hash[key] = bucket;
	}
	bucket.push(shv);
}

Each position in the dictionary, called a bucket, need to hold a list of items since more than one item can exist in the same cell simultaneously, hence the push operation.

Removing an object

Removing an object is almost as simple as adding it – just iterate over the imaginary cells and remove it.

public function remove(shv:SpatialHashValue):void
{
	for (var cy:int = shv.cy1; cy <= shv.cy2; ++cy)
		for (var cx:int = shv.cx1; cx <= shv.cx2; ++cx)
			_removeFromBucket(shv, cx, cy);
}

Only now we need to traverse the bucket to find it

private function _removeFromBucket(shv:SpatialHashValue, cx:int, cy:int):void
{
	const key:uint = _getKey(cx, cy);
	const bucket:Vector.<SpatialHashValue> = _hash[key];
	if (bucket == null) return;
	const size:int = bucket.length;
	for (var i:int = 0; i < size; ++i)
	{
		const hashValue:SpatialHashValue = bucket[i];
		if (hashValue != shv) continue;
		if (i == size - 1)
			bucket.pop();
		else
			bucket[i] = bucket.pop();
		break;
	}
	if (bucket.length == 0)
		delete _hash[key];
}

Finding overlapping objects

When we want to find possible collisions for a bounding box the spatial hash algorithm traverses all cells and performs actual box to box collision.

public function getOverlapping(test:SpatialHashValue):Vector.<SpatialHashValue>
{
	const result:Vector.<SpatialHashValue> = new Vector.<SpatialHashValue>;
	const cx1:int = test.x1 / _cellSize;
	const cy1:int = test.y1 / _cellSize;
	const cx2:int = test.x2 / _cellSize;
	const cy2:int = test.y2 / _cellSize;
	for (var cy:int = cy1; cy <= cy2; ++cy)
		for (var cx:int = cx1; cx <= cx2; ++cx)
		{
			const bucket:Vector.<SpatialHashValue> = _hash[_getKey(cx, cy)];
			if (bucket == null)	continue;
			for each (var b:SpatialHashValue in bucket)
			{
				if (b.timeStamp >= _timeStamp)
					continue;
				b.timeStamp = _timeStamp;
				if (test.x1 < b.x2 && test.x2 > b.x1 &&
					test.y1 < b.y2 && test.y2 > b.y1)
					result.push(b);
			}
		}
	++ _timeStamp;
	return result;
}

Note that each object is time stamped at every query, this is so the same object won’t be added more than once into the result vector, remember that an object can exist in multiple buckets.

Updating an object

When an object moves we also need to update the spatial hash data structure i.e. remove it from the old buckets and add them to the new buckets. I threw in a small optimization on the assumption that objects in general doesn’t leave all its former buckets, but stay in some, therefore we don’t need to remove it from the old cells that overlaps with the new, or add it to new buckets where it already exists.

public function update(shv:SpatialHashValue):void
{
	const newCx1:int = shv.x1 / _cellSize;
	const newCy1:int = shv.y1 / _cellSize;
	const newCx2:int = shv.x2 / _cellSize;
	const newCy2:int = shv.y2 / _cellSize;

	// add new
	for (var cy:int = newCy1; cy <= newCy2; ++cy)
		for (var cx:int = newCx1; cx <= newCx2; ++cx)
			if (cx < shv.cx1 || cx > shv.cx2 || cy < shv.cy1 || cy > shv.cy2)
				_addToBucket(shv, cx, cy);

	// remove old
	for (cy = shv.cy1; cy <= shv.cy2; ++cy)
		for (cx = shv.cx1; cx <= shv.cx2; ++cx)
			if (cx < newCx1 || cx > newCx2 || cy < newCy1 || cy > newCy2)
				_removeFromBucket(shv, cx, cy);

	shv.cx1 = newCx1;
	shv.cy1 = newCy1;
	shv.cx2 = newCx2;
	shv.cy2 = newCy2;
}

Hash function

private function _getKey(cx:int, cy:int):uint
{
	// prime numbers from http://code.google.com/p/chipmunk-physics/source/browse/trunk/src/cpSpaceHash.c
	return (cx * 1640531513 ^ cy * 2654435789) % _maxBuckets;
}

Conclusion

Spatial Hashing is straightforward to implement and pretty efficient performance wise. One drawback is that it needs some manual tweaking of the cell size depending on number of object and sizes. It’s sensitive to big variance in object sizes, since one object can exist in multiple cells all those cells need to be updated if the object move. One solution is to have hierarchical Spatial Hash structures with different cell sizes -then map objects depending on their size to the best fit.

Code

Here is all code that is needed, let me know if there are any bugs or possible improvements.

SpatialHash.as

package shared.algorithm.spatial
{
	import flash.utils.Dictionary;

	/**
	 * A simple 2D spatial hashing class from the Playchilla Physics Engine.
	 *
	 * @author playchilla.com - License: free to use and if you like it - link back!
	 */
	public class SpatialHash
	{
		public function SpatialHash(cellSize:Number, maxBuckets:uint)
		{
			_cellSize = cellSize;
			_maxBuckets = maxBuckets;
		}

		public function add(shv:SpatialHashValue):void
		{
			shv.cx1 = shv.x1 / _cellSize;
			shv.cy1 = shv.y1 / _cellSize;
			shv.cx2 = shv.x2 / _cellSize;
			shv.cy2 = shv.y2 / _cellSize;
			for (var cy:int = shv.cy1; cy <= shv.cy2; ++cy)
				for (var cx:int = shv.cx1; cx <= shv.cx2; ++cx)
					_addToBucket(shv, cx, cy);
		}

		public function remove(shv:SpatialHashValue):void
		{
			for (var cy:int = shv.cy1; cy <= shv.cy2; ++cy)
				for (var cx:int = shv.cx1; cx <= shv.cx2; ++cx)
					_removeFromBucket(shv, cx, cy);
		}

		public function update(shv:SpatialHashValue):void
		{
			const newCx1:int = shv.x1 / _cellSize;
			const newCy1:int = shv.y1 / _cellSize;
			const newCx2:int = shv.x2 / _cellSize;
			const newCy2:int = shv.y2 / _cellSize;

			// add new
			for (var cy:int = newCy1; cy <= newCy2; ++cy)
				for (var cx:int = newCx1; cx <= newCx2; ++cx)
					if (cx < shv.cx1 || cx > shv.cx2 || cy < shv.cy1 || cy > shv.cy2)
						_addToBucket(shv, cx, cy);

			// remove old
			for (cy = shv.cy1; cy <= shv.cy2; ++cy)
				for (cx = shv.cx1; cx <= shv.cx2; ++cx)
					if (cx < newCx1 || cx > newCx2 || cy < newCy1 || cy > newCy2)
						_removeFromBucket(shv, cx, cy);

			shv.cx1 = newCx1;
			shv.cy1 = newCy1;
			shv.cx2 = newCx2;
			shv.cy2 = newCy2;
		}

		public function getOverlapping(test:SpatialHashValue):Vector.<SpatialHashValue>
		{
			const result:Vector.<SpatialHashValue> = new Vector.<SpatialHashValue>;
			const cx1:int = test.x1 / _cellSize;
			const cy1:int = test.y1 / _cellSize;
			const cx2:int = test.x2 / _cellSize;
			const cy2:int = test.y2 / _cellSize;
			for (var cy:int = cy1; cy <= cy2; ++cy)
				for (var cx:int = cx1; cx <= cx2; ++cx)
				{
					const bucket:Vector.<SpatialHashValue> = _hash[_getKey(cx, cy)];
					if (bucket == null)	continue;
					for each (var b:SpatialHashValue in bucket)
					{
						if (b.timeStamp >= _timeStamp)
							continue;
						b.timeStamp = _timeStamp;
						if (test.x1 < b.x2 &&
							test.x2 > b.x1 &&
							test.y1 < b.y2 &&
							test.y2 > b.y1)
							result.push(b);
					}
				}
			++ _timeStamp;
			return result;
		}

		private function _addToBucket(shv:SpatialHashValue, cx:int, cy:int):void
		{
			const key:uint = _getKey(cx, cy);
			var bucket:Vector.<SpatialHashValue> = _hash[key];
			if (bucket == null)
			{
				bucket = new Vector.<SpatialHashValue>();
				_hash[key] = bucket;
			}
			bucket.push(shv);
		}

		private function _removeFromBucket(shv:SpatialHashValue, cx:int, cy:int):void
		{
			const key:uint = _getKey(cx, cy);
			const bucket:Vector.<SpatialHashValue> = _hash[key];
			if (bucket == null) return;
			const size:int = bucket.length;
			for (var i:int = 0; i < size; ++i)
			{
				const hashValue:SpatialHashValue = bucket[i];
				if (hashValue != shv) continue;
				if (i == size - 1)
					bucket.pop();
				else
					bucket[i] = bucket.pop();
				break;
			}
			if (bucket.length == 0)
				delete _hash[key];
		}

   		private function _getKey(cx:int, cy:int):uint
   		{
   			// prime numbers from http://code.google.com/p/chipmunk-physics/source/browse/trunk/src/cpSpaceHash.c
  			return (cx * 1640531513 ^ cy * 2654435789) % _maxBuckets;
   		}
		private var _cellSize:Number;
		private var _maxBuckets:uint;
		private var _timeStamp:uint = 1;
		private const _hash:Dictionary = new Dictionary;
	}
}

SpatialHashValue.as

package shared.algorithm.spatial
{
	/**
	 * Value stored in the spatial hash. Represents an AABB, a timestamp, and some internal cell coordinates.
	 *
	 * @author playchilla.com - License: free to use and if you like it - link back!
	 */
	public class SpatialHashValue
	{
		public function SpatialHashValue(x1:Number, y1:Number, x2:Number, y2:Number)
		{
			update(x1, y1, x2, y2);
		}

		public function update(x1:Number, y1:Number, x2:Number, y2:Number):void
		{
			this.x1 = x1;
			this.y1 = y1;
			this.x2 = x2;
			this.y2 = y2;
		}

		public function deltaMove(dx:Number, dy:Number):void
		{
			x1 += dx;
			y1 += dy;
			x2 += dx;
			y2 += dy;
		}

		/**
		 * Excluded objects will not be found when searching the spatial hash (getOverlapping).
		 */
		public function setExclude(exclude:Boolean):void { timeStamp = exclude ? uint.MAX_VALUE : 0; }

		/**
		 * Exposed internally for performance reasons.
		 */
		internal var x1:Number;
		internal var x2:Number;
		internal var y1:Number;
		internal var y2:Number;
		internal var cx1:int = 0;
		internal var cx2:int = 0;
		internal var cy1:int = 0;
		internal var cy2:int = 0;
		internal var timeStamp:uint = 0;
	}
}

If you want to bind a SpatialHashValue to a custom class you can do that by extending it, this is for example how the Playchilla Physics Engine uses it

public class PhysicsHashValue extends SpatialHashValue
{
	public function PhysicsHashValue(entity:IPhysicsEntity)
	{
		const swept:Aabb2 = entity.getSweptAabb();
		super(swept.x1(), swept.y1(), swept.x2(), swept.y2());
		_entity = entity;
	}
	...
	private var _entity:IPhysicsEntity;
}

Example usage

This is from the unittest suit to give you an idea of how to use the spatial hash class

private function _testDemo():void
{
	const spatialHash:SpatialHash = new SpatialHash(10, 1009);
	const shv:SpatialHashValue = new SpatialHashValue(0, 0, 4, 4);

	// add it
	spatialHash.add(shv);

	// move the object - remember to update the spatial hash
	shv.deltaMove(2, 0);
	spatialHash.update(shv);

	// create a test object
	const testObject:SpatialHashValue = new SpatialHashValue(-1, 0, 1, 1);

	// test if another object is overlapping
	var overlapping:Vector.<SpatialHashValue> = spatialHash.getOverlapping(testObject);
	// should be empty - we have moved shv
	Debug.assert(overlapping.length == 0); 

	// move the test object over the shv object
	testObject.deltaMove(2, 0);
	overlapping = spatialHash.getOverlapping(testObject);
	// We should now find it
	Debug.assert(overlapping.length == 1);
}