Collision Detection - HTML5 Animation with JavaScript - page 212

test them so that you don't miss any possible collisions. Furthermore, as you have more and more objects
being tested, it becomes very important to perform your tests with some kind of efficiency in mind.
Basic multiple-object collision detection
With just two objects, only one collision is possible—A versus B. With three objects, you have three
possibilities: A-B, B-C, and C-A. Four objects give you six collisions, and five objects give you ten
collisions. When you get up to 20 objects, you need to take into account 190 separate collisions! That
means that in your drawFrame function, you need to run a collision detection calculation 190 times.
That's enough as it is, so you certainly don't need to be adding any more unnecessary hit testing. But
many beginners wind up doing not just a few extra hit tests, but exactly twice as many as necessary! For
20 objects, they do 380 hit test (20 objects each testing 19 others, or 20 × 19 = 380). You can see why you
should have a solid understanding of this subject.
To understand the problem, let's take a look at what needs to be done, and how it is often approached.
Say you have six objects, named object0 , object1 , object2 , object3 , object4 , and object5 . You
have them moving around nicely, bouncing or whatever, and you want to know when any one of the
objects hits any other one. The obvious solution is to make two nested loops. The outer one iterates
through each of the six objects, gets a reference to each one in turn, and then loops through again,
comparing it to each of the others. Here it is in pseudo-code:
objects.forEach(function (objectA, i) {
for (var j = 0; j < objects.length; j++) {
var objectB = objects[j];
if (hitTestObject(objectA, objectB)) {
//do something
}
}
});
That's 36 hit tests for six objects. Seems reasonable, but this code has two huge problems.
First, take a look what happens the first time through it. The variables i and j will both equal 0. So
objectA will hold a reference to object0 , as will objectB . That means you're testing an object against
itself, which is a waste of a calculation. You could make sure that objectA != objectB before
performing the hit test, or you could even go simpler and just make sure i != j . Then you get
something like this:
objects.forEach(function (objectA, i) {
for (var j = 0; j < objects.length; j++) {
var objectB = objects[j];
if ( i !== j && hitTestObject(objectA, objectB)) {
//do something
}
}
});
That eliminated six hit tests, so you're down to 30, but this is still too many. Let's write out the exact tests
you're doing. You are comparing the following: