What is a good design practice to avoid asking a subclass type?

Question

I've read that when your program needs to know what class an object is, usually indicates a design flaw so I want to know what is a good practice to handle this. I'm implementing a class Shape with different subclasses inherited from it like Circle, Polygon or Rectangle and I've different algorithms to know if a Circle collides with a Polygon or a Rectangle. Then suppose we got two instances of Shape and want to know if one collides the other, in that method I've to infer what subclass type is the object I'm colliding in order to know what algorithm I should call but, this is a bad design or practice? This is the way I solved it.

abstract class Shape {
  ShapeType getType();
  bool collide(Shape other);
}

class Circle : Shape {
  getType() { return Type.Circle; }

  bool collide(Shape other) {
    if(other.getType() == Type.Rect) {
      collideCircleRect(this, (Rect) other);     
    } else if(other.getType() == Type.Polygon) {
      collideCirclePolygon(this, (Polygon) other);
    }
  }
}

This is a bad design pattern? How could I solve this without having to infer the subclass types?

Answer 1

Polymorphism

So long as you use getType() or anything like it, you're not using polymorphism.

I understand feeling like you need to know what type you have. But any work you would want to do while knowing that should really be pushed down into the class. Then you just tell it when to do it.

Procedural code gets information then makes decisions. Object-oriented code tells objects to do things.
— Alec Sharp

This principle is called tell, don't ask. Following it helps you not spread details like type around and create logic that acts on them. Doing that turns a class inside out. It's better to keep that behavior inside the class so it can change when the class changes.

Encapsulation

You can tell me no other shapes will ever be needed but I don't believe you and neither should you.

A nice effect of following encapsulation is that it's easy to add new types because their details don't spread out into the code where they show up in if and switch logic. The code for a new type should all be in one place.

A type ignorant collision detection system

Let me show you how I'd design a collision detection system that is performant and works with any 2D shape by not caring about the type.

Say you were supposed to draw that. Seems simple. It's all circles. It's tempting to create a circle class that understands collisions. The problem is this sends us down a line of thinking that falls apart when we need 1000 circles.

We shouldn't be thinking about circles. We should be thinking about pixels.

What if I told you that the same code you use to draw these guys is what you can use to detect when they touch or even which ones the user is clicking on.

Here I've drawn each circle with a unique color (if your eyes are good enough to see the black outline, just ignore that). This means every pixel in this hidden image maps back to what drew it. A hashmap takes care of that nicely. You can actually do polymorphism this way.

This image you never have to show to the user. You create it with the same code that drew the first one. Just with different colors.

When the user clicks on a circle I know exactly which circle because only one circle is that color.

When I draw a circle on top of another I can quickly read every pixel I'm about to overwrite by dumping them in a set. When I'm done the set points to every circle it collided with and now I only have to call each one once to notify it of the collision.

A new type: Rectangles

This was all done with circles but I ask you: would it work any different with rectangles?

No circle knowledge has leaked into the detection system. It doesn't care about radius, circumference, or the center point. It cares about pixels and color.

The only part of this collision system that needs to be pushed down into the individual shapes is a unique color. Other than that the shapes can just think about drawing their shapes. It's what they're good at anyway.

Now when you write the collision logic you don't care what subtype you have. You tell it to collide and it tells you what it found under the shape it's pretending to draw. No need to know type. And that means you can add as many sub types as you like without having to update the code in other classes.

Implementation choices

Really, it doesn't need to be a unique color. It could be actual object references and save a level of indirection. But those wouldn't look as nice when drawn in this answer.

This is just one implementation example. There certainly are others. What this was meant to show is that the closer you let these shape subtypes stick with their single responsibility the better the whole system works. There likely are faster and less memory intensive solutions but if they force me to spread knowledge of the subtypes around I'd be loath to use them even with the performance gains. I wouldn't use them unless I clearly needed them.

Double dispatch

Up till now I've completely ignored double dispatch. I did that because I could. So long as the colliding logic doesn't care which two types collided you don't need it. If you don't need it, don't use it. If you think you might need it, put off dealing with it as long as you can. This attitude is called YAGNI.

If you decide you really need different kinds of collisions then ask your self if n shape subtypes really need n² kinds of collisions. So far I've worked really hard to make it easy to add another shape subtype. I don't want to spoil it with a double dispatch implementation that forces circles to know that squares exist.

How many kinds of collisions are there anyway? A little speculating (a dangerous thing) invents elastic collisions (bouncy), inelastic (sticky), energetic (explody), and destructive (damagy). There could be more but if this is less than n² lets not over design our collisions.

This means when my torpedo hits something that accepts damage it doesn't have to KNOW it hit a space ship. It only has to tell it, "Ha ha! You took 5 points of damage."

Things that deal damage send out damage messages to things that accept damage messages. Done that way you can add new shapes without telling the other shapes about the new shape. You only end up spreading around new types of collisions.

The space ship can send back to the torp "Ha ha! You took 100 points of damage." as well as "You're now stuck to my hull". And the torp can send back "Well, I'm done for so forget about me".

At no point does either know exactly what each is. They just know how to talk to each other through a collision interface.

