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

Just think about it: what you need is a behavior that changes according both parameters (this and other).

In other words, what you need is Multiple Dispatch (or more specifically, Double Dispatch). At first, like many other "OOP" languages derived from C++, C# was designed to support Single Dispatch only (like Java, and unlike languages such as Common Lisp, Clojure, Lua, which were designed to support Multiple Dispatch).

There is a classical way to emulate multiple dispatch on single dispatch languages, called the Visitor Pattern. If you want to follow that path, there is already an answer here on Stack Overflow (using both C# and the Visitor Pattern, and for a problem quite similar to yours), so I won't repeat it.

What I can add is that, unlike e.g. Java, C# 4.0+ does support Multiple Dispatch... By using the dynamic keyword, plus usual method overloading.

So we could have something like this:

public abstract class Shape
{
    private CollisionDetector detector = new CollisionDetector();

    public bool IsColliding(Shape that)
    {
        return detector.IsColliding((dynamic) this, (dynamic) that);
    }
}

public class CollisionDetector
{
    public bool IsColliding(Circle circle1, Circle circle2)
    {
        Console.WriteLine("circle x circle");
        return true;
    }

    public bool IsColliding(Circle circle, Rectangle rectangle)
    {
        Console.WriteLine("circle x rectangle");
        return true;
    }

    public bool IsColliding(Rectangle rectangle, Circle circle)
    {
        // Just reuse the previous method, it is the same logic:
        return IsColliding(circle, rectangle);
    }

    public bool IsColliding(Rectangle rectangle1, Rectangle rectangle2)
    {
        Console.WriteLine("rectangle x rectangle");
        return true;
    }
}

public class Circle : Shape { }

public class Rectangle : Shape { }

And yes, that would work as expected. Using dynamic would force late binding, so the actual method call would be chosen during runtime. Of course, that would have a performance cost: dynamic type resolution is much slower then a static one. If that is not acceptable, use the answer that I referenced above.

Answer 2

I really think you are over-engineering here.

All your shapes are essentially a collection of vertices and edges, even circles (just choose how many vertices satisfies your precision needs).

Once all your shapes are a collection of points and edges, you only need to handle collissions in one place and it will be valid for any shapes involved.

If your shapes are convex, your collision algorithm could as simple as checking if one shape contains at least one vertice of the other shape, and Contains(Point p) could be a virtual method overridden by each shape.

Answer 3

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

Answer 4

Maybe it's not the most beautiful solution, but you could write the method accepting all kinds of shape.

CollisionHandler.Check(Rectangle r = null, Circle c = null, Triangle t = null)
{
   if(r != null && c != null
   {
      return CollisionHandler.CheckRectangleVsCircle(r,c);
   }
}

Answer 5

Yes, you are right. In your current approach, you are breaking the Open/Closed principle.

The first part of the task is done properly. You are taking the decision of how the collision is handled by adding collision handlers for each shape, e.g. you are creating classes Rectangle etc with IsColliding method.

Then you need to take another decision, how to respond to this collision. The responding side needs to take care about it. So it's the other shape's job to respond to this collision.

I would suggest to add a new method RespondToCollision(IShape) in the contract.

In this case you can create the following (pseudo) scenario

Collide(IShape other) {
    // do smth with other.Properties
    other.RespondToCollision(this);
}

RespondToCollision(IShape other) {
    // do smth with this.Properties<>other.Properties
}

If the shapes are not enough arguments for both functions, you can change your static classes with OneToAnotherCollisionMethod to strategy classes (take a look at Strategy Pattern) and pass these strategies as arguments too.

Considering the fact that shapes are checked for collision maybe by their coordinates it will not be that hard to build the formula by passing the target side to the source side and vice versa.