Quadtree and AABB gists from nengi

AABB.js

//var BinarySerializer = require('./BinarySerializer')
//var BinaryType = require('./BinaryType')
// axis-aligned bounding box
/* PARAMS: (Point)center, (Point)half */
function AABB(x, y, halfWidth, halfHeight) {
	this.initialize(x, y, halfWidth, halfHeight)
}

AABB.pool = []
AABB.instanceCount = 0
AABB.inUseCount = 0
AABB.logStats = function() {
	console.log(
		'AABBs', 
		'total', AABB.instanceCount, 
		'avail', AABB.instanceCount - AABB.inUseCount, 
		'in-use', AABB.inUseCount
	)
}

AABB.create = function(x, y, halfWidth, halfHeight) {
	//return new AABB(x, y, halfWidth, halfHeight)
	var instance

	if (AABB.pool.length === 0) {        
		instance = new AABB(x, y, halfWidth, halfHeight)
		AABB.instanceCount++
    } else {
        instance = AABB.pool.pop()
        instance.initialize(x, y, halfWidth, halfHeight)        
    }

    AABB.inUseCount++
	return instance
}

AABB.prototype.release = function() {
	AABB.pool.push(this)
	AABB.inUseCount--
}

AABB.prototype.initialize = function(x, y, halfWidth, halfHeight) {
	this.x = x
	this.y = y
	this.halfWidth = halfWidth
	this.halfHeight = halfHeight
}

AABB.prototype.containsPoint = function(x, y) {
	// inclusive on the lower bound, exclusivive on the upper bound for quadtree
	// compatibilty, so that a point exactly on a line belongs to only one node
	return (x >= this.x - this.halfWidth 
		&& y >= this.y - this.halfHeight
		&& x < this.x + this.halfWidth
		&& y < this.y + this.halfHeight)
}

AABB.prototype.intersects = function(aabb) {
	return (Math.abs(this.x - aabb.x) * 2 < (this.halfWidth  * 2 + aabb.halfWidth  * 2))
		&& (Math.abs(this.y - aabb.y) * 2 < (this.halfHeight * 2 + aabb.halfHeight * 2))
}

AABB.prototype.clone = function() {
	return AABB.create(this.x, this.y, this.halfWidth, this.halfHeight)
}


/*
// only used for debugging quadtrees across a network
AABB.prototype.netSchema = BinarySerializer.createSchema({
	'x': BinaryType.Int32,
	'y': BinaryType.Int32,
	'halfWidth': BinaryType.Int32,
	'halfHeight': BinaryType.Int32
})
*/

module.exports = AABB

Quadtree.js

var AABB = require('./AABB')

var minimumNodeSize = 60

// quadtree
function Quadtree(aabb) {
	this.initialize(aabb)
}

Quadtree.pool = []
Quadtree.instanceCount = 0
Quadtree.inUseCount = 0
Quadtree.logStats = function() {
	console.log(
		'Quadtrees', 
		'total', Quadtree.instanceCount, 
		'avail', Quadtree.instanceCount - Quadtree.inUseCount, 
		'in-use', Quadtree.inUseCount
	)
}

Quadtree.create = function(aabb) {
	//return new Quadtree(aabb)
	var instance

	if (Quadtree.pool.length === 0) {
		instance = new Quadtree(aabb)
        Quadtree.instanceCount++        
    } else {
        instance = Quadtree.pool.pop()
        instance.initialize(aabb)
    }
    
    Quadtree.inUseCount++
	return instance
}


/*
* Converts a quadtree into an array of aabbs, DEBUG USE
*/
Quadtree.prototype._getAllAABBs = function(aabbs) {

	aabbs.push(this.aabb)

	if (!this.nw) return aabbs

	aabbs.concat(this.nw._getAllAABBs(aabbs))
	aabbs.concat(this.ne._getAllAABBs(aabbs))
	aabbs.concat(this.sw._getAllAABBs(aabbs))
	aabbs.concat(this.se._getAllAABBs(aabbs))
	
	return aabbs
}

Quadtree.prototype.getAllAABBs = function() {
	var aabbs = []
	return this._getAllAABBs(aabbs)
}



Quadtree.prototype.release = function() {	
	Quadtree.pool.push(this)
	Quadtree.inUseCount--

	this.aabb.release()
	this.aabb = null	

	if (this.nw) this.nw.release()
	if (this.ne) this.ne.release()
	if (this.sw) this.sw.release()
	if (this.se) this.se.release()
}

Quadtree.prototype.initialize = function(aabb) {
	// boundaries
	this.aabb = aabb
	// max points this node can hold; 4 for leaf, 0 for branch
	this.capacity = 4
	// points contained in this node
	this.points = [] 

	// sub quadtree nodes
	this.nw = null
	this.ne = null
	this.sw = null
	this.se = null
}


