a.k.a. Sort and sweep
For each axis,
Create sorted list of start and end points of intervals for each box (use Insert Sort to exploit frame to frame coherency)
Traverse each list
Each time a startpoint is reached insert into active list
If endpoint is hit remove it from active list
If 2 or more objects are active at the same time they overlap in the specified dimension
Potential colliding pairs must overlap in all 3 lists
/**
* Base class for broadphase implementations. Don't use this class directly.
* @class Broadphase
* @constructor
*/
var vec2 = require('../math/vec2');
var Body = require('../objects/Body');
module.exports = Broadphase;
function Broadphase(type){
this.type = type;
/**
* The resulting overlapping pairs. Will be filled with results during .getCollisionPairs().
* @property result
* @type {Array}
*/
this.result = [];
/**
* The world to search for collision pairs in. To change it, use .setWorld()
* @property world
* @type {World}
* @readOnly
*/
this.world = null;
/**
* The bounding volume type to use in the broadphase algorithms. Should be set to Broadphase.AABB or Broadphase.BOUNDING_CIRCLE.
* @property {Number} boundingVolumeType
*/
this.boundingVolumeType = Broadphase.AABB;
}
/**
* Axis aligned bounding box type.
* @static
* @property {Number} AABB
*/
Broadphase.AABB = 1;
/**
* Bounding circle type.
* @static
* @property {Number} BOUNDING_CIRCLE
*/
Broadphase.BOUNDING_CIRCLE = 2;
/**
* Set the world that we are searching for collision pairs in.
* @method setWorld
* @param {World} world
*/
Broadphase.prototype.setWorld = function(world){
this.world = world;
};
/**
* Get all potential intersecting body pairs.
* @method getCollisionPairs
* @param {World} world The world to search in.
* @return {Array} An array of the bodies, ordered in pairs. Example: A result of [a,b,c,d] means that the potential pairs are: (a,b), (c,d).
*/
Broadphase.prototype.getCollisionPairs = function(/*world*/){};
/**
* Check whether the bounding radius of two bodies overlap.
* @method boundingRadiusCheck
* @param {Body} bodyA
* @param {Body} bodyB
* @return {Boolean}
*/
Broadphase.boundingRadiusCheck = function(bodyA, bodyB){
var d2 = vec2.squaredDistance(bodyA.position, bodyB.position),
r = bodyA.boundingRadius + bodyB.boundingRadius;
return d2 <= r*r;
};
/**
* Check whether the AABB of two bodies overlap.
* @method aabbCheck
* @param {Body} bodyA
* @param {Body} bodyB
* @return {Boolean}
*/
Broadphase.aabbCheck = function(bodyA, bodyB){
return bodyA.getAABB().overlaps(bodyB.getAABB());
};
/**
* Check whether the bounding volumes of two bodies overlap.
* @method boundingVolumeCheck
* @param {Body} bodyA
* @param {Body} bodyB
* @return {Boolean}
*/
Broadphase.prototype.boundingVolumeCheck = function(bodyA, bodyB){
var result;
switch(this.boundingVolumeType){
case Broadphase.BOUNDING_CIRCLE:
result = Broadphase.boundingRadiusCheck(bodyA,bodyB);
break;
case Broadphase.AABB:
result = Broadphase.aabbCheck(bodyA,bodyB);
break;
default:
throw new Error('Bounding volume type not recognized: '+this.boundingVolumeType);
}
return result;
};
/**
* Check whether two bodies are allowed to collide at all.
* @method canCollide
* @param {Body} bodyA
* @param {Body} bodyB
* @return {Boolean}
*/
Broadphase.canCollide = function(bodyA, bodyB){
var KINEMATIC = Body.KINEMATIC;
var STATIC = Body.STATIC;
var typeA = bodyA.type;
var typeB = bodyB.type;
// Cannot collide static bodies
if(typeA === STATIC && typeB === STATIC){
return false;
}
// Cannot collide static vs kinematic bodies
if( (typeA === KINEMATIC && typeB === STATIC) ||
(typeA === STATIC && typeB === KINEMATIC)){
return false;
}
// Cannot collide kinematic vs kinematic
if(typeA === KINEMATIC && typeB === KINEMATIC){
return false;
}
// Cannot collide both sleeping bodies
if(bodyA.sleepState === Body.SLEEPING && bodyB.sleepState === Body.SLEEPING){
return false;
}
// Cannot collide if one is static and the other is sleeping
if( (bodyA.sleepState === Body.SLEEPING && typeB === STATIC) ||
(bodyB.sleepState === Body.SLEEPING && typeA === STATIC)){
return false;
}
return true;
};
Broadphase.NAIVE = 1;
Broadphase.SAP = 2;
/**
* Returns all the bodies within an AABB.
* @method aabbQuery
* @param {World} world
* @param {AABB} aabb
* @param {array} result An array to store resulting bodies in.
* @return {array}
*/
Broadphase.prototype.aabbQuery = function(/*world, aabb, result*/){
// To be implemented in subclasses
};The ACTUAL CLASS
var Utils = require('../utils/Utils')
, Broadphase = require('../collision/Broadphase');
module.exports = SAPBroadphase;
/**
* Sweep and prune broadphase along one axis.
*
* @class SAPBroadphase
* @constructor
* @extends Broadphase
*/
function SAPBroadphase(){
Broadphase.call(this,Broadphase.SAP);
/**
* List of bodies currently in the broadphase.
* @property axisList
* @type {Array}
*/
this.axisList = [];
/**
* The axis to sort along. 0 means x-axis and 1 y-axis. If your bodies are more spread out over the X axis, set axisIndex to 0, and you will gain some performance.
* @property axisIndex
* @type {Number}
*/
this.axisIndex = 0;
var that = this;
this._addBodyHandler = function(e){
that.axisList.push(e.body);
};
this._removeBodyHandler = function(e){
// Remove from list
var idx = that.axisList.indexOf(e.body);
if(idx !== -1){
that.axisList.splice(idx,1);
}
};
}
SAPBroadphase.prototype = new Broadphase();
SAPBroadphase.prototype.constructor = SAPBroadphase;
/**
* Change the world
* @method setWorld
* @param {World} world
*/
SAPBroadphase.prototype.setWorld = function(world){
// Clear the old axis array
this.axisList.length = 0;
// Add all bodies from the new world
Utils.appendArray(this.axisList, world.bodies);
// Remove old handlers, if any
world
.off("addBody",this._addBodyHandler)
.off("removeBody",this._removeBodyHandler);
// Add handlers to update the list of bodies.
world.on("addBody",this._addBodyHandler).on("removeBody",this._removeBodyHandler);
this.world = world;
};
function sortAxisList(a, axisIndex){
axisIndex = axisIndex|0;
for(var i=1,l=a.length; i<l; i++) {
var v = a[i];
for(var j=i - 1;j>=0;j--) {
if(a[j].aabb.lowerBound[axisIndex] <= v.aabb.lowerBound[axisIndex]){
break;
}
a[j+1] = a[j];
}
a[j+1] = v;
}
return a;
}
SAPBroadphase.prototype.sortList = function(){
var bodies = this.axisList,
axisIndex = this.axisIndex;
// Sort the lists
sortAxisList(bodies, axisIndex);
};
/**
* Get the colliding pairs
* @method getCollisionPairs
* @param {World} world
* @return {Array}
*/
SAPBroadphase.prototype.getCollisionPairs = function(/*world*/){
var bodies = this.axisList,
result = this.result,
axisIndex = this.axisIndex;
result.length = 0;
// Update all AABBs if needed
var l = bodies.length;
while(l--){
var b = bodies[l];
if(b.aabbNeedsUpdate){
b.updateAABB();
}
}
// Sort the lists
this.sortList();
// Look through the X list
for(var i=0, N=bodies.length|0; i!==N; i++){
var bi = bodies[i];
for(var j=i+1; j<N; j++){
var bj = bodies[j];
// Bounds overlap?
var overlaps = (bj.aabb.lowerBound[axisIndex] <= bi.aabb.upperBound[axisIndex]);
if(!overlaps){
break;
}
if(Broadphase.canCollide(bi,bj) && this.boundingVolumeCheck(bi,bj)){
result.push(bi,bj);
}
}
}
return result;
};
/**
* Returns all the bodies within an AABB.
* @method aabbQuery
* @param {World} world
* @param {AABB} aabb
* @param {array} result An array to store resulting bodies in.
* @return {array}
* @todo since the list is sorted, optimization can be done
*/
SAPBroadphase.prototype.aabbQuery = function(world, aabb, result){
result = result || [];
this.sortList();
var axisList = this.axisList;
for(var i = 0; i < axisList.length; i++){
var b = axisList[i];
if(b.aabbNeedsUpdate){
b.updateAABB();
}
if(b.aabb.overlaps(aabb)){
result.push(b);
}
}
return result;
};
Comments