Pythagorean Distance Between Two Points

by Michael James Williams on May 8, 2009 · 26 comments

in Maths

screenshot

When programming almost any sort of game you will often need to work out the distance between two objects. How far is the player from the exit point? Are the enemies close enough to hear the hero’s footsteps? Can this house be built so close to that other one?

Fortunately there’s a very simple formula that’s commonly used to do this. It can be summarised in one line of code:

?View Code ACTIONSCRIPT3
distance = Math.sqrt( ( firstObject.x - secondObject.x ) * ( firstObject.x - secondObject.x ) + ( firstObject.y - secondObject.y ) * ( firstObject.y - secondObject.y ) );

…admittedly it is a long line.

If all you need is an easy function to work out distance, you can just copy and paste the above. But if you want to find out more about this, including why the function works, how to speed it up, and what to do in 3D (or even 4D), read on.

How does this work?

Take a look at this situation again:

screenshot

(Note that I’m using Flash’s convention of having the y-coordinate increase as you move down the screen, which is the opposite to normal mathematical convention. As we’ll see, it doesn’t really make a difference.)

We can’t figure out the length of that line without a ruler. If we add a couple more lines, however:

screenshot

…now things become much easier. The horizontal line goes from (10, 5) to (25, 5), so it’s obvious that its length is (25 – 10 =) 15 units. The vertical line goes from (25, 5) to (25, -5), so again its length is obvious: 10 units.

screenshot

By changing this so that we only had to work in one dimension (either width or height), we made things very simple for ourselves. Now we can make things even simpler by removing everything except the lines:

screenshot

Have you ever used Pythagoras’ theorem? It’s one of those stereotypical things they use on TV to make a character sound smart, so you’ve probably heard it even if you don’t know what it means:

The square of the hypotenuse of a right-angled triangle is equal to the sum of the squares of the other two sides.

That’s needlessly complicated; less so if you know that hypotenuse just means longest side.

You can probably see where I’m going with this. We have a right-angled triangle, we know the lengths of the two shorter sides, and we want to find out the length of the hypotenuse.

So first we have to find “the sum of the squares of the other two sides”. That’s just 10-squared plus 15-squared, i.e. ( 10 * 10 ) + ( 15 * 15 ), so 100 + 225, which equals 325.

That gives us “the square of the hypotenuse”, or the length-squared of the longest side. To get the actual length, we need to find the square-root of this. You can use a calculator for this, but I usually just Google sqrt(325). Either way, you get your answer: 18.03 units (to two decimal places).

screenshot

Seems like a lot of work, but like I said, it can be compressed to a single line of code:

?View Code ACTIONSCRIPT3
distance = Math.sqrt( ( firstObject.x - secondObject.x ) * ( firstObject.x - secondObject.x ) + ( firstObject.y - secondObject.y ) * ( firstObject.y - secondObject.y ) );

And of course you can put that in a function and use it over and over again. In fact, in AS3 you can use the built-in Point.distance() function to do just that.

It’s Hip to Be a Square

The slowest part of this function is the square root. It’s a lot slower to find the square root of something than it is to square it; perhaps that’s not surprising as squaring something is easy to do on paper, but square rooting is such a long and tedious process that it isn’t even taught in school.

When I say “slow” I’m talking in terms of milliseconds (or even less time) of course, so it doesn’t seem like a big deal. It becomes a problem when you have hundreds of these checks going on every tick, and every little bit of speed you can squeeze out of your game counts. Fortunately, in a lot of cases we can remove the need for a square-root entirely.

For example, suppose we have a landmine that we want to explode when the player gets within 25 pixels.

?View Code ACTIONSCRIPT3
if ( distanceBetweenPlayerAndLandmine < 25 )
{
	landmine.explode();
}
else
{
	//player is safe for now
}

(Obviously here we’re using the distance formula from above as applied to the player and landmine objects.)

If you think about it, it would be exactly the same to check whether the square of the distance was less than the square of 25 (which, incidentally, is 625). So if we write another formula:

?View Code ACTIONSCRIPT3
distanceSquared = ( firstObject.x - secondObject.x ) * ( firstObject.x - secondObject.x ) + ( firstObject.y - secondObject.y ) * ( firstObject.y - secondObject.y );

…we can then use this in our landmine scenario:

?View Code ACTIONSCRIPT3
if ( distanceSquaredBetweenPlayerAndLandmine < 625 )
{
	landmine.explode();
}
else
{
	//player is safe for now
}

(And this time of course we’ve used our new formula to work out the square of the distance between the player and landmine objects.)

