# Efficient Distance Calculation?

This topic is 4579 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm currently using:
public static double GetDistance( ref float x1, ref float x2, ref float y1, ref float y2 )
{
return Math.Sqrt( ( x1 - x2 )*( x1 - x2 ) + ( y1 - y2 )*( y1 - y2 ) );
}


I call this function many, many, many times per second server-side on my 2D space sim. The number of calls grows exponentially for each player that joins the server, so my question is, am I doing this the best way? Is there a cheat to get around doing it so much? Thanks, Cyric

##### Share on other sites
Not really, if you are having performance issues with a 2D space sim you should probably be looking at the bigger picture. There may be some other areas you can improve performance on, quadtrees perhaps? i don't know what is causing the problems but i'm sure there are other areas that you should think about optimising first.

The only trick with distances that i can think of is that if you are just comparing distance, you can compare the distances squared which avoids using the square root function. But you probably already knew that.

##### Share on other sites
One optimization that can often be done is to simply not do the square root. Use this when all you care about is comparing two distances to each other to see which one is larger. In this situation, the square root is absolutely useless, as it doesn't change the result of the comparison.

Me.Slow == true[/edit]

##### Share on other sites
x = x1-x2;
y = y1-y2;
return sqrt(x*x + y*y);

Just shaved off 2 subtracts

##### Share on other sites
Quote:
 Original post by Raymond_Porter420Just shaved off 2 subtracts

Common subexpression elimination.

##### Share on other sites
Cool. I did not know that.

##### Share on other sites
to increase speed u can remove the square root and work with higher values [smile]

##### Share on other sites
Quote:
 Original post by DevLiquidKnightto increase speed u can remove the square root and work with higher values [smile]

They won't necessarily be higher: sqrt(x) > x is true for any x < 1.0

##### Share on other sites
I would suggest returning float (not double) and inlining it. A good compiler should eliminate the common sub expressions without creating the 2 extra variables.

I always...when in doubt cheat by looking at what the compiler actual does by examining the output .asm or .cod files.

##### Share on other sites
Just out of curiosity what are the circumstances by which you have to keep using the distance formule "many, many, many times per second." ?

##### Share on other sites
No idea why you'd have to compute distances every frame, but in any case either don't use sqrt like others said, or there are ways of approximating sqrt, which I dare not go into.

##### Share on other sites
You may also be advised to look at your design and to why your execution is O(N^N)

[I'm assuming you actually did mean exponential rather than something like O(N^2)]

You can achieve a lot by saving the results of distance computations (the old space vs execution time trade-off).

##### Share on other sites
you could try an approximate distance/sqrt algorithm.

##### Share on other sites
You could try changing your design so that more of the calculations take place on the client side, e.g distances to static or slow moving objects.

##### Share on other sites
I heard somewhere that using double now is actually faster than using floats on modern computers.

Is this true?

##### Share on other sites
Hey, im new here and im a junior programmer pretty much, but i did some projects for mathematic calculators and collision detection....i know that newton had a very efficient method of solving square roots.....i also have a method, im not sure if its as fast as you'd like but the good thing about it is that u can give it the accuracy you want. If you need the code i'll be glad to share

##### Share on other sites
I heard somewhere that using double now is actually faster than using floats on modern computers.

Is this true?

i beleive this is true only on 64 bit processors with 64 bit o/s's

##### Share on other sites
Quote:
 Original post by lunar-blueHey, im new here and im a junior programmer pretty much, but i did some projects for mathematic calculators and collision detection....i know that newton had a very efficient method of solving square roots.....i also have a method, im not sure if its as fast as you'd like but the good thing about it is that u can give it the accuracy you want. If you need the code i'll be glad to share

Newton refinement approximation:
It's not as efficient as a sqrt done in hardware, I bet. Division is pretty slow.

##### Share on other sites
If you are doing collision testing, there are much better ways. (just a guess).

Also note, you are missing abs's in your distance formula

tmpa = x1 - x2; tmpb = y1 - y2; out = tmpa + tmpb; outa = tmpa - tmpb; r = roa + rob; //Set collision boundries, roa = Radius of object a, same for robr *= r; //Square the other side of the equasion. ra = -r;if (out > r) | (outa < ra) {    //Collision}

This works out about equal to

if (sqrt(abs(x1 - x2) * abs(x1 - x2) + abs(y1 - y2) * abs(y1 - y2))) > r {}

Just probably a bit faster for it.

You could also try using integers instead of floats. (unless you really need them).

From,
Nice coder

##### Share on other sites
Ok, so if you're having that big O n^n problem you should use an oct-tree or break up your space into sectors and give each of them an oct-tree.

Also, you can use a combination of dirty distance methods and accurate ones. So I'd say use something really dirty for most distances, but once you get close(like for a collision or something) re-calc for something more accurate.

Dirty method one: The octagon
// perfect on the axis, 18% average error
// 8+ times faster
// assuming all numbers are positive, or changed to be... x = abs(x);
d = 0.5*(x + y + ... + max(x, y, ..)); // generally
d = 0.5*(x + y + (x>y)?x:y); // c++ish 2d case

Dirty method two: Know your floating point, EDIT: this is for 32bit float
// perfect for powers of 2, 1.8% average error
// 6+ times faster
union{float f[2]; // store your x, y & z
unsigned int i[2];};// temp
i[0] <<= 1;
i[1] <<= 1;
i[0] -= 0x3F800000;
i[1] -= 0x3F800000;
f[0] += f[1];
i[0] += 0x3F800000;
i[0] >>= 1;
// f[0] is your final distance

EDIT: unless you're squaring complex numbers(normal float doesn't support) then you don't need to abs() your displacements (x1-x2)... we forgive him, the hour is late...

