Last active
February 9, 2017 04:47
-
-
Save timetocode/2397daf7d0ffb61812237035fcb6c753 to your computer and use it in GitHub Desktop.
point quadtree with pooling (the AABBs are pooled)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
var BinarySerializer = require('../binary/BinarySerializer') | |
var BinaryType = require('../binary/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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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