   Very Weird Ball Collision Behavior
  I'll have to admit, I'm stumped.I am creating a collision detection demo so that I can learn some basic 2D collision detection. Currently, it is just two balls bouncing around the screen, Pong-style. I have a collision function for wall collisions (when the ball hits the side of the screen), and a separate function for ball-to-ball collisions.The function for ball-to-wall collisions seems to be working fine. The function for ball-to-ball collisions, however, is working a little screwy. I used some basic vector math (which was no so "basic" to me a few weeks ago) in order to calculate when, if at all, the two balls collide in between two frames. So, if my time variable is t, then the current frame is t=1 and the previous frame is t=0. If a collision occurred exactly in the middle of the two frames, then the collision occured at t=0.5 and I can move each ball back to where they were at those points.I used this web page as a guide, and I solicited help in this thread in order to understand the underlying math.The basic plan is to test two balls at a time. The trick is to see if there is any point during the frame at which the distance between the two balls' centers equal the sum of their radii. If so, then you know you have a collision.You take the center of ball A at frame 0 (call this point A0), and also the center of ball A at frame 1 (call it A1). You use that to create a line which traces the path of the ball over the course of the frame (letsc all that line segment A). The velocity of the ball, or the magnitude and direction that it travels from A0 to A1 can be expressed as A1-A0, and so line segment A can be though of as:A = A0+(A1-A0)To find the location of ball A's center at any given moment in time, you can do this:A(t) = A0+VatWhere t is the amount of time, and 0<t<1, and Va is the velocity of the vector (A1-A0).To find the distance, d, between two balls (A and B) at any given time, you simply do this:d(t) = | A0+Vat - [B0+Vbt] | = ra+rbSubtracting B(t) from A(t) will result in a certain vector, the magnitude of which can be found using the pythagorean theorem. If there is any solution for t which equals ra+rb (the sum of the two radii), then that is when the collision occurred. But this is easier:[A0+Vat - (B0+Vbt)] . [A0+Vat - (B0+Vbt)] = (ra+rb)^2We can square the sum of the radii easily enough, and just multiplying the vector by itself using the dot product is a lot easier than using the PT (can you even solve for t using the PT? I'm not sure). This works out to a quadratic equation:Vab.Vab*t^2 + 2*AB.Vab*t + AB.AB - (ra+rb)^2 = 0So, here are the coefficients of this equation:a: Vab.Vabb: 2*AB.Vabc: AB.AB - (ra+rb)^2Since all these values are known, I can plug them into the quadratic formula:-b±sqrt(b^2-4ac) / 2aIf this yields two answers for t, then the smallest value is the time when the the balls first collided, and the higher value is the value when they first diverged (presuming that they passed right through each other). If there is only one answer, then that means the balls just grazed each other. If there is no valid answer (i.e., if b^2-4ac yields a negative number, which you can't sqrt) then the balls never hit.So, now that I have my answers, the next problem is collision response. Ideally, I would like to reset their positions back to the time of the first collision, and then reverse their speeds with respect the normal of the tangent at the point of impact. I could then transfer some momentum, perhaps reduce some kinetic energy, and other cool physics stuff.But for now, I just want to test the above collision detection to see if it's working. So, instead of altering the trajectory of the ball, I've decided to simple have the balls change hue from orange to blue (and then back again if they ever collide again). For my first test, I have just two balls.But I'm finding something wierd. It appears that my program is detecting the collisions way before they happen. Don't get me wrong. It seems to know when a collision is about to happen, but it just thinks it happens before it actually does.Picture this. The balls are bouncing around the screen; doing their thing. At one point, one of the balls hits a wall, reflecting it into the path of the other ball. The timing is perfect for a collision. Well, the program seems to "know" this even before the collision occurs, and it rapidly changes the color of the balls from orange to blue and back to orange again, until the balls actually do collide (at which point it settles on the last color change). The balls remain that same color until one of them gets knocked back into a collision course with the other one and they start flipping colors rapidly again.My program is completely deterministic. There is no random element or human input. I just give each ball an initial velocity (x,y) and an initial position (x,y) and I just let them do there thing. So, the program could, in theory, forsee all future collisions at the very start of the program. However, the program doesn't seem to be doing it THAT early. In fact, it doesn't actually detect the collision until one of the balls gets knocked, by a wall, in another direction such that it's path converges with the path of the other ball with perfect timing for a collision.In other words, the last direction change for the balls prior to the collision is when the colors start changing.Any help you guys can offer would be greatly appreciated. Here are the files:main.cpp#include <stdio.h>#include <stdlib.h>#include "ball.h"#include <SDL/SDL.h>void Slock(SDL_Surface *screen);void Sulock(SDL_Surface *screen);void DrawPixel(SDL_Surface *screen, int x, int y, Uint8 R, Uint8 G, Uint8 B);void DrawScene();Ball ball1(1, 240, 200, 100, 0);Ball ball2(623, 240, -200, 100, 0);SDL_Surface *image;SDL_Surface *screen;int start_time = SDL_GetTicks();int frame_time = SDL_GetTicks();int main(int argc, char *argv[]){   srand(SDL_GetTicks());  // initialize SDL  if ( SDL_Init(SDL_INIT_AUDIO|SDL_INIT_VIDEO) < 0 )  {    printf("Unable to init SDL: %s\n", SDL_GetError());    exit(1);  }  atexit(SDL_Quit); // shut down SDL when program returns    // set video mode  screen=SDL_SetVideoMode(640,480,32,SDL_HWSURFACE|SDL_DOUBLEBUF);  if ( screen == NULL )  {    printf("Unable to set 640x480 video: %s\n", SDL_GetError());    exit(1);  }  int done=0;    image = SDL_LoadBMP("image.bmp");  double now = 0;  while(done == 0)  {    SDL_Event event;    while ( SDL_PollEvent(&event) )    { if ( event.type == SDL_QUIT )  {  done = 1;  } if ( event.type == SDL_KEYDOWN ) {   if ( event.key.keysym.sym == SDLK_ESCAPE ) { done = 1; } }    } ball1.CheckBallCollision(ball2);   ball1.CheckWallCollision();  ball2.CheckWallCollision();ball1.UpdatePosition(now);    ball2.UpdatePosition(now);   frame_time = SDL_GetTicks();    DrawScene();    now = (double)SDL_GetTicks() - (double)frame_time;  }  return 0;}void Slock(SDL_Surface *screen){  if ( SDL_MUSTLOCK(screen) )  {    if ( SDL_LockSurface(screen) < 0 )    { return;    }  }}void Sulock(SDL_Surface *screen){  if ( SDL_MUSTLOCK(screen) )  {    SDL_UnlockSurface(screen);  }}void DrawPixel(SDL_Surface *screen, int x, int y, Uint8 R, Uint8 G, Uint8 B){  Uint32 color = SDL_MapRGB(screen->format, R, G, B);  switch (screen->format->BytesPerPixel)  {    case 1: // Assuming 8-bpp {   Uint8 *bufp;   bufp = (Uint8 *)screen->pixels + y*screen->pitch + x;   *bufp = color; } break;    case 2: // Probably 15-bpp or 16-bpp {   Uint16 *bufp;   bufp = (Uint16 *)screen->pixels + y*screen->pitch/2 + x;   *bufp = color; } break;    case 3: // Slow 24-bpp mode, usually not used {   Uint8 *bufp;   bufp = (Uint8 *)screen->pixels + y*screen->pitch + x * 3;   if(SDL_BYTEORDER == SDL_LIL_ENDIAN)   {bufp[0] = color;bufp[1] = color >> 8;bufp[2] = color >> 16;   } else {bufp[2] = color;bufp[1] = color >> 8;bufp[0] = color >> 16;   } } break;    case 4: // Probably 32-bpp {   Uint32 *bufp;   bufp = (Uint32 *)screen->pixels + y*screen->pitch/4 + x;   *bufp = color; } break;  }}void DrawScene(){  SDL_Rect scr;  scr.x = 0;  scr.y = 0;  scr.w = 640;  scr.h = 480;//SDL_FillRect(screen, &scr, 0);SDL_Rect src1;  SDL_Rect src2;    ball1.GetSrcRect(&src1);  ball2.GetSrcRect(&src2);    SDL_Rect dest1;  SDL_Rect dest2;    dest1.x = (int)ball1.pos.x;  dest1.y = (int)ball1.pos.y;  dest2.x = (int)ball2.pos.x;  dest2.y = (int)ball2.pos.y;    SDL_BlitSurface(image, &src1, screen, &dest1);  SDL_BlitSurface(image, &src2, screen, &dest2);    SDL_Flip(screen);}ball.h#include <SDL/SDL.h>#include "vector.h"class Ball{  public:Ball();  Ball(SCALAR,SCALAR,SCALAR,SCALAR,int,SCALAR); VECTOR pos;  VECTOR prev_pos;  VECTOR velocity;  SCALAR radius;  int birth;  int color;    int GetCurrentFrame();  int GetCurrentCell();  void GetSrcRect(SDL_Rect * src);   void CheckWallCollision();  bool BallSweep(Ball& B, SCALAR& t1, SCALAR& t2);  void CheckBallCollision(Ball& B);    void UpdatePosition(double time);    inline bool QuadraticFormula(SCALAR a, SCALAR b, SCALAR c, SCALAR& r1, SCALAR& r2); };Ball::Ball(){   pos.x = 312; pos.y = 232;  velocity.x = 500; velocity.y = 500;  color = 0;  radius = 8;  birth = SDL_GetTicks();  } // end of Ball constructorBall::Ball(SCALAR _xpos, SCALAR _ypos, SCALAR _xspeed, SCALAR _yspeed, int _color, SCALAR _radius=8){   pos.x = _xpos; pos.y = _ypos;  velocity.x = _xspeed; velocity.y = _yspeed;  color = _color;  radius = _radius;  birth = SDL_GetTicks();  } // end of Ball constructorint Ball::GetCurrentFrame(){  int interval = (SDL_GetTicks() - birth) % 1160; int frame = interval / 20;  return frame;   } // end GetCurrectFrameint Ball::GetCurrentCell(){int cell = GetCurrentFrame(); if(cell > 29)  {   int sub = (cell - 29)*2;   cell -= sub;}  return cell;    } // end GetCurrentCellvoid Ball::GetSrcRect(SDL_Rect * src){ src->x = GetCurrentCell() * 16; src->y = color*16; src->h = 16; src->w = 16;} // end GetSrcRectvoid Ball::CheckWallCollision(){  // X TOO SMALL if(pos.x < 0) {   SCALAR a = 0 - prev_pos.x;  SCALAR b = pos.x - prev_pos.x;  SCALAR t = a/b;    pos.x = 0;// move X to 0  pos.y = prev_pos.y + (pos.y - prev_pos.y)*t;  // adjust Y accordingly } // X TOO LARGE if(pos.x > 624) {   SCALAR a = 624 - prev_pos.x;  SCALAR b = pos.x - prev_pos.x;  SCALAR t = a/b;    pos.x = 624;// move X to 624  pos.y = prev_pos.y + (pos.y - prev_pos.y)*t;  // adjust Y accordingly }  // Y TOO SMALL if(pos.y < 0) {   SCALAR a = 0 - prev_pos.y;  SCALAR b = pos.y - prev_pos.y;  SCALAR t = a/b;    pos.y = 0;// move XY to 0  pos.x = prev_pos.x + (pos.x - prev_pos.x)*t;  // adjust X accordingly }  // Y TOO LARGE if(pos.y > 464) {   SCALAR a = 464 - prev_pos.y;  SCALAR b = pos.y - prev_pos.y;  SCALAR t = a/b;    pos.y = 464;// move Y to 464  pos.x = prev_pos.x + (pos.x - prev_pos.x)*t;  // adjust X accordingly }  // Reverse Velocities if(pos.x == 0) velocity.x = -velocity.x; if(pos.y == 0) velocity.y = -velocity.y; if(pos.x == 624) velocity.x = -velocity.x; if(pos.y == 464) velocity.y = -velocity.y;} // end of WallCollisionvoid Ball::UpdatePosition(double time){ prev_pos.x = pos.x; // save last prev_pos.y = pos.y; // position   double r = time / 1000; pos.x += velocity.x*r;pos.y += velocity.y*r;   } // end of UpdatePositioninline bool Ball::QuadraticFormula(SCALAR a, SCALAR b, SCALAR c, SCALAR& r1, SCALAR& r2){    const SCALAR q = b*b - 4*a*c;    if( q >= 0 )    {   const SCALAR sq = sqrt(q);   const SCALAR d = 1 / (2*a);   r1 = ( -b + sq ) * d;   r2 = ( -b - sq ) * d;   return true;//real roots    }    else    {   return false;//complex roots    } }bool Ball::BallSweep(Ball& B, SCALAR& t1, SCALAR& t2){ VECTOR center_offset; center_offset.x = 8;center_offset.y = 8;  const VECTOR Va = (pos + center_offset) - (prev_pos + center_offset); const VECTOR Vb = (B.pos + center_offset) - (B.prev_pos + center_offset);const VECTOR CACB = (B.prev_pos + center_offset) - (prev_pos + center_offset); const VECTOR Vab = Vb - Va; const SCALAR radii = radius + B.radius; const SCALAR rsq   = radii * radii;  const SCALAR a = Vab.dot(Vab);   const SCALAR b = 2*Vab.dot(CACB); const SCALAR c = CACB.dot(CACB) - rsq;   //check if they're currently overlapping    if( CACB.dot(CACB) <= rsq )    {   t1 = 0;   t2 = 0;   return true;    }    //check if they hit each other    // during the frame    if( QuadraticFormula( a, b, c, t1, t2 ) )    {   return true;    }    return false;  }void Ball::CheckBallCollision(Ball& B){ SCALAR t1; SCALAR t2;if(BallSweep(B, t1, t2)) {    if( t1 < t2 )  {   SCALAR temp = t1;   t1 = t2;   t2 = temp;  } // end nested if    if(t1 >= 0 && t1 >= 1)  { if(color == 0) color = 1; else color = 0;   if(B.color == 0) B.color = 1; else B.color = 0;  }  // end nested if    } // end if   } // end of functionvector.h#include <cmath>typedef float SCALAR;class VECTOR{   public:SCALAR x,y;    VECTOR() { x=0; y=0; }  VECTOR(SCALAR a, SCALAR b) { x=a; y=b; } // compare  const bool operator == ( const VECTOR& v ) const { return (v.x==x && v.y==y); }  const bool operator != ( const VECTOR& v ) const { return !(v == *this); }    // negate  const VECTOR operator - () const { return VECTOR( -x, -y ); }    // assign  const VECTOR& operator = ( const VECTOR& v ) { x = v.x; y = v.y; return *this; }    // plus-equals  const VECTOR& operator += ( const VECTOR& v ) { x+=v.x; y+=v.y; return *this; }    // minus-equals  const VECTOR& operator -= ( const VECTOR& v ) { x-=v.x; y-=v.y; return *this; }    // times-equals  const VECTOR& operator *= ( const SCALAR& s ) { x*=s; y*=s; return *this; }   // self-divide  const VECTOR& operator /= ( const SCALAR& s ) { const SCALAR r = 1 / s; x *= r; y *= r; return *this; }  // add  const VECTOR operator + ( const VECTOR& v ) const { return VECTOR(x + v.x, y + v.y); }    // subtract  const VECTOR operator - ( const VECTOR& v) const { return VECTOR(x - v.x, y - v.y); }    // post-multiply by scalar  const VECTOR operator * ( const SCALAR& s ) const { return VECTOR( x*s, y*s ); } // pre-multiply by scalar  friend inline const VECTOR operator * ( const SCALAR& s, const VECTOR& v ) { return v * s; }    // divide  const VECTOR operator / (SCALAR s) const { s = 1/s; return VECTOR( s*x, s*y ); }    // dot product  const SCALAR dot( const VECTOR& v ) const { return x*v.x + y*v.y; } // length  const SCALAR length() const { return (SCALAR)sqrt( (double)this->dot(*this) ); }    // unit vector  const VECTOR unit() const { return (*this) / length(); }    // make this a unit vector  void normalize() { (*this) /= length(); }    // equal within an error ‘e’  const bool nearlyEquals( const VECTOR& v, const SCALAR e ) const { return fabs(x-v.x)<e && fabs(y-v.y)<e; }   }; // end of Vector Class// A 3D positiontypedef VECTOR POINT;
  I don't know if this helps, but if I remove the if(t >= 0 && t <= 1) requirement, found in void Ball::CheckBallCollision(Ball&), the colors change rapidly ALL the time; not only when the balls are about to collide.   ;  If only everyone described their problem so clearly :) I'm off to work now, but If you haven't fixed this by this evening, I'll take a look at the code and see if I can spot anything.   ;  Couple quick questions/observations. First of all, with this particular application of the quadratic formula, you know that the denominator 2a will always be positive. So if you take these two lines:r1 = ( -b + sq ) * d;r2 = ( -b - sq ) * d;And re-arrange them as:r1 = ( -b - sq ) * d;r2 = ( -b + sq ) * d;Then r1 will always be the lower root and you won't have to sort them.Furthermore, in your current code it seems you're sorting them incorrectly anyway. It seems that the following bit of code:if( t1 < t2 ){    SCALAR temp = t1;    t1 = t2;    t2 = temp;}Puts the larger of the two t values in t1, which is probably not what you want. Finally, this:if(t1 >= 0 && t1 >= 1)Is probably supposed to be this:if(t1 >= 0 && t1 <= 1)That error alone could be causing the problems you described.Let me know if you need any more help.   ;  Thanks a ton. I will try that out when I get home.Shouldn't the quadratic equation always produce roots that are >= 0 and <= 1 anyway?   ;  The roots that the quadratic formula gives you can be real or imaginary, positive or negative.  It does not have to be in between 0 and 1.   ;  Wow, then that really might be it, because the test that I had before, if(t1 >=0 && if t1 >=1), will work as long as the root is greater than 1. If the two balls are on a collision course with one another, I wouldn't be surprised if the quadratic found SOME value for the collision time that is greater than 1, which according to my code would count as a collision detection. If I restrict collisions to t1 values between 0 and 1, then it should restrict collision detections to collisions that occur WITHIN the frame, rather than some time in the future.Wow, this might work. Thanks guys! I can't tell you how long I've been working on this one stupid bug. I've done too many experiments to count. Typing a post here was my last resort because I knew that very few people would want to read the whole backstory. Thanks for taking the time to help.   