Apologies for the delays

As you can see I just released Part 2 of my series on custom content in XNA Game Studio. I think you can also see that I haven't maintained my promised weekly schedule of blog updates.

It's now nearing the end of the semester and things have gotten quite hectic. The only major issue is that my deadlines are tending to arrive in bunches with assignments coming due all at once so I have to work like mad on non-project stuff then, work like mad on the project until the next wave of assignments hits.

So, what am I up to now? Glad you asked! I'm working on turning my game into something that actually resembles a game. This means adding the ability to target, shoot and kill other players as well as a small host of other features. How many?

1. Create teams
2. Assign players to teams
3. Create spawn points
4. Spawn players at spawn points
5. Timing for when players should spawn
6. Collision detection
7. Rules for damaging fighters
8. Weapon targeting
9. Kill scoring
10. Improved network code

I've finished 1-5 already. They're not thatinteresting to talk about at this point since they don't have much effect at this phase of the project. Most of the real work in getting team assignments, spawning etc. working well will happen in the next couple development phases. What I'm doing now though is feature number 6. And it's a bear of a feature.

Collision detection, in my case, is really about detecting when two objects overlap. A lot of effort is required to figure out whether or not two objects, of any shape or size, are touching or overlapping. So most of my efforts have gone into, first, minimizing the number of objects to be tested, and second, simplifying the math required to find overlaps.

I'm currently using two general tricks to eliminate objects for testing. First, objects are generally defined as groups. For example a fighter isn't just a fighter. It's a hull, wings, thrusters and guns. Capital ships are many pieces of hull and many many guns etc. This allows me to eliminate a large amount of tests very quickly by asking "are these objects close enough to have a chance of overlapping?"

Second is what's known as spatial hashing. This is a way of finding the answer to "are these objects close enough to have a chance of overlapping?" quickly. The basic idea is to take a point in space and assign it to a bucket based on its location. Each bucket represents an area of some size, let's say 50x50x50 units. So if you divide an object's position by 50, you now have the number you need to assign the object to a bucket. All objects that occupy the same bucket get tested for collisions.

Now that we have the objects to test we could just test every object against every other object. e.g. if a bucket has ten objects the result is every object being tested ten times or 100 tests. However what we're really doing is testing pairs of objects. We don't need to test if object A is hitting object B if we already checked object B against object A. We also don't need to test an object against itself. So what do we test?

1. Test the first object against the next nine
2. Test the second object against the next eight
We don't test aginst the first, it's already been tested in step 1
3. Test the third object against the next seven
The previous two steps tested this against the first and second objects
4. Etc.

This means we only need 9 + 8 + ... + 2 + 1, or 45 tests... which do what?

Yes, we're finally at the point of actually doing collision detection. There are two general choices here. First is doing perfect collision detection for the object. This involves a lot of tests for even relatively simple objects, so I'm not doing it. The second choice is to test simplified volumes for overlap. This is what I'm doing.

In my case I'm using two kinds of boxes. First is the axis-aligned box (AABB.) The AABB is useful since I can rapidly eliminate non-collisions by simple value comparisons. The AABB for an object contains the bounding box all objects that are attached as well as the object itself. This helps in eliminating many collisions at once.

This second box is shaped so that it covers the object volume as accurately as possible. This one is used for making the final decision of whether or not two objects are colliding. The math for doing, known as the separating axis theorem, this is somewhat more complex than that for the AABB but not by much. In fact the simple test for the AABB is a special case of the same theorem.

This picture shows all of the boxes involved in a collision test (it also shows a tool I created last week for the purpose of setting these boxes up XD) The AABB is orange and the actual collision volume is yellow.

Sorry about the vagueness of the fighter, it's a test model and I haven't set up lighting for the game yet.