Hi Allegators!

I have a problem on how to implement the collision handling in my game in a good style. Let's say I have a class CObject, a class CCollidingObject and furthermore the classes CShip, CPowerup, and CBullet. I think the names are pretty self-explanatory. Anyway the class hierarchy is like this:

CObject
|
CCollidingObject
|
CBullet, CShip, CPowerup

Now, I have a singleton-class which stores a list to all CCollidingObjects. The collision-detection is not the problem. What I need help with is where to respond on a collision. I have thought up two different approaches:

1.) Every CCollidingObject has a virtual method called "collided_with(CCollidingObject* object)" where the collision is handled. My problem with this is, that I will probably need to make downcasts to the specific classes. For example, if the player's ship collides with a power-up, the method needs to downcast to see if the object is a CPowerup and if it is, do the correct thing (gain hull energy or health, give more ammo, ...) I really don't like this approach because of the downcasts and I will most probably run into include-loops.

2.) The collisions are handled somewhere global in one place. The downside with this is, that I will also need downcasts to call the specific methods (like decrease_health(), destroy() or the like) and I would also need to make all these methods public.

I would like you to give me advice on how to resolve this. Is there a cleaner way (without downcasts at best) to do this? How would you do this?

Thank you for your time!

I'm not an expert in OOP... yet... but I think if you want to stay fully OOP compliant, you may be stuck with having to downcast.

Though my approach with my game engine was to reduce collision detection to a process only some objects can initiate and which only the base class information is distributed in the process. The base class objects store enough basic information that knowing specifics about any particular derived class would be unnecessary. When the two objects collide, each object should primarily affect its OWN status, not each other's, beyond the basics.

Thus the level within the class hierarchy that the collision takes place at should not have anything critical to the collision further derived. IE: If two objects distribute kinetic energy by mass on an impact with each other, you wouldn't store the mass of the object in a derived class above the collision object, you would store it below or in the collision object itself.

So if you need to know whether something which hits a ship is a powerup or not and what kind of powerup it is, that information needs to be stored at the collision level, or closer to the base level, and then the ship, not the powerup, would process it.

...If that makes any sense at all. I'm still figuring all this OOP stuff out so I could be way off my rocker there...

--- Kris Asick (Gemini)
--- http://www.pixelships.com

Collision is probably irrelevent for :
CBullet - CBullet
CBullet - CBonus
CBonus - CBonus

Which leaves you CShip - everything else (including CShip)
Now you only need to derive thevirtual CollidingObject::handle_collision_with (CShip & ship)
for all 3 classes.
Does it suit your needs?

edit: after further research, in the general case what you need is multiple polymorphism, which doesn't seem to be available in C++.
It would consist of a "method"

virtual collision(CollidingObject &a,CollidingObject &b)

that you would derive for all 3x3 combinations, and at run-time it would select which one to use depending on a and b.

One way would be to have a map from two type IDs to a function pointer.

Thanks for your suggestions so far but I am not satisfied.

Kris Asick: If I would put all the necessary informations that I need to fully handle every collision into the CCollidingObject-class or even higher in the tree, it would defeat one of the most basic OOP-features. Why should a CCollidingObject have a member which stores the shield energy, as a ship would have? I really don't like that!

Audric: well, if for example a bullet collides with a ship, who would then destroy the bullet? Should the ship destroy the bullet? IMHO, when they collide the ship AND the bullet should both handle the collision, the ship should decrease it's health/shield energy, and the bullet should set some flag, so that it gets destroyed in the next frame. (I already figured out that having objects being destroyed at a global place is by far the best method)
Furthermore, consider I only have a linked list of all CCollidingObjects, so even calling your function would require me to do a down-cast. Apart from that, it would work for your scenario, but I also want objects like asteroids and other stuff which should also collide with ships and bullets. So, all in all it doesn't suit my needs!

edit:

Audric: that's a feature I miss in C++ since I have started using it!

Flad: care to elaborate a bit more? I am not quite sure I did understand.

