Build 10 classic Flash games and learn game development along the way with this ultra-fast paced game development course.

If you love this blog, this is the book for you.

Get the source code of 12 commercial Flash games, which have been loaded more than 50 million times!

Learn from real world successful examples.

Get it now

Box2D for Flash Games teaches you how to make Flash physics games from scratch with the most advanced features.

Create the new Flash game smashing hit.

# The fastest way to find the distance between two points

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:

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?

Rate this post: (19 votes, average: 3.00 out of 5)

## This post has 22 comments

1. ### matakukos

on July 29, 2010 at 1:00 am

hi emmanuelle, when are you gonna publish some flash mobile game tuts? =)

2. ### Steve

on July 29, 2010 at 4:09 am

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?”

3. ### Scott

on July 29, 2010 at 7:05 am

Hi Emanuele, why do you say “Myth busted”? The calculation speed was more than twice as fast using the Manhatten distance vs the Euclidean.

4. ### ThievingSix

on July 29, 2010 at 7:11 am

Euclidian: 566.56ms
Euclidian(Optimized): 204.43ms

Manhattan: 694.83ms
Manhattan(Optimized): 243.11ms

5. ### Vega

on July 29, 2010 at 7:43 am

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.

6. ### Vega

on July 29, 2010 at 7:48 am

Ehhh, forget my post – just realized that the “max” distance is wanted. Too early to write “clever” comments..

7. ### Nathan

on July 29, 2010 at 8:56 am

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

8. ### Rafarel

on July 29, 2010 at 4:03 pm

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

9. ### JZ

on July 29, 2010 at 5:46 pm

Very useful. Thank you for this post.

10. ### Alex MacCaw

on July 29, 2010 at 5:51 pm

Also, you should check out the inverse square root (as used in Quake) – much faster.

http://en.wikipedia.org/wiki/Fast_inverse_square_root

11. ### Emanuele Feronato

on July 29, 2010 at 6:36 pm

the “pure” manhattan is slower than the “pure” euclidian, and the modified ones see the euclidian one faster than manhattan

12. ### AL

on July 29, 2010 at 11:05 pm

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?

13. ### xPy

on July 30, 2010 at 11:13 am

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).

14. ### Martin

on July 31, 2010 at 1:21 am

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.

15. ### Kaustav

on August 1, 2010 at 6:06 am

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!

16. ### Astro75

on August 1, 2010 at 10:31 am

Actually you don’t need 3 multiplications. Only 2 is enough, because you can store the value needed for distance comparison.

17. ### Bokan

on August 17, 2010 at 4:10 pm

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.

18. ### Bokan

on August 17, 2010 at 4:42 pm

“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.

19. ### Justin

on August 26, 2010 at 2:46 pm

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;

20. ### Chris Churn | Website and application development

on November 17, 2010 at 1:46 am

[...] out the distance, I’ve used the Euclidean geometry method as described on this great article: http://www.emanueleferonato.com/2010/07/29/the-fastest-way-to-find-the-distance-between-two-points/ This is the function; p1 is the tower x,y. p2 is the mouse (we’ve got no enemies yet) and [...]

21. ### Anthony Tambrin

on May 17, 2011 at 4:15 am

Would it yield faster result if we use negation instead of multiplication?

if(\$x_dist<0){
\$x_dist = -\$x_dist;
}
if(\$y_dist<0){
\$y_dist = -\$y_dist;
}
\$distance = \$x_dist+\$y_dist;

22. ### pio11

on May 18, 2012 at 1:12 am

Good explanation of Taxi Cap is here http://jwilson.coe.uga.edu/MATH7200/TaxiCab/TaxiCab.html