Collision detection in Java game?

Question

I am developing a game in which I have the problem of collision detection of moving images. The game has a spaceship and number of asteroids (obstacles). I want to detect the collision between them. How can I do this?

Answer 1

The chances of me reading all that code to help you out are somewhere between zero and zero percent (inclusive). Doubly so now that Jeff has removed the code itself (since it probably contributed little to the question).

However, collision detection is tricky for anything other than rectangles.

The way I've done this in the past is to provide both an image and a mask for each object. So for example, an object like the Jupiter 2 spaceship from Lost in Space would have the following image and mask:

     X            00000100000
  XXXXXXX         00111111100
 X       X        01111111110
X         X       11111111111
 X       X        01111111110
  XXXXXXX         00111111100
    XXX           00001110000

The image is what gets blatted to the screen but the mask is what's used for collision detection. You'll notice that the 1's in the mask are basically the outline and contents of the image.

The way in which you detect collision:

• check if the rectangles overlap. If not, there can be no chance of collision.
• Otherwise create a rectangle of object number 1 consisting of its mask.
• Construct another rectangle of object 2 consisting of its mask.
• Bitwise-AND the overlapping part of rectangle 2 with rectangle 1.
• If there are any 1-bits left in rectangle 1, you have collision.

This takes into account "near misses" where the bounding rectangles of each object overlap but not necessarily the object outlines themselves. Bitwise operators are an efficient way to detect this.

Here's an example of an arrow not quite hitting a balloon - tremble before my graphical design skills:

....xx....
..xx..xx..
.x......x.
.x......x.
x........x
x........x
.x......x.
.x......x.
..xx..xx..
....xx.**y.....
       .y......
       yyyyyyyy
       .y......
       ..y.....

You can see that, even though the rectangles overlap (see **y), the arrow has not actually made contact with the balloon. By applying the bitwise AND operation to the masks, those bits will end up as zero, resulting in a non-collision.

---

And @kyoryu raises an interesting point in his comment. Some games adapt well to having objects made up off smaller rectangles and you can simplify collision detection based on the rectangular components (without worrying about pixel perfection). For example, our old friend the space invader (actually the defender against the space invaders in that game) may be made up of two rectangles, X and Y with the missiles being made from Z:

    YYYY                .Z.
    YYYY                .Z.
XXXXXXXXXXXX            .Z.
XXXXXXXXXXXX            ZZZ
XXXXXXXXXXXX            .Z.
XXXXXXXXXXXX

This would come down to a simple rectangular check of the missile against the two space invader rectangles - Given the size of the missile, you could probably call it a collision even if you contact one of the . characters (consider them proximity missiles rather than those of the impact variety).

Answer 2

For simple games like this I find using circles makes detecting collisions very easy. We can make use of the Pythagorean Theorem for triangles

c^2 = a^2 + b^2

We can detect collision between two circles by knowing the that if the distance between the centers is less the the combined radius they must be colliding, right? You can then do a collision check like this:

distX ^ 2 + distY ^ 2 <= (radius1 + radious2) ^ 2 == COLLISION!

distX and distY are the distance between the centers of the two circles and the radius1 + radius2 squared can be pre-calculated unless the circle sizes are changing.

A nice thing about using circles is calculating how objects bounce off each other is also much easier than with square or rectangles.

Answer 3

Detect the X and Y of both images and then do some calculation minus width and height of each images if they are of not same size to get correct x and y coordinates. Example:

|-------
|   |
|   |
|   |
|_______|

`    |
    |
    |
    |
comming down



      |---------|
      |     |
      |     |
      |     |
      |---------|
Minus width and height to find out correct x and y

Answer 4

It's pretty easy to do collision with boxes. If you look at just the x axis, there's three possible arrangements for two boxes to be in:

1. Overlapping
2. The first box is to the left of the second one
3. The first box is to the right of the second one.

If the first box is to the left of the second one, that means that its rightmost point must be to the left of the second box's leftmost point.

first.right < second.left

If the first box is to the right of the second one, its leftmost point must be to the right of the second box's rightmost point.

first.left > second.right

If neither of these are true, then the boxes overlap on the x axis.

You can then repeat this for the y plane (substituing top and bottom for left and right) to find out if the boxes also overlap on the y axis - if they do, they are colliding! And that's really all you need to do for simple collisions in a 2d game.

The bigger problem may come up depending on how many different objects you have, as the naive implementation of collision detection is an O(N^2) algorithm.