Organising and scheduling collision detection in good OO

Game Mechanics
#1

My question targets at the organisation or architecture of code for collision detection. Normally, your game has
different game entities, which have the ability to collide. For each game loop all of them (or using some advanced
techniques: a subset of them) have to check each other for a collision and react to that.

I see different possibilities to arrange that code, each of them with its pros and cons. Starting very simplistic
(please do not care about sophisticated performance issues), there could be a class just crossing every game
entity with others for the collision check.

Every game entity carries its own (generic) method for checking a collision and the proper reaction, e.g.


checkCollision(GameEntity other)
{
  if(boundingBox.intersects(other.boundingBox))
  {
    reactToCollision(other);
  }
}
  • the entity knows about its collision method
  • about how to react (change its own state)

Problem one:

When the collision method has a generic parameter, it lacks the ability to react to a certain type of collided
game entity. So I can check that a collision occurred, but not differ between a rocket collision or that of an
astroid… which can result in a different state.

You could make advantage of polymorphism and add a method for each other type:


checkCollision(Rocket other)
{
  if(boundingBox.intersects(other.boundingBox))
  {
    takeDamage(other)
  }
}

checkCollision(Astroid other)
{
  if(boundingBox.intersects(other.boundingBox))
  {
    explode(other)
  }
}
  • can react to every derived game entity individually
  • poor design, because every new entity needs an additional method -
    Sure you can use instanceof to avoid multiple methods, but that smells as well

Problem two:
Who is responsible to apply the effects of the collision? Imagine a rocket hits a ship. The collision scheduler
(by chance) started to take the rocket and does something like:


rocket.checkCollision(ship);

We have these effects of that collision:

  1. the rocket is destroyed
  2. the ship’s health is reduced by the rocket’s damage

That could be handled:

  1. completely in the rocket’s method:

void collideWithShip(Ship ship)
{
 ship.takeDamage(getDamage());
 explode();
}
  1. for the case that the ship first was checked, the same:

void collideWithRocket(Rocket rocket)
{
  takeDamage(rocket.getDamage());
  rocket.explode();
}
  1. it could be split up, so that every entity only changes its own state:

Rocket:
void collideWithShip(Ship ship)
{
 explode();
}

Ship:
void collideWithRocket(Rocket rocket)
{
  takeDamage(rocket.getDamage());
}

The third version seems to be the cleanest one for me, because it does not require an game entity to know too much
about others and defines its own behaviour. On the other hand, what is more true: Does a ship actively take the damage information
from the rocket, or does the rocket apply damage to the ship?

Problem three:
When the collision effects are split up like in the last example, the collision scheduler has to do something like this:


void manageCollisions()
{
  // iterate all entities, rockets ships …
  …
  if(rocket.checkCollision(ship))
  {
     ship.reactToCollision(rocket);
  }
}

Meaning that both collision effect happen at the same time, so that e.g. state changes are visible to other game entities, which
are checked within the same cycle. But then the ship has to be marks as having already collided with this rocket entity. Otherwise
the scheduler would grab the ship to check for collision and redo it for the rocket.

I know that there a quite a lot of thoughts mixed up in this post and there are variants of putting this code out of the entities into
a manager class (which would have knowledge about the effects). But this is the very essential about these questions: How do you
approach this OO-issue and with what success/ drawback?

#2

I could pull that logic out of the entities, and make a dedicated class for it:


public static void collide(Entity a, Entity b)
{
   Volume va = a.getVolume();
   Volume vb = b.getVolume();

   Sphere sa = va.getBoundingSphere();
   Sphere sb = vb.getBoundingSphere();
   if(!VecMath.intersects(sa, sb)) // extremely cheap check
       return;

   Box ba = va.getBoundingBox();
   Box bb = vb.getBoundingBox();
   if(!VecMath.intersects(ba, bb)) // quite cheap check
       return false;

   if(!VecMath.intersects(va, vb)) // can be a very expensive check
       return;

   a.onCollision(b);
   b.onCollision(a);
}

