How to
detect collisions
between moving GUI-objects?
In a GUI with moving objects (e.g. animation) it's sometimes nice to know when
two (or more) objects are colliding - this note describes a solution.
|
The solution is used in the applet you (hopefully) see to the right (we'll
discuss the applet a little later). Two types of objects (circles and
planets) are moving (and bouncing) inside a rectangle with individual
direction (angle) and speed. When a circle is "touching" a planet
they both change color. In this applet a collision is defined as "the
areas of the two objects are overlapping".
In other situations the definition could be different (maybe overlapping
isn't possible) - that's not important here. You can define your own rules
and construct your program so it reacts accordingly. The main problem
is to know how you can detect that objects are colliding!
First let me admit that the solution isn't perfect!! In defining the
objects area I'm cheating a bit. It turns out that for complex shapes
it's VERY difficult to detect a collision.
Imagine you must detect a collision between to stars:  and:
 . There
is hundreds - if not thousands - of different ways these two areas can
overlap. You end up comparing every single bit in the first image
against every single bit in the second image. Even for a computer
that's hard work! And say you have a few hundred objects to check....
We have to cheat!!
|
|
|
Instead of comparing complex shapes we'll compare rectangles. The trick is
that we define the smallest rectangle that covers the shape completely (or partial
if that's more suitable).
In other words this area will be the bounds for our shape. So instead
of checking: we'll
be checking: 
- much easier!
We loose a little accuracy, but you'll normally not see the difference when
the shapes are moving.
To check whether two rectangles overlap we have to compare their x-coordinates
and their y-coordinates.
For the sake of simplicity we'll assume that the y-coordinates of the two rectangles
DO overlap. So for the time being we'll only focus on the x-coordinates.
Ignoring the y-coordinates we have five different possibilities:
| Example 1 |
Example 2 |
Example 3 |
Example 4 |
Example 5 |
 |
 |
 |
 |
 |
Let's name the left and right sides of Box A as A_Left and A_Right.
For Box B we name the sides as B_Left and B_Right.
For a collision to occur the following statement must be true:
| |
(A_Left is to the left of B_Right) AND (A_Right is to the right of
B_Left) |
|
| |
(To be absolutely precise
we should say: "...to the left of or equal to..." etc.) |
|
Note that the statement consists of two parts which both must be true!
The first part excludes "Example 5"
and the second part excludes "Example 1" leaving us with the three examples
where collision do occur (as we wanted!)..
Take your time to ensure yourself that the statement implies collision and,
importantly: collision implies that the statement is true!
Now if we name the x-coordinate for the side A_Left as AX1,
the x-coordinate for the side A_Right as AX2 and
so on, we can translate the statement (using Java code) into :
It's possible to do exactly the same considerations for the y-coordinates.
NOTE that on a GUI the y-coordinate's starts from the top (y = 0) and
increases as we go down the screen (in contrast to "normal" coordinates).
So we end up with: (AY1 <= BY2) && (AY2 >= BY1).
Of course both the x-coordinate and the y-coordinate must overlap
so the final statement is:
| |
(AX1 <= BX2) && (AX2 >= BX1) && (AY1 <= BY2) &&
(AY2 >= BY1) |
| |
If you're not sure what's going
on, then draw some examples with and some without overlap, then check the
x- and y-coordinates against the statement. |
|
 |
Now back to the applet (which, btw, can run as an application
also).
Below is a description of each file.
I've tried to apply "quality" as much as possible (at least for the
model-classes) - see comments below. The model-view-controller (MVC) architecture
is used.
| MovingPoint.java |
Defining a class describing an "invisible"
moving point. Contains modifiers for all "moving attributes":
position (x- and y-coordinates), direction (angle for movement)
and speed (distance moved in each time-period).
Also contains a bounding rectangle (see above).
Implemented with "Effective Java" in mind! |
| MovingCircle.java |
Sub-class of MovingPoint.
Adds a radius and a color (with modifiers).
Implemented with "Effective Java" in mind! |
| MovingImage.java |
Subclass of MovingPoint.
Adds an image (with modifiers).
Implemented with "Effective Java" in mind! |
| GameDefaults.java |
Holds all the default-values like
width and height of the field, the number of circles and images, the color
of a "normal" circle and of a circle participating in a collision
etc. etc.
Look for yourself - the attribute names should be self-explaining!
One trick, though: The images must be loaded completely in
order to determine their width and height (bounds). As the load-procedure
uses non-static Java-methods it must be performed in a non-static context.
My solution is to do the image-loading in the constructor. As the class
has no methods (only final values) there is no reason for creating an instance
of the class (in the same way as you don't instantiate the Math-class).
But because of the loading in the constructor it is very important
to create an instance (which can be abandoned afterwards) before
reading the image-data! Any "cleaner" solutions out there?? |
| GameModel.java |
The model holds an array of circles
and an array of images. When initializing objects, the common attributes
are set (with random values) in a method handling MovingPoint's.
As the model must notify the view when it should be updated there's a method
to be called from anyone who changes the state of the model.
Note that the array's can be accessed directly via two methods getXxx() |
| GameView.java |
The view knows how to visualize
the objects. Holds a reference to the model so it can get access to the
two array's. |
| GameController.java |
The controller is responsible for
updating the movements of every object. Using a bit of math the new positions
are calculated. Then they're checked against the global borders and corrected
if an object tries to get out of the game....
When an object hits the borders, the objects "bounce" back - so
the angle is also checked and maybe corrected.
And finally we check for collisions. First the appearance of every
object is set to normal (so objects who just left a collision looks as they
should) and then every image is checked against every circle for collision
(objects don't change if they collide with an object of the same type).
If two objects collide their appearance is changed (according to values
from GameDefaults).
The last thing done by the controller is to notify the model that it's state
has changed. |
| CollisionExample.java |
Ties everything together.
Note that there's a main()-method
so the program can be executed as an application and there's
init(), start()
and stop() methods
so it can run as an applet. Both ways sets up the game through a common
method.
The controller is "powered" by a Timer
(defining the "time-slices" between every movement) |
| Earth1.gif,
Earth2.gif |
Images for a "normal"
earth and a "collided" earth. |
In this web-page all files has been packed into one .jar
file
Particularly the model-classes are more "heavyweight" than
necessary for this example.
They're constructed according to the recommendations in "Effective Java",
in the other classes you'll see less dogmatic programming... 
The following items have been considered (more or less..) during the process
: 1, 2, 3, 4, 7, 8, 9, 10, 11, 12, 13, 14, 15, 19(!), 23, 24, 25, 26, 29, 30,
37, 38, and 39.
Note that I wrote considered - sometimes this actually means that after
considering, I choose to go against the recommendations! I also did that
a few times without any considering......
Have fun finding all my mistakes!
If you find a lot I'll consider rewriting the program....
- Allan
