How to implement a method of a base class for every possible combination of its derived types

Question

I have the following Shape interface which is implemented by multiple other classes such as Rectangle, Circle, Triangle ...

interface IShape{
    bool IsColliding(IShape other);
}

The method IsColliding is supposed to check whether a Shape is colliding with another or not, regardless of their concrete type. However, each couple of shape (Rectangle/Rectangle, Rectangle/Circle, Circle/Triangle etc...) have its own implementation for this collision check.

I'm trying to find a good design solution for this problem.

The naive method would be to switch over the type of the "other" shape to call the correct implementation :

class Rectangle : IShape{
    bool IsColliding(IShape other){
        if(other is Rectangle){
            return CollisionHandler.CheckRectangleVsRectangle(this,(Rectangle)other);
        }else if(other is Circle){
            return CollisionHandler.CheckRectangleVsCircle(this,(Circle)other);
        } else
            // etc ...
    }
}

But adding a new shape would mean modifying the method in every derived class to add the new case.

I also thought of calling a unique static method like this one :

static bool IsColliding(IShape shapeA, IShape shapeB);

But even if it centralizes everything, it doubles the number of type-test to perform and I'd still have to add a new case in each first-level "if".

if(shapeA is Rectangle){
    if(shapeB is Rectangle){
        // Rectangle VS Rectangle
    }else if(shapeB is Circle){
        // Rectangle VS Circle
    }else{
        // etc ...
    }
}else if(shapeA is Circle){
    if(shapeB is Rectangle){
        // Rectangle VS Circle
    }else{
        // etc ...
    }
} // etc ...

So, how could it be better designed ?

Answer 1

Here is an idea using double dispatch (the principle beyond the visitor pattern):

The basic fact is that the collision function is symmetric. I.e. IsCollision(shapeA, shapeB) = IsCollision(shapeB, shapeA). So you do not need to implement every n^2 combinations (n being the number of shape classes) but only roughly half of it:

         circle  tri rect
circle      x     x    x
tri               x    x
rec                    x

So assuming that you have an order of the shapes, every shape is responsible for collision with shapes that are located before them or are equal.

In this implementation, the shape-specific collision handling is dispatched to an object called the CollisionHandler. Here are the interfaces (simplified for reasons of brevity):

interface IShape
{
    int CollisionPrecedence { get; }
    AbstractCollisionHandler CollisionHandler { get; }
    void Collide(AbstractCollisionHandler handler);
}

class AbstractCollisionHandler
{
    public virtual void Collides(Circle other) { throw new NotImplementedException(); }
    public virtual void Collides(Rect other) { throw new NotImplementedException(); }
}

Based on these interfaces, the specific shape classes are:

class CircleCollisionHandler : AbstractCollisionHandler
{
    public override void Collides(Circle other)
    {
        Console.WriteLine("Collision circle-circle");
    }
}
class Circle : IShape
{
    public int CollisionPrecedence { get { return 0; } }
    public AbstractCollisionHandler CollisionHandler { get { return new CircleCollisionHandler(); } }
    public void Collide(AbstractCollisionHandler handler) { handler.Collides(this); }
}

class TriCollisionHandler : AbstractCollisionHandler
{
    public override void Collides(Circle other)
    {
        Console.WriteLine("Collision tri-circle");
    }

    public override void Collides(Tri other)
    {
        Console.WriteLine("Collision tri-tri");
    }
}

class Tri : IShape
{
    public int CollisionPrecedence { get { return 1; } }
    public AbstractCollisionHandler CollisionHandler { get { return new TriCollisionHandler(); } }
    public void Collide(AbstractCollisionHandler handler) { handler.Collides(this); }
}

And the function that calls the specific collision functions is:

static void Collides(IShape a, IShape b)
{
    if (a.CollisionPrecedence >= b.CollisionPrecedence)
        b.Collide(a.CollisionHandler);
    else
        a.Collide(b.CollisionHandler);
}

If you now want to implement another shape Rect, then you have to do three things:

Alter the AbstractCollisionHandler to include the rect

abstract class AbstractCollisionHandler
{
    ...
    public virtual void Collides(Rect other) { throw new NotImplementedException(); }
}

Implement the collision handler

class RectCollisionHandler : AbstractCollisionHandler
{
    public override void Collides(Circle other)
    {
        Console.WriteLine("Collision rect-circle");
    }

    public override void Collides(Tri other)
    {
        Console.WriteLine("Collision rect-tri");
    }

    public override void Collides(Rect other)
    {
        Console.WriteLine("Collision rect-rect");
    }
}

and implement the relevant interface methods in the Rect class:

class Rect : IShape
{
    public int CollisionPrecedence { get { return 2; } }
    public AbstractCollisionHandler CollisionHandler { get { return new RectCollisionHandler(); } }
    public void Collide(AbstractCollisionHandler handler) { handler.Collides(this); }

}

Simple as that. Here is a small test program that shows the called functions:

Collides(new Circle(), new Tri());
Collides(new Tri(), new Circle());
Collides(new Rect(), new Circle());

Output:

Collision tri-circle
Collision tri-circle
Collision rect-circle