HTML and CSS Reference
In-Depth Information
object0 with object1, object2, object3, object4, object5
object1 with object0, object2, object3, object4, object5
object2 with object0, object1, object3, object4, object5
object3 with object0, object1, object2, object4, object5
object4 with object0, object1, object2, object3, object5
object5 with object0, object1, object2, object3, object4
Look at the first test on the first row:
object0
with
object1
. Now look at the first test on the second row:
object1
with
object0
—that's the same thing! If
object0
is not hitting
object1
,
object1
is also not
hitting
object0
. Or if one is hitting the other, you can be sure the other is hitting the first. There are many
of these double checks in there. If you remove all the duplicate tests, you get this:
object0 with object1, object2, object3, object4, object5
object1 with object2, object3, object4, object5
object2 with object3, object4, object5
object3 with object4, object5
object4 with object5
object5 with nothing!
You see that in the first round of tests, you're testing
object0
with every other object. Because no other
object needs to test against that one again, you drop
object0
off the list. Then
object1
tests against the
remaining objects, and you drop it off the list. By the time you get to the last one,
object5
, every other
object has already tested itself for a collision with it. There's no need to test it against anything. The result
is that you're down to 15 tests, so you see why our initial solution ends up being double what is needed.
To code this, you still have two nested loops—a
for
loop within the
forEach
iteration—but now it looks
like this:
objects.forEach(function (objectA, i) {
for (
var j = i + 1
; j < objects.length; j++) {
var objectB = objects[j];
if (hitTestObject(objectA, objectB) {
//do whatever
}
}
});
In the inner
for
loop, you always start with one higher than the index of the outer iteration. This is because
you've already tested everything lower, and you don't want to test the same index, which, as you saw,
would be testing an object against itself. This lets you get rid of that check. The result is just a few
characters different from the original code, but gives you a 100% performance increase!
Also, even beyond its performance impact, in many cases, doing double hit testing might have unwanted
results. If you're changing the velocity or some other value when you detect a collision, you may wind up
changing it twice, resulting in an undetermined, and hard to debug, effect.
If this topic interests you, and you'd like to dig a lot deeper, this is all a part of Combinatorics, a field of
math concerned with problems of selection and arrangement, or: How to count without counting.