Sign in to follow this  
Crazy Chicken

My Collision Code. Good, Bad or OK?

Recommended Posts

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.
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 );
};

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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!

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.

Share this post


Link to post
Share on other sites
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)!

Share this post


Link to post
Share on other sites
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...

if(hasHit(GameObjects[i], GameObjects[j]))
{
GameObjects[i]->beenHit(GameObjects[j]);
GameObjects[j]->beenHit(GameObjects[i]);
}

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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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

Share this post


Link to post
Share on other sites
Hmm, starting to sound like I'm in well over my head!

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.

Share this post


Link to post
Share on other sites
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[i]->beenHit(GameObjects[j]);
GameObjects[j]->beenHit(GameObjects[i]);

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]

Share this post


Link to post
Share on other sites
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:

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);
}

Share this post


Link to post
Share on other sites
@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):


// 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... :s
Collision 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.
}

Share this post


Link to post
Share on other sites
Thanks Z.

My current game project is a 2D platformer, and i've found that convex polys work good for pretty much everything including tiles, the play, laser blasts etc. A polygon with enough sides can represent a triangle, box, or circle. It's the uber-shape! The only gotcha is objects with multiple contact points (imagine a monster with three large eyes). So i have collision detection between *lists* of polygons now, although i haven't found much use for it yet. Most of my code is separation of axis algorithm code that i got from oliii.

Share this post


Link to post
Share on other sites
Quote:

What is about this "Double Dispatch" object?

Why make an object, that only contains methods?


But it doesn't just contain functions. A BoundSphere would containt that spheres radius; a BoundAABB box would contain the dimensions of that bounding box.

Quote:

I've torn my collision system apart and put it back together so many times, it hurts to think about


Yup, I've got a feeling that might happen here too!

Quote:

A circle-circle collision will react differently than a polyline-box collision


Ah, now that's not something I'd though of - I'd just considered the implications of entityA colliding with entityB, and not the implications of different bounding types.

Quote:

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:


I was going to rely on messaging and then use a switch statement with the same general properties (such as default ignore), so we're on similar tracks. I've also been reading up on using function pointers as callback functions; this might be an alternative (although technically I suppose it's just a C-implementation of polymorphism).

Quote:

3) do the actual testing code outside the class. Have it return some basic data on the collision. I have response go like so:


Yep, we're the same on this one.

Quote:

So i have collision detection between *lists* of polygons now


Again, this is the path I was intending to head down.


Thanks leiavoia and zahlman, this is exactly the kind of information I've had problems finding in the past.

Jim.

Share this post


Link to post
Share on other sites
Including all primitives into a single file makes for a very large file.

However, you can sort primitives from "simplest" to "most complex", and give them a rank (small integer from 1 through N primitive types). The rank might be something like "plane, point, sphere, line, capsule, box, cylinder, convex hull, polymesh" for a very fleshed-out system. This is a total of 9 primitives, and chances are you won't do polymesh anytime soon if you're starting from scratch :-) Make that 8 -- then collapse point into sphere, and line into capsule, and you have 6 primitive types.

Then create collision functions between a primitive, and any primitive with the same or lower rank. Thus, in the file "plane.cpp" you'd find only "collide_plane_plane". In the file "sphere.cpp" you'd find "collide_sphere_sphere" and "collide_sphere_plane". Etc. In the file "convexhull.cpp" you'd find six functions; starting with "collide_convexhull_convexhull" and ending with "collide_convexhull_plane". Use index 0 for "null" so you'd also have "collide_sphere_null," "collide_convexhull_null" etc.

For headers, you can easily put the forward declaration of these functions, and the concrete classes, in a single header. They could all derive from a class with a single public member, called "rank". You can use a getter if you think this is better, but it should not be virtual, because that's too expensive when running lots of collisions.

Now, create a matrix of size NxN, and fill in the collision functions you have, by rank in each dimension. You will note that the upper half of the matrix is empty. Make all of the upper half point at a single function, which reverses its two arguments, and re-dispatches into the matrix -- or code out the specifics of each combination to call the appropriately reversed function directly if you really want to optimize the call overhead.