It seems counter-intuitive, because in The Real World we’re used to using rulers and tape measures to find the distance between things, so working out the square of this distance seems like an unnecessary extra step. But in computer-land, it’s the other way around. Doing it this way is a lot more efficient and optimised.

Another situation where we can avoid using Math.sqrt() is when we are comparing distances. If Andy and Barry are both running away from the landmine, and we want to find out who is the closest, we can use the squares. Suppose Andy is 30 pixels away from the landmine and Barry is 50 pixels away; the squares of their distances will be 900 and 2,500 respectively. As 2,500 is larger than 900, we can deduce that Barry is further from the landmine than Andy is. Good for Barry.

What we can’t do is make any assumptions about how far away Andy and Barry are from each other. In the above example, the two will be 20 pixels apart (assuming that they’re running along the same path). But the square root of ( 2,500 – 900 ) is 40, *not 20!

Likewise, if Andy was 100 pixels away from the landmine and Barry was 110 pixels away, the squares of their distances would be 10,000 and 12,100, and they’d now only be 10 pixels apart from each other — but the square root of ( 12,100 – 10,000 ) is 45.8, which is even larger when they were 20 pixels apart!

So be careful. Especially around landmines.

What about in 3D?

In 1D, the distance is just:

?View Code ACTIONSCRIPT3
distance = firstObject.x - secondObject.x;

In 2D, we square each of the distances along the x- and y-axes, add them up, and square-root:

?View Code ACTIONSCRIPT3
distance = Math.sqrt( ( firstObject.x - secondObject.x ) * ( firstObject.x - secondObject.x ) + ( firstObject.y - secondObject.y ) * ( firstObject.y - secondObject.y ) );

So in 3D it must be the cube root of the sum of the cubes of the distances along the x-, y-, and z-axes, right?

Wrong.

This is a common mistake, and one that must be avoided. The 1D distance is actually this:

?View Code ACTIONSCRIPT3
distance = Math.sqrt( ( firstObject.x - secondObject.x; ) * ( firstObject.x - secondObject.x ) );

We just tend to simplify it to make life easier. (Note that if we did use the version without the squaring from above, sometimes we’d get a negative distance.)

The formula for 3D distance follows this pattern:

?View Code ACTIONSCRIPT3
distance = Math.sqrt( ( firstObject.x - secondObject.x ) * ( firstObject.x - secondObject.x ) + ( firstObject.y - secondObject.y ) * ( firstObject.y - secondObject.y ) + ( firstObject.z - secondObject.z ) * ( firstObject.z - secondObject.z ) );

I’m sure you can work out the formula for 4D distance, too. If you’re wondering what the heck a 4D game would look like, check out Miegakure.

What about on a sphere?

Er…

Actually here’s where things fall down a bit.

Try drawing a triangle on a deflated balloon and then blowing it up. The angles inside the curved triangle will add up to more than 180 degrees. Basically, things get crazy when you try to work in a curved space.

The “normal” space, the one we sketch out on paper and in map editors, is called Euclidean space. There are a whole bunch of conditions that a space has to obey to make it a Euclidean space; you can read about them here, if you’re so inclined. But basically, Euclidean space is what we would consider “everyday” space (don’t correct me here, relativistic physicists). I don’t know of any games that use a non-Euclidean space, so you’re probably safe to assume yours is using one too, but I would certainly be interested to see some use different types of spaces.

Pythagoras’ theorem has been proven to be true (and always to be true) in a Euclidean space, but not necessarily in other types of space. For this reason, the Pythagorean distance we’ve been looking at here is also known as the Euclidean distance. If you want to sound smart, you can casually drop that into conversation. “Oh yeah, we’re using a standard, y’know, Euclidean distance algorithm for our game.” Say the word “hypotenuse” a few times too, and your peers will definitely think you’re a genius.

Or pretentious.

{ 23 comments… read them below or add one }

MichaelJWilliams May 8, 2009 at 5:29 pm

Before anyone says, “but Michael, you mis-typed the title of Huey Lewis and the News’ classic 80s hit,” let me advise you check this out.

MichaelJWilliams May 8, 2009 at 5:30 pm

Heck, while we’re on the subject of Sesame-Street-produced-music-video-parodies-based-on-geometry, take a look at My Triangle.

tomdeaap May 15, 2009 at 10:31 pm

We get stuff like that at school :) however where now calculating corners with angles rather then pythagorus.

Michael Williams May 16, 2009 at 3:48 pm

What do you mean?

tomdeaap May 16, 2009 at 9:07 pm

