12

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 combinations      
   }

   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
1
  • See my proposal to use Reflection. It is easy to use the same method for objects of type Rectangle/Circle and Circle/Rectangle if you use Reflection to dispatch the call.
    – Achim
    May 28, 2011 at 21:51

4 Answers 4

13

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
1
  • Visitor pattern was a thing that i was looking for! Anyway i had to mix yours solution with my current code to avoid duplicated code.
    – zgorawski
    May 29, 2011 at 6:47
5

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.

1

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();
    }
}
7
  • 1
    This if..else if...else based on the type of object usually sound to be replaced with a virtual function.
    – Uwe Keim
    May 28, 2011 at 18:29
  • @Uwe Keim, yeah, and in this case you would have an infinite recursion, because that virtual function would be the same Shape.Intersects implementation. Or did I get you wrong? May 28, 2011 at 18:30
  • The IntersectionChecker already seems to check for the type, so you do a double check here?
    – Uwe Keim
    May 28, 2011 at 18:32
  • @Uwe Keim, no - in this case IntersectionChecker.Intersect would call his typed private methods (which I recommended to make public static). And the IntersectionChecker.Intersect(Shape, Shape) should be removed. May 28, 2011 at 18:34
  • Just a thought - could one not add Intersects(Rectangle other) and Intersects(Circle other) functions to the base class - or is this extraordinarily sick?
    – Will A
    May 28, 2011 at 18:35
1

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. ;-)

5
  • Your "double dispatch is only supported" comment is incredibly misleading. Double dispatch, while not really supported by the C-like languages can still be simulated. wiki double dispatch Your solution is bad code because you must write nearly twice as many functions as you really need: Intersect(Rectangle, Circle) and Intersect(Circle, Rectangle). The Visitor pattern works well if you keep future changes minimal. For the record, "Everything is encapsulated in one single place" is not a good paradigm to follow.
    – josaphatv
    Aug 29, 2013 at 15:16
  • Can you please explain, why the visitor pattern would need less functions to be changed? I don't even mention the functions you give as an example?!
    – Achim
    Aug 29, 2013 at 18:33
  • Visitor wouldn't need less changing. I'm saying that if you only have a few things to support like Circle, Rect, and Triangle, and you don't plan on adding more than that, the visitor pattern will work fine. I know you don't mention the functions I gave as an example. I'm not very familiar with Reflection, but I thought you would still need to check the types to find what order the arguments need to go in ( whether you're going to invoke Intersect(Rectangle, Circle) or Intersect(Circle, Rectangle)). You say you won't need ifs but I think you need either ifs or duplicated code.
    – josaphatv
    Aug 30, 2013 at 13:49
  • No. Assuming you intersect only two elements, you can use a the sorted types of the signature as keys in a dictionary. The values are the intersect method for that type combination. If you now want to intersect two elements, you just "calculate" the key depending on their types, get the intersect method and pass the objects to them. No if will be needed at all to dispatch the calls to the correct intersect method.
    – Achim
    Sep 3, 2013 at 15:03
  • But now you're adding ugly and non-intuitive procedures (sorted dictionary look-up for types) into an already ugly API (Reflection). The Visitor Pattern, while it could quickly become a maintenance nightmare, is much easier to follow and understand for small numbers of supported class pairs.
    – josaphatv
    Sep 4, 2013 at 0:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.