How to determine the collision of a circle with a rectangle?

Question

I have looked EVERYWHERE for leads on how to get this to work (nicely) and so far every solution I have come up with has been ugly or didn't work. What I have is a circular sprite, the enemy. Then I have a sprite that is in the shape of an arrow.

When checking for collision for the arrow in the enemy, I use CGRectIntersect(rect1, rect2) but... circles are not rectangles! The collision is disgusting.

So my question is, how do I go about checking for collision inside a circular object? Should I make many rects, or is there something out there that is made for this purpose?

Answer 1

I found a very handy page (http://www.migapro.com/circle-and-rotated-rectangle-collision-detection/) with some code and a nice demonstration, and have ported that solution to Objective-C.

when I ported the code, I also altered it such that the coordinate provided within the CGRect is actually the center of the rectangle as opposed to the top-left corner as per the original code. This allows it to be used for Cocos2D objects like CCSprite's very easily.

The code (which for me seems to work very well) is shown below:

@interface Cocosutil : NSObject

typedef struct {
    float overlapSize;
    BOOL intersects;
} ccIntersection;

+ (ccIntersection) intersectionOfCircleWithRadius:(float)radius 
                                          atPoint:(CGPoint)circlePt
                                     andRectangle:(CGRect)rect
                                     withRotation:(float)rotation;

@end

@implementation CocosUtil

#define CC_DEGREES_TO_RADIANS(__ANGLE__) ((__ANGLE__) * 0.01745329252f) // PI / 180

// Original code is from:
//
// http://www.migapro.com/circle-and-rotated-rectangle-collision-detection/
//
+ (ccIntersection) intersectionOfCircleWithRadius:(float)radius atPoint:(CGPoint)circlePt andRectangle:(CGRect)rect withRotation:(float)rotation {
    ccIntersection result;

    // Rotate circle's center point back
    float unrotatedCircleX =
        cosf(CC_DEGREES_TO_RADIANS(rotation)) * (circlePt.x - rect.origin.x) -
        sinf(CC_DEGREES_TO_RADIANS(rotation)) * (circlePt.y - rect.origin.y) + rect.origin.x;

    float unrotatedCircleY =
        sinf(CC_DEGREES_TO_RADIANS(rotation)) * (circlePt.x - rect.origin.x) +
        cosf(CC_DEGREES_TO_RADIANS(rotation)) * (circlePt.y - rect.origin.y) + rect.origin.y;

    // Closest point in the rectangle to the center of circle rotated backwards(unrotated)
    float closestX, closestY;

    // Find the unrotated closest x point from center of unrotated circle
    if (unrotatedCircleX  < (rect.origin.x - (rect.size.width/2.0f))) {
        closestX = rect.origin.x - (rect.size.width/2.0f);
    } else if (unrotatedCircleX  > rect.origin.x + (rect.size.width+rect.size.width/2.0f)) {
        closestX = rect.origin.x + (rect.size.width/2.0f);
    } else {
        closestX = unrotatedCircleX ;
    }

    // Find the unrotated closest y point from center of unrotated circle
    if (unrotatedCircleY < (rect.origin.y - (rect.size.height/2.0f))) {
        closestY = rect.origin.y - (rect.size.height/2.0f);
    } else if (unrotatedCircleY > (rect.origin.y + (rect.size.height/2.0f))) {
        closestY = rect.origin.y + (rect.size.height/2.0f);
    } else {
        closestY = unrotatedCircleY;
    }

    // Determine collision

    float distance = [CocosUtil distanceFrom:CGPointMake(unrotatedCircleX , unrotatedCircleY) to:CGPointMake(closestX, closestY)];

    if (distance < radius) {
        result.intersects = YES; // Collision
        result.overlapSize = radius - distance;
    } else {
        result.intersects = NO;
        result.overlapSize = 0.0f;
    }

    return result;
}

+ (float) distanceFrom:(CGPoint)from to:(CGPoint)to {

    float a = abs(from.x - to.x);
    float b = abs(from.y - to.y);

    return sqrt((a * a) + (b * b));
}

@end

Answer 2

Detecting the collision of a circle and a rectangle is anything but simple. Here's a C++ example class that does this kind of test (source with plenty of other intersection test examples). There's also an answer on SO that only shows pseudo-code. The N+ developers also explain their approach to circle vs rectangle collision detection. If any of this seems too much for you, you're hereby advised to look for a simpler approach. ;)

For example, since you mentioned "arrow" that implies a pointed, thin object that tends to fly relatively straight in one direction, with the arrowhead always being pointed in the direction of flight. If that is not the case, I may be have been living on a different planet, otherwise I'll use this assumption.

It means you can very easily change the collision type of the arrow from rectangle to circle. The circle only needs to be as big so that it encloses the arrowhead. Depending on graphics and your game design it may be even sufficient to have a collision circle at the very tip of the arrowhead. Then you can implement Joshua's suggestion of circle vs. circle collision tests.

An alternative for very thin arrows would be to assume the arrow to be a line, then you can work with a reasonably simple line-circle intersection test.

Answer 3

I have no idea if Cocos provides a function to do this, but the math is really quite simple.

You take the two center points of the circles, and get the distance between them using your standard distance formula. float distance = sqrt(pow((x2-x1), 2) + pow((y2-y1), 2) and check if that is less than the sum of the radius of the two circles you're checking.

BOOL checkCircleCollision(CGPoint center1, float radius1, CGPoint center2, float radius2)
{
    float distance = sqrt(pow((center2.x-center1.x), 2) + pow((center2.y-center1.y), 2);
    return distance < (radius1 + radius2);
}

BOOL optimized_CheckCircleCollision(CGPoint center1, float radius1, CGPoint center2, float radius2)
{
    float a = center2.x - center1.x;
    float b = center2.y - center1.y;
    float c = radius1 + radius2;
    float distanceSqrd = (a * a) + (b * b);
    return distanceSqrd < (c * c);
}