Now sure, double dispatch lets you control things more intimately than this but do you really want that?

If you do please at least think about doing double dispatch through abstractions of what kinds of collisions a shape accepts and not on the actual shape implementation. Also, collision behavior is something you can inject as a dependency and delegate to that dependency.

Performance

Performance is always critical. But that doesn't mean it's always an issue. Test performance. Don't just speculate. Sacrificing everything else in the name of performance usually doesn't lead to performent code anyway.

Answer 2

The description of the problem sounds like you should use Multimethods (aka Multiple dispatch), in this particular case - Double dispatch. The first answer went at length on how to deal generically with colliding shapes in raster rendering, but I believe OP wanted "vector" solution or maybe the whole problem has been reformulated in terms of Shapes, which is classical example in OOP explanations.

Even wikipedia article cited uses same collision metaphor, let me just cite (Python does not have built-in multimethods like some other languages):

@multimethod(Asteroid, Asteroid)
def collide(a, b):
    """Behavior when asteroid hits asteroid"""
    # ...define new behavior...
@multimethod(Asteroid, Spaceship)
def collide(a, b):
    """Behavior when asteroid hits spaceship"""
    # ...define new behavior...
# ... define other multimethod rules ...

So, the next question is how to get support for multimethods in your programming language.

Answer 3

This problem requires redesign on two levels.

First, you need to exctract the logic for detecting the collision between the shapes out of the shapes. This is so you would not violate OCP every time you need to add a new shape to the model. Imagine you already have Circle, Square and Rectangle defined. You could then do it like this:

class ShapeCollisionDetector
{
    public void DetectCollisionCircleCircle(Circle firstCircle, Circle secondCircle)
    { 
        //Code that detects collision between two circles
    }

    public void DetectCollisionCircleSquare(Circle circle, Square square)
    {
        //Code that detects collision between circle and square
    }

    public void DetectCollisionCircleRectangle(Circle circle, Rectangle rectangle)
    {
        //Code that detects collision between circle and rectangle
    }

    public void DetectCollisionSquareSquare(Square firstSquare, Square secondSquare)
    {
        //Code that detects collision between two squares
    }

    public void DetectCollisionSquareRectangle(Square square, Rectangle rectangle)
    {
        //Code that detects collision between square and rectangle
    }

    public void DetectCollisionRectangleRectangle(Rectangle firstRectangle, Rectangle secondRectangle)
    { 
        //Code that detects collision between two rectangles
    }
}

Next, you must arrange for the appropriate method to be called depending on the shape that calls it. You can do that using polymorphism and Visitor Pattern. In order to achieve this, we must have the appropriate object model in place. First, all shapes must adhere to the same interface:

    interface IShape
{
    void DetectCollision(IShape shape);
    void Accept (ShapeVisitor visitor);
}

Next, we must have a parent visitor class:

    abstract class ShapeVisitor
{
    protected ShapeCollisionDetector collisionDetector = new ShapeCollisionDetector();

    abstract public void VisitCircle (Circle circle);

    abstract public void VisitSquare(Square square);

    abstract public void VisitRectangle(Rectangle rectangle);

}

I am using a class here instead of the interface, because I need each visitor object to have an attribute of ShapeCollisionDetector type.

Every implementation of IShape interface would instantiate the appropriate visitor and call the appropriate Accept method of the object that the calling object interacts with, like this:

    class Circle : IShape
{
    public void DetectCollision(IShape shape)
    {
        CircleVisitor visitor = new CircleVisitor(this);
        shape.Accept(visitor);
    }

    public void Accept(ShapeVisitor visitor)
    {
        visitor.VisitCircle(this);
    }
}

    class Rectangle : IShape
{
    public void DetectCollision(IShape shape)
    {
        RectangleVisitor visitor = new RectangleVisitor(this);
        shape.Accept(visitor);
    }

    public void Accept(ShapeVisitor visitor)
    {
        visitor.VisitRectangle(this);
    }
}

And specific visitors would look like this:

    class CircleVisitor : ShapeVisitor
{
    private Circle Circle { get; set; }

    public CircleVisitor(Circle circle)
    {
        this.Circle = circle;
    }

    public override void VisitCircle(Circle circle)
    {
        collisionDetector.DetectCollisionCircleCircle(Circle, circle);
    }

    public override void VisitSquare(Square square)
    {
        collisionDetector.DetectCollisionCircleSquare(Circle, square);
    }

    public override void VisitRectangle(Rectangle rectangle)
    {
        collisionDetector.DetectCollisionCircleRectangle(Circle, rectangle);
    }
}

    class RectangleVisitor : ShapeVisitor
{
    private Rectangle Rectangle { get; set; }

    public RectangleVisitor(Rectangle rectangle)
    {
        this.Rectangle = rectangle;
    }

    public override void VisitCircle(Circle circle)
    {
        collisionDetector.DetectCollisionCircleRectangle(circle, Rectangle);
    }

    public override void VisitSquare(Square square)
    {
        collisionDetector.DetectCollisionSquareRectangle(square, Rectangle);
    }

