First off, as promised, I will talk about collision detection. However, on the way there, I encountered some other fun things.
The first one is wonderment at how efficient my algorithms are. Here I am wanting to write something that will work well with the user, and I wanted to check to see what the fps (frames per second) rate was. This turned out to be pretty easy, and the bulk of it is as follows:
///
/// Note that a frame has passed and do any math that we need to.
///
public void NoteFrameOccurence()
{
// Take the measurement every 1000ms or 1s.
if ((Environment.TickCount - _lastTick) >= 1000)
{
// Keep the count that we achieved here.
LastMeasurement = _frameCount;
_numberOfSamples++;
_totalFrameCount += _frameCount;
// Reset the count and measurement.
_frameCount = 0;
_lastTick = Environment.TickCount;
}
_frameCount++;
}
Basically, keep track of how many frames we see before 1000ms or 1s passed. If we hit that time, stop collection for that section, remember the last one and add the data to our major sample counters, so we can reflect what the average across our application’s run time.
That being said, I had initially implemented the sprite engine as having a collection of GameSprite objects. Now that I had some way of measuring it, I wanted to see if using an array would be more efficient. With some refactoring, tuning and stuff, I was able to get an array provider that was able to get between 60 and 66 fps with the number usually around 62 or 63. The collection on was usually between 59 and 64 with 61 being the sweet spot. Thus, the array provider seems to work slightly better for now.
On to collision detection. Collision detection is primarily about geometry. The first two types of detection are pretty simple: bounding boxes and bounding circles. The basis for both is pretty much the same: what is the smallest entity of that type that can fit around all of the points in the geometric object in the sprite. These are both used for first pass detection as you can handle both of them pretty easily and quickly. Mileage may vary.
For my first pass I use a bounding circle which can easily be computed at the beginning of the sprite’s life. All I do is check to see what the maximum distance is from the centroid of the sprite to each vertex. This works really well in this case because we are doing a lot of rotations and the bounding circle doesn’t change based on orientation. And for those who need some reminders… distance = sqrt(( a.x – b.x )^2 + (a.y – b.y)^2).
A bounding rectangle would pretty much work the same way, compute the tightest rectangle that completely surrounds the object in question. In our case, we would have to compute it for our sprite after every change in orientation, but could cache that and apply the current position to that. I’ll probably check it out later, but for now, the bounding circle is working just fine.
That leaves us to the more detailed checking. For our purposes, we want to check to see if any point in one sprite is within the bounds of the other sprite. After doing a bunch of searching, I came across this useful article [need to add link here] that explained the math. Okay, I remembered all of the math he is talking about, but didn’t think to apply it in this way. There are some algorithms that he pulls form Graphic Gems IV as well that proved useful.
The one in particular that I liked had to do with a simple way of figuring out if the point is in the polygon. The neat part is that it works for concave and convex polygons, which is useful. I tried it out with a couple of polygons on paper, so if you want to do the same thing, I recommend it… its neat. Draw out your polygon and then pick a point on the inside or outside. Draw the X and Y axis so that the origin is at your test point. Now, pick any point as the start. Add one to a total if you cross one of the axis lines going clockwise and minus one if you cross it counterclockwise. When you reach your starting point, if your total is 4 or -4, your point is inside of the polygon. Neat?!
The code for it is pretty simple as well, the bulk of it being in the case where you cross 2 different axes with the same line. As long as you can figure out which section the vertex point is in, you can figure out (through subtraction) whether or not you have crossed a boundary, and in which direction. Once you have all that put together, it works pretty neatly.
