Circle/circle and rectangle/rectangle collision detection is incredibly easy, but circle/rectangle is a harder. I know that pixel-perfect can be done by pretty much testing for any overlap in the shapes, but is there a quicker way? If I do resort to pixel perfect, I'd probably first test a bounding box, to save time.
Also, if a circle bounces off of a corner, what would be the effect? What would model that? I was thinking that a 45° angle would be roughly correct, but I realized that I had no idea what would actually happen.
You'll probably want to start getting into the separating axis theorem.
Are your boxes rotated? If not, it should be relatively easy to work something out without needing SAT.
If circle-circle collisions are incredibly easy, it seems to me that you could "cheat" at rectangle corners by emulating an arbitrarily small circle at the corner.
For the sides of the rectangle I'd simply bounce the center of the circle (which is a point after all) off of a line that's offset from the rectangle by the radius of the circle.
Axis-aligned or object-oriented?
If the former, you can just check (center + radius > left side) && (center - radius < right side) && (center + radius > upper side) && (center - radius < lower side). The latter is slightly more complicated but works on pretty much the same principle...
If circle-circle collisions are incredibly easy
They are.
if distance from center1 to center2 < radius1 + radius2 collision else no collision
It generalizes to spheres as well. It doesn't even require any costly mathematical functions, since you can check for distance squared < radius1 squared + radius2 squared instead and do away with the square root in the distance calculation.
Axis-aligned or object-oriented?
just "oriented", as in "axis-aligned or oriented?"
Detecting collisions is easier than calculating the correct collision response.
Didn't we have a thread on this just the other day?
Anyway, one way to do it properly is to start with circle - line-segment collision. This is done by finding the perpendicular distance of the centre of the circle to the line-segment. If this is smaller than the radius of the circle and if the point of intersection of the perpendicular bisector is within the bounds of the line-segment (you don't want an infinite line of course!), then you have a collision.
Do this for each line-segment defining the rectangle to check of a collision.
Finally (or firstly, if you care about optimisation), you'll also want to check if the centre of the circle is inside the rectangle, in which case you have a collision for sure.
However, it's the usual case of : "If you were capable of writing the code to do it, you would be capable of coming up with the solution on your in own in the first place". Which means that you're probably not capable of coding it, and you should instead use someone else's code.
Didn't we have a thread on this just the other day?
More like a month ago.
For axis-aligned rectangles:
A circle (defined by cx, cy, and cr) and a rectangle (defined by l, t, r and b) intersect if any of the following is true:
1. (l < cx < r) AND (t - cr < cy < b + cr)
2. (l - cr < cx < r + cr) AND (t < cy < b)
3. Any one of the rectangle's corners lies inside the circle
A quick rough outer bounding box check can be added to sort out the obvious non-collisions.
For rotated rectangles, the trick is to rotate the entire thing so that the rectangle is axis-aligned.
I went to go read about the separating axis theorem and then I mowed the lawn and then I got distracted which is why I'm just now responding. I sort of understand the separating axis theorem, but it isn't actually necessary. I actually came to the same conclusion as Tobias.
Individual responses:
@Mark Oates: Boxes are not rotated, but there are triangles, so I'll need to figure those out. I can probably just apply the same principles, right?
@gnolam: Wouldn't that just check for the four sides, not bouncing off of a corner?
So...triangles. They're right isosceles triangles (with two sides parallel to the x and y axis). Just check intersection on each side and if any of the corners are inside it?
Bonus new question: since the circle is moving around a map and it can be hitting something like
___ __ | | / \ |___| \__/ | | |___|
and it could "hit a corner" by checking from partially through one block. If I want it to bounce of like a normal wall, what would be the best way to do that?
Maybe just look at the eight blocks around the circle's position (and the one where it is) and don't treat them as separate blocks, but make a collision detection algorithm that just treats the surrounding area as a bunch of lines instead of multiple blocks?
I guess I might as well put in a SS.
{"name":"6ifb6e.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/9\/8\/983fe099c23171d333ffeaf482074a66.png","w":616,"h":676,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/9\/8\/983fe099c23171d333ffeaf482074a66"}
I need to check if a circle and an AABB will collide in the next frame, and if so at what time during the frame will the collision occur.
The method I'm using is to see if the centre of the circle will intersect with the Minkowski sum of the circle and the AABB. I'm breaking it up into four steps, one for each line segment.
Determining when the collision occurs is easy if it occurs within the edge Voronoi regions, but I'm not sure how to determine if and when it will intersect the vertex Voronoi regions.
Here's a diagram to explain what I'm talking about:
{"name":"601377","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/2\/b\/2b5b5bfd51bef53b6489e59f755da245.png","w":553,"h":295,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/2\/b\/2b5b5bfd51bef53b6489e59f755da245"}
If the red line (which represents the path at which the centre of the circle will travel) intersects the blue round-cornered box (this is the Minkowski sum of the circle and the AABB), then the circle and the AABB (the black rectangle) will collide.
The vertex Voronio regions I'm interested are there areas here (magnified and shaded):
{"name":"601378","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/f\/3\/f3b25a3050833a669ef42387aef8a129.png","w":508,"h":388,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/f\/3\/f3b25a3050833a669ef42387aef8a129"}
What would be the best way to determine if and when it intersects this region, when the circle could be travelling in any direction?
I'm only just starting to get a grasp of the concepts involved here, so I nice simple explanation would be appreciated.
When the distance between the vertex and the circle center is equal to the circle's radius, you have a collision; when it's smaller, you have an overlap.
You do have to weed out the solutions where the collision point lies inside the line region, but that's easy.
When the distance between the vertex and the circle center is equal to the circle's radius, you have a collision; when it's smaller, you have an overlap.
That's the part I already know.
Perhaps I worded my query badly. How, algorithmically, should I go about determining if the centre of the circle will pass through this region?
Ever heard of Sutherland Hodgeman clipping? Then this diagram should make sense. If the center is within the upper and lower lines of the original rectangle, then you test against the right and left sides, vice versa for within right and left. Otherwise you see if the center of the circle is within a similar sized circle at each corner.
{"name":"601379","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/0\/1\/011fd87c494ae1d5f90fe0bb06b80626.png","w":639,"h":485,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/0\/1\/011fd87c494ae1d5f90fe0bb06b80626"}
Circle A is hitting the top edge, circle B is hitting the left edge, and circle C is hitting the lower left corner.
You can always have superfast pixel-perfect collision detection by comparing scanline boundaries between two sprites.
Ever heard of Sutherland Hodgeman clipping? Then this diagram should make sense.
I hadn't, no. After reading the linked article, I'm not sure how it would help with my problem. Could you explain more?
If the center is within the upper and lower lines of the original rectangle, then you test against the right and left sides, vice versa for within right and left. Otherwise you see if the center of the circle is within a similar sized circle at each corner.
I don't want to know if two circles overlap. That is trivial. I want to know if a circle moving along a path will overlap another circle, and at what point.
You can always have superfast pixel-perfect collision detection by comparing scanline boundaries between two sprites.
I can't unfortunately, as I'm not working with Allegro. The library I'm working with (and I have no choice in this, since I'm doing this for its developers) has no concept of sprites or pixels. I only have circles and lines.
I want to know if a circle moving along a path will overlap another circle, and at what point.
This can be solved with this page
http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/
as the center of the stationary circle is indeed a point, and the center of the moving circle forms a loci that is the line.
{"name":"601381","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/a\/6a95be606e1925890c2b9fa5dea07365.png","w":950,"h":548,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/a\/6a95be606e1925890c2b9fa5dea07365"}
The vertical line is the distance at closest approach, and the slanted line is the yet-to-be-found line where the first collision occurs (hypotenuse). This hypotenuse is necessarily the sum of the two circles radii. Now apply this:
{"name":"triangle-soh-cah-toa.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/5\/e5c9cabcb07d486d4d4ada401a4a1f4e.png","w":400,"h":313,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/5\/e5c9cabcb07d486d4d4ada401a4a1f4e"}
and this:
Well you want the arcsine I think. (reciprocal)
Thanks Arthur, but I'd prefer to do this with vector mathematics rather than trigonometry.
I actually decided to redo my approach. I'm now going to do four circle/line-segment intersection checks instead. This way the code can be used for OBBs as well as AABBs, and for any other polygon.
The way I intend to do this check is to produce the Minkowski sum of the line segment and the circle, and see if the circle centre will intersect the capsule that is produced. This can be done with two line/line and two line/circle intersection tests.
This brings me to my next query. The following diagram shows the capsule produced when the line AB is swept by a circle of radius r.
{"name":"601402","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/c\/a\/cafc51c989a4d6155828a509b1b4cd32.png","w":457,"h":397,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/c\/a\/cafc51c989a4d6155828a509b1b4cd32"}
I need to calculate the positions of points A', A'', B' and B'', so that I can test for the intersection of lines A'B' and A''B''. Here's how I think it can be done, but if anyone knows a better way, I'd love to here it:
First, create a 2D vector (dx, dy), where dx = B.x - A.x and dy = B.y - A.y. Then produce the normal to this vector N1, which will be (-dy, dx). N1 will then need to be normalized to produce a unit vector U1 (U1 = N1 * 1/N1.length). The unit vector will then be multiplied by the scalar value r, to produce the final vector, which can be added to A and B to produce A' and B' (A' = A + rU1), B' = B + rU1).
The steps for A'' and B'' will be the same, except using N2 = (dy, -dx).
Correct to this point?
If I want a perpendicular line, I just multiply the slope by -1 <shrug>
If I want a perpendicular line, I just multiply the slope by -1 <shrug>
Essentially, that's what I am doing.
I don't know the slope of the line, so it would have to be calculated using the positions of points A and B. If you have a vector (dx, dy) representing the line, then the angle of the slope is dx/dy. If you multiply that by -1 you get -dy/dx, which when put back into vector form, gives (-dy, dx) or (dy, -dx).
edit:
Well, It all seems to be working ok. Here's what I ended up with: