Another Late Entry

So here's yet another late entry. Once again, sorry for not keeping to my "at least once a week" schedule. This time I don't really have an excuse since school is finally over for Christmas and New Year.

What's happened? Well, lessee...

• Collision detection is finished
• Damage model is finished
• Demonstrated the project to the rest of the 3rd year class
• Wrote up some extra documentation for the faculty's benefit

I ended up ditching one of the collision test elimination methods I mentioned previously. Testing the objects in game, hierarchically (i.e. test a group to eliminate all related objects) added complexity that cost more than the benefit of eliminating a few collisions early on. Additionally a commonish edge case makes the algorithm design slightly hairier than my initial plan which was to use a breadth-first search. The AABB of each group of objects on a given level in the hierarchy would be tested, any non-overlapping branches would be eliminated from further testing. Collisions would then be fired for overlaps between objects at the lowest level of the hierarchy. Astute readers might see a potential problem here.

Collidable objects can be attached to other collidable objects objects across different levels in the entity hierarchy. Because of this collisions can occur at different levels of the hierarchy. In fact collisions can even occur across multiple levels in the entity hierarchy. For example, a fighter's gun can touch another fighters hull and the attached wing. This has to be taken into account. The additional complexity, during my testing, amounted to more CPU work than simply testing all object AABBs within a spatial hash bucket without grouping them.

A plausible compromise would be to use the grouping only as a first-pass (i.e. whole group) method of eliminating collisions. This would probably give the best bang for the buck since group parents are easy to find (removing the pain of implementing breadth-first with the current entity storage system, a giant array) and, in the case of capital ships, a LOT of collision tests can be eliminated at once. For now though, this solution doesn't exist. I'll probably add it when I have the time.

Speaking of time, the previous sprint (number three for those who care) finished seriously behind schedule with an estimated 50ish hours of work leftover. For comparison purposes, the faculty expects a bit less than that amount of work to be done per person per sprint.

I am now confronting the pile of unfinished work and attempting to catch up to where I originally wanted to be at the halfway point for the project. This particular sprint, currently set up to occupy my between-semester vacation time, I decided to focus on eye and ear candy in addition to the neglected work from sprint 3.

• Positional audio
• Particle effects (running on the GPU no less, though I got the original code/concept from Microsoft's sample code at the XNA Community site)
• Lighting, at least some basic global lights and hopefully an initial shadowing model
• Fixing an amusing, but mysterious, off-by-one-frame bug in the view (or world) matrix of some objects

I'll talk about my plans, and completed development, for positional audio and particle effects in the next couple days this week. Perhaps I'll have something screenshot worthy soon...

I'll also try to find some time to get another Content Pipeline series entry written up.

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.