3
\$\begingroup\$

I'm developing a 2D game made of squares.

What I need to do is check if a circle collides with any of the squares as it moves.

I have a raycast function to check the same idea, but using a point. I think the best idea would be to do a circle-raycast, but I have no idea how to do it.

The information I have:

  • Starting coordinates of the center of circle
  • Last coordinates of the center of the circle
  • Radius of the circle

Given some coordinates, I can check if there is a square in those coordinates.

\$\endgroup\$
  • 1
    \$\begingroup\$ expand the squares to rounded squares (radius equal to to the radius of the circle) and then check intersection of the line \$\endgroup\$ – ratchet freak Dec 2 '14 at 21:31
  • \$\begingroup\$ I asked for suggestions on Twitter, here's what I got so far: twitter.com/uliwitness/timelines/542692239739473920 \$\endgroup\$ – uliwitness Dec 10 '14 at 14:52
2
\$\begingroup\$

First thing you should do to save some time is eliminate the ones that can not match. To do this, calculate the smallest rect that contains the circle. Intersect that with whatever rect you think might intersect with it (loop over all of them, most likely). Two rectangles intersect if they overlap both horizontally or vertically. There are three ways an intersection can happen:

Left edge of rect A is between left and right edges of rect B

enter image description here

Right edge of rect A is between left and right edges of rect B

enter image description here

Left edge of rect A <= left edge of rect B and right edge of rect A > right edge of rect B

enter image description here

And the same for vertical (i.e. swap top for left and bottom for right). If you have an intersection in both directions, the rectangles overlap.

If that doesn't match, they can't be intersecting. If it does, you can do more expensive, more complicated tests:

If the circle's surrounding rect fits into the rect you're intersecting with, you know they intersect.

The only cases left are whether the center of the circle lies inside the rect (point-in-rect test) and whether one of the rect's edges intersect the circle. For that, you use a circle equation. If your centre is a,b and your radius is r, you'd have to solve

(x-a)*(x-a) + (y-b)*(y-b) = r

to find out if a point (x,y) lies within the circle. So loop over each point in the line for each edge and plug it into the above equation as x,y. If any of them solve, you know that the rect intersects the circle.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ (If I understood correctly), by using this I could check if a circle overlaps with a square (or many spquares if I loop through them). But what I actually need is to check if the circle would overlap if it moved in a certain direction. So... The problem is.... I don't know where there is going to overlap (or if it is going to overlap). I could do that by making multiple checks, moving the circle a little, cheking, moving, cheking, etc.... As I have it implemented right now. But.... thats not very efficient. Anyway, thanks for your answer :) \$\endgroup\$ – DevPGSV Dec 9 '14 at 19:52
  • \$\begingroup\$ @DevPGSV You can make this faster by calculating the rectangle enclosing the start and end position of the circle and intersecting that first. If there's nothing or interest in there, you can avoid the actual circle intersections. Then do a rectangle check for individual circle bounding rectangles that you move forward in steps of the rectangle's height, and once you have an intersection there, test it against the actual circle (<rect height> times). That's sufficient if your movements can only be h or v, else you need to intersect polygons (rotated rects) as extra steps. \$\endgroup\$ – uliwitness Dec 10 '14 at 14:03
  • \$\begingroup\$ @DevPGSV Oh wait, you could maybe calc the intersection of the two overlapping rectangles, then check if that is more than <radius> pixels from all possible circle centers. Right triangles and Pythagoras should be all that's needed for that. \$\endgroup\$ – uliwitness Dec 10 '14 at 14:08
2
\$\begingroup\$

This is a problem that has several solutions and optimizations to it, especially in 3d. 2d, there are fewer but still more than one "right answers". If you understand the first answer, but not this one, it has a good chance of being "Fast enough" on modern hardware there won't be a problem.

Another solution is Quadtrees: http://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space--gamedev-374

Also linked in that article (at the bottom) is a good article on the general problems and optimizations

This is an area it's easy to over optimize if you are writing your own engine. Consider using a library such as http://box2d.org if writing the game engine isn't what you're concerned with.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.