First of all, divide the collision problem into two sub-problems: collision DETECTION and collision RESPONSE.
Only objects that MOVE require collision detection, all other objects are static and should only be a "passive" partner in any collision. This alone can drastically reduce the amount of computing needed for collision detection (e.g. by maintaining two separate lists for dynamic and static objects, or by sorting your list so that dynamic objects come first, allowing you to stop iterating when you hit a static object). Objects that trigger no collision response at all (backgrounds and decorative sprites, as well as particle effects and scores popping up when you kill an enemy) can be skipped for both the "active" (outer loop) and the "passive" (inner loop) iteration, so putting them at the very end of the list makes sense too.
Abstract collision detection behavior into a class hierarchy of its own:

cBoundingObject (pure virtual)
|
+- cBoundingSphere
|
+- cBoundingBox
|
+- cBoundingPoint
|
+- cBoundingLine
|
+- cWhateverBoundingThingy

Whether the actual collision check should be a member function or a global function is a matter of taste. If all your objects use the same bounding type, there is no need for an entire class hierarchy and virtual functions, but it's still a good idea to encapsulate the collision detection.

When it comes to collision response, you should group all possible sorts of collision responses into groups, such as:
- bounce
- deal damage
- explode
- be picked up and apply powerup
- ...
The class should have a set of member functions or variables to indicate the desired collision response. Since many of the responses require access to 2 objects, as well as object insertion / deletion, it is a good idea to keep the actual response code in the main game class (I usually call it cScene); it is not very OOP to have objects manipulate the main object list. Also, this is far more flexible, and usually faster, than the downcasting approach, since you can re-use the collision response code for totally unrelated types of objects, provided it is handled in the main game class. For example, a generic bullet could use linear non-accelerated movement, and no bouncing, while a missile class derived from it might use the same damage dealing, but "inherit" its bouncing code from the ship class.

--- EDIT ---
Your examples:
- not every class needs a shield, but the cCollisionObject should have a member function get_shield(), returning either cShield* (defaulting to NULL), or a number indicating the current shield load. I recommend encapsulating the shield code into its own dedicated structure, this allows you to put a shield on anything you want quite easily. This does NOT mean that cCollisionObject should have a member van cShield* shield; only classes where this makes sense should. Conversely, cCollisionObject() should have a member function take_damage(float), which will reduce shield / hull / ... or whatever is available, and marking the object as "dead" if necessary. For an indestructible object, this obviously does nothing.
- "dead" flags are a good idea, since they allow you to remove all dead objects in one go, and clear all references to dead objects before removing them. It is not a good idea to have individual objects messing around with the global list.

edit: I didn't precise below, this is about collision RESPONSE

Personnally, I use a very Actor-oriented model:

What does a bonus do when it touches something ?
It informs it that a bonus wants to hug him - if the target acknowledges, the bonus dies.

What does a enemy bullet do when it touches something ?
It informs it that it has come in contact. If target acknowledges a positive hit, the missile becomes a hit flash, then later dies.

etc.

The messaging is simply done by calling for example: bool actor::hit_by_missile(missile * this)
Each class derives its own, the default code for all interaction is simply
{ return FALSE; } // I don't care
Also, to reduce the number of checks, at the base class level I do a simpleif (active_actor->active_flags & passive_actor->passive_flags)

I prefer having the scene inform the objects involved that they are touching, and decide what to do with them according to their stats.

The common practice is for CCollidingObject to handle it on movement. If any sub-class of CCollidingObject ever wants to move it must call a movement function implemented by CCollidingObject. That function checks if the new position collides with any other CCollidingObjects.

Pretty simple really.

No down-up or any casting at all.

You assume that only movement can cause a collision.
Don't forget "growing" and "state changing" (ie: from invis/invulnerable to vulnerable)
I'm thinking of growing especially for (dangerous/damaging) explosions.

Well, anyway, do what's most suited for the game at hand. A classic shoot'em up will typically have 70% objects on screen as player projectiles, so better "optimize" for this situation.

All the events that can trigger a collision must be implemented in CCollideObject. It is the OOP way.

Why do you need that much information to be accessible?

In the case of a weapon hitting a ship, the weapon has a damage value, the ship has its shields. A collision is detected by the system and both objects run their collision routines.

Ship Collision:
Is target object a weapon? Yes
Call target object function GetDamageVal().
Decrease shields by damage value retrieved from target object.

Weapon Collision:
Is target object a weapon? No
Is target object a ship? Yes
Queue self to be destroyed after collision detection is over.

You never have to send the damage or shield data through the collision class since the ship class has its own method of handling collisions and so does the weapon class.

