Quick distance checking!

Recap

A while ago (ah hem 8 years ago) I made a post about how to implement basic bounding box coliision detection. I thought I would make a post about how to use a little short-cut method to determine if two objects are nearby each other.

The Problem

If we have a world full of objects, which are anything from the trees, and grass to the little particles racing around the screen we do not want to needlessly check every object with every other object if we do not have to. For instance, an object on the left side of the screen could not possibly collide with an object on the right side of the screen.

You want to eliminate as many of these expensive mathematical calculations as possible. Or perhaps you just want to see if two objects will affect each other anytime soon. There are a couple things we need to know about the objects in order to quickly make the determination if we want to check them. We might be currently checking collisions on objects that will never touch each other. Each time we can eliminate a future check it is can save us from wasting a check. Although not as big of a problem with modern day graphics if you use the GPU for rendering. Still it will help update cycles which that we run on the CPU and anything that is still prone to bottlenecks.

There may also be other areas where you want to quickly find all objects close or nearby each other. I plan to cover some partitioning strategies in the future that will help eliminate massive amounts of loops from being necessary.

The Math

We want to determine if two objects are close to each other. We need to at least have a radius around the objects in order to calculate whether or not they are within another objects radius. So we use the distance between the two objects which is calculated as

// SquareRootCalculator
double d = Math.sqrt( Math.pow(object1.x - object2.x, 2) + Math.pow(object1.y - object2.y,2));

We can improve the speed of this a little bit by short-cutting the math and applying some variables.

// SingleDiffCalculator
double diffX = object1.x - object2.x;
double diffY = object1.y - object2.y;
double distSquared = diffX * diffX + diffY * diffY;

No Math routine calls and eliminate the need to calculate difference twice. Although the compiler and JIT may not use a register for diffX and diffY they may instead decide to use the stack which is less optimal but probably negligent difference in performance. You can expand it out to be a long equation.

// DirectFromObjectsCalculator
double distSquared = (object1.x - object2.x) * (object1.x - object2.x) + (object1.y - object2.y) * (object1.y - object2.y);

And because I like to take things farther than they need to be here accessing the x and y variables may not be efficient enough since the objects were probably allocated on the heap and may not be in cpu cache lets force them to be put on the stack which is probably in cache still.

// DirectFromStackCalculator
double ox1 = object1.x;
double oy1 = object1.y;
double ox2 = object2.x;
double oy2 = object2.y;
double distSquared = (ox1-ox2) * (ox1-ox2) + (oy1-oy2) * (oy1-oy2);

Because I like to be thorough lets see if that matters at all lets put them into a utility class and use a Unit Test and get some output. And lets do it in an object oriented way.

Ok so there was not much of a difference or enough to be noticable between methods.

283 ms for 10000000 using DirectFromObjectsCalculator
263 ms for 10000000 using DirectFromStackCalculator
283 ms for 10000000 using SingleDiffCalculator
268 ms for 10000000 using MathCalculator
304 ms for 10000000 using SquareRootCalculator

Another run:

336 ms for 12000000 using DirectFromObjectsCalculator
347 ms for 12000000 using DirectFromStackCalculator
391 ms for 12000000 using SingleDiffCalculator
394 ms for 12000000 using MathCalculator
409 ms for 12000000 using SquareRootCalculator

These results did not change much on repeated runs and varied a bit between winners the only obvious looser was the SquareRootCalculator obviously.

So no need to go drastically changing your coding style use variables if you want to clean things up. Doing temporary calculations like the SingleDiffCalculator.

If you would like to fiddle with the code then you can find it here.

The Check

So the final piece which I should have mentioned before going into all that testing above, is the comparison of against the radius.

The calculation returns the squared distance so we need to see if the square of the distance from the objects centers is less than the square of the sum of the radii.

Something like

double radiusSquared = Math.pow(object1.radius + object2.radius, 2);
if(distSquared < radiusSquared) {
  // objects could be colliding
}else{
  // objects not colliding
}

That should be about it. Hopefully I will get some time to back fill that repo with examples from earlier snippets I posted.