Skip to content

Instantly share code, notes, and snippets.

@timetocode
Created May 24, 2015 22:47
Show Gist options
  • Save timetocode/a8699b556203ec200dd5 to your computer and use it in GitHub Desktop.
Save timetocode/a8699b556203ec200dd5 to your computer and use it in GitHub Desktop.
Quadtree and AABB gists from nengi
//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
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment