Archive
This post is archived and may contain outdated information. It has been set to 'noindex' and should stop showing up in search results.
Fast Distance Threshold Formula AS3, C++, Java, Python
Nov 17, 2010ProgrammingComments (0)
Most game programmers are familiar with the distance (magnitude) equation and how inefficient it is. Using a square root is a costly function that usually can't be afforded many times per frame. Here is a much more efficient distance equation for situations in which you want to check the distance against a threshold (such as determining if two bounding spheres collide).

Here is the original distance formula:

Distance = Sqrt( (x2 - x1)² + (y2 - y1)² )
And here it is expanded into simple multiplication :

Distance * Distance = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)
(For 3D be sure to add the z part of the formula)

Using simple multiplication results in extremely fast calculations. Here are some performance tests I ran in Actionscript 3. Other programming languages should be similar. I started with the traditional distance equation:

dist = Math.sqrt(Math.pow(x2 - x1,2) + Math.pow(y2 - y1,2));
if(dist < minDist)
{
// Perform action
}

Looping the above code 10,000,000 iterations resulted in a total process time of 4387 milliseconds. Now here is the simple multiplication version:

dist = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
if(dist < minDist * minDist)
{
// Perform action
}

The above only took 172 milliseconds!

Note: For both tests I initialized the required variables before any timing, to eliminate initialization time from the test.

I'm sure most game programmers have used the above formula or something similar before, but for those still struggling I hope it will help. Unfortunately it doesn't help as much when you need to use the distance to scale another value (such as using distance to determine how much splash damage to take), as you will be scaling it exponentially! (you can use threshold steps to work around this of course)
Comments (0)
Add a Comment


Please review the commenting policy prior to commenting.
No comments yet