2D Collision detection

[Kirl]

I'm having some recurring troubles with basic square vs circle collisions (unrotated), actually it's square vs square as I only use the width and height of both objects to determine their bounds. As you might have noticed in my demo for the liquid challenge, sometimes a ball slips through the walls and I'm unsure why.

In pseudo code my approach goes something like this (Flash 0,0 coord is upper left corner, so +y is downward):

Code: [Select]

if( ball.left < square.right && ball.right > square.left )
   if( ball.bottom > square.top )      ball hits square top
   else if( ball.top < square.bottom ) ball hits square bottom

same method for left and right walls

How do you guys handle collision between static square vs moving balls?

[Shockwave]

You could test each point of the square  to see if it lies within the circle by measuring the distance between the centre of the circle and each point something like this;

Code: [Select]

d=sqrt((px-cx)*(px-cx)+(py-cy)*(py-cy))
if d>CircleRadius
Then
not in circle
else
incircle
end if

And you'd also need to check to see if the circle was inside the 4 points of the square too, otherwise if the circle is contained within a block the collision would be missed.

[LittleWhite]

Hum, I am unsure about your statement Shockwave (maybe not get it).
If you have the ball standing in the middle of the width of the rect, the ball does not touch the corner of the squares but can touch the corner edge ... It's a collision.

I think, the solution can be done (take your papers) by a point detection (the center is in the square) + kind of wall detection using the radius of the sphere/

Code: [Select]

If ( square.point_inside(ball.center) )
{
  Collision for sure
}
+

Code: [Select]

if ( ball.center.x + radius > square.left || ball.center.x - radius < square.right || ball.center.y + radius > square.top || ball.center.y - radius < square.top )
{
 Collision
}
I think my second method is not quite correct

[Kirl]

@Shockwave
If the circle is smaller then the squares width/height, it might pass straight through it without any of the corners ever being inside the circle.

Also when a corner is inside the circle, how do I know which side it hit?

@ littleWhite
Your second method is how I do it, I only do it in steps so I know which side it hit.

[Shockwave]

In that case, Paul Bourke could have the answer for you;

http://paulbourke.net/geometry/lineline2d/

If you know the old centre point of the circle and the one you want to move it to, that can describe a line.
You can use similar logic for the sides of the box to create 4 lines to test against.

The beauty of this is that it would work for any size ball / square, even if the ball is moving in a step size that's greater than the size of the box.

[Raizor]

Kirl, have you considered using a physics engine such as Box2D? That would take a lot of the away for you.  There's an AS version available:

http://box2dflash.sourceforge.net/

[hellfire]

To get water-tight collisions you'd also span the objects' bounding boxes from one frame to the next:

[rain_storm]

The solution is simple you find the nearest point on the square to the center of the circle

Code: [Select]

nearX = min(max(squareX1, circleX), squareX2); // where squareX1 < squareX2
nearY = min(max(squareY1, circleY), squareY2); // where squareY1 < squareY2
nearZ = min(max(squareZ1, circleZ), squareZ2); // where squareZ1 < squareZ2

now you have a point which is clipped to the dimensions of the box but which is also the closest point within the box to the circle. From here is just a simple hypotenuse to see if the distance is less than the circle radius

Code: [Select]

distance = nearX*nearX + nearY*nearY + nearZ*nearZ;
if (distance > circleR*circleR) { return 0.0; }

So now you know that a collision has occured and you have reduced the collision response to something equivelent to a simple circle circle. At this point I usually do the following

Code: [Select]

distance = 1.0/sqrt(distance); // now it's time to apply the square root
averageX = (nearX+circleX) / 2.0; // take the average between the two points
averageY = (nearY+circleY) / 2.0; // take the average between the two points
averageZ = (nearZ+circleZ) / 2.0; // take the average between the two points
circleX = averageX - circleRadius*distance*nearX;
circleY = averageY - circleRadius*distance*nearY;
circleZ = averageZ - circleRadius*distance*nearZ;

I use this simple response because I find that the closer you try to mimic real physics the more unstable the simulation becomes. It is still possible for a circle to smash through a box using this algorithm but it is fairly stable.

Edit: Opps I meant something like this for response the above is for two dynamic circles but here one circle should be static

Code: [Select]

distance = 1.0/sqrt(distance); // now it's time to apply the square root
circleX = nearX - circleR*distance*(nearX-circleX);
circleY = nearY - circleR*distance*(nearY-circleY);
circleZ = nearZ - circleR*distance*(nearZ-circleZ);


[energy]

Watch here in this package by Hitchhikr.
it includes a very good collision detection for 2D Sprites!

http://franck.charlet.pagesperso-orange.fr/Ogl_Asm.zip

[relsoft]

SAT? http://imortisoft.no-ip.org/b2b/?Issue_%231:2D_Convex_Polygon_Collision_using_SAT

Or just 4 dot products between each of the rectangle's edge and the line from one of the point on each edge to the center of the circle should do it.


BTW Shockie: I like the new look of DBF.