Sign in to follow this  
Replicon

Collision handling (not detection)

Recommended Posts

I was wondering what clever and innovative solutions people out there have come up with for the problem of how to handle collisions as generically as possible. Note that I'm NOT asking how to do collision-detection. Rather, once your code says "hey, these two game objects have collided", how do you typically handle it in a nice and generic/flexible/scalable fashion? This isn't as trivial as it may seem. For one thing, different object types have to have different behaviours when combined. If a character gets hit by a shotgun blast, he'll bleed some and fall over dead. If a character is hit by rocket, he explodes all over the place. If a bullet hits a bullet... well, in most games, those age ignored/do nothing, fine... If a character hits another character (walks into him), it's just a soft collision that prevents one from just passing through the other somehow... if a character gets hit by a car, he gets flattened... if a car gets hit by a car, there's a nice crash sequence......... As you can see, this problem can get quite hairy, and a silly enumeration of pairs of object types that can collide, and the effect it has, just doesn't sit right with me (but I guess in some cases, it's necessary). In a very simple game (e.g. Gradius-style space scroller), one can come up with some restrictions. For instance, every sprite can have only ONE death sequence (explosion, let's say). Then, you can say EVERY game object has a certain "energy level" (an integer). When two objects collide, you take the min of their energy levels and subtract them from both. Any of the two (at least one of them) that are at zero are now destroyed. This solves some problems nicely. If bullets have an energy level that is lower than anything else's, they will always be destroyed upon first contact. And if walls have more energy than anything else, they will never be destroyed. But what if I want to expand this model into something a little bit more flexible (but not necessarily SUPER-flexible)? What have you folks come up with for this type of problem? cheers!

Share this post


Link to post
Share on other sites
There's a really nice 2D graphics engine that handles these collisons that you discribed very well, it called Physical: http://physical.alecrivers.com/

But you'd have to understand a lot of simple calculus to handle both rotational forces and movement of the whole based on the collsion points of the objects, it's called rigid body.

Share this post


Link to post
Share on other sites
Oh sorry, let me clarify. I'm not talking about handling collisions from a physics perspective (though that's another interesting topic). Think old school 2D sprite games. This is more of a software design topic, sorry about the mixup (I guess I got carried away in the description hehe).

Share this post


Link to post
Share on other sites
I would have the collision code delegated to the game entities, and the 'collision manager' just asks the two objects involved to sort themselves out.

(Edit: Code changed to reflect some thought, see post below)
// pseudocode (C#)
enum CollisionType { Static, Physics, NoPhysics };
struct CollisionData {
CollisionType Type;
GameObject OtherObject;
}

class GameObject {
// All your basic entity code in here, including ...
virtual void Collide(CollisionData data){ }
CollisionType CollisionType;
}

class Bullet : GameObject {
int Damage;
Bullet(){ CollisionType = CollisionType.NoPhysics; }
override void Collide(CollisionData data){
if(data.OtherObject is IDamagable){
(data.OtherObject as IDamagable).Damage(Damage, this);
}
Game.RemoveEntity(this);
}
}

class Rocket : GameObject {
int Damage;
Bullet(){ CollisionType = CollisionType.NoPhysics; }
override void Collide(CollisionData data){
Game.RemoveEntity(this);
if(data.OtherObject is IDamagable){
(data.OtherObject as IDamagable).Damage(Damage, this);
}
Game.AddEntity(new Explosion(Position, Damage));
}
}

class DamagableCharacter : GameObject, IDamagable {
// Base class for player-controlled and enemy-controlled
// game characters who can take damage and die

// This doesn't need any custom collision at all any more!
// Damage is dealt by the enemy, motion is done by the
// collision manager and physics entity

void Damage(int amount, GameObject source){
health -= amount;
if(health <= 0){ ... // die horribly }
}
}



[Edited by - Bob Janova on June 7, 2006 1:59:57 PM]

Share this post


Link to post
Share on other sites
Right, that's my first iteration as well. While it makes logical sense to delegate that task to the game objects, a number of problems arise:

1) Every game object has an ugly switch branch in it.

