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.
{ 23 comments… read them below or add one }
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.
Heck, while we’re on the subject of Sesame-Street-produced-music-video-parodies-based-on-geometry, take a look at My Triangle.
We get stuff like that at school 🙂 however where now calculating corners with angles rather then pythagorus.
What do you mean?
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 …
where I said corners I meant lenght of lines in my first entry…
Ah, I gotcha. SOHCAHTOA 😉
yea… it’s SOSCASTOA in our country 😛
Hunh, that’s interesting. What does the S stand for?
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 😛
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 😀
Cheers Gianfun!
Oops, thanks for pointing out those typos. Corrected 🙂
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?
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.
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 .. 🙂
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”
Hullo Daniel. Homework? 😛
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:
So: sqrt( [( -4 ) – 1]squared + [ ( -3 ) – 1 ]squared )
Hope that helps 😉
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!
Cheers, Victor 🙂
Are Pythagorean and the rule of Pythagoras The same Thing?.. If Not, What Would the Formula be for the Rule of The Pythagoras?..
Thanks. 🙂
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
i want distance formula of two points in 3d space.plece help me
…Did you read the post?
Explain how you could use the Pythagorean Theorem to find the distance between (-4,-3) and (1,1) and please hurry
{ 3 trackbacks }