Does that make more sense?

--- Kris Asick (Gemini)
--- http://www.pixelships.com

class Collidable {
 void moveTo(int x, int y)
 {
  if(.. collision ..)
   this->onCollision(otherCollidablePointer);
 }
 virtual void onCollision(Collidable*) {}
};

class Ship : public Collidable {
 ...
};
class Missle : public Collidable {
 virtual void onCollision(Collidable *c)
 {
  Ship *s = dynamic_cast<Ship*>(c);

  if(s)
   s->inflictDamage();

  dienow();
 }
};

This is the proper OOP style. If you're going to do differen't go for it but know that you are not doing OOP style.

no comments...

Here is a perhaps easier way to handle the problem (If only C++ had multimethods!): have a base class CCollision with a virtual method 'execute':

class CCollision {
public:
    virtual void execute() = 0;
};

Then have a template subclass with two types, one for each type of object; this class acts as a container of the two types:

Then have a specific subclass which handles specific types. For example, to manage the collision between the ship and the powerup, you can do the following:

class CShipPowerUpCollision : public CBinaryCollision<CShip, CPowerUp> {
public:
    CShipPowerUpCollision(CShip *ship, CPowerUp *powerUp) : CBinaryCollision<CShip, CPowerUp>(ship, powerUp) {
    }

    virtual void execute() {
        CShip *ship = getFirstObject();
        CPowerUp *powerUp = getSecondObject();
        if (ship->collidesWith(powerUp)) {
            ship->power++;
        }
    }
};

Then place all collision objects in a list which you frequently scan, invoking the 'execute' method:

std::list<CCollision *> collisions;
collisions.push_back(new CShipPowerUpCollision(myShip, myPowerUp));
while (gameLoop) {
    ...
    for(std::list<CCollision *>::iterator it = collisions.begin(); it != collisions.end(); ++it) {
        CCollision *collision = *it;
        collision->execute();
    }
}

EDIT:

If there are not many collisions to test, perhaps the procedural approach is best:

while (gameLoop) {
    ...
    testCollision(myShip, powerUps);
    testCollision(myShip, bullets);
    ...
}

Thank you again for your help!

It seems there is no 100 percent clean method to do this. But you all gave quite some cool stuff to make it at least come close. I especially like axilmar's idea! Thank you!

edit: ok, axilmar, I really like your approach but there is one thing I am still not fond of.
In your code:

std::list<CCollision *> collisions;
collisions.push_back(new CShipPowerUpCollision(myShip, myPowerUp));
while (gameLoop) {
    ...
    for(std::list<CCollision *>::iterator it = collisions.begin(); it != collisions.end(); ++it) {
        CCollision *collision = *it;
        collision->execute();
    }
}

How do I check, which collision has occured? How do I know it's a CShipPowerUpCollision and not something else?

By checking the types of the colliding objects, duh.
Either dynamic_cast the objects (which is ugly), or give them virtual member functions that return some value with which you can recognize them.

You shouldn't do that! the whole point of putting the collision code into objects is that you don't have to do that. Put all the code that must be executed in a collision inside the CCollision subclass.

Here is a wikipedia article about multimethods:

multimethods

You can use the "CShipPowerUpCollision" system if you want, but your project wont last more then a week when you realize how many utterly useless objects you've created and what a pain in the ass it is. Then your code will turn so ugly you'll give up on the project and start over

But, some lessons have to be learned the hard way.

this works nice the script pointer hard coded id based.

one of the objects

Hey, I couldn't agree more. That's why I wrote that if his collision detection needs are simple, the best approach is the procedural one.

Thanks for all your thoughts! Although I hope that your assumptions concerning my project failing are wrong.

I use a CCollisionHandler which's process-method currently looks like this:

In the first part, I check all objects for collisions and create CCollision-objects which are saved in a temporary list. In the second part, I handle all the collisions based on it's type.

Works quite nice, so I am pleased.

edit: damn, piccolo you are random!

I suppose that could work, assuming all projectiles are implemented as 'bullets'. You've sorted created your own OOP paradigm without using C++ syntax.

std::lists are quite bloated by the way, using them might hurt your fps.

