# Detecting collision of multiple moving objects

I have wrote a simple game that has a 100 balls bouncing off the borders of the canvas. Each ball is an instance of ball class function that has the following definition:

var cnv = document.getElementById("mycanvas");
var ctx = cnv.getContext("2d");
...
...

function ball() {
// at instantiation, set the ball in a random position
this.x = parseInt(Math.random()*cnv.width) +1;
this.y = parseInt(Math.random()*cnv.height) +1;
this.size = parseInt(Math.random() * 10) + 1;

// and give the ball a random speed at a random direction
this.x_speed = parseInt(Math.random()*10) +1;
this.y_speed = parseInt(Math.random()*10) +1;
if (this.x_speed>5) {
this.x_speed *= -1;
}
if (this.y_speed>5) {
this.y_speed *= -1;
}

// draw() and update() for the instance will be called from the main game loop
this.draw = function() {
ctx.beginPath();
ctx.fillStyle = "white";
ctx.arc(this.x,this.y,this.size,0,Math.PI*2,true);
ctx.fill();
};

this.update = function() {
this.x += this.x_speed;
this.y += this.y_speed;

if (this.x >= cnv.width || this.x<=0) {
this.x_speed *= -1;
}
if (this.y >= cnv.height || this.y <= 0) {
this.y_speed *= -1;
}
}
}


In the main game loop, I call gameUpdate() which in turn calls update() for each ball, like so:

var balls = [];   // array to hold all instances
...
...
function gameStart() {

for(var i=0;i<100;i++) {
balls.push( new ball() );   // create an instance and store its reference
}
}

function gameUpdate() {
for(var i=0; i<balls.length;i++) {
balls[i].update();     // this ensures that each ball moves on its own

}
}


Now my question is: How can I manage to detect collision between all of the instances of balls ?

Here is my attempt, but I already know it is not efficient:

function detectCollision() {
for(var i=0;i<balls.length;i++) {
for(var j=0;j<balls.length-1;j++) {
if (i !== j) {   // make sure we have two different balls to check with
// assuming that collision() exists and checks x,y for each parameter and return boolean
if (collision(balls[i],balls[j])) {
console.log("boom!");
}
}
}
}
}


What is a better way for checking collision of moving objects?

• An Octree for space partitioning is the best solution. you split the game area into many smaller areas.　Then you perform the best between the balls only in the same areas. Keep in mind that if the balls are all in the same area the worst case is still the same as a On^2 – gimpycpu Nov 1 '16 at 2:26
• ^^^ I meant quadtree since you are in 2d but same principle. – gimpycpu Nov 1 '16 at 2:37