Collision Detection

Part of simulating a real-world experience is handling collision detection between objects. This discussion will offer some challenges for you to face and offer some suggestions on how to handle them. I can't provide any detailed algorithms because this is a fairly new subject for me.

Collisions can take place between objects and environments. You must have some representation of the physical shape of these areas in order to properly simulate, or at least approximate, collisions.

It is also important to set up your data structures and compliment them with other data structures such that collision detection takes place as quickly as possible. As an example, consider a space game where there are many craft firing lasers all of the time. The lasers can't collide with each other, but lasers can collide with craft, and craft can collide with other craft. If every object was checked for collisions against every other craft in the play area, the calculations would slow everything down. To counter this, most games with a large number of collidable objects will optimize by setting up smaller invisible regions within the play area, and keep track of which region an object is in. Then, when collisions are checked for, a given object will only check collisions against objects in the current region or adjacent regions. This provides an incredible performance gain.

The Billiard game

You will need to be familiar with keying off the system time clock for this exercise. Each frame will have an amount of elapsed time to it, and this will be important to track for moving the billiards along.

Write an application that simulates a billard moving around inside a rectangular area, bouncing off the edges. Make the graphic representation separate from the collision model (That is, don't let the graphics determine the collision model, set that up separately).

Try to write the application so that you can determine the direction the ball will go, and the speed at which it will be sent. Have the ball slow down gradually to a standstill.

Deceleration causes a little complexity for calculating the time at which a collision takes place. If you use a constant deceleration, it makes it easier. Get out your physics book! Express the position of the billiard as equations of x and y, relative to t. You should be able to solve for the time at which the distance between two billiards is equal to their radii added together, which would be a collision. Don't forget to account for the fact that a ball that reaches zero velocity also stops decelerating!

For your next challenge, put other billiards in the play area and have them react to striking each other. Since it is possible for every billiard to go bouncing off each other, it will be important to have accuracy such that no two billiards ever end up inside each other. Here is one way to handle this...

In a given frame, when you check for collisions, note the time at which any given collision is taking place. When you have examined all collisions, deal only with the collision that took place at the earliest time. There may be some special circumstances where multiple collisions with a single billiard takes place at the exact same time, but I believe the math works out, so you don't have to do anything special. Just choose a single collision to handle, as long as it is an earliest one. Once you have handled the new travel direction of the billiards for the collision you are handling, move everything up to that time (velocities, positions, etc.), and check for collisions again (from a fresh start, because the billiard movements have changed). Handle the collision that took place at the earliest time, just like you did before. Repeat until all the time for that rendering frame has been used up handling collisions and moving the billiards forward.

Billiards is a good way to start out with collision detection because the collision models between objects are circles. Circles are very easy to check for collisions. When you move to polygonal figures like cubes and pyramids, it gets a lot more complicated. You will also find that some collision detection can afford to not be so precise. The less you have to calculate, the better frame rates your game will get. You almost always have to compromise between accuracy and speed.

Algebraic considerations

You only need an equation to solve for the object's new position based on time, given their current movement and acceleration. This is enough for moving the object along based on elasped time during a frame, and for figuring out exactly where two objects are during their collision (solve for the time t that they collided, then calculate their position at that time to calculate how to respond).

This may be an oversimplification. The terms on which an object accelerates can really complicate this equation (a ship that is speeding up AND turning, for example, has a muchmore complicated position calculation than an asteroid floating in space, or even an object travelling in a parabolic trajectory).

What's important is that if you want your game to perform the same way on all machines, no matter what the framerate is, you should base all calculations for position on time. That is NOT the same as calculating an object's velocity during a tick and moving it along the whole tick at that velocity! If the object is going through some acceleration, you should take that into account as well in the position calculation. Otherwise, objects may speed up or slow down differently on a machine with a different framerate. For network games, that would also mean more messages being sent to sync up for objects that are in the wrong position.

If you're finding it too difficult to accurately calculate position based on time, then maybe you can fudge it a little, and hopefully it won't create too much of a problem. But in this day and age, when clans are rampant, someone is bound to complain on performance differences based on framerate. That would create a big problem for a game that was released for purchase.