Jump to content

  • Log In with Google      Sign In   
  • Create Account

Distance formula in c++

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
10 replies to this topic

#1 LAURENT*   Members   -  Reputation: 500


Posted 25 August 2014 - 12:12 PM

Hello all,


I have recently came very very close to making the gameplay style I want but I stumbled into a small problem. I need the distance between two objects counted by the pixel. At first it seemed easy but I soon realized I didn't know what I was doing. Does anyone know how to do the distant formula in c++. I need the distance between two separate objects for my collision detection to work to my liking. The objects are the size of pixels by the way.


I tried using a for loop to figure out the distance but the second object of the 2 moves around and the for loop only activate  when the second object triggers it moving away from the first object. If it get closer after activating the for loop the distance will not be checked.

Edited by LAURENT*, 25 August 2014 - 12:23 PM.

#2 fastcall22   Crossbones+   -  Reputation: 9048


Posted 25 August 2014 - 12:19 PM

For points A and B, the distance between them is:
C = A-B
sqrt(C dot C)

It's essentially just the Pythagorean theorem.

If you're only comparing distances, then you can leave out the sqrt, keep the distances squared, and only sqrt when you need to. This is because a < b and sqrt(a) < sqrt(b) is always true, for a and b >= 0.

Edited by fastcall22, 25 August 2014 - 12:24 PM.

gzip: H4sIAAAAAAAEAG1QTUvEMBC991e8nvaiFfYoS7yo sLCo6MnjtJ1ugmkiyWRL/72z3T1YEQIJ8z4zA2Xp yPvt1qBpGrRFIJZkk9FyRyUzHCbKIHgn4hnZOrm1 TD0mG0HCCs+QGDGWziKXI6Wm2n++GYwUVH2mrGEE PnGCVQ8K8+JYfXA6URDEQfMZh5h6g5eoAlWJdeEI bbH2qYZf7XMUfw8f/Q0oMeZYNL9/WHF0uFEshvMr XYujd9SycFb+F18QcSOvlJauZ8ejqevdnV7/d550 e0t6prmunh73Bu+vz4c/XUeOQXfJgvKNkhf95U8/ Dtgmy5IBAAA=

#3 LAURENT*   Members   -  Reputation: 500


Posted 25 August 2014 - 12:35 PM

I was ready to include cmath and do some calculation but what I forgot and didn't realized was how simple getting the distance was addition/subtraction. Alright thanks for the refresher this thread is done. You made this a little simplier than the youtube video I watched.

#4 Álvaro   Crossbones+   -  Reputation: 19082


Posted 25 August 2014 - 02:39 PM

Since C++11:
hypot(B.x-A.x, B.y-A.y)


#5 Servant of the Lord   Crossbones+   -  Reputation: 32522


Posted 25 August 2014 - 03:36 PM

Nice! I wasn't aware of the std::hypot() function. smile.png


As fastcall22 mentioned, you actually don't need to do a squareroot, unless you actually want the actual distance. If you just want to check if something is within range, then you do:

((x2-x1)^2 + (y2-y1)^2) < (distance^2)   //  '^2' means to square it.

Basically, the same as Pygorean's theorum, but instead of square-rooting the result, you square the distance, which is faster if you're going to be doing it alot - for example, if you need to test which entities are within range of other entities or within range of the player, but don't need to know the actual distance, only if it is within range or not.


Probably a pre-mature optimization, but if you're going to wrap it in a convenience function, you might as well write both versions.


C++ code

It's perfectly fine to abbreviate my username to 'Servant' or 'SotL' rather than copy+pasting it all the time.