It’s probably best to check the type of the other Entity using instanceof, because hardcoding types in method-parameters/method-names is much worse than hardcoding them in method bodies. You probably already know how very specific Entity pairs are going to react to eachother, like Ship vs. Asteroid, so hardcoding that is no problem.

Please remember that in game-design there is no such thing as a perfect solution. Heck, I’d go as far as stating that there often is no nice solution. Games are so complex that a little spaghetti code here and there is perfectly acceptable. Over-engineering and abstracting away everything behind 10 layers to make it ‘neat’ will backfire sooner or later.

As aways, just my $0.02

#3

I usually have some collision organizer or manager that keeps track of all the entities that can collide with each other. Then every frame it gets updated (to recompute the bounding boxes) and then is queried for all of the colliding objects. These collisions (and where they collide on each object, too) can then be looked at by anyone that is interested. There is a system that goes through and figures out how to update object velocities so that they bounce off each other in a physically plausible way. It would be easy to add another system that is more specific and just looks for any collision between a rocket and a ship and handles that case, and as you need more custom handlers for collision events, just make more listeners that process the collision information.

This nicely separates computing the collisions (which has to worry about returning a collision between the ship and the rocket and then not returning one for the rocket and the ship) and then figuring out what to do with all of the collisions.

#4

In terms of ‘which object should handle collisions’ I would say in principal it doesn’t matter. However if the events are connected then they should always be togher in the same method. In practice I would say which ever results in the least number of calls should handle this. I imagine there will always be more rockets then ships, so the ship should handle the collisions logic.

I also agree with Riven that the intersection check should be hidden and performed automatically.

Personally rather then setting up collisions to happen later, I prefer to have one event that handles the object logic and allow them to check for collisions in there. Like:


public class Ship extends Entity
{
    public void update()
    {
        // move ship logic
        
        for ( Rocket r : getCollisions(Rocket.class) ) {
            this.damage( r.getDamage() );
            r.explode();
        }
        
        if ( ! isDead() ) {
            // handle firing
        }
    }
}

The above is a simplifaction of what I do, but it makes it much simpler to have all of the Ships logic in one place like that. All of the intersection and collision checking code is hidden away behind the ‘getCollisions’ call.

I also prefer to have more generic methods then say ‘explode’. I normally have a ‘remove’ method that by default removes the object from the game, but conceptually it’s designed to be more of a request. It will then override remove to allow other things to happen, like an explosion. The object isn’t even required to remove itself at all and can freely ignore the call (there is another way to do this in my code for when you want to guarantee removing entities).

This makes it much simpler if your always calling ‘remove’ rather then ‘explode’ for one type of entitiy and ‘die’ for another.

#5

I have been always using codeandcoke’s very first tutorial to check collision of all entities those stored in one ArrayList.


for (i=0; i<entitylist().size(); i++){
   for (j=i+1; j<entitylist().size(); j++){
      e1 = (Entity)entitylist.get(i);
      e2 = (Entity)entitylist.get(i);
      if (e1.collideWith(e2)){
         e1.notifyCollide(e2);
         e2.notifyCollide(e1);
      }
   }
}


public void notifyCollide(Entity other){
if (this instanceof Ship && other instanceof Rocket)
   //get damage
if (this instanceof Rocket && other instanceof Ship)
   //remove rocket
}
#6

I have recently written a tutorial on a similar topic. It is at http://env3d.org/beta/node/37 and scroll down to “simulation logic”.

The gist of my lesson is that if each object handles its own collision with other objects, it makes the main game loop easier to understand (no need to incorporate the game logic into the game loop). It also decouples adding of new object types from the game loop.

Of course, it all depends on what you want to do, and each approach has advantages and disadvantages. For example, in this “decentralized” approach, if you have a bug in your collision logic, you’ll need to look at multiple classes, instead of just one class.

