2D Collision Detection and Response?

[dandymcgee]

So I've decided my design skills are incredibly bad, and I'm lacking some very important fundamentals. Therefore I've also decided to make a Breakout clone.

Implementation details:
Bricks are represented as a vector of Objects. When the ball collides with a brick, it is removed from the vector. This part works fine at the moment, the question comes into play when figuring out changes in the ball's velocity due to a collision.

Right now if the ball hits a brick or the paddle I simply reverse the y velocity. This works fine if it hits the top of the paddle or the bottom of a brick.. but what if it hits the side? Obviously I would negate the x velocity as opposed to the y, but how would I determine with which side of a brick the ball has collided?

This is what I've written to start:

Code: Select all

if( (ball.x + ball.w + ball.xVel > brick.x) && (ball.x + ball.xVel < brick.x + brick.w) && (ball.y + ball.h + ball.yVel > brick.y) && (ball.y + ball.yVel < brick.y + brick.h))
{
     delete (*bricksIter);
     bricks.erase( bricksIter );
     ball->yVel = -ball->yVel;
}

I would imagine determining the collision side involves splitting this into at least four separate conditions, but I figured I would inquire before writing a butt load of unnecessary if statements.

Any ideas/suggestions (yes I realize this is elementary rectangular collision...)?

[Falco Girgis]

You need to find the "axis" of minimal overlap.

Imagine two rectangles colliding. You have four possible edges/faces on either rectangle that the collision could have occurred on. If you would like to determine which edge has "collided" with a rectangle, it will always be the edge that is penetrating the other rectangle minimally.

If your axis of minimal overlap for your "ball" is on either the top or bottom, negate your y velocity.
If your axis of minimal overlap for your "ball" is on either the left or right side, negate your x velocity.