I see through the lies of the Jedi... to learn the true power of the code one must look at both sides and find their true power!

[Edited by - ismakefire on June 4, 2005 4:07:57 AM]

##### Share on other sites
Quote:
 Original post by lunar-blueHey, im new here and im a junior programmer pretty much, but i did some projects for mathematic calculators and collision detection....i know that newton had a very efficient method of solving square roots.....i also have a method, im not sure if its as fast as you'd like but the good thing about it is that u can give it the accuracy you want. If you need the code i'll be glad to share

I use my own method, wich is the binary method.

Basically, you express number n in the form a * 2^0 + b * 2^1.... then you halve each exponent.

Dead simple in hw. (with some mods, it can be done without transisters at all).

In sw, you need tables tho...

Theres other things, like binary trees, ect. Which can be faster...

From,
Nice coder

##### Share on other sites
"Nice coder"

Can you please show an example of this process of sqrt-ing? (I don't mean code example - I mean just pick a number and show the process of sqrt-ing it)

##### Share on other sites
Quote:
 Original post by cyric74I'm currently using:*** Source Snippet Removed ***I call this function many, many, many times per second server-side on my 2D space sim. The number of calls grows exponentially for each player that joins the server, so my question is, am I doing this the best way? Is there a cheat to get around doing it so much?Thanks,Cyric

WHy do you need the distance, and do you need the actual value or just use it for comparison against a threshold???

If only comparison, you need only compare the squares (no need for sqrt).

If it can be a rough distance to compare, you can do the clasic box test:
rough_dist = MAX(x2-x1, y2-y1, z2-z1);

You can also do whats called lazy evaluation where if you know the 2 objects
will not need to be processes if they are outside of a threshold distance, you first do a rough dist calc and then if its inside of your threshold then you do the costlier sqrt calculations.

Another estimation calc (that is only a few percent off) for 2D is adding the length of the longest delta (X or Y) to the shortest delta (Y or X) divided by 2.

dx = abs(x2-x1)
dy = abs(y2-y1)
if dx>dy dist=dx+(dy/2) else dist=dy+(dx/2)

Another idea (depending on how it is used) is to store the distances in a table
and then only update them on an interval proportinal to the distance (probably by distance intervals of squares).

##### Share on other sites
that works just fine for an int value into float, but that's basiclly what the 2nd method I showed does, but it transfers from powers of 2 linearly(which is why it's so fast). I've tried it and any use of tables will either be inaccurate(using an incomplete table) or slows it down to the point where you should just use a sqrt(if you use a complete table or linearly interpolate). Having a 18%, 2% and a 1%< function isn't a bad combination.Just remember to use them right. So if you're testing something bounded by 10 then use 12 for the first function(18%) and like 10.2 for the 2nd one(1.8%). Don't be afrad of using a function with a moderatly sized error, because all the floating point calculations you make have errors... we just like to ignore them :)

So I'd say use the three functions in conjuction with quad-trees(oct-trees are 3d) if you want a real speed up. Maybe even make the real memory for preformace trade off and slice up your space.

In the end, you are the programmer. Run some time tests and see what ranges work the best, and maybe just drop the calculation quality when there's a slow down rather then always having some distances a certen % off.

EDIT: will ppl PLEASE stop posting how you can compare two vector distances without the square root, it's been said 3 times! It would be nice if ppl would read the thread rather then just posting everything they know!

##### Share on other sites
Quote:
 Original post by Nice CoderAlso note, you are missing abs's in your distance formulaif (sqrt(abs(x1 - x2) * abs(x1 - x2) + abs(y1 - y2) * abs(y1 - y2))) > r {}From,Nice coder

Please define a number n where (n * n) != (abs(n) * abs(n) + e)
Where e is a small value.

As for the problem, you really have to tell us a bit more of what you are doing?

##### Share on other sites

This topic is 4579 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.