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:
Given some coordinates, I can check if there is a square in those coordinates.
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
Right edge of rect A is between left and right edges of rect B
Left edge of rect A <= left edge of rect B and right edge of rect A > right edge of rect B
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.
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.