Now, your middle collider object will just use the "rank" of each colliding primitive, look up the function pointer in the matrix, and call that. Done! It's a very simple, very fast operation. You could, conceivably, detect that the ranks are out of order and reverse the arguments inside this function, instead of creating the second half of the matrix -- that's a reasonable alternative.

Each object would be described with a struct, or a public class, at this level, because all the collider functions need to poke directly at the representation of the others. An alternative is to make them private, but make the collider class a friend of each of them, and make the "collide" as well as each "prim_prim" function static members of the collider class, if you want to protect the user from seeing the internals, but want to still provide the concrete classes in headers.

If you look how collision is set up in the open source dynamics system ODE, it's very similar to this (look how dCollide() is implemented). The key is to realize that virtual dispatch is only useful for single-dispatch solutions, and that the number of primitive combinations you will use is small enough that the n-squared complexity (the matrix) isn't a problem -- note that there is no exponential growth in this problem, like someone else suggested.

Share this post


Link to post
Share on other sites
Quote:
Original post by JimPrice
Quote:

Lots of stuff from hplus0603


Now that's elegant! Thanks very much.

Jim.


If i understand all that, that sounds a lot like what i originally started with. Each of my primitive collision detection functions was turned into a pointer and stuffed into a square look-up table. So when i wanted to handle collision between two different types, i would simply activate the function at the appropriate table intersection (syntax escapes me):

table[ A.type ][ B.type ](A,B);

I still use that for comparing my basic collision types, but like i mentioned previously, i did away with multiple collision geometries so i don't use it for that anymore.

It's a good technique for a general problem though, not just collision detection.

Share this post


Link to post
Share on other sites
It still means O(n^2) functions to write and maintain, though. My idea is to try to make that into O(n) by asking each object to "translate itself" into a simpler primitive according to the circumstances of the potential collision. Assuming this is feasible (and it seems to be in the case I explored, anyway), you just write the one for each geometry, and then a common routine for processing those. So in 3D, and going off of hplus' "geometric tower", the idea would be to get a tangent plane for each geometry, according to what part of the object would hit first (given it hits).

Hmm, now that I think about it, I got it wrong the first time around - collisions between polyline geometries will generally involve a corner of one of the objects and a side of the other. Need to think about it some more... :s

Share this post


Link to post
Share on other sites
Wow, this discussion has become very interesting! Was not not expecting so many replies. So basically what is being said is that using double dispatch is not the best of approches since it is part of the problem that we are trying to solve. This brings me back to something I mentioned earlier.
An article on the internet quotes...

Quote:

"Templates could be used to solve the double dispatch problem conveniently if we change the setting slightly. Since templates work at compile time we have to know the actual types of colliding objects and we cannot work with base class pointers. The generic template implements the symmetry, the specialized functions implement the actual collision handling. This solution is extendible. A new class has to implement all possible combinations with old classes."


To me that sounds quite sensible yet I am a little confused how I this would be implemented. Any ideas?

Thanks. Lukas

Share this post


Link to post
Share on other sites
Quote:
Wow, this discussion has become very interesting! Was not not expecting so many replies. So basically what is being said is that using double dispatch is not the best of approches since it is part of the problem that we are trying to solve. This brings me back to something I mentioned earlier.


That's one way to look at it, but basically, the problem is that you have a many-to-many scenario. Each thing has to react differently with all the other things. What i'm saying is, regardless of the solution it's going to get dirty :-)

Share this post


Link to post
Share on other sites
I use what Zahlman is describing. The only limitation is requiring the bounding volumes to be convex. I think its a great method because they don't know about eachother in order to collide properly. I've implemented spheres, capsules, cylinders, and OBBs with it, works great.

Share this post


Link to post
Share on other sites
I have looked at what Zahlman is proposing but I am having a little trouble understanding what it is we are actually checking agianst. Will this apply to 3D too? What about static objects that dont have a velocity? It would be great if someone could clear that up for me.

Thanks,
Lukas

Share this post


Link to post
Share on other sites
This may be a similar answer to one of the earlier answers... but what if you had one of those common message routing objects (that were spoken of early on in the post), and gave it the ability to discern interactions not with particular objects, but with generalized types? It would still be O(N^2) as someone pointed out, but the number itself would be kept small enough that it wouldn't matter.