2) Adding a new game object type involves updating said ugly switch branch in every other relevant game object type. This isn't THAT bad, since you can have a relatively small amount of types (sprites, bullets, solid structures), but it doesn't cover the cases where two objects of the same type may have a differing effect on another (different player death animation, for instance).

3) Suppose the game object manager detects a collision between obj1 and obj2 (remember, it doesn't know what these are). It may call obj1.collide(CollisionData(obj2)) or the converse (obj2.collide(...)). Or you could have it call both, and agree with yourself only to change the the object whose member function you're calling... But then, you have to worry about writing it up such that the order of execution of the two calls doesn't matter (one call changes the state of an object, so the other call cannot depend on any modified state).

What if the collision manager handled pairs of colliding game objects? You could have a default collision model (either pass-through/do nothing, or something like the default I described in my first post), and then branch only on the pairs you want to handle in a special way?

Share this post


Link to post
Share on other sites
Actually, I'm also working on this thing, and also have my problems with it ;)

My solution is also basing on the overridin idea, that BobJanova presented, but i use an affect() Method - that describes ONLY how THIS object is affecting the OTHER - because the affects hasn't to be reflexive - and mostly the aren't. On a collision(A,B) I check simple A.affect(B) and then B.affect(A). Of course - here you have to differ the object-type first. And I'm affraid - some kind of switching you can't avoid - you want somehow differ the responses, though. I haven't, however, hard-coded the responses - scripting it - brings the flexibility of adding new objects after the game is compiled. (yet, I don't know how fast the script will be running...). When you bring then a new object, you have only to describe in the object, how it will affect the enviroment and in the other objects, that collisions with it will be "special" (!= default), you add the affect(NEW_OBJECT) Method. In all other objects the new object will be affected by "default" case (for exaple bounce off if colliding with a spring).
Now, there is indeed the problem with the refexivity of the collision, so I've decided to add a "collisionDone" boolean in the object, that will be flipped, if the collision check will be done. I intentionally said "flipped", because if we would make them hardly "true", then we had to reset all the bools at the end of the check - and with "flipping" you can simply define one frame computing phase as "true" phase and the next as "false" and so on. So, when you have objectA collisions computed, then you flip his "collisionDone" state to the "phase-state", then, if there comes a objectB that already collided with objectA (and the responses were already computed), you will notice that through the "collisionDone" bool, and will simple skip the object. Should work - but I haven't implemented it yet.

My worry is now, how to integrate the collision events elegant to the "map-rules-checker"...

Share this post


Link to post
Share on other sites
This is what comes to mind, I don't know how good of a method it is though.
Using an "enum" for object types:

enum ENTITY_TYPE
{
ENTITY_NPC,
ENTITY_BULLET,
ENTITY_ROCKET
};

class IEntity
{
public:
// ...
virtual ENTITY_TYPE getEntityType() const = 0;
virtual void OnCollision(IEntity *other) = 0;
};

class CNPC : public IEntity
{
public:
virtual ENTITY_TYPE getEntityType() const { return ENTITY_NPC; }
virtual void OnCollision(IEntity *other)
{
switch(other->getEntityType())
{
case ENTITY_NPC:
stopMovement();
break;
case ENTITY_BULLET:
// .. etc.



Or without using an "enum":

class IEntity
{
public:
// ...
virtual void OnCollision(IEntity *other) = 0;
};

class CNPC : public IEntity
{
public:
virtual void OnCollision(IEntity *other)
{
if (dynamic_cast<CNPC*>(other))
stopMovement();
else if // .. etc.



Now you can just call the OnCollision for both objects involved in the collision.

Share this post


Link to post
Share on other sites
Quote:
Original post by Replicon
...

In a very simple game (e.g. Gradius-style space scroller), one can come up with some restrictions. For instance, every sprite can have only ONE death sequence (explosion, let's say). Then, you can say EVERY game object has a certain "energy level" (an integer). When two objects collide, you take the min of their energy levels and subtract them from both. Any of the two (at least one of them) that are at zero are now destroyed. This solves some problems nicely. If bullets have an energy level that is lower than anything else's, they will always be destroyed upon first contact. And if walls have more energy than anything else, they will never be destroyed.

...


That's actually a very good place to start. A field in 2D (for the 2D side-scroller) which contains this destructability information, as well as its colour data. If highly accurate reflection of bullets is wanted, the field could also contain surface normal data. Non-surface pixels would of course have a blank normal of 0, 0, 0 since they really don't ever collide with things.

Share this post


Link to post
Share on other sites
@AsOne: I think you should google up on the double dispatch and visitor patterns. Most likely, there will also be an explanation there as to why enums and downcasts are not a good idea ;)

-Markus-

Share this post


Link to post
Share on other sites
Cygon:
I see, it seems you can avoid using downcasts and enums just by function overloading, and the trick of ...
Quote:

virtual void CollideWith(Asteroid& inAsteroid) {
inAsteroid.CollideWith(*this);
}
Link

[Edited by - AsOne on June 7, 2006 12:55:54 PM]

Share this post


Link to post
Share on other sites
If you mean you use the function signature to work out which collision mechanics to follow, that is far worse than a switch inside the function! Now when you add a new type of collision object, you have to write a new function in every class that is collidable with! ... instead of just adding a new case clause to those objects with which the new type of collision makes a difference.

I admit that sticking a switch in every classes Collide method is rather ugly. However a typical game would only have perhaps three types of collision object: static (i.e. walls and other things that stop everything else), physics-active (i.e. bodies that cause a 'proper' physics collision response, like players, moving balls, rockets maybe) and physics-inactive (i.e. things where there is no physics involved, just entity updates, like bullets, health packs and so on). So the Collide functions would only have three main branches.

You then need to think a bit more carefully than I did before about where damage goes. I guess something like
interface IDamagable {
int Health { get; }
void Damage(int amount, GameObject source);
}

... which players, monsters, destroyable wall entities etc derive from. Then a bullet would, in its collision method, do
if(other is IDamagable) (other as IDamagable).Damage(howMuchDamage, this);


Edit: just read your link on double dispatch, and ewww!

Share this post


Link to post
Share on other sites
Yeah, I still don't see why using enums or dynamic_cast is so bad in this situation, it seems like way more work to write the function prototypes for all the collisions and then implement all the functions themselves then to just use a switch.

e.g. if using the double dispatch method the entity interface would need all types of collisions defined as pure virtual. However, what if some game entity like a gas cloud or something does nothing to itself when collided with anything (except for if it hits the player, it vanishes). You would end up with all of the collision functions (except one) for the gas cloud as just empty functions, gross.

Post before mine says it better ...
Quote:
Original post by Bob Janova
If you mean you use the function signature to work out which collision mechanics to follow, that is far worse than a switch inside the function! Now when you add a new type of collision object, you have to write a new function in every class that is collidable with! ... instead of just adding a new case clause to those objects with which the new type of collision makes a difference.


I agree, just using a swtich would make this neater IMO.

void GasCloud::OnCollision(IEntity *other)
{
switch (other->getEntityType())
{
case ENTITY_PLAYER:
delete this;
}
}

// ...

void Player::OnCollision(IEntity *other)
{
switch (other->getEntityType())
{
case ENTITY_GAS_CLOUD:
health--;
break;
// ...
}
}





Can someone tell my why using enums or dynamic_casts is so bad in this situation? Specifically to the OP's question, why would doing this be bad in a collision response system?

Share this post


Link to post
Share on other sites
I have all objects that inherit from PhysicalObject implement an OnCollision method with a force value, and a pointer to another PhysicalObject (which might expose public traits like IsOnFire or whatever).

Then in my game loop, when I detect the collision, I make both involved objects call OnCollision with the other one and let them work it out internally with their response (a RubberBall object might set its velocity based on the force, or explode, and a Statue object won't move but might crumble if the force is significant enough or the colliding object is explosive). It's pretty simple (thank you polymorphism) but effective. Then after I've run the OnCollision I just check the destroyed status of both objects and discard those that have gone onto the great bit bucket in the sky.

Depending on what properties your base PhysicalObject class exposes, you can have a wealth of different object types. I'm not sure if this is "good" OO but it seems to work for me.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this