Idea for collision detection between arbitrary shaped objects in 2D

Game Mechanics
#1

How viable is this idea in a game? You give each sprite (bouncing ball, bullet, monster, etc…) a java.awt.geom.Area object which represents it’s bounds. You could even have a list of them if you want to for animations which change shape. Then to test for a collision you can just see if the areas union equals their xor. If it does then no collision happened.

public boolean collision(Area a, Area b) {
 Area union = new Area(a); // you make copies of a since Area's add() and exclusiveOr() methods will edit the object
 Area xor = new Area(a);
 union = aa.add(b);
 xor.exclusiveOr(b);

 return !union.equals(xor); // equals is built into Area
}

I don’t know how fast or slow these Area methods are (no doubt they are slower than Rectangle.contains()), but I don’t see why this wouldn’t work, especially for a small number of sprites on the screen. You could even have the Area object created automatically from your sprites Image. Anyone have any thoughts on this method? I came up with this while working on my Tower Defense game and trying to figure out a way to set certain parts of the map “unbuildable” (like where the enemies walk, and where you have already built something).

#2

So After thinking about it for 2 seconds I realized it’s better to just test if their intersection is empty. DOH! :stuck_out_tongue:

#3

dont’ know about java.awt.geom.Area but Slick2d’s Polygon class has intersect() and contains() and it’s all implemented to be fast as possible. I suggest using circle vs circle or rectangle vs rectangle for (extreamly) fast result.

#4

Area is realllllllllly slow, I don’t recommend doing that at all.

If you really need pixel perfect collision detection, I would first check if their rectangle bounds intersect, THEN you do the Area checking:


public boolean collision(Area a, Area b) {
    if(a.getBounds().intersects(b.getBounds())) {
        Area union = new Area(a);
        union.intersect(b);
        return !union.isEmpty();
    }
    
    return false;
}
#5

That’s how I usually end up doing things. If the game entities can’t be represented well by (axis-aligned) rectangles or circles (or by a collection of rectangles or circles), then Area objects are a simple way of getting things working.
Simon

#6

Be warned that although this allows you to detect collisions, it doesn’t give you the normals to handle a collision response. So it’s fine if you want to overlap the monsters and take continual damage, but not if you want to bounce off them.