Using polymorphism for collision detection in an elegant way

Question

I am trying to set up some simple 2D shapes which can be dragged about the window using the mouse. I want the shapes to register a collision when I drag one into another. I have an interface.

interface ICollidable
{
    bool CollidedWith(Shape other);
}

I then have an abstract class Shape that implements the above interface.

abstract class Shape : ICollidable
{
    protected bool IsPicked { private set; get; }
    protected Form1 Form { private set; get; }

    protected int X { set; get; } // Usually top left X, Y corner point
    protected int Y { set; get; } // Used for drawing using the Graphics object

    protected int CenterX { set; get; } // The center X point of the shape
    protected int CenterY { set; get; } // The center X point of the shape

    public Shape(Form1 f, int x, int y)
    {
        Form = f;
        X = x; Y = y;
        Form.MouseDown += new MouseEventHandler(form_MouseDown);
        Form.MouseMove += new MouseEventHandler(Form_MouseMove);
        Form.MouseUp += new MouseEventHandler(Form_MouseUp);
    }

    void Form_MouseMove(object sender, MouseEventArgs e)
    {
        if(IsPicked)
            Update(e.Location);
    }

    void Form_MouseUp(object sender, MouseEventArgs e)
    {
        IsPicked = false;
    }

    void form_MouseDown(object sender, MouseEventArgs e)
    {
        if (MouseInside(e.Location))
            IsPicked = true;
    }

    protected abstract bool MouseInside(Point point);
    protected abstract void Update(Point point);
    public abstract void Draw(Graphics g);
    public abstract bool CollidedWith(Shape other);
}

I then have ten concrete classes Circle, Square, Rectangle etc that extend the Shape class and implement the abstract methods. What I would like to do is come up with some oop clean and elegant way to do the collosion detection instead having a large block of if statements in the CollidedWith method such is

public bool CollidedWith(Shape other)
{
    if(other is Square)
    {
        // Code to detect shape against a square
    }
    else if(other is Triangle)
    {
        // Code to detect shape against a triangle
    }
    else if(other is Circle)
    {
        // Code to detect shape against a circle
    }
    ...   // Lots more if statements
}

Has anyone any ideas. It's a problem I've thought about before but am only putting into practice now.

It would be helpful if you could explain how you are defining a collision, and how it may vary between the subclasses. Is `Shape` also going to contain any information on the instances coordinates? — mclark1129, Sep 06 '12 at 17:10
@Mick C. I have changed the code inserting the entire code for the Shape class — John ClearZ, Sep 06 '12 at 23:34

score 4 · Answer 1 · answered Sep 06 '12 at 17:09

Is the collision detection so "Shape Specific" that there's a different implementation for every permutation of

Circle vs. Other Circle
Circle vs. Other Square
Circle vs. Other Triangle
Square vs. Other Circle
...

It sounds like you're trying to create a matrix of all possibilities but if you come up with 10 new shapes, 20 in total, you have 400 possibilites.

Instead, I would try to come up with a generic Shape.Overlaps(Shape other) method in your abstract class that would satisfy all of them.

If this is just 2D Geometry if should be trivial to figure out if the Edge Paths of any shapes intersect.

score 1 · Answer 2 · edited May 23 '17 at 12:27

1

Instead of specific shapes, all they ALL are are Paths or Regions.

A square is just a poly with 4 points, that happen to be at right angles. Then just write one Path.CollidesWith(Path) method and be on your way.

Check out some related questions.

edited May 23 '17 at 12:27

Community

1
1

answered Sep 06 '12 at 17:06

hometoast

11,522
5
41
58

score 1 · Answer 3 · answered Sep 06 '12 at 17:15

1

Double dispatch is commonly used in this situation.

answered Sep 06 '12 at 17:15

Tom Seddon

2,648
1
19
28

1

If you think about it, this isn't really all that different than the OP's `CollideWith` method with the large if statement. The only difference is that the framework would be handling the switching logic for you. The other problem is that this approach still requires you to modify every subclass and provide a new implementation for every new type that is created, which would result in an exponentially growing maintenance burden. – mclark1129 Sep 06 '12 at 17:29

Using polymorphism for collision detection in an elegant way

3 Answers3