I would argue that the decentralize approach is more “OO”, since the idea of OOP is reduce coupling by moving the relevant code into multiple classes.

#7

I disagree, the decentralized approach you suggest has more coupling, it’s just hidden in a sneaky way. If you have a rocket or missile, that missile must be coupled with every type of thing that it should collide with or damage. That means that any time you want to add a new entity type or player type, you have to update a lot of existing classes. This turns into spaghetti code. If you leave the entities as POJO objects so they only store pure data, you can have handler types for each type of interaction. Then adding collision between new types only requires updating a handler.

#8

Good point, although I think that it all depends on the size of your project and the inheritance hierarchy. For example, if you divide your entities into Weapon and Player, and you can have the Weapon class to only know about the Player class as follows:


public class Weapon {
...
   public void hit(List<Player> players) {
      for (Player p: Players) {
         if (this.closeTo(p)) {
            p.damage();
         }
      }
   }
...
}

The above Weapon class executes without having to know the specific player subclass. You can further define a Player.damage() method as an abstract method so that every player subclass can handle it differently. The coupling, in the above design, is restricted to Weapon and Player classes only, and not to any of the subclasses.

In general, a centralized logic handling class is good if the logic code is not too complex. As the logic becomes complex and you have to handle lots of classes, you’ll end up having a very complex class with a lot of data only classes, which is more “Procedural Programming” than “Object Oriented Programming”.

Having said all that, I think there is no one generic “best” approach, as each problem is unique.

#9

my solution is something like that;

  1. we have an interface for all objects that can collide with others:


public interface Collisionable {

    public Shape/Rectangle/Bounds getCollisionBounds();

    public boolean intersects( Collisionable c );

    public Type getType();

}
  1. we have a manager that holds and organize all Collisionable objects from current object-model


public interface CollisionManager {

    public void register( Collisionable c );

    public void unregister( Collisionable c );

    public Collisionable checkCollision( Collisionable c );

    public LinkedList<Collisionable> checkCollisions( Collisionable c );

    public void update( Collisionable c );

}
  • the manager can be implemented as a simple list or for better performance, as quad-tree or something…
  • the register method adds the Collisionable object to the list ( or quad-tree )
  • the checkCollision method checks for collision on registered objects and returns the first found ( in the second case all it founds in a list) or null if no collision was detected
  • the update method updates a the specified Collisionable if its position has changed ( in a simple list implementation this is not needed but in a quad-tree we have to find the new area or areas that the object now belongs to)
  • on game initialization all Collisionable objects register itself to the manager

now we have a concrete Entity that implements Collisionable and receive calls from update loop



public class Ship extends Entity implements Collisionable {

    private Bounds collisionBounds;

    private CollisionManager cManager;
    @Required    // Dependency Injection or set by a Factory on creation
    public void setCollisionManager( CollisionManager cManager ) {
        this.cManager = cManager;
    }

    public void init() {
        super.init();
        this.cManager.register( this );
    }

    public Bounds getCollisionBounds() {
        return this.collisionBounds;
    }

    public boolean intersects( Collisionable c ) {
        return this.collisionBounds.intersects( c.getCollisionBounds() );
    }

    public Type getType() {
        return Type.SHIP;
    }

    public void update() {

        // compute next position and store it temporarily in collisionBounds...

        // check collisions
        Collisionable collision = this.cManager.checkCollision( this );
        // or
        LinkedList<Collisionable> collisions = this.cManager.checkCollisions( this );

        // handle collisions...

        // if object moved to new position
        this.cManager.update( this );
        
    }

    public void destroy() {
        this.cManager.unregister( this );
    }

}

and now you can decide on our own if a bullet should do a collision check or just moving on and update its position on CollisionManager



public class Bullet extends Entity implements Collisionable {

....

    public void update() {
        ...
        // if object moved to new position
        this.cManager.update( this );
        
    }

}