Be my fan on FacebookThe fastest way to find the distance between two points
- July 29, 2010 by Emanuele Feronato
- Filed under PROgramming, Php | 19 Comments
While I was reading Claytus Hood Tower Defense case study I was impressed by this:
To estimate the distances and so check the range, I use Manhattan distance formula, less accurate but faster than Euclidian distance
Named after the grid layout of most Manhattan streets, it’s a form of geometry in which the usual metric of Euclidean geometry is replaced by a new metric in which the distance between two points is the sum of the absolute differences of their coordinates (for more information refer to Wikipedia’s Taxicab geometry page).
Now the question is: is Manhattan distance really faster than Euclidian distance?
For the following test I used PHP, but feel free to make it in any other language and I’ll be glad to publish your results.
First, I set two variables, named $x_dist and $y_dist, to 10 and 20 respectively, then to -10 and -20
These variables should represent the x and y distance between two points.
I generated a script to calculate a million times the distance with Euclidean geometry this way:
$distance = sqrt($x_dist*$x_dist+$y_dist*$y_dist);
The server took an average 566.56 milliseconds to give me the response.
I thought most of the time is spent to calculate the square root, so a smart programmer could remove the square root and eventually compare the result with a given number multiplied by itself… so if the distance has to b less than 30, I will check if it’s less than 30*30=900.
This way to determine the distance:
$distance = $x_dist*$x_dist+$y_dist*$y_dist;
took an average time of 204.43 milliseconds to generate a million results.
Then it’s time to use Manhattan distance:
$distance = abs($x_dist)+abs($y_dist);
This method took 694.83 milliseconds… the slowest so far… so I tried to avoid using abs this way:
if($x_dist<0){ $x_dist *=-1; } if($y_dist<0){ $y_dist *=-1; } $distance = $x_dist+$y_dist;
and I got 243.11 milliseconds. Trying with positive or negative starting distance values did not change response times in a valuable manner.
So I would say: “Myth Busted“.
Do you agree?
(11 votes, average: 2.73 out of 5)
Loading ...
hi emmanuelle, when are you gonna publish some flash mobile game tuts? =)
PD:I love your blog :P
the “pure” manhattan is slower than the “pure” euclidian, and the modified ones see the euclidian one faster than manhattan
Though what you postulate is technically true won’t the added time to “compare the result with a given number multiplied by itself” eventually add up to way more time spent then the ~39 milliseconds more time that the Manhattan takes the one time. I guess the question is: “do you compare the distance more times then you calculate it?”
Hi Emanuele, why do you say “Myth busted”? The calculation speed was more than twice as fast using the Manhatten distance vs the Euclidean.
Euclidian: 566.56ms
Euclidian(Optimized): 204.43ms
Manhattan: 694.83ms
Manhattan(Optimized): 243.11ms
Isnt
$distance = $x_dist+$y_dist;
if($distance <0){
$distance *=-1;
}
enough?!
Not sure if there is a faster way to get rid of the "-" in php.
Ehhh, forget my post – just realized that the “max” distance is wanted. Too early to write “clever” comments..
var point1:Point = new Point(10,20);
var point2:Point = new Point(-10,-20);
// Euclidian
var timer:int = getTimer();
for(var i:uint = 0; i < 1000000;i++) (Math.sqrt(point1.x*point2.x+point1.y*point2.y));
trace("Euclidian time: " + String(getTimer() – timer));
// Taxicab
timer = getTimer();
for(var i:uint = 0; i < 1000000;i++) (Math.abs(point1.x-point2.x)+Math.abs(point1.y-point2.y));
trace("Taxicab time: " + String(getTimer() – timer));
——————————-
Euclidian time: 205
Taxicab time: 164
Hi! Here is my AS3 Benchmark :
function distManhattan(p1:Point, p2:Point):Number {
return Math.abs(p1.x-p2.x)+Math.abs(p1.y-p2.y);
}
function distEuclidian(p1:Point, p2:Point):Number {
return Math.sqrt(Math.pow((p1.x-p2.x),2)+Math.pow((p1.y-p2.y),2));
}
var p1:Point = new Point(10, 20);
var p2:Point = new Point(55.2, -28);
var d:Number;
var elapsedTime:Number;
var t:Number;
t = getTimer();
for(var i:int=0; i<1000000; i++)
{
d = distEuclidian(p1, p2);
}
elapsedTime = getTimer() – t;
trace("Euclidian Benchmark : "+elapsedTime);
//Output = Euclidian Benchmark : 293
t = getTimer();
for(var j:int=0; j<1000000; j++)
{
d = distManhattan(p1, p2);
}
elapsedTime = getTimer() – t;
trace("Manhattan Benchmark : "+elapsedTime);
//Output = Manhattan Benchmark : 177
What do you think about that? In my test Manhattant is the fastest, isn't it?
Euclidian Benchmark : 293ms
Manhattan Benchmark : 177ms
Very useful. Thank you for this post.
Also, you should check out the inverse square root (as used in Quake) – much faster.
http://en.wikipedia.org/wiki/Fast_inverse_square_root
I notice that Emanuele used PHP to show that Euclidean is faster than Manhattan, while the other scripts proving that Manhattan is faster than Euclidean are written using AS3.
Could this difference be an issue based on how these two languages are compiled?
I think that the execution times of sqrt() and abs are compiler dependent. That may means that the fastest method is also compiler dependent.
While experimenting I found that this is the fastest way:
if($valx*$valy<0)
{
$distance=$valx-$valy;
}
else
{
$distance=$valx+$valy;
}
tested on php and actionscript.
The result may be a positive or negative number but that is not a problem since you can check your distance like (-$dist<$distance<$dist).
Sorry, but I think it is not a question of speed, but a question what kind of result you like to get.
For tile-based games the Taxicab is the right one, if you like to get the real distance you need the euclidean-algo.
Maybe I´m wrong, because I can´t believe that you all ignore the fact, that you can´t compare them.
I think you are right. Finding distance for ranges of fire like the one used in TD games doesn’t need to be accurate. So taxicab can be used. Otherwise when you need collisions euler MUST be used. The question is optimizing both to be as fast as possible.
Emanuele’s method of squaring the distance you want instead of sqrting the measured distance is the fastest IMO (only 3 multiplications and one addition)
With collision response, you can either calculate response with vectors or trig. Trig is just wayyy too cpu expensive, so most people use vectors.
When you use vectors, to calculate the unit vector, you NEED the magnitude (distance), not the magnitude squared. So i tried to find a fast way to calculate the sqrt.
I got this. Its the newton method; very fast and the number of significant figures DOUBLES with every loop.
function sqrt(n)
a = guess
for (accuracy) {
a = 0.5(a + (n/a))
}
return a
Generally, the precompiled Math.sqrt is faster than this for general squareroots, since this is the method it uses =)
But, if you have a tile-based game, or broadphase quadtrees, or grids, the ability to guess and determine accuracy really lowers CPU load. Thats because the computer automatically guesses 1, but since you know the squares apart, you can give a much better guess. Also, you generally don’t need 16bit precision. 3 loops on this will give 8 significant figures, (with a good guess), which is more than anyone needs.
Try it!
Actually you don’t need 3 multiplications. Only 2 is enough, because you can store the value needed for distance comparison.
There is no “myth busted” here. This kind of optimization are for compiled language. This benchmark means nothing when done with PHP because most of the CPU cycles are used to parse the code and not to compute the result.
Creating a fast PHP code is more a matter of knowing how PHP translate the code, seek for variables in his dictionary, reserve and release memory…
It would be interesting to run your PHP tests under HIP HOP PHP or APC cache.
If you write the code in ASM and do it right, computing manathan distance is times faster than just parsing PHP version of the code.
To finish this kind of code is just bad
if($x_dist<0){
$x_dist *=-1;
}
It require a conditional JMP and a multiplication where you just need to set the sign bit of the variable $x_dist to positive.
“It require a conditional JMP and a multiplication where you just need to set the sign bit of the variable $x_dist to positive.” > I’m wrong for this. Changing sign is not that simple, we must add one unit if the number was negative.
But since we are working on a not accurate algorythm one unit won’t make a big difference.
You failed math due to they are not match result for distance answer.
if($x_dist<0){
$x_dist *=-1;
}
if($y_dist<0){
$y_dist *=-1;
}
$distance = $x_dist+$y_dist;