Design pattern for checking collision between shapes

I use various shapes for collision detection ( Rectangle, Circle, Cone, Ring etc.) All those shapes are derived from base abstract Shape class. My game objects have property of type Shape.

class GameObject
{
    (...)
    public Shape CollisionShape { get; set; }
}

and during initialize process I decide what shape will be used for each object, like:

GameObject person = new GameObject();
person.CollisionShape = new Circle(100); // 100 is radius

Now when I want to check if two objects intersects I use following class:

public class IntersectionChecker
{
   public bool Intersect(Shape a, Shape b)
   {
      Type aType = a.GetType();
      Type bType = b.GetType();

      if( aType == typeof(Rectangle) && bType == typeof(Rectangle))
          return Intersect(a as Rectangle, b as Rectangle);

      if( aType == typeof(Rectangle) && bType == typeof(Circle))
          return Intersect(a as Rectangle, b as Circle);

      // etc. etc. All combinati开发者_Python百科ons      
   }

   private bool Intersect(Rectangle a, Rectangle b)
   {
      // check intersection between rectangles
   }
}

so my code looks like:

IntersectionChecker ic = new IntersectionCHecker();
bool isIntersection = 
    is.Intersect(personA.CollisionShape, personB.CollisionShape);

Is there better way to achieve my goal, without dozens of 'if' checks and type checks in IntersectionChecker class?

EDIT:

Please take in mind, that method that check intersection between shape A and B can be used to check intersection between B and A aswell. In many answers ( thanks for all yours thoughts!) intersection check is proposed to be invoked from shape itself rather than IntersectionChecker object. I think it will force me to duplicate code. Now i can do as follow:

  if( aType == typeof(Rectangle) && bType == typeof(Circle))
      return Intersect(a as Rectangle, b as Rectangle);

  if( aType == typeof(Circle) && bType == typeof(Rectangle))
      return Intersect(b as Rectangle, a as Circle); // same method as above

---

You could use the Visitor Pattern, here is a C# example

That would allow you to simply have Shape.Intersect(Rectangle), Shape.Intersect(Circle), ... methods that each derived shape implements. It would prevent you from having to do any reflection on types at the cost of an extra method call.

EDIT - Here is a sample implementation, it would probably be cleaner to use an interface IShape if there is no shared functionality that would go in Shape, but I just stuck in an abstract base class.

public class GameObject
{
    private Shape _collisionShape;

    public GameObject(Shape collisionShape)
    {
        _collisionShape = collisionShape;
    }

    public bool Intersects(GameObject other)
    {
        return _collisionShape.IntersectVisit(other._collisionShape);
    }
}

public abstract class Shape
{
    public abstract bool IntersectVisit(Shape other);
    public abstract bool Intersect(Circle circle);
    public abstract bool Intersect(Rectangle circle);
}

public class Circle : Shape
{
    public override bool IntersectVisit(Shape other)
    {
        return other.Intersect(this);
    }

    public override bool Intersect(Circle circle)
    {
        Console.WriteLine("Circle intersecting Circle");
        return false; //implement circle to circle collision detection
    }

    public override bool Intersect(Rectangle rect)
    {
        Console.WriteLine("Circle intersecting Rectangle");
        return false; //implement circle to rectangle collision detection
    }
}

public class Rectangle : Shape
{
    public override bool IntersectVisit(Shape other)
    {
        return other.Intersect(this);
    }

    public override bool Intersect(Circle circle)
    {
        Console.WriteLine("Rectangle intersecting Circle");
        return true; //implement rectangle to circle collision detection
    }

    public override bool Intersect(Rectangle rect)
    {
        Console.WriteLine("Rectangle intersecting Rectangle");
        return true; //implement rectangle to rectangle collision detection
    }
}

And example code calling it:

GameObject objectCircle = new GameObject(new Circle());
GameObject objectRect = new GameObject(new Rectangle());

objectCircle.Intersects(objectCircle);
objectCircle.Intersects(objectRect);
objectRect.Intersects(objectCircle);
objectRect.Intersects(objectRect);

Produces the output:

Circle intersecting Circle
Rectangle intersecting Circle
Circle intersecting Rectangle
Rectangle intersecting Rectangle

---

You could defer to your Shape class to perform the collision checking, adding an IntersectsWith(Shape other) method to Shape. I'd also suggest adding an IntersectsWith(GameObject other) to your GameObject which allows you to keep your CollisionShape private.

---

If checks would have to reside somewhere anyway.

You could add an Intersects method to Shape:

abstract class Shape
{
    public abstract Boolean Intersects(Shape other);
}

Then make your Intersect methods in IntersectionChecker public static and implement Intersects method for each concrete shape like this:

class Rectangle : Shape
{
    public override Boolean Intersects(Shape other)
    {
        if (other is Rectangle)
        {
            return IntersectionChecker.Intersect(this, (Rectangle)other);
        }
        else if (other is Circle)
        {
            return IntersectionChecker.Intersect(this, (Circle)other);
        }

        throw new NotSupportedException();
    }
}

---

There is no easy build in solution for your problem. What you need is called "double dispatch", which is only supported in languages like Smalltalk or Lisp. All proposed solutions will force you to change all derived classes if you add one new class. That's bad code!

I would approach the problem like this: Implement your Shape-derived classes without any intersection code. Then implement a Intersection class like this:

public class Intersection {
    public bool Intersect(Shape a, Shape b) {....}

    private bool Intersect(Rectangle a, Circle b) {...}

    private bool Intersect(Circle a, Circle b) {...}
}

The public methods analyzes the incoming shapes and dispatches (-> double dispatch) the work to the matching private method. Which contains the raw intersection logic. The implementation of Intersect does not need "ifs". You can use reflection to find the best matching method. The details depend on your exact requirements and how you weight complexity against performance. But it's easy to get started with an simple straight foward implementation. Because everything is encapsulated in one single place, it's easy to optimize later. Which is a good approach in my opinion. ;-)