Pythagorean Distance Between Two Points

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:

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:

(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:

…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**.

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:

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

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

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.

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:

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:

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:

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:

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:

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:

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.

Tagged as: AS3, distance, euclidean, flash, Maths, pythagoras, standalone, useful function