/* Insert a point! Quadtree will subdivide accordingly */
Quadtree.prototype.insert = function(gameObject) {
	// point not within this node's bounds? return immediately
	if (!this.aabb.containsPoint(gameObject.x, gameObject.y)) return false

	// if node is not too small nor too full add the point to this node and return
	if (this.points.length < this.capacity || this.aabb.halfWidth * 2 < minimumNodeSize) {
		this.points.push(gameObject)
		return true
	}	

	// too crowded? split this node into 4 nodes
	if (!this.nw) this.subdivide()

	// recursively add this point to whichever subnode qualifies
	if (this.nw.insert(gameObject)) return true
	if (this.ne.insert(gameObject)) return true
	if (this.sw.insert(gameObject)) return true
	if (this.se.insert(gameObject)) return true

	return false // unreachable code, in theory
}

Quadtree.prototype.subdivide = function() {
	this.nw = Quadtree.create(
		AABB.create(
			this.aabb.x - this.aabb.halfWidth * 0.5, 
			this.aabb.y - this.aabb.halfHeight * 0.5, 
			this.aabb.halfWidth * 0.5,
			this.aabb.halfHeight * 0.5
		)
	)
	this.nw.parent = this

	this.ne = Quadtree.create(
		AABB.create( 
			this.aabb.x + this.aabb.halfWidth * 0.5,
			this.aabb.y - this.aabb.halfHeight * 0.5, 
			this.aabb.halfWidth * 0.5,
			this.aabb.halfHeight * 0.5
		)
	)
	this.ne.parent = this

	this.sw = Quadtree.create(
		AABB.create( 
			this.aabb.x - this.aabb.halfHeight * 0.5,
			this.aabb.y + this.aabb.halfHeight * 0.5, 
			this.aabb.halfWidth * 0.5,
			this.aabb.halfHeight * 0.5
		)
	)
	this.sw.parent = this

	this.se = Quadtree.create(
		AABB.create( 
			this.aabb.x + this.aabb.halfWidth * 0.5,
			this.aabb.y + this.aabb.halfHeight * 0.5, 
			this.aabb.halfWidth * 0.5,
			this.aabb.halfHeight * 0.5
		)
	)
	this.se.parent = this

	// transfer points from this node to the appropriate subnodes	
	for (var i = 0; i < this.points.length; i++) {
		this.nw.insert(this.points[i])
		this.ne.insert(this.points[i])
		this.sw.insert(this.points[i])
		this.se.insert(this.points[i])
	}

	// remove the points from this node now that they've been transfered
	this.points = []
	// this is now a branch, not a leaf, and cannot have points added to it
	this.capacity = 0
}

Quadtree.prototype.queryRange = function(aabb, pointsInRange) {
	if (!this.aabb.intersects(aabb)) return pointsInRange

	for (var i = 0; i < this.points.length; i++) {
		if (aabb.containsPoint(this.points[i].x, this.points[i].y)) {
			pointsInRange.push(this.points[i])
		}
	}

	if (!this.nw) return pointsInRange

	pointsInRange.concat(this.nw.queryRange(aabb, pointsInRange))
	pointsInRange.concat(this.ne.queryRange(aabb, pointsInRange))
	pointsInRange.concat(this.sw.queryRange(aabb, pointsInRange))
	pointsInRange.concat(this.se.queryRange(aabb, pointsInRange))
	
	return pointsInRange
}

Quadtree.prototype.select = function(aabb) {
	var gameObjects = []
	this.queryRange(aabb, gameObjects)
	return gameObjects
}

// limit is optional
Quadtree.prototype.selectIds = function(aabb, limit) {
	var gameObjects = this.select(aabb)
	var ids = []

	var max = gameObjects.length

	if (typeof limit !== 'undefined')
		max = (gameObjects.length > limit) ? limit : gameObjects.length

	for (var i = 0; i < max; i++) {
		ids.push(gameObjects[i].id)
	}
	return ids
}

Quadtree.prototype.selectObjectAndEventIds = function(aabb, limit) {
	var gameObjects = this.select(aabb)
	var objectIds = []
	var eventIds = []

	var max = gameObjects.length

	if (typeof limit !== 'undefined')
		max = (gameObjects.length > limit) ? limit : gameObjects.length

	for (var i = 0; i < max; i++) {
		if (gameObjects[i].type === 1) {
			objectIds.push(gameObjects[i].id)
		} else if (gameObjects[i].type === 2) {
			eventIds.push(gameObjects[i].id)
		}
		
	}
	return { objectIds: objectIds, eventIds: eventIds }
}


module.exports = Quadtree