Collision detection

Holger Weissböck on April 13, 2010

Collision detection is a substantial part of almost all games. Unfortunately it is also a part where lots of CPU cycles can get lost, resulting in choppy game-play and short battery life. In order to keep calculation costs down, it helps to exit collision detection code as soon as possible. Gradually refining the detection complexity helps doing so. Using Sparrow, we recommend a 3 step approach to collision detection:

Bounding Sphere Check

Start by checking collisions of the bounding spheres of the object. (That’s just another way of saying: check the distance between your objects.) To do that, it helps if your objects have their origin roughly in the center of your objects. Let’s use an example: the 2 objects you want to check are both images of space-ships. You could make a class “Ship”:

@interface Ship : SPSprite
@end

@implementation Ship

- (void)init
{
  if (self = [super init])
  {
    SPImage *img = [SPImage imageWithContentsOfFile:@"spaceship.png"];
    img.x = -img.width / 2;
    img.y = -img.height / 2;
    [self addChild:img];
  }
  return self;
}

@end

The important thing here is that we moved the image into the center of the SPSprite. If you rotate the spaceship now, it rotates about its center - probably, that’s what you would have needed, anyway.

The image shows the red bounding spheres and the center distance of our two spaceships. Now, to check if the two spaceships collide, we just need to check how far they are apart:

SPPoint *p1 = [SPPoint pointWithX:ship1.x y:ship1.y];
SPPoint *p2 = [SPPoint pointWithX:ship2.x y:ship2.y];

float distance = [SPPoint distanceFromPoint:p1 toPoint:p2];
float radius1 = ship1.width / 2;
float radius2 = ship2.width / 2;

if (distance < radius1 + radius2)
  NSLog(@"Collision!")

That’s the bounding sphere test - easy, isn’t it? In the image, you can see that the bounding spheres are slightly bigger than the spaceships, so the test is not accurate enough yet. If the bounding sphere test resulted in a collision, we can refine the detection and move on to the next, more exact, check.

Bounding Box Check

For this test, imagine that you draw a rectangle around your object (instead of the circle): a rectangle that is just big enough that all contents of your object fits into it:

Again, we have a look at our spaceships: If both of them are part of the same coordinate system, the bounding box check is super easy:

SPRectangle *bounds1 = image1.bounds;
SPRectangle *bounds2 = image2.bounds;

if ([bounds1 intersectsRectangle:bounds2])
   NSLog(@"Collision!");

The bounds-property is supported by all display objects - including Sprites. It calculates a bounding box that contains all its child elements. Sometimes, the objects are not in the same coordinate system (perhaps they are in different sprites). Fortunately, you can get the bounding box in just the coordinate system you need:

SPRectangle *bounds = [someObject boundsInSpace:self];

Keep in mind, however, that all those bounding boxes are upright rectangles. An SPRectangle object does not have a rotation property! So, if you have a rotated image, the bounding rectangle will grow during the rotation so that the image fits in.

Thus, this method might still be not exact enough - but it will suffice for many purposes. And if it’s not exact enough, you can advance to an even more exact collision detection check.

Custom Point Check

In order to check for different shapes of objects, you can test for collisions of special points of an object (e.g.: in a rectangle: the corners.). The SPRetangle class has the method containsPoint:, for exactly that reason.

Custom point checks make it possible to test for even the most peculiar object shapes. However, this test is also the most CPU intensive one and should be avoided if possible.

Conclusion

In the end it’s all about starting rough, and then getting more exact. Exiting collision detection early keeps you from bothering the CPU with unnecessary tasks. This not only saves a lot of time in every frame, but can also save precious battery life. Happy colliding!