Sign in to follow this  
LAURENT*

Distance formula in c++

Recommended Posts

LAURENT*    779

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*

Share this post


Link to post
Share on other sites
LAURENT*    779

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.

Share this post


Link to post
Share on other sites

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.

 

[rollup=C++ code]

//Returns true if we are within 'distance' of 'other'. This is faster than 'DistanceFrom', because it saves a sqrt().
bool cPoint::WithinDistanceOf(const cPoint &other, int distance) const
{
	//Pygorean's theorum: A^2 + B^2 = C^2
	int horizontal = (this->x - other.x); //(this->x - other.x) could be negative, but multiplying it by itself will always be positive anyway.
	horizontal *= horizontal;

	int vertical = (this->y - other.y);
	vertical *= vertical;

	//Square the distance.
	distance *= distance;

	//Use the squared distance for comparison, instead of getting the square root.
	return (horizontal + vertical) <= distance;
}

//Returns the absolute distance between this point and 'other'.
int cPoint::DistanceFrom(const cPoint &other)
{
	//Pygorean's theorum: A^2 + B^2 = C^2
	int horizontal = (this->x - other.x); //(this->x - other.x) could be negative, but multiplying it by itself will always be positive anyway.
	horizontal *= horizontal;

	int vertical = (this->y - other.y);
	vertical *= vertical;

	return std::sqrt(horizontal + vertical);
}

[/rollup]

Share this post


Link to post
Share on other sites
Ravyne    14300

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.

Share this post


Link to post
Share on other sites
izackp    215

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 );
} 

http://www.flipcode.com/archives/Fast_Approximate_Distance_Functions.shtml

 

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));
}

http://gamedev.stackexchange.com/questions/586/what-is-the-fastest-way-to-work-out-2d-bounding-box-intersection

 

Separating Axis Theorem:

http://www.metanetsoftware.com/technique/tutorialA.html 

Edited by Isaac Paul

Share this post


Link to post
Share on other sites
Trienco    2555

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.

Share this post


Link to post
Share on other sites
Norman Barrows    7179

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

Share this post


Link to post
Share on other sites
Ravyne    14300

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this