How so? A list uses some extra memory for the list structure (3 pointers per node plus 2 for the head and tail nodes IIRC, so 12n + 8 bytes of overhead for n objects on a typical 32 bit system), true. But it all depends on what you are doing.

Lots of random insertions / deletions? Lists are your friend. The time you save in memory reallocation due to vector resizing should easily compensate for the memory overhead, unless we're talking thousands and thousands of objects.
OTOH, if you can live without random insertion, and use "dead" flags for an en-bloq deletion (by copying the live objects to a new vector), a vector or some other type of dynamic array may be faster. A custom dynamic array can sometimes exploit some special properties of your objects, which allows for certain optimizations (e.g. short-circuiting some loops); this may or may not increase your performance. (If your custom dynamic array is badly sub-optimal, it might actually be slower than any STL container...)
I suggest you code in a way that allows for easy switching between the two container types, and let the profiler decide.

std::list goes out of the way to support a large number of features. This bloat has a high cost. If you can manage to make your list simpler and not require these advanced features you will be saving a lot of overhead.

Yes there is some memory overhead and something tells me its larger then this (maybe some test-cast programs are in order?) but memory is not my main concern.

iterating a list is costly, with at the very least a pointer lookup per iteration. A pointer lookup typically will cost you a whole cycle. So the overhead is in actually iterating the list, not insertion and deletion.

If you must insert randomly and require deletes to happen instantly, then you will be forced to use std::list. But an experienced coder will realize that most list uses can be achieved without these two requirements.

Lets take an example. Say you had a particle engine. Particle engines are always trying to cram more particles and more effects into the game without hurting the frame rate. Every little bit of optimization counts.

In order to avoid having to resize your list, you can employ a simple trick of adding a flag to each particle object specifying if its alive or not. Instead of actually removing the element and reallocating the whole array, you can simply flag the element as dead and re-use it when you have to create new particles later on.

This technique is used in a project I'm working on currently. I'm going to report the FPS for level 1 during normal place as well as the particle count. I'm then going to switch over to a std::list type and report the same results. (I'll put them in my next post / edit).

[edit]
Alright, using the as-is vector style:
58 particles on screen = 95 fps
Using list:
51 particles on screen = 91 fps

So the difference isn't amazingly large in this case, but the more particles the more dramatic the effect.

Ah, but if you had 1000 particles with only the last one flagged as on it would take 1000 iterations to get to it. If you used a list where you removed dead particles it would take only one. You can go in circles trying to figure which is better but it's 'Horses for courses' in the end.

BTW. My particle engine does the same as your's (uses flags) but I use what I call 'Particle Trees' which are groups of particles (ie. explosion tree, snow tree). When all the particles are dead the tree is killed. Particle 'Trees' are created in the Entity List (along with ememies, items etc) which is a linked list (beacause it changes a lot dynamically). Best of both worlds.

It's funny, but I had the same problem and with the same type of objects. Let's say it was something similar to Asteroids. Every object in the game was moving so every collision "A with B" is important. I partially solved the collision response problem without the dynamic_cast stuff. It should be faster. Here's what I've got:

Than in the game:

if( Collision(object1,object2) )
{
  // if both functions return true the physics response is applied
  if( object1->Call(object2) && object2->Call(object1) )
    Physics(object1,object2);
}

And here's how it works. The Call function calls the Bounce function of the other object, i.e.:

bool Bullet::Call( Object *object )
{
  object->call(this);
  return false; // the bullet dies so it doesn't need to bounce off
}

Since the functions are overloaded there is no need to check the object type. If the bullet::call was called and the object was a ship then the ship::bounce( *bullet ) function will be called. I hope it's quite clear.

The obvious drawback is that when you have X different objects you'll end up writing X^2 functions. I have some other solutions, but I have to think them over.

This argument doesn't hold up because I loop every particle updating them every frame. Things like making the particle move etc. During that 'update' I also check for dead and flag if necessary.

On top of that, iterating to the last element in a vector is two instructions: Adding and a pointer lookup. A list lookup of the end is one instruction: a pointer lookup.

Since a pointer lookup will halt the branching, the time needed for these two operations is exactly the same. *

But no one ever needs to access particles in that fashion anyway.

• Corrected, although I still feel like I'm wording this slightly wrong.

I apologise, I misinterperated exactly how you were doing it. I think we're both on the same track or very close anyway. Carry on all...