Sunday, May 12, 2013

Game, Set, Pattern Match

I've been recently revisiting my game engine collision detection logic, which I'm migrating from Java to Scala. I don't want to bore anyone with dull algorithmic details but, as it happens, letting aside the algebraic mumbo-jumbo I like so much, I found a pretty interesting design problem along with a nice Scala solution. It goes like this:

Basically, back then in Java, I had some objects which where responsible for collision detection. I called them "Bounding Boxes". Every collisionable object in the game was associated with one of these to whom they would ask whether or not they where colliding with one another. Code was very much like this:

public interface BoundingBox {

    public abstract boolean collidesWith(BoundingBox box);

    public abstract boolean collidesWithCircle(CircularBoundingBox box);

    public abstract boolean collidesWithRectangle(RectangularBoundingBox box);

        ...
}


public class CircularBoundingBox {

    @Override
    public boolean collidesWith(BoundingBox box) {
        return box.collidesWithCircle(this);
    }

    @Override
    protected boolean collidesWithCircle(CircularBoundingBox box) {

        // Borring Circle-to-Circle collision detection code

    }

    @Override
    public boolean collidesWithRectangle(RectangularBoundingBox box) {

        // Borring Circle-to-Rectangle collision detection code

    }
}


public class RectangularBoundingBox {

    @Override
    public boolean collidesWith(BoundingBox box) {
        return box.collidesWithRectangle(this);
    }

    @Override
    public boolean collidesWithCircle(CircularBoundingBox box) {
        box.collidesWithRectangle(this);
    }

    @Override
    protected boolean collidesWithRectangle(RectangularBoundingBox box) {

        // Borring Rectangle-to-Rectangle collision detection code

    }
}
Nothing really special about that. As you can see, every collisionable shape is model with a class of it's own, and the dual nature of the problem is easily solved using the Double Dispatch pattern. I actually liked this implementation (specially compared to some other engine's aproaches, like providing a monolithic low-level collision library) but it didn't really lived up to my expectations.

I originally wanted BoundingBox to act as an extension point to my engine, so users could extend it to add new crazy shapes to collide with. As it turned out, with the existing implementation there was no way of adding a new Bounding Box without also adding the corresponding methods to all the existing others. This isn't as much of a problem when you have the engine sources, but it was clear that no jar-user would be able to do it.

Also, just adding a couple more of boxes (the engine already had 6...) would get the interfaces really dirty, because of the combinatorial explosion. Double Dispatch is OK for small scenarios, but having dozens of  public methods (most of them only dispatches) just to solve one piece of logic soon turns quite unpleasant.

Here's where Scala comes in.

 trait BoundingBox {
  def apply(target : BoundingBox) = collidesWith(target)(true)
  
  protected def collidesWith(arg : BoundingBox)(shouldDispatch : Boolean) : Boolean =
   if(shouldDispatch) arg.collidesWith(this)(false)
   else throw new MissingCollisionLogic(this,target)
 }
 
 class CircularBoundingBox extends BoundingBox {
  override protected def collidesWith(target : BoundingBox)(shouldDispatch : Boolean) = target match {
   case c : CircularBoundingBox => //Check Circle-Circle collision
   case r : RectangularBoundingBox => // Check Circle-Rectangle collision
   case _ => super.collidesWith(target)(shouldDispatch)
  }
 }
 
 class RectangularBoundingBox extends BoundingBox {
  override protected def collidesWith(target : BoundingBox)(shouldDispatch : Boolean) = target match {
   case r : RectangularBoundingBox => // Check Rectangle-Rectangle collision
   case _ => super.collidesWith(target)(shouldDispatch)
  }
 }

In a nutshell, BoundingBox public apply method calls a protected collidesWith method that only delegates in it's argument. Implementors' responsibility is easy: they just have to override collidesWith providing whatever collision logic they want for any specific box type. In case the argument doesn't match any pattern, a quick call to super will perform the symmetric call on the argument or throw an exception it was the original receiver.

So, what's so special about this solution? Well, for starters, thanks to the magic of Pattern Matching the giant public interface was reduced to a single protected method. This leave us with a much tidier, less verbose classes.
That's alright, but what about extensibility? That's the best part! Let's say that we want to add another box, for complex polygons. All we have to do is extend BoundingBox as follows:


 class ComplexPoligonalBoundingBox extends BoundingBox {
  override protected def collidesWith(target : BoundingBox)(shouldDispatch : Boolean) = target match {
   case c : CircularBoundingBox => //Check ComplexPoligon-Circle collision
   case r : RectangularBoundingBox => // Check ComplexPoligon-Rectangle collision
   case _ => super.collidesWith(target)(shouldDispatch)
  }
 }

Notice that, by providing the collision algorithms against them, booth CircularBoundingBox and RectangularBoundingBox are now able to detect collisions against the new class, without even having to touch them. This allows to extend the boxes provided by the engine in a clean way while, at the same time, providing a full symmetric implementation.

There's no much left to say. I'm quite content with the final result as it has proven to be more flexible and aesthetic than it's predecessor. Guess it's time to go out there and give it a try. See you around.


N.

No comments:

Post a Comment