Sign in to follow this  
  • entries
  • comments
  • views


Sign in to follow this  
Sir Sapo


Hey everyone!

Dragon88 requested that I elaborate on my side project, and I am happy to oblige.....

Collision Detection!!!!
Well, this is actually the first time that I've attempted to code a modular physics system, so hopefully it doesn't show[wink] In our new project, every collidable object has a "CollisionMesh" object which essentially outlines the areas of the object that can be collided with. The CollisionMesh is formed from one or more "Polygon2D" objects, which in turn are formed by a series of "Line2D" objects, which are made by two "Vector2D" objects.

In order to test for a collision, each vertex of the CollisionMesh is tested to see if it's inside the other CollisionMesh polygon we're testing against. In order to do this, I used the Crossings Test to determine if any of the vertices are inside.

This is a pretty simple task, as all that is required is for you to cast a long ray from the vertex you are testing in any direction, and see how many sides of the CollisionMesh it intersects. If the number of intersections is odd, then the point is inside the polygon, and if the number is even, you are outside the polygon, as seen in my handy diagram below:

There are also a few other functions used to determine which "Line2D" you collided with in order to find its normal vector and whatnot, but thats basically how everything works. I'm considering cleaning up the code and posting it in here, because I remember having a hell of a time getting any sort of collision detection working when I was first learning.

In my next entry, I'll detail how my (crappy) messaging system works! Peace Out!
Sign in to follow this  


Recommended Comments

Wow, it really seems like polygonal collision detection (and response; I'm guessing) is the new 'fad'. EasilyConfused has been playing with it as well, and I've also been working with it (although I haven't mentioned it publically) for the last couple of weeks, with regards to physics. Seems like only a while before that we had the 'random content' fad, where you, Programmer16, and myself were working on games that focused on random level generation. I wonder what's next? [grin]

Oh, and where's that networking post on FoT that you promised me? [sad]

Share this comment

Link to comment
Mind elaborating on why this is evidently extremely useful in your ubar new project? It's a neat feature and all, but unless you guys are making a huge departure from your previous style, it's nothing you couldn't do without.

Share this comment

Link to comment
Lol, I can't wait until the MMORPG fad[wink]

As for the FoT networking stuff, we never really had that implemented to the point of us playing games over the net, before we scrapped the feature, but I would be more than happy to get a "whats the better way" correspondence going if you'd like[grin]

Well, it Angels 22 and FoT, all the objects are small enough that we could get away with simple AABB's and bounding spheres, but with our new project, the relative scale between the smaller ships and the large ones is so large that using those old methods would result in some annoyingly sloppy collision detection.

For our new project we just outline each ship with a polygon, and then no matter how its rotated or scaled, the polygon will still match up with the ship.

Share this comment

Link to comment
I hate to be a git, but I'm reasonably sure this doesn't always work for polygons (eg, for two polygons where the lines intersect but have no points inside each other, think of two really long and narrow triangles crossing near their narrow ends and you'll find an example)

I had to do something similar at work recently (though it was with Mappoint rather than something fun like a game), and so maybe what I found will help you out.

The method I used in the end was the Separating Axis Theorem. It works by projecting each side of the shape onto a 1d plane and checking for intersection there (if you like I will find you a link later). This seems to work pretty well, but there are a few caveats. Firstly, things get a bit complicated when you have complex shapes (though I doubt you will in a game, so don't worry about this). Secondly, the shapes you are testing have to be convex. To achieve this, you can either limit your collision boxes to be convex and just use them as is, or you can break them down into a set of smaller shapes and test each shape individually. Triangles are always convex, but you gain performance by using fewer, larger shapes

With what you have, you could also add line intersection tests in addition to your point tests, which would tell you if the polygons intersect. However you would lose the knowledge of which point caused the intersection, necessary for your physicsy stuff. I remember seeing how you do this though, I think the basic idea was that you project the polygons along the vectors that they are moving, which gives you two 'fat' lines, factor in their speeds and based on that see if they will intersect. This method is also good for slow computers, since with your current method the accuracy of the collision detection is dependent on the framerate of the game, and a slow computer might miss a collision completely if in the time between frames one object has passed right through another

I think that is mostly correct, hope it helps!

Share this comment

Link to comment

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