Collision Detection with rotating sprites

Hi there!

I'm writing a small asteroid-based 2d game using D3D sprites. There is a feature with those sprites - they support rotation and I use it a lot (i.e. player's ship is rotating).

I understand the basics of collision detection and I'm pretty sure I can write a pixel-perfect checking routine, but what bugs me is that there are NO rectangles, and also, after I draw with an angle, which is not Zero, I virtually don't know where exactly my sprite was drawn.

I've searched the forums, but was unable to find something regarding this topic. So here am I, asking you. There has to be some way! Thanks in advance, waiting for comments... :)

Don't go for pixel perfect collision detection if you are rotating your sprites - its more trouble than its worth.

one solid alternative includes defining an approximating convex polygon which defines the boundary of each sprite and then rotate these approximate polygons before checking them for collision - you wouldnt want to change your drawing code at all (ie, you never draw these approximating polygons.. they are only there for collision detection)

Thanks for your reply =)

Don't go for pixel perfect collision detection if you are rotating your sprites - its more trouble than its worth.

Yeah, I beleive, that you're right. So I'm after those convex polygons. Could you please point me somewhere to read/learn about them? This term is completly new to me.

A polygon in its simplest form is a list of coplanar ordered points who are considered to be connected by edges. The set of all polygons can be divided into subsets with similar properties.

http://astronomy.swin.edu.au/~pbourke/modelling/polygon/

A convex polygon is defined as a polygon where every vertex can "see" every other vertex. Another way to put it is that the shortest line between any two vertices is completely in the interior of the polygon. Still another way is to say that all the angles in a convex polygon are positive (or all negative.)

The 3D equivilent of a convex polygon is a convex hull, which describes a convex 3D volume instead of a convex 2D area. Convex hull's are extensively used in 3D games that have highly dynamic 3D physics (Half-Life 2 for example)

The reason to use convex polygons is that in some cases operations are much simpler and/or more efficient on them. For example, finding a separating axis between two convex polygons (if one exists, they cannot intersect), the tesselation of a polygon into triangles, or computing sweapt volumes.

Its not necessary to restrict the engine to convex polygons, but I believe it to be a good idea none-the-less. Some of the concepts that can be applied only to convex polygons can also apply to convex hulls in the 3D world.

In any event, you will also want to keep bounding circles/spheres for these polygons so that you can do a very fast circle/sphere collision checks.

The nice thing is how you can construct the collision detection in phases. There are various ways to manage your game objects (usualy called a scene graph) and some of them lend themselves well to collision detection. By implimenting circle-circle or sphere-sphere collision detection first, you can get a very good idea as to how practical your scene graph is for the number of objects you want to be handling. You can also get an idea of which objects actualy need better collision resolution than a simple circle.

Note that the circle-circle test is only an approximation that can yield false positives but never false negatives.

Then, circle-polygon collision detection can be implimented to refine potential collisions as determined by circle-circle... and here again, many interactions may not need better collision resolution than this. For example, bullet vs avatar probably doesnt need better than this.

Note that you can do two tests, given objects A and B:

test(A.circle, B.polygon) and test(B.circle, A.polygon)

They are both approximations and again never produce false negatives, but has the potential for false positives.

Most expensive is polygon-polygon collision detection and hopefully you only need to perform this test very rarely .. this is however the definitive collision detector - its always right.

In the end you can have your engine perform all your collision detection types and compile false-positive statistics .. In those cases where there are very low rates of false positives for circle-circle, you can tweak the engine in those cases to accept the circle-circle result verbatim. The same holds true for any other approximations you have implimented. In those cases with sufficiently high false positives you can skip that approximation because its a waste of time.

Thanks for your detailed and solid reply, Rockoon!

To be fair that info scared me to hell =) I hope I'm not biting more, than I could chew, cause I only wanted a simple 2d game :)

So should I keep those polygons invisible and just use them for collisions ? Or should I draw my sprites with them?

Invisible.