best way to implement collision detector in oop

Question

I am making a simple physics based game in java and i am stuck in implementing the collision detection methods. I have several classes which inherits from a comman base class shape. I am storing all the visible objects in an arraylist of shape class. I have created several collision detection methods for every possible collision of objects. When i started implementing the methods i ended up with a code like this:

private void collision_detector(Shape s1,Shape s2){

    if(s1.getClass()==Ball.class)
        if(s2.getClass() == Block.class) collision_detector((Ball)s1,(Block)s2);
        else collision_detector((Ball)s1,(Ball)s2);
    else if(s1.getClass()==Block.class)
        if(s2.getClass()==Block.class) collision_detector((Block)s1,(Block)s2);
        else collision_detector((Ball)s2,(Block)s1);        
}

It just doesn't feel like the right way to implement the collision detection because i have to update this method to check for every possible combination every time i add a new shape like triangle or hexagon. I know a bit about Visitor patterns. But Is there any better way to do this ?

Answer 1

If you don't mind putting collision detection code in the objects themselves, you could eliminate one side of the checks by doing something like:

public abstract class Shape {
    public abstract boolean collidesWith (Shape s);
}

public class Ball extends Shape {
    @Override public boolean collidesWith (Shape s) {
        if (s instanceof Block)
            return Collision.blockBall((Block)s, this);
        else if (s instanceof Ball)
            return Collision.ballBall(this, (Ball)s);
        else
            return false;
    }
}

public class Block extends Shape {
    @Override public boolean collidesWith (Shape s) {
        if (s instanceof Block)
            return Collision.blockBlock(this, (Block)s);
        else if (s instanceof Ball)
            return Collision.blockBall(this, (Ball)s);
        else
            return false;
    }
}

public class Collision {
    public static boolean blockBlock (Block a, Block b) { ... }
    public static boolean blockBall (Block a, Ball b) { ... }
    public static boolean ballBall (Ball a, Ball b) { ... }
}

That also gives you the freedom to implement collision algorithms for certain combinations of Shapes in the Shape itself if necessary -- you can even get rid of Collision and just make e.g. Block.collideWithBall, Block.collideWithBlock, and Ball.collideWithBlock, calling those as appropriate, e.g.:

public abstract class Shape {
    public abstract boolean collidesWith (Shape s);
}

public class Ball extends Shape {
    @Override public boolean collidesWith (Shape s) {
        if (s instanceof Block)
            return collidesWithBlock((Block)s);
        else if (s instanceof Ball)
            return collidesWithBall((Ball)s);
        else
            return false;
    }
    public boolean collidesWithBall (Ball b) {
        ... 
    }
    public boolean collidesWithBlock (Block b) {
        ...
    }
}

public class Block extends Shape {
    @Override public boolean collidesWith (Shape s) {
        if (s instanceof Block)
            return collidesWithBlock((Block)s);
        else if (s instanceof Ball)
            return ((Ball)s).collidesWithBlock(this);
        else
            return false;
    }
    public boolean collidesWithBlock (Block b) { 
        ...
    }
}

Personally, I kind of like the latter better, since it keeps collision code contained in the relevant classes. Note that Block.collidesWithBall is unnecessary, as Ball.collidesWithBlock can be used.

You still have to update the above code each time you add a new shape. If performance is not an issue, you could do something like this as well:

public abstract class CollisionAlgorithm {
    public abstract boolean canCollide (Class<? extends Shape> a, Class<? extends Shape> b);
    public abstract boolean collide (Shape a, Shape b);
}

public class Collider {

    private static final List<CollisionAlgorithm> algorithms;

    public static void registerAlgorithm (CollisionAlgorithm a) { 
        algorithms.append(a); 
    }

    public static CollisionAlgorithm findAlgorithm (Class<? extends Shape> a, Class<? extends Shape> b) {
        for (CollisionAlgorithm algo : algorithms)
            if (algo.canCollide(a, b))
                return algo; 
        return null;
    }

    public static boolean collide (Shape a, Shape b) {
        if (a == null || b == null) 
            return false;
        CollisionAlgorithm algo = findAlgorithm(a.getClass(), b.getClass());
        if (algo != null)
            return algo.collide(a, b);
        algo = findAlgorithm(b.getClass(), a.getClass()); // try swapped order
        if (algo != null)
            return algo.collide(b, a);
        return false;
    }

}

// usage: first register algorithms
Collider.registerAlgorithm(new BallBallAlgorithm());
Collider.registerAlgorithm(new BallBlockAlgorithm());
Collider.registerAlgorithm(new BlockBlockAlgorithm());

// then 
Shape myShape1 = ...;
Shape myShape2 = ...;
boolean collide = Collider.collide(myShape1, myShape2);

Please note: I typed this here quickly, and it's meant to illustrate a concept -- many improvements can be made. For example, a map can be used with the two Shape classes as a key to improve performance, or CollisionAlgorithm can be given generic parameters to eliminate the need for casting Shapes. Still, keep in mind, this approach requires a lookup in the algorithm container every time you need to perform a collision test.