say you got a triangle … on line is 10 cm long …. the angle is 40 degrees … depending on what line it is you use tangens sinus or cosinus ( thats how we call it in holland, don’t know about other countries) to calculate the length of the other lines …

tomdeaap May 16, 2009 at 9:09 pm

where I said corners I meant lenght of lines in my first entry…

Michael Williams May 17, 2009 at 8:04 pm

Ah, I gotcha. SOHCAHTOA ;)

tomdeaap May 18, 2009 at 2:17 pm

yea… it’s SOSCASTOA in our country :P

Michael Williams May 18, 2009 at 2:39 pm

Hunh, that’s interesting. What does the S stand for?

Gianfun May 28, 2009 at 10:15 pm

Hey! nice article :) Now I wont have to think as much when I have to find the distance between 2 things (I bet I would spend some time looking for the answer), and also thanks for the ‘not sqare rooting’ tip !

Yeah, I learn all of this at school too :P

Btw Michael, you did a little typo here, which may confuse people that didn’t learn pythagoras
” i.e. ( 10 * 10 ) + ( 15 + 15 ), so 100 + 225, which equals 325.”
should be “( 10 * 10 ) + ( 15 * 15 )” (*, not +)
And also you wrote Pythagorus once :D

Michael Williams May 28, 2009 at 10:46 pm

Cheers Gianfun!

Oops, thanks for pointing out those typos. Corrected :)

Gianfun June 1, 2009 at 11:18 pm

Hey michael!
One question. If a game were to be on a non-euclidian space, if one would walk to a direction (i.e. left), he would gradually curve upwards/downwards, like the lines on a (burst) balloon?

Michael Williams June 2, 2009 at 1:33 pm

Wow, interesting question.

First, I just want to make it clear that “non-Euclidean space” doesn’t necessarily refer to any particular type of space (like a balloon-shaped or spherical space), but just any type of space that isn’t Euclidean.

So yeah, you probably could find a non-Euclidean space where walking left made you move upward or downward as well — but then, you could argue that “left” doesn’t really mean anything in such a space!

On a space that is the surface of a sphere, you can think of things in terms of the Earth’s surface — if you walk far enough west, you’ll eventually return to your starting point. This doesn’t happen in a flat, Euclidean space.

tomdeaap June 10, 2009 at 4:40 pm

Oh … Pretty late answer to your question … but here is the explination:
s – schuine zijde
o- overstaande rechthoekszijde
s- sin
c- cos
t – tan
a- aanligende rechthoekszijde

Not that it explains anything … since it’s dutch .. :)

Daniel July 28, 2009 at 7:37 am

I am on 7th grade, i dont get this proplem at all, Math is my worts subject, can you help please?
Explain how you could use the Pythagorean Theorem to find the distance between the
(-4,-3) points and (1,1). Find the distance. You can type to indicate “squared” and “sqrt”

Michael Williams July 28, 2009 at 11:44 am

Hullo Daniel. Homework? :P

Sounds like you’re looking for a more general explanation of the the theorem than this game-related one, in which case I’d recommend this post over at BetterExplained.

But basically, you just:

  • Subtract one x-coordinate from the other, and square the result
  • Subtract one y-coordinate from the other, and square the result
  • Add those two squares together
  • Square root the result

So: sqrt( [( -4 ) - 1]squared + [ ( -3 ) - 1 ]squared )

Hope that helps ;)

Victor G. Reano April 27, 2010 at 6:02 am

Wow, that was extremely helpful and intuitive Michael! I never, ever, thought about just squaring the two sides which would completely eliminate the Math.sqrt. This will save me a handful of calls for my game. Thanks!

Michael Williams April 27, 2010 at 1:04 pm

Cheers, Victor :)

Jasmin C. May 10, 2012 at 12:31 am

Are Pythagorean and the rule of Pythagoras The same Thing?.. If Not, What Would the Formula be for the Rule of The Pythagoras?..
Thanks. :)

ky July 15, 2012 at 2:35 pm

Nice tut! Already know this stuff, but still handy as a cheat sheet when stuff ain’t working as it supposed to O_O.

ky

ammara September 30, 2012 at 7:59 pm

i want distance formula of two points in 3d space.plece help me

Michael James Williams October 1, 2012 at 3:12 pm

…Did you read the post?

kendall March 17, 2013 at 1:10 am

Explain how you could use the Pythagorean Theorem to find the distance between (-4,-3) and (1,1) and please hurry

Leave a Comment

Writing code? Write <pre> at the start and </pre> at the end to keep it looking neat.

Anti-Spam Protection by WP-SpamFree

{ 3 trackbacks }

Previous post:

Next post: