# Collision Detection design issues

This topic is 3630 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Im trying to implement collision detection in a different thread so it can run hopefully in parallel with the rendering of the objects. The collisions are reported back with SDL user event structure to get collision. Now the event structure looks like this:

SDL_Event event;
event.type = COLLISION_DETECTED;
event.user.code = 0;
event.user.data1 = pair.object1;
event.user.data2 = pair.object2;
SDL_PushEvent(&event);


The collsion detected event is then extracted like this:
			case COLLISION_DETECTED:
{
Entity* ent1 = dynamic_cast<Entity*>(event.user.data1), ent2 = dynamic_cast<Entity*>(event.user.data2);
ent1->hitted(ent2);
}
break;


The hierarchical structure looks like this: Entity -> Unit -> "Many different units" Entity -> Bullet -> "Many different bullets" (This is only a simplified version) Right now it looks like this:
class Entity {
public:
virtual void hitted(Entity* other) {};
};

class Bullet : public Entity
{
void hitted(Entity* other) {
// Here is where it becomes complicated
// A bunch of if-statements to check what the other type is?
};
};

class Unit : public Entity
{
void hitted(Entity* other) {
// Here is where it becomes complicated
// Maybe this is a bad design?
};
};


The problem is that I don't feel like checking with dynamic_cast what the things that hits what. There must bee a more object oriented solution to this and a lot nicer one also. I will have maybe 10 units and 10 bullets that mean 100 combinations and if statements and a lot of stuff. A lot of cases can be generalized like fire melts ice but it still needs a lot of lookups with dynamic_cast. I will probably transfer the actual implementation of the different bullets and units to Python but I want it to work in C++ first. So im a bit disoriented from where to go from here. I have some ideas but not a very good solution. So let's hear some of your solutions to the problem.

##### Share on other sites
The general solution to this is know as double dispatch. As mentioned briefly on that page, implementing double dispatch is more than a little tricky in C++ - and funnily enough, isn't trivial in Python either.

##### Share on other sites
class Entity {public:	virtual void hitted(Entity* other) {};	virtual void hitted(class Bullet* other) {};	virtual void hitted(class Unit* other) {};};class Bullet : public Entity{	void hitted(Entity* other) 	{		// visitor pattern		other->hitted(this);	}	void hitted(Bullet* other) 	{		// do bullet-bullet hit		// ....	}	void hitted(Unit* other) 	{		// do bullet-unit hit		// ....	}};class Unit : public Entity{	void hitted(Entity* other) 	{		// visitor pattern		other->hitted(this);	}	void hitted(Bullet* other) 	{		// do unit-bullet hit		// ....	}	void hitted(Unit* other) 	{		// do unit-unit hit		// ....	}};

##### Share on other sites
Quote:
 Original post by lephyriusThere must bee a more object oriented solution to this and a lot nicer one also.

How about a different approach altogether.

Have one collision shape only, and let it be represented with some common shape. Circle, polyline, etc. Something that is practical for testing collisions - line, circle, rectangle, ray. There may be arbitrary number of units, but they can be described with fixed and quite limited set of test pairs, making case statement a perfect choice.

Then, all your collisions are collisions between same shapes. If using sprites, rectangles can work, unless you're doing per-pixel tests, in which case shape would be the bitmap itself.

Even without double dispatch as core problem, I prefer collisions between collision shapes, rather than objects. And even if at some point you do need accurate CD, such as ray against mesh (after the bounding shape test), using CD-relevant primitives (ray, triangle, sphere) is much more relevant than FireAndIceBullet vs FancyUnitWithHelmet.

Each of your objects then just contains a single member CollisionShape, and collision is done between them only.

##### Share on other sites
Quote:
Original post by Antheus
Quote:
 Original post by lephyriusThere must bee a more object oriented solution to this and a lot nicer one also.

How about a different approach altogether.

Have one collision shape only, and let it be represented with some common shape. Circle, polyline, etc. Something that is practical for testing collisions - line, circle, rectangle, ray. There may be arbitrary number of units, but they can be described with fixed and quite limited set of test pairs, making case statement a perfect choice.

Then, all your collisions are collisions between same shapes. If using sprites, rectangles can work, unless you're doing per-pixel tests, in which case shape would be the bitmap itself.

Even without double dispatch as core problem, I prefer collisions between collision shapes, rather than objects. And even if at some point you do need accurate CD, such as ray against mesh (after the bounding shape test), using CD-relevant primitives (ray, triangle, sphere) is much more relevant than FireAndIceBullet vs FancyUnitWithHelmet.

Each of your objects then just contains a single member CollisionShape, and collision is done between them only.

I think you misunderstood the problem. I already have the collision detection code in place in a different thread (Using Spatial Hashmaps and GJK btw). I just needed to handle the collisions in a way that doesn't create so much spaghetti code. The thing is to make the code that calculates damage between the units and the bullets.

##### Share on other sites
Quote:
 Original post by lephyriusI will have maybe 10 units and 10 bullets that mean 100 combinations and if statements and a lot of stuff.
No it doesn't - 10 units and 10 bullets is 3 combinations: all bullets deal damage, and all units take damage (the only difference being the amount). So all you have are unit-unit, unit-bullet and bullet-bullet collisions. The the bullet class has a member variable 'damage', which tells the hit unit how much to subtract from its hitpoints.

Subclass mania for different unit and bullet types is very rarely helpful - prefer composition, i.e. each bullet type is merely a bullet that deals a certain amount of damage, uses a certain sprite, and has a certain speed and lifetime.

##### Share on other sites
Quote:
 Original post by swiftcoderSubclass mania for different unit and bullet types is very rarely helpful - prefer composition, i.e. each bullet type is merely a bullet that deals a certain amount of damage, uses a certain sprite, and has a certain speed and lifetime.

Sounds logical in my opinion also. I didn't think about that before. But how do I handle that an ice bullet works better on a flaming unit and vice versa? Should I have a table with exceptions for that? Or is there some other clever solution to that?

Maybe thats a stupid question but I ask it anyway. ;)

##### Share on other sites
Quote:
 Original post by lephyriusSounds logical in my opinion also. I didn't think about that before. But how do I handle that an ice bullet works better on a flaming unit and vice versa? Should I have a table with exceptions for that? Or is there some other clever solution to that?
I would go the simple route - add a damage type variable to bullets, and an armour type or weakness type variable to units. These can be used to calculate the bonuses (i.e. if (damage_type == weakness_type) damage *= 2).

##### Share on other sites
your bullet would be composed of a collision object for starters. The collision object can be of a particular type (sphere, rectangle, point, segment, triangle...), but it doesn't need to know what type of object it belongs to. It just needs to detect and report a collision found with another collision object.

Your collision detection routine works by testing pairs of objects. When objects collide, the collision information are queued in a list (send message if you prefer), and the collision result would be processed somewhere else.

as for the collision reponse (ice bullet vs flaming unit), each of your objects would have special properties associated with them.

What I would do is store object's properties as a component of each objects. A bullet damage property would point to a damage table, listing the damage multiplier to apply against a list of armors (Ice armor, flame armor, steel armor, ...). The damage handler, that catches the collision result message, look at the unit's armor, the base damage of the bullet, and look up the damage multiplier of the bullet against that armor, and apply the total damage to the unit, with maybe some armor modifier (say you picked up a spell that divides total damage taken by 2), and send the result in the form of a 'damage' message to the unit.

The damage handler would also be responsible for sending a similar message back to the bullet (typically a 'damage' to damage the bullet, a 'destroy' message if the bullet just dies on impact, 'fragment', 'deflect' or 'rebound' message, or a more generic message doing any of those effect at the same time).

In case of two units colliding, the damage handler would probably do a similar thing to each unit (probably a 'collide' message to make the unit bounce of each other, and maybe 'damage' as well, to apply some damage from the collision).

##### Share on other sites
Quote:
 Original post by lephyriusI already have the collision detection code in place in a different thread (Using Spatial Hashmaps and GJK btw). I just needed to handle the collisions in a way that doesn't create so much spaghetti code. The thing is to make the code that calculates damage between the units and the bullets.

The mess comes from trying to model orthogonal approach. For example, damage involves one object being damage dealer and other target. Collision involves both being equal. Some other type of interaction is something else again.

So let's define interaction types as:
enum InteractionTypes {  DAMAGE_DEALER     = 1 << 0,  // object deals damage  DAMAGE_TAKER      = 1 << 1,  // object can take damage - not invincible  SIMPLE_COLLISION  = 1 << 2,  // object bounces off  DESTRUCTIVE       = 1 << 3,  // on collision, object is destroyed    ...};
Next, we need interactions as a set of the above. If your collisions always result in a pair of object, it's quite easy and natural to acomplish:
const int DAMAGE_INTERACTION = DAMAGE_DEALER | DAMAGE_TAKER;const int COLLISION = SIMPLE_COLLISION;const int DESTROY = SIMPLE_COLLISION | DESTRUCTIVE;...

Finding the type of collision is now fairly trivial:
int getInteraction(object * a, object * b) {  return a->collision_flags | b->collision_flags;};

So from all pairs we've now gone down to a single function. All we need to check now is different interactions:
void handleCollisiont(object * a, object * b) {  int type = getInteraction(a, b);  if (type & DAMAGE_INTERACTION == DAMAGE_INTERACTION) {    // handle DamageDealer + Target  }  if (type & SIMPLE_COLLISION == SIMPLE_COLLISION) {    // handle elastic collision, calculate bounce, etc...  }  if (type & DESTROY == DESTROY ) {    // find which of a or b needs to be destroyed  }};

The interesting thing above is that it uses one if statement for each interaction type. This allows you to handle multiple interactions for each collision.

For example, a bouncer bullet. It hits a target, deals some damage, but bounces off. So one collision needs multiple handlers.

The core of the above is to compose interactions using bitfields. Each object has a member "int collision_flags". Bullet's flags would be: "DAMAGE_DEALER | DESTRUCTIVE", but bouncing bullet's flags would be: "DAMAGE_DEALER | SIMPLE_COLLISION".

This is a fairly simple but quite flexible approach that is also quite efficient. There is one handler for each type of collision (of which there will be only a handful), but takes care of multiple collisions as well.

Since interaction types are known, handlers can also blindly cast into proper interface. For example, anything that deals damage extends DamagaDealer interface, so when you handle DAMAGE_INTERACTION, you simple check which of a or b has DAMAGE_DEALER flag.

While this may seem counter-OO, or at least like duplicating it, it's actually the reason why various component/entity models evolved. If properly implemented, it gives you ability to reconfigure such parameters at run-time, without modifying the code, just depends on actual interfaces.

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 11
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633721
• Total Posts
3013537
×