All glory be to the Man at the right hand... On David's throne the King will reign, and the Government will rest upon His shoulders. All the earth will see the salvation of God.
Of Stranger Flames - [indie turn-based rpg set in a para-historical French colony] | Indie RPG development journal | [Fly with me on Twitter

#6 Ravyne   GDNet+   -  Reputation: 13476


Posted 25 August 2014 - 05:23 PM

Nice to know about hypot() too! I was hoping to find one for 3 dimensions as well (its easy enough to implement oneself, of course), but no dice.

throw table_exception("(ノ ゜Д゜)ノ ︵ ┻━┻");

#7 frob   Moderators   -  Reputation: 39064


Posted 25 August 2014 - 06:11 PM

Note that std::hypot() is not a trivial function since it must deal with a bunch of complications and edge cases that don't usually exist in games. Denormalized numbers are usually an error in game environments, as are INF and NAN situations.

A frustrating thing about several of the standard library algorithms is their general purpose nature. They must handle a bunch of conditions that are rare, unlikely, or probably errors in games.

All the big implementations of std::hypot involve multiple branches with some of them taking rather slow steps to solve the equation.

Really, go look at what they do. As long as your numbers aren't crazy big, aren't crazy small, and are not exceptional with INF or NAN, you can do so much better with just a simple naive version.

Generally you won't need to handle the edge cases and simply need a comparison of 2D (dx*dx+dy*dy) or 3D (dx*dx+dy*dy+dz*dz), or if you need the actual distance taking sqrt(). Even these plain functions can outperform std::hypot since they don't require the branching, rounding needs, and special error handling.

If performance is a concern or if you are keeping your vector inside one of the extended SIMD registers for a math library, there are several algorithms that can give even better performance on these oft-used functions. No need to reinvent the wheel when there are so many good Euclidean distance functions already out there.

Check out my book, Game Development with Unity, aimed at beginners who want to build fun games fast.

Also check out my personal website at bryanwagstaff.com, where I occasionally write about assorted stuff.

#8 Isaac Paul   Members   -  Reputation: 213


Posted 26 August 2014 - 06:17 AM

My favorite method for calculating approximate distance:

u32 approx_distance( s32 dx, s32 dy )
   u32 min, max, approx;

   if ( dx < 0 ) dx = -dx;
   if ( dy < 0 ) dy = -dy;

   if ( dx < dy )
      min = dx;
      max = dy;
   } else {
      min = dy;
      max = dx;

   approx = ( max * 1007 ) + ( min * 441 );
   if ( max < ( min << 4 ))
      approx -= ( max * 40 );

   // add 512 for proper rounding
   return (( approx + 512 ) >> 10 );



Its useful for pathfinding and AI.. though it might be weird for collision. I recommend storing everything collide-able inside of an array and iterating through them while checking to see if the edges of the objects over lap with each other via box collision or separating axis theorem. 


Box Collision:

bool DoBoxesIntersect(Box a, Box b) {
  return (abs(a.x - b.x) * 2 < (a.width + b.width)) &&
         (abs(a.y - b.y) * 2 < (a.height + b.height));



Separating Axis Theorem:


Edited by Isaac Paul, 26 August 2014 - 06:23 AM.

#9 Trienco   Crossbones+   -  Reputation: 2551


Posted 26 August 2014 - 10:17 PM

Somehow I feel the strange urge to actually profile this against a straightforward implementation using a modern compiler on modern hardware, just to see if all this obscure trickery is still worthwhile.


#10 Norman Barrows   Crossbones+   -  Reputation: 5520


Posted 27 August 2014 - 07:35 AM

fast diamond 2d distance: dx+dy


fast BBox 2d distance: greater of dx and dy


fast 2d distance comparison: dx*dx+dy*dy      (paythag w/o sqrt, as mentioned above).


true 2d distance: sqrt(dx*dx+dy*dy)            (true pythag, as mentioned above).

Norm Barrows

Rockland Software Productions

"Building PC games since 1989"







#11 Ravyne   GDNet+   -  Reputation: 13476


Posted 27 August 2014 - 05:04 PM

Somehow I feel the strange urge to actually profile this against a straightforward implementation using a modern compiler on modern hardware, just to see if all this obscure trickery is still worthwhile.


Me too.


For distance comparisons, the naive computation leaving out square-root is definitely faster ( can count 3 multiplies here, plus all the other instructions, vs. 4 multiplies and an add for the naive) and totally accurate to boot.


For true distance, it probably depends entirely on how fast your hardware can do square root. The branches above gave me pause at first, but they look like they can be compiled into conditional moves to eliminate branch misprediction and potential stalls. But on even a 45nm Core 2 CPU, sqrt takes between 6 and 20 clock cycles only. I would hazard a guess that the above fast approximation is little if any faster on a modern CPU than the naive implementation. That might not be true if you can only have one sqrt instruction in flight but many multiplies/shifts/additions, though.


But on a CPU with slow square root, or gods forbid -- software emulation of square root, the above approximation will certainly be faster.

Edited by Ravyne, 27 August 2014 - 05:06 PM.

throw table_exception("(ノ ゜Д゜)ノ ︵ ┻━┻");

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.