H3XED

Fast Distance Threshold Formula AS3, C++, Java, Python

Nov 17, 2010   Programming   Nick Vogt   Comments
Please note that this post is over a year old and may contain outdated information.
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)
Share This Post
Twitter

Comments (0)

Share This Post
Twitter
H3XED © Nick Vogt   RSS   Policies   Twitter