Consider this code (I'm pulling this out of my ass, so it is untested) within your collision resolution:

Code: Select all

//Determine overlap for each axis
xOverlap = rect1.x+0.5*rect1.width - rect2.x + 0x5*rect2.width;
yOverlap = rect1.y+0.5*rect1.height - rect2.y+0.5*rect2.height;

//Test for axis of minimal overlap
if(abs(xOverlap) < abs(yOverlap)) {
    rect1.xvel = -rect1.xvel;
}
else rect1.yvel = -rect1.yvel;

[dandymcgee]

You need to find the "axis" of minimal overlap.

Imagine two rectangles colliding. You have four possible edges/faces on either rectangle that the collision could have occurred on. If you would like to determine which edge has "collided" with a rectangle, it will always be the edge that is penetrating the other rectangle minimally.

If your axis of minimal overlap for your "ball" is on either the top or bottom, negate your y velocity.
If your axis of minimal overlap for your "ball" is on either the left or right side, negate your x velocity.

Consider this code (I'm pulling this out of my ass, so it is untested) within your collision resolution:

Code: Select all

//Determine overlap for each axis
xOverlap = rect1.x+0.5*rect1.width - rect2.x + 0x5*rect2.width;
yOverlap = rect1.y+0.5*rect1.height - rect2.y+0.5*rect2.height;

//Test for axis of minimal overlap
if(abs(xOverlap) < abs(yOverlap)) {
    rect1.xvel = -rect1.xvel;
}
else rect1.yvel = -rect1.yvel;

Brilliant! I knew you would have something much better that whatever I would have conceived. The only place where this becomes kind of personalized is where xOverlap==yOverlap, but I'll probably just reverse both velocities if someone gets THAT lucky.

Edit:

xOverlap = rect1.x+0.5*rect1.width - rect2.x + 0x5*rect2.width;

"Wtf.. it's not working."
Lmao.

[davidthefat]

http://www.loomsoft.net/resources/alltu ... esson8.htm
Im reading that

[dandymcgee]

http://www.loomsoft.net/resources/alltu ... esson8.htm
Im reading that

That's exactly what I was doing before, doesn't tell you which side was collided with.

Falco, I'm having an issue with the overlap code:

error.PNG (1.58 KiB) Viewed 4796 times

Any more ideas?

[Falco Girgis]

Brilliant! I knew you would have something much better that whatever I would have conceived. The only place where this becomes kind of personalized is where xOverlap==yOverlap, but I'll probably just reverse both velocities if someone gets THAT lucky.

Don't bother. If somebody were to get that lucky, the physics would be completely believable in either direction. Hence I didn't address that case.

Oops, my previous algorithm wasn't quite right. Sue me. I pulled a new and improved algorithm out of my ass. This should be a complete collision check for you. The overlaps on the axes should have been calculated based on the difference between the distance of the two centers and the maximal distance that they can be without colliding.

Make sure your x,y is at the center of the rectangle (not top left).

Code: Select all

bool Collision(Rect rect1, Rect rect2) {
//Determine overlap for each axis
float xDist = abs(rect1.x - rect2.x);
float yDist = abs(rect1.y - rect2.y);

//minimal amount of distance that the two can be apart and not collide
float xMinDist = rect1.width + rect2.width;
float yMinDist = rect1.height + rect2.height;

if(xDist >= xMinDist || yDist >= yMinDist) return false; //neither axis is colliding

float xOverlap = xDist - xMinDist;
float yOverlap = yDist - yMinDist;

if(xOverlap < yOverlap) xvel = -xvel;
else yvel = -yvel;

return true;
}

[Falco Girgis]

You better let me know if that didn't work. Otherwise I will assume my untested code was flawless.

[dandymcgee]

You better let me know if that didn't work. Otherwise I will assume my untested code was flawless.

Haven't had time to implement it yet, I was busy all day yesterday. I'll do it in a bit and let ya know.

[dandymcgee]

Gah, finally figured out why it wasn't working right.

I was calling:

Code: Select all

delete (*bricksIter);
bricks.erase( bricksIter );

BEFORE testing for collisions (where I referenced (*bricksIter) multiple times).

Also, note to self: abs() casts doubles to ints.

Thanks Falco.

[Falco Girgis]

Gah, finally figured out why it wasn't working right.

I was calling:

Code: Select all

delete (*bricksIter);
bricks.erase( bricksIter );

BEFORE testing for collisions (where I referenced (*bricksIter) multiple times).

Also, note to self: abs() casts doubles to ints.

Thanks Falco.

No problem at all. The same geometric interpretation of the problem can be applied to oriented bounding boxes as well (where they are both rotated). You basically just applied the separating axis theorem on axis-aligned bounding boxes.

[dandymcgee]

No problem at all. The same geometric interpretation of the problem can be applied to oriented bounding boxes as well (where they are both rotated). You basically just applied the separating axis theorem on axis-aligned bounding boxes.

Oh, sweet. Now I'm one step closer to understanding separating axis.

[DeltaFolee]

Brilliant! I knew you would have something much better that whatever I would have conceived. The only place where this becomes kind of personalized is where xOverlap==yOverlap, but I'll probably just reverse both velocities if someone gets THAT lucky.

Don't bother. If somebody were to get that lucky, the physics would be completely believable in either direction. Hence I didn't address that case.

Oops, my previous algorithm wasn't quite right. Sue me. I pulled a new and improved algorithm out of my ass. This should be a complete collision check for you. The overlaps on the axes should have been calculated based on the difference between the distance of the two centers and the maximal distance that they can be without colliding.

Make sure your x,y is at the center of the rectangle (not top left).

Code: Select all

bool Collision(Rect rect1, Rect rect2) {
//Determine overlap for each axis
float xDist = abs(rect1.x - rect2.x);
float yDist = abs(rect1.y - rect2.y);

//minimal amount of distance that the two can be apart and not collide
float xMinDist = rect1.width + rect2.width;
float yMinDist = rect1.height + rect2.height;

if(xDist >= xMinDist || yDist >= yMinDist) return false; //neither axis is colliding

float xOverlap = xDist - xMinDist;
float yOverlap = yDist - yMinDist;

if(xOverlap < yOverlap) xvel = -xvel;
else yvel = -yvel;

return true;
}

The part of that algorithm where you calculated the minimum distance allowed between the two boxes doesn't make any sense to me, I thought it would just be the larger of the two widths/heights would be the minimal distance. Could someone please explain this for me?

[Bakkon]

Also, note to self: abs() casts doubles to ints.

This is way late and you probably know this by now, but fabs() returns a float, double, or long depending on what's passed in.

[dandymcgee]

Also, note to self: abs() casts doubles to ints.

This is way late and you probably know this by now, but fabs() returns a float, double, or long depending on what's passed in.

Not late at all, I most certainly appreciate that information! Will keep that in mind for 2010.

[koolgraph]

The Collision Detection works great, except when it collide at a high speed. Exemple

Speed = 10 Char by tick
X = the Player
OO = Some kind of brick/wall

First Tick

Code: Select all

--------OOOO
-X------OOOO
--------OOOO

Enverything's fine

Next Tick

Code: Select all

--------OOOO
--------OOXO
--------OOOO

Now it says the YDistance is less than X distance, so pull back top, but the collision did happened on the side. How to fix this ?

I should say, how to take into account the Velocity in the Collision Response ?