Elegant way of encapsulating behaviour that depends on the combination of involved objects?

Question

In want to check whether two items collide in space. For that purpose both items are represented by some simplified geometric shapes - for simplicity lets assume these shapes can only be circles, polygons and lines. The items can be represented by any of these shapes and the collision-detection needs to be able to handle any of the possible combinations. I want to find a strategy that involves minimal code duplication and allows adding further shapes in the future.

My approach is the following:

public class Item{

   private Collidable bounds;

   public boolean checkCollision(Item target){
       return bounds.checkCollision(target.getBounds());
   }
}

Where Collidable is the interface for any geometric shape and a possible shape would look like:

public class Circle implements Collidable{

   public boolean checkCollision(Collidable target){
      if(target instanceof Cirlce){
         //Algorithm for circle-circle collision
      }else if(target instanceof Line){
         //Algorithm for circle-line collision
         //...
      }else{
         return false;
      }
   }
}

This however yields a lot of code duplication (the same circle-line collision algorithm would need to be repeated in the Line class) and does not seem elegant. I looked into different design patterns in search of a solution, but only ended up with this strategy-like solution. What would be a better approach here?

Collision detection is a cross-cutting concern, so it's perhaps easier to maintain to put it into a single class that knows all the other classes (that's kind of like the Mediator pattern, but not quite). See https://gamedev.stackexchange.com/questions/43397/collision-detection-game-design-and-architecture — Fuhrmanator, Feb 28 '18 at 21:16

Nikolay Lebedev · Accepted Answer · 2018-02-27T20:54:13.643

Use the Visitor pattern to restore information of type of the Collidable. The circle can not know which figure is being checked for a collision, but the figure knows it. Let's find it out by double dispatching.

You can rename these methods, but the meaning should remain the same. You can also mark these methods as internal so that they can not be called in a different context.

You can delegate methods of checking specific pairs to an external static class in order to avoid code duplication.

public interface Collidable {
    boolean checkCollision(Collidable target);
    boolean visit(Collidable collidable);
    boolean accept(Circle circle);
    boolean accept(Line line);
}

public static class CollisionChecks {
    public static boolean check(Circle a, Circle b) { return false; }
    public static boolean check(Circle a, Line b) { return false; }
    public static boolean check(Line a, Line b) { return false; }
}

public class Line implements Collidable {
    @Override
    public boolean checkCollision(Collidable target) {
        return target.visit(this);
    }

    @Override
    public boolean visit(Collidable collidable) {
        return collidable.accept(this);
    }

    @Override
    public boolean accept(Circle circle) {
        return CollisionChecks.check(circle, this);
    }

    @Override
    public boolean accept(Line line) {
        return CollisionChecks.check(this, line);
    }

}

public class Circle implements Collidable {
    @Override
    public boolean checkCollision(Collidable target) {
        return target.visit(this);
    }

    @Override
    public boolean visit(Collidable collidable) {
        return collidable.accept(this);
    }

    @Override
    public boolean accept(Circle circle) {
        return CollisionChecks.check(this, circle);
    }

    @Override
    public boolean accept(Line line) {
        return CollisionChecks.check(this, line);
    }
}

@f_mene you accepted this answer, but what happens when you need a Square and a Triangle? Does it scale? It doesn't look easy to me to add future shapes, but maybe I'm missing something here. Visitor is NOT easily extendable when you want to add new elements to the set of elements that are visited. — Fuhrmanator, Feb 28 '18 at 20:42
Check this answer for advice (it points out also that double dispatch is not easy to maintain when adding new objects): https://stackoverflow.com/a/1876578/1168342 — Fuhrmanator, Feb 28 '18 at 20:48
Yes, the visitor pattern has negative sides. You need to define methods for all the interaction options. But it also has a benefits: double dispatching works faster than `instanseof` and the compiler helps you by giving out errors in those places where you forgot to define the interaction option. This will protect you from errors in the future. — Nikolay Lebedev, Feb 28 '18 at 21:49
@Furhmanator Thanks for the further consideration. I want any shape I introduce to be handled in any existing combination anyway, and most combinations require quite unique algorithms. The only real overhead I see is updating the interface and adding `accept` methods for any possible combination - something my original `instanceof`-approach would require as well. Your particular examples of squares and triangles would actually be covered by the polygon, but I see your point. — MonkeyKhan, Mar 01 '18 at 00:46

score 0 · Answer 2 · answered Feb 27 '18 at 19:42

Maybe your collision detection doesn't belong to the shape classes. Instead, you could implement a set of collision algorithm classes, one for each combination of shapes. Then the code only lives in one place.

You would need some way of choosing the right algorithm. You could keep them in a map of maps keyed by shape name, or inject only the relevant ones into each shape.

Now when a shape has to decide if it's colliding with another shape, it finds the right collision algorithm and asks that for an answer.

Elegant way of encapsulating behaviour that depends on the combination of involved objects?

2 Answers2