    public override void VisitRectangle(Rectangle rectangle)
    {
        collisionDetector.DetectCollisionRectangleRectangle(Rectangle, rectangle);
    }
}

This way, you do not need to change shape classes every time you add a new shape, and you do not need to check for type of shape in order to call the appropriate collision detection method.

A drawback of this solution is that if you add a new shape, you have to extend the ShapeVisitor class with the method for that shape (e.g. VisitTriangle(Triangle triangle)), and consequently, you would have to implement that method in all other visitors. However, since this is extension, in the sense that no existing methods are changed, but only new ones are added, this does not violate OCP, and the code overhead is minimal. Also, by using the class ShapeCollisionDetector, you avoid the violation of SRP and you avoid code redundancy.

Answer 4

Your basic problem is that in most modern OO programming languages function overloading does not work with dynamic binding (i.e. the type of function arguments is determined at compile time). What you would need is a virtual method call that is virtual on two objects rather than only one. Such methods are called multi-methods. However, there are ways to emulate this behavior in languages like Java, C++, etc. This is where double dispatch comes in very handy.

The basic idea is that you make use of polymorphism twice. When two shapes collide you can call the correct collision method of one of the objects through polymorphism and pass the other object of the generic shape type. In the called method you then know whether the this object is a circle, rectangle or whatever. You then call the collision method on the passed shape object and pass it the this object. This second call then again finds the correct object type through polymorphism.

abstract class Shape {
  bool collide(Shape other);
  bool collide(Rect other);
  bool collide(Circle other);
}

class Circle : Shape {

  bool collide(Shape other) {
    return other.collide(this);
  }

  bool collide(Rect other) {
    // algorithm to detect collision between Circle and Rect
  }

  // ...
}

class Rect : Shape {

  bool collide(Shape other) {
    return other.collide(this);
  }

  bool collide(Circle other) {
    // algorithm to detect collision between Circle and Rect
  }

  // ...
}

A big drawback of this technique, however, is that each class in the hierarchy has to know about all the siblings. This places a high maintenance burden if a new shape is added later.

Answer 5

Maybe this is not the best way to approach this problem

The math behing shape collision is particular to the shape combinations. Meaning that the number of sub-routines you will need is the square of the number of shapes you system supports. The shape collisions are not actually operations on shapes, but operations that take shapes as parameters.

Operator Overload Strategy

If you can not simplify the underlying math problem, I would recomend the operator overload approach. Something like:

 public final class ShapeOp 
 {
     static { ... }
    
     public static boolean collision( Shape s1, Shape s2 )  { ... }
     public static boolean collision( Point p1, Point p2 ) { ... }
     public static boolean collision( Point p1, Square s1 ) { ... }
     public static boolean collision( Point p1, Circle c1 ) { ... }
     public static boolean collision( Point p1, Line l1 ) { ... }
     public static boolean collision( Square s1, Point p2 ) { ... }
     public static boolean collision( Square s1, Square s2 ) { ... }
     public static boolean collision( Square s1, Circle c1 ) { ... }
     public static boolean collision( Square s1, Line l1 ) { ... }
     (...)

On the static intializer I would use reflection to make a map of the methods to implement a diynamic dispather on the generic collision( Shape s1 , Shape s2 ) method. The static intializer can also have a logic to detect missing collision functions and report them, refusing to load the class.

This is kind similar to the C++ operator overload. In C++ operator overload is very confusing because you have a fixed set of symbols that you can overload. However, the concept is very interesting and can be replicated with static functions.

The reason why I would use this approach is that collision is not an operation over an object. A collision is an external operation that says some relation about two arbitrary objects. Also, the static initializer will be able to check if I miss some collision function.

Simplify your math problem if possible

As I mentioned, the number of collision functions are the square of the number of shape types. This means that in a system with only 20 shapes you will need 400 routines, with 21 shapes 441 and so on. This is not easly extensible.

But you can simplify your math. Instead of extending the collision function you can rasterize or triangulate every shape. That way the collision engine does not need to be extensible. Collision, Distance, Intersection, Merging and several other functions will be universal.

Triangulate

Did you notice most 3d packages and games triangulate everything? That is one of the forms of simplifying the math. This applies to 2d shapes too. Polys can be triangulated. Circles and splines can be approximated to poligons.

Again... you will have a single collision function. Your class become then:

public class Shape 
{
    public Triangle[] triangulate();
}

And your operations:

public final class ShapeOp
{
    public static boolean collision( Triangle[] shape1, Triangle[] shape2 )
}

Simpler is it not?

Rasterize

You can rasterize your shape to have a single collision function.

Rasterization may seem to be a radical solution, but may be affordable and fast depending on how precise your shape collisions need to be. If they do not need to be precise (like in a game) you may have low resolution bitmaps. Most applications does not need absolute precision on the math.

Approximations may be good enough. The ANTON supercomputer for biology simulation is an example. Its math discards a lot of quantum effects that are hard to calculate and so far the simulations made are consistent with the experiments made in the real world. The PBR computer graphics models used in game engines and rendering packages make simplifications that reduces the computer power needed to render each frame. Is not actually phisically accurate but is close enough to be convincing to the naked eye.