class BoundSphere;
class BoundAxisAlignedBox;
class BoundType
{
virtual bool IsColliding( const BoundType& bType ) const = 0;
virtual bool IsColliding( const BoundSphere& bType ) const = 0;
virtual bool IsColliding( const BoundAxisAlignedBox& bType ) const = 0;
virtual void Transfrom( const D3DXMATRIX& matTrans ) = 0;
};
class BoundSphere : public BoundType
{
public:
float fRadius;
D3DXVECTOR3 vPos;
virtual bool IsColliding( const BoundType& bType ) const;
virtual bool IsColliding( const BoundSphere& bType ) const;
virtual bool IsColliding( const BoundAxisAlignedBox& bType ) const;
virtual void Transfrom( const D3DXMATRIX& matTrans );
};
class BoundAxisAlignedBox : public BoundType
{
D3DXVECTOR3 vMin, vMax;
D3DXVECTOR3 vCenter;
virtual bool IsColliding( const BoundType& bType ) const;
virtual bool IsColliding( const BoundSphere& bType ) const;
virtual bool IsColliding( const BoundAxisAlignedBox& bType ) const;
virtual void Transfrom( const D3DXMATRIX& matTrans );
};
My Collision Code. Good, Bad or OK?
Author
Hi,
I posted a topic not too long ago where I asked about any good and clean ways of designing collison code. Someone pointed out that the 'double dispatch' pattern is useful when trying to accomplish this.
I sat down and wrote some code. I would like to know what you think of the design.
The Transform() function will be used to move the bounding volume to a meshes positon by passing a reference to its world matrix.
The IsColliding() function will check if a collison between two bounding volumes has occured.
Is this ok or is there a better way to do this? I read that templates could be used to make the code look cleaner but I don't know how this could be done. The text about the templates can be found on the bottom of this page... http://www.mpi-sb.mpg.de/~kettner/courses/lib_design_03/notes/advanced.html#DoubleDispatch
Thankx,
Lukas
No, no, no... the problem with your method is you have a combinatorial number of files to edit as you add collision primitives and each primitive needs to 'know' (i.e. #include) about each other primitive. Big mess.
Now, it's not really possible to eliminate the mess totally, but it is possible to contain the messy part to just one place, rather than spread it through multiple objects in multiple header files. You need a separate object whose job it is to take the colliding primitives and call the appropriate collision function... instead of having collision functions be members of each primitive.
I remember that Scott Meyers wrote an article on double dispatch using exactly collision as his example. I think it's in More Effective C++. Great read. Maybe the most "worth the money" books I've ever read. Now beware that his solution may or may not be what's best in your situation, but his analysis of possible solutions and their pitfalls is a MUST read... or you'll find yourself riddled with well-known flaws.
Now, it's not really possible to eliminate the mess totally, but it is possible to contain the messy part to just one place, rather than spread it through multiple objects in multiple header files. You need a separate object whose job it is to take the colliding primitives and call the appropriate collision function... instead of having collision functions be members of each primitive.
I remember that Scott Meyers wrote an article on double dispatch using exactly collision as his example. I think it's in More Effective C++. Great read. Maybe the most "worth the money" books I've ever read. Now beware that his solution may or may not be what's best in your situation, but his analysis of possible solutions and their pitfalls is a MUST read... or you'll find yourself riddled with well-known flaws.
Morning,
I was the person who suggested double dispatch - my original suggestion was here.
Unfortunately I don't have More Effective C++ (it's the only one of Sutters and Meyers books I don't have - ironic, given the topic, huh!) - wish I'd known about this originally!
Yup, this is what I thought. But the way I solved this was by:
firstly thinking there are only a limited number of boundtypes, so although its an exponential increase in code as you add more types, there is a very definite limit on this.
Secondly (and this is probably just semantic) - just include all the types in one file. It's not likely that many files are going to need to collision detection code, so the number of includes is limited.
Er - isn't this what the boundtype class does. Every Entity has a boundtype* data-member (or a std::list/vector or boundtype*'s). Then they rely on the base class to sort out all the multiple types - see the link above.
The problem I had when first writing collision code was that, whereas there are plenty of people willing to discuss the theory behind it, there's relatively little info on implementation. I had a stab, which worked for my relatively simple examples!
Of course, as I said in my reply to the original topic - what do I know, I'm just an amateur!!
Sorry if this comes across as defensive - it's not meant to be, I want to learn as much from this as the CrazyChicken. Just trying to put it into context!
All the best,
Jim.
I was the person who suggested double dispatch - my original suggestion was here.
Unfortunately I don't have More Effective C++ (it's the only one of Sutters and Meyers books I don't have - ironic, given the topic, huh!) - wish I'd known about this originally!
Quote:
the problem with your method is you have a combinatorial number of files to edit as you add collision primitives and each primitive needs to 'know' (i.e. #include) about each other primitive. Big mess
Yup, this is what I thought. But the way I solved this was by:
firstly thinking there are only a limited number of boundtypes, so although its an exponential increase in code as you add more types, there is a very definite limit on this.
Secondly (and this is probably just semantic) - just include all the types in one file. It's not likely that many files are going to need to collision detection code, so the number of includes is limited.
Quote:
You need a separate object whose job it is to take the colliding primitives and call the appropriate collision function... instead of having collision functions be members of each primitive.
Er - isn't this what the boundtype class does. Every Entity has a boundtype* data-member (or a std::list/vector or boundtype*'s). Then they rely on the base class to sort out all the multiple types - see the link above.
The problem I had when first writing collision code was that, whereas there are plenty of people willing to discuss the theory behind it, there's relatively little info on implementation. I had a stab, which worked for my relatively simple examples!
Of course, as I said in my reply to the original topic - what do I know, I'm just an amateur!!
Sorry if this comes across as defensive - it's not meant to be, I want to learn as much from this as the CrazyChicken. Just trying to put it into context!
All the best,
Jim.
Quote:I had a stab, which worked for my relatively simple examples!
There's another principle that I really like known as YAGNI, meaning "Ya ain't gonna need it". It basically means you don't engineer a complex, general solution to a problem until you actually need one. Google for it.
So, yeah. If it works for you, go with it. But the main thing is that, if at some point your solution becomes unmaintainable, you DO go back and rewrite it to a form that scales better. That's the tough part about YAGNI... recognizing the WYFNI (when you finally need it)!
Also, I should note that 'Double Dispatch' is the nature of the problem, not a type of solution... and while there may be only a few types of primitives to collide, there may be lots of different game objects each type of which needs to respond differently upon impacting each other type (to take damage, collision response, or ignore collision, or set off some event trigger, etc). So in your code in the other thread, your 'beenHit' would need to be rewritten to take the other object as a type.
So even though your objects share bounding types, the code to respond to collisions is still dispatched based on the objects themselves...
Well anyway, you can do whatever works best in your own particular situation... but you still need to think about pitfalls, especially when your problem is well-studied and known for its complexity.
So even though your objects share bounding types, the code to respond to collisions is still dispatched based on the objects themselves...
if(hasHit(GameObjects, GameObjects[j])){ GameObjects->beenHit(GameObjects[j]); GameObjects[j]->beenHit(GameObjects);}Well anyway, you can do whatever works best in your own particular situation... but you still need to think about pitfalls, especially when your problem is well-studied and known for its complexity.
Bad :)
Ajas is right. One thing that should strike you as odd in your desing is where the processing of the collide is happening :
boundSphere.IsColliding(boundAxisAlignedBox);
doesn't get process at the same place that
boundAxisAlignedBox.IsColliding(boundSphere);
You probably should think about taking the processing out of one or the other and put it in a third class.
CollisionProcessor
{
bool isColliding(BoundSphere, BoundAxisAlignedBox);
}
Like Ajas said, it's gonna be messy, but at least you don't have to go back and change your base class boundType (and every other derived class!) just because your adding another collision test.
I don't think double dispatching is what you are looking for in this case.
Shadx
Ajas is right. One thing that should strike you as odd in your desing is where the processing of the collide is happening :
boundSphere.IsColliding(boundAxisAlignedBox);
doesn't get process at the same place that
boundAxisAlignedBox.IsColliding(boundSphere);
You probably should think about taking the processing out of one or the other and put it in a third class.
CollisionProcessor
{
bool isColliding(BoundSphere, BoundAxisAlignedBox);
}
Like Ajas said, it's gonna be messy, but at least you don't have to go back and change your base class boundType (and every other derived class!) just because your adding another collision test.
I don't think double dispatching is what you are looking for in this case.
Shadx
Hmm, starting to sound like I'm in well over my head!
I was just writing how I thought I was going to solve this when I saw a huge flaw.
Oops.
But this was exactly the problem I was finding - I could find little info on how to actually implement collision detection. I dearly remember my original search on GameDev, for example, which didn't seem to include any solutions.
Ah well, it's fun to learn through experimentation.
Thanks for all the help,
Jim.
Quote:
So in your code in the other thread, your 'beenHit' would need to be rewritten to take the other object as a type.
I was just writing how I thought I was going to solve this when I saw a huge flaw.
Oops.
Quote:
Well anyway, you can do whatever works best in your own particular situation... but you still need to think about pitfalls, especially when your problem is well-studied and known for its complexity.
But this was exactly the problem I was finding - I could find little info on how to actually implement collision detection. I dearly remember my original search on GameDev, for example, which didn't seem to include any solutions.
Ah well, it's fun to learn through experimentation.
Thanks for all the help,
Jim.
Quote:
I was just writing how I thought I was going to solve this when I saw a huge flaw
Hah - quoting myself now.
Reconsidering what I was thinking - this was how I was going to solve it.
Instead of having:
GameObjects->beenHit(GameObjects[j]);
GameObjects[j]->beenHit(GameObjects);
I was going to use a message passing system from one object to t'other.
So, if I know objectA and objectB have collided (using the beenHit function), then I pass a message (object) to objectA telling it that it's been hit by objectB, and vice versa.
Then the first step each object takes during its update is to check all messages. OK, so you've got to have a big switch-type statement to process all 'BeenHit' messages, but I couldn't see an obvious way to avoid this.
Quote:
boundSphere.IsColliding(boundAxisAlignedBox);
doesn't get process at the same place that
boundAxisAlignedBox.IsColliding(boundSphere);
You probably should think about taking the processing out of one or the other and put it in a third class.
CollisionProcessor
{
bool isColliding(BoundSphere, BoundAxisAlignedBox);
}
That's a good point, but you only need to write the code once - if your boundSphere.IsColliding(BoundAxisAlignedBox) code has the actual collision mechanics in it, then you could just redirect boundAxisAlignedBox.IsColliding(boundSphere) to that function. OK, it's another function call, but it's not the end of the world.
Quote:
at least you don't have to go back and change your base class boundType (and every other derived class!) just because your adding another collision test.
And I still don't see this as a big problem - there is only a limited (and small) number of potential boundTypes; once you've entered them once then Bob's your father's second uncles cousin.
Please feel free to points out any more inadequacies in my arguments!
Jim.
Edit : I should add that most of the motivation for what I have done comes from the book Collision Detection in Interactive 3D Environments, by Gino Van Den Bergen. In there, whilst talking about the SOLID library, it specifically talks about using double dispatch in this way (although they also note that this isn't natively available in C++, and therefore resort to using RTTI), and using callbacks to handle communicating with entities - I sort of thought that was what I was doing.
[Edited by - JimPrice on December 3, 2004 7:35:50 PM]
I've torn my collision system apart and put it back together so many times, it hurts to think about. But i'll share what wisdom i have gained by doing so:
1) Having multiple bounding geometries is a real pain. My first 2D collision system had boxes, circles, and polylines. I distilled it down to those three. But that means that there are 6 separate tests. That's okay, but the more serious problem is collision response. A circle-circle collision will react differently than a polyline-box collision. So now each geometry requires not only 3 different tests to detect collision but 3 different ways to respond! My solution was to have only one kind of geometry: convex polygons. One type of test, one type of response. Your solution may differ, but i strongly advise going with one single bounding geometry. Your life will be much simpler.
2) Collision response is a real pain anyways. You will certainly have several different object types: players, enemies, world, weapons, etc. These are all going to interact in different ways. For this, i DID use double dispatch. Each Object type has it's own set of collision reaction functions:
The default response is to do nothing at all. If a RealBadGuy (which inherits from EnemyCollisionObject) object wants to do something special (like, besides nothing at all...), then it defines the virtual function for a particular reaction. So, RealBadGuy will have specialized virtual functions for interacting with object types, except perhaps for EnemyWeapon which we leave with the default behaviour (nothing) since Enemies and EnemyWeapons don't interact in this game.
3) do the actual testing code outside the class. Have it return some basic data on the collision. I have response go like so:
1) Having multiple bounding geometries is a real pain. My first 2D collision system had boxes, circles, and polylines. I distilled it down to those three. But that means that there are 6 separate tests. That's okay, but the more serious problem is collision response. A circle-circle collision will react differently than a polyline-box collision. So now each geometry requires not only 3 different tests to detect collision but 3 different ways to respond! My solution was to have only one kind of geometry: convex polygons. One type of test, one type of response. Your solution may differ, but i strongly advise going with one single bounding geometry. Your life will be much simpler.
2) Collision response is a real pain anyways. You will certainly have several different object types: players, enemies, world, weapons, etc. These are all going to interact in different ways. For this, i DID use double dispatch. Each Object type has it's own set of collision reaction functions:
PlayerCollisionObject { // generic dispatch function virtual void ReactTo( CollisionObject* obj ) { obj->ReactTo(this); } // specific functions: virtual void ReactTo( PlayerCollisionObject* obj ) { return; } virtual void ReactTo( EnemyCollisionObject* obj ) { return; } virtual void ReactTo( WorldCollisionObject* obj ) { return; } virtual void ReactTo( WeaponCollisionObject* obj ) { return; } }The default response is to do nothing at all. If a RealBadGuy (which inherits from EnemyCollisionObject) object wants to do something special (like, besides nothing at all...), then it defines the virtual function for a particular reaction. So, RealBadGuy will have specialized virtual functions for interacting with object types, except perhaps for EnemyWeapon which we leave with the default behaviour (nothing) since Enemies and EnemyWeapons don't interact in this game.
3) do the actual testing code outside the class. Have it return some basic data on the collision. I have response go like so:
if ( Collides(A,B) ) { A->ReactTo(B); B->ReactTo(A); }
@leiavoia, I think this may let you handle the other geometries [smile]
First, when running the collision detection, model it with both objects moving at speed X-Y/2. (That is, discard the component of their motion which is perpendicular to the line connecting them. If they are moving away from each other, which you can determine by a dot-product test, report "no collision" immediately.)
Second, give the Geometry objects this method (I assume an abstract Geometry interface which lists the method):
This represents, in all cases, the bit of the BB that would touch the other BB first if there is a collision. So now you just do a collision test between "swept line segments (possibly points)" which are just parallelograms (possibly lines).
To run the whole test, then:
First, when running the collision detection, model it with both objects moving at speed X-Y/2. (That is, discard the component of their motion which is perpendicular to the line connecting them. If they are moving away from each other, which you can determine by a dot-product test, report "no collision" immediately.)
Second, give the Geometry objects this method (I assume an abstract Geometry interface which lists the method):
// a LineSegment consists of a direction and two endpoints.// Single points can be represented as LineSegments; this is the// representation of points on the boundary of a Circle// (i.e. a tangent line).LineSegment ConvexPolygon::getTangent(Vector direction) { // Find out which side of this is intersected and return it // The ConvexPolygon is represented by a set of LineSegments // which are its sides.}LineSegment Rectangle::getTangent(Vector direction) { // A rectangle is a special case of a convex polygon, so no // problem here.}LineSegment Circle::getTangent(Vector direction) { // both endpoints of the return value are equal to // centre + (direction * radius) // and the direction is perpendicular to the radius.}This represents, in all cases, the bit of the BB that would touch the other BB first if there is a collision. So now you just do a collision test between "swept line segments (possibly points)" which are just parallelograms (possibly lines).
To run the whole test, then:
// I *think* I got all the math right... :sCollision collide(Thing x, Thing y) { Vector xv = x.velocity(); Vector yv = y.velocity(); if xv.dot(yv) < 0 return Collision::none; // Null Object Vector headonDirection = (xv - yv).normalize(); LineSegment x_face = x.getTangent(headonDirection); // Things delegate to their Geometry for this info LineSegment y_face = y.getTangent(-headonDirection); // Get components of xv and yv which are in the appropriate // direction xv = xv.dot(headonDirection); yv = yv.dot(-headonDirection); // Do the real collision detection now. // A parallelogram can be described in terms of two adjacent // sides, one of which is given by the direction of motion Point x = x_face.endpoint_a(); Parallelogram x_sweep(x_face, LineSegment(xv.normalize(), x, x+xv)); Parallelogram y_sweep(y_face, LineSegment(yv.normalize(), y, y+yv)); // Intersect these. If there is an intersection, then the // xv and yv tell you the force of the collision, and the // normals to the face vectors let you determine which // direction to bounce back. Presumably these bits of info // will both be represented by the Collision object you return. // If no collision, return Collision::none, of course.}This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