My rationale for this is that, in most games, the number of different *reactions* that something can have to another thing is fairly finite. For instance, in a simple run-n-gun game you only have Player-Enemy, Player-Pickup, Enemy-Background and Player-Background... sometimes Enemy-Enemy or even Enemy-Pickup. If coded well, the actual properties of the collision (for instance, what the pickup gives you or how much damage you take from a player-Enemy interaction) could be coded into the message itself, thus saving the time of having to go through every *specific* type of pickup/enemy/etc...

I don't know if this is a feasable aid, but it was something I was thinking of as I was reading this, so I figured I'd toss it out there.

Share this post


Link to post
Share on other sites
Quote:
Original post by Crazy Chicken
I have looked at what Zahlman is proposing but I am having a little trouble understanding what it is we are actually checking agianst. Will this apply to 3D too? What about static objects that dont have a velocity? It would be great if someone could clear that up for me.

Thanks,
Lukas

It applies to 3D as well, that is what I use it for. Here is a summary of the important parts of my system:

class IConvexVolume
{
public:
virtual bool GetTangent(CPlane & Plane, const CVector & Position) = 0;
virtual void GetCorner(CVector & Corner, const CVector & Normal) = 0;
};
// examples

class CSphere : public IConvexVolume
{
float Radius;

bool GetTangent(CPlane & Plane, const CVector & World )
{
CVector Position = World * m_InverseTransform; // find the position of the other point in local coordinate system

Position.ToNormalize();

Plane.n = Position;
Plane.n.TransformVector(m_Transform);
Plane.n.ToNormalize();
Plane.d = -Plane.n.Dot(Position * Radius * m_Transform); // Collision.Sphere = radius
}

void GetCorner(CVector & Corner, const CVector & Normal)
{
// Edit: Missed this next line when copying!!!
CVector Flipped = Normal * -1.0f;

Corner = Flipped.TransformVector(m_InverseTransform);
Corner.ToNormalize(); // 'unit sphere' position
Corner *= Collision.Sphere; // sphere of proper radius
Corner *= m_Transform; // world space
}
}








This obviously will not compile, I tried to make the example as clean as possible but ripped code from my game into it, hopefully you get the idea.

To use it:

IConvexVolume * A, * B;
...
CPlane TangentPlane;
if(A->GetTangent(TangentPlane, PositionOfB))
{
CVector Corner;
B->GetCorner(Corner, TangentPlane.n);

// if Corner is behind the plane, move B by the depth of Corner into TangentPlane along the normal of TangentPlane
}








Its not perfect, far from it actually, but it is quite close, and it plays well in game. Its problems come from things like this terrible ascii art example:

______
| |
\ | |
\C | |
\ | |
\ | |
\ | |
\ | |
\ | * B |
\ | |
____ \ | |
/ \\| |
/ \ |
| |\ |
| * A ||\ |
| D*__\___|
\ / \ . (wtf is with gamedev and \ on the last line?)
\______/ \ .

Here, A is a sphere and B is a cylinder. When A returns its tangent plane C, it will not be vertical like it should be, instead something near the line in the picture. because of this, B will give its corner as the point marked D (this is not necessarily wrong, it would be the same point or an equivilent point (same depth) if the plane was correct as well). It is behind the plane, so the cylinder will be moved out of intersection with the sphere, however, it will move the cylinder up and to the right, rather than correctly just to the right. I've rarely seen this cause anything weird to happen though, and it will never allow objects to intersect, just the response is off sometimes.

All of my code and the example here assumes object A is static, B is moving, however, this collision detection system doesn't provide any less information than equivilent systems so anything implemented with those should work here. I handle two moving objects extremely simplistically, just each one gets half of the penetration depth and one gets a reversed normal.

I've looked closer at what Zahlman was saying and apparently its not quite as similar as I thought, just the concept of tangents vs. points and how to get them. His seems to have potentially better response, but what I have described here is plenty good for what I'm doing.

edit: My ascii art got mangled a bit

[Edited by - Kibble on December 6, 2004 8:48:31 PM]

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