Collision detection android (with asteroids!!)

Question

I'm currently creating an android java game. A kind of lunar lander type game. I wish to implement some kind of obstacles, and have gone for asteroids that will be randomly placed on screen.

However, I am struggling to understand how about doing collision detection for these. I will be using images for the asteroids, so could easily use a rectangular bounding box for each image, but as asteroids are circular (or at least mine will be!), a collision could be detected when moving just over the corner of the rectangle, that isn't visually part of the asteroid.

I'm guessing I need to use some sort of bounding circles, but not really sure how I could set this up with images?

I guess, if all the asteroids were the same size, I could hardcode some points for a circular/polygon bounding box and then translate these to the position of the images - so in effect, the polygon is the shape of the asteroid?

Any suggestions on the best method of doing this would be great. Additionally, if someone could whip up some high level collision detection pseudocode, that would be appreciated :)

Answer 1

If the lander rectangle is axis-aligned (its edges are parallel to the coordinate axes), it is easy to check collisions with circles. Given a circle with radius r and centre (cx, cy) and a rectangle with origin (x, y), width w, and height h; they collide if one of the followings is true:

• (x < cx < x+w) and (y-r < cy < y+h+r)
• (y < cy < y+h) and (x-r < cx < x+w+r)
• The distance between any of the rectangle's corner and (cx, cy) is lower than r.

As I've said in my comment, the collision between circles is even easier, because you only have to check if the distance between the centers is lower than the sum of the radius.

For non axis-aligned rectangles, the solution is a bit more complex. Given the four vertices of the rectange (A, B, C, D); if any of the following is true, then a collision occurs:

• (x < cx < x+w) and (y < cy < y+h)
• intersectCircle(A, B, cx, cy, r)
• intersectCircle(B, C, cx, cy, r)
• intersectCircle(C, D, cx, cy, r)
• intersectCircle(D, A, cx, cy, r)

The pseudocode of the function intersectCircle is this:

intersectCircle(P1, P2, a, b, r):
    x1, y1 = P1
    x2, y1 = P2
    p = abs((x1-x2)*(a-x1)+(y2-y1)*(b-y1))
    q = sqrt((x1-x2)^2 + (y1-y2)^2)
    return r > p/q

This function is based on the formula of this Mathematics' answer, which is by far the simplest one I've found.