File: src/solver/IslandSolver.js
var Solver = require('./Solver')
, vec2 = require('../math/vec2')
, Island = require('../solver/Island')
, Body = require('../objects/Body')
, STATIC = Body.STATIC
module.exports = IslandSolver;
/**
* Splits the system of bodies and equations into independent islands
*
* @class IslandSolver
* @constructor
* @param {Solver} subsolver
* @param {Object} options
* @extends Solver
*/
function IslandSolver(subsolver,options){
Solver.call(this,options);
var that = this;
/**
* The solver used in the workers.
* @property subsolver
* @type {Solver}
*/
this.subsolver = subsolver;
/**
* Number of islands. Read only.
* @property numIslands
* @type {number}
*/
this.numIslands = 0;
// Pooling of node objects saves some GC load
this._nodePool = [];
/**
* Fires before an island is solved.
* @event beforeSolveIsland
* @param {Island} island
*/
this.beforeSolveIslandEvent = {
type : "beforeSolveIsland",
island : null,
};
};
IslandSolver.prototype = new Solver();
function getUnvisitedNode(nodes){
var Nnodes = nodes.length;
for(var i=0; i!==Nnodes; i++){
var node = nodes[i];
if(!node.visited && !(node.body.motionState & STATIC)){ // correct?
return node;
}
}
return false;
}
function bfs(root,visitFunc){
var queue = [];
queue.push(root);
root.visited = true;
visitFunc(root);
while(queue.length) {
var node = queue.pop();
// Loop over unvisited child nodes
var child;
while((child = getUnvisitedNode(node.children))) {
child.visited = true;
visitFunc(child);
queue.push(child);
}
}
}
/**
* Solves the full system.
* @method solve
* @param {Number} dt
* @param {World} world
*/
IslandSolver.prototype.solve = function(dt,world){
var nodes = [],
bodies=world.bodies,
equations=this.equations,
Neq=equations.length,
Nbodies=bodies.length,
subsolver=this.subsolver,
workers = this._workers,
workerData = this._workerData,
workerIslandGroups = this._workerIslandGroups;
// Create needed nodes, reuse if possible
for(var i=0; i!==Nbodies; i++){
if(this._nodePool.length)
nodes.push( this._nodePool.pop() );
else {
nodes.push({
body:bodies[i],
children:[],
eqs:[],
visited:false
});
}
}
// Reset node values
for(var i=0; i!==Nbodies; i++){
var node = nodes[i];
node.body = bodies[i];
node.children.length = 0;
node.eqs.length = 0;
node.visited = false;
}
// Add connectivity data. Each equation connects 2 bodies.
for(var k=0; k!==Neq; k++){
var eq=equations[k],
i=bodies.indexOf(eq.bi),
j=bodies.indexOf(eq.bj),
ni=nodes[i],
nj=nodes[j];
ni.children.push(nj);
ni.eqs.push(eq);
nj.children.push(ni);
nj.eqs.push(eq);
}
// The BFS search algorithm needs a traversal function. What we do is gather all bodies and equations connected.
var child, n=0, eqs=[], bds=[];
function visitFunc(node){
bds.push(node.body);
var Neqs = node.eqs.length;
for(var i=0; i!==Neqs; i++){
var eq = node.eqs[i];
if(eqs.indexOf(eq) === -1){
eqs.push(eq);
}
}
}
// Get islands
var islands = [];
while((child = getUnvisitedNode(nodes))){
var island = new Island(); // @todo Should be reused from somewhere
eqs.length = 0;
bds.length = 0;
bfs(child,visitFunc); // run search algo to gather an island of bodies
// Add equations to island
var Neqs = eqs.length;
for(var i=0; i!==Neqs; i++){
var eq = eqs[i];
island.equations.push(eq);
}
n++;
islands.push(island);
}
this.numIslands = n;
// Solve islands
var e = this.beforeSolveIslandEvent;
for(var i=0; i<islands.length; i++){
var island = islands[i];
e.island = island;
this.emit(e);
island.solve(dt,this.subsolver);
}
};