Welcome back. This is the second article in the 'art of collision' series (the first can be found lower down) and this time the focus is going to be on circles. This tutorial is going cover static and dynamic circle collision testing during which I'll give a comparison of the techniques and how this applies to shooter games in particular. Hopefully this will give you a good understanding of the advantages of dynamic testing over static testing in general as well as the sacrifices which must be made. I apologise now if you took part in the rather long and detailed thread a while back which covered this area since a lot will be repeated, but I'll do so in a more formalised way so hopefully it makes more sense. Don’t worry though; there will be something good for you here too. As a bonus, since we're talking about circles, I'm also going to let you in on a technique you can apply, which shmups tend to be well suited for, which will be like adding a nitrous tank to your collision engines. They're really going to fly after this.

So why use circles? For a start they're an accurate shape for many of the objects we'll encounter in shooters such as bullets or the cockpit of the player ship which defines their hit area. Also just as with the aabb's in the last tutorial they're extremely cheap and easy to collide together. In the case of circles this comes down to the fact that they are isotropic shapes, i.e. the same in all directions. This means our collision test boils down to just measuring the distance between the circles' centres and if this is less than the sum of the circles' radii then they must be intersecting. This distance calculation would usually involve a square root but if instead we work with the sum of the square of the circles radii then we can use the square distance saving us this expensive calculation. Therefore our test looks like so:

struct Circle

{

float x; // x position

float y; // y position

float sqRadius; // square radius

}

bool Collide(Circle A, Circle B)

{

// calculate separation on each axis

float x = A.x - B.x;

float y = A.y - B.y;

// calculate square distance

float sqDistance = x*x + y*y;

// test for collision

return (sqDistance < A.sqRadius + B.sqRadius);

}

Imagine a scene with lots of circles in it were we are testing for collisions between the circles using the above test. Each frame becomes like a snap-shot in time and the collisions we detect will be an accurate representation of what the scene appears to be doing in that snap-shot. Next frame all our circles move a bit and we get another snap-shot. What happens between the frames though? Imagine two circles moving quickly enough towards each other that during one snap-shot they appear separated and then in the next snap-shot they have swapped positions but still appear separated. The above test will tell us in both frames that these circles aren't colliding but in reality we know that they must have passed through each other between the frames and hence we should really trigger the collision resolution code for the two objects these circles represent. So how do we detect these situations? Well this is were dynamic collision tests come in, i.e. collision tests which account for the motion of the objects between the frames. So how do we do this dynamic test. Well we know we can find the position of a circle at any time (t) between the frames using, position(t) = position(t=0) + t*velocity, where t=0 is the time of the previous frame. What we need to find though is whether the distance between two circles ever becomes less than the sum of the radii for any time between the frames. I'll not go into the derivation of the algorithm since although it’s simple it’s quite long and is far better described in many other places on the internet. Instead I'll just give you a code dump of a robust implementation taken from

http://www.gamedev.net/reference/articles/article1234.asp which you should read if you're interested in the maths.

struct DynamicCircle

{

float x; // x position in the current frame

float y; // y position in the current frame

float px; // x position in the previous frame

float py; // y position in the previous frame

float sqRadius; // square radius

}

bool Collide(DynamicCircle A, DynamicCircle B)

{

// calculate relative velocity and position

float dvx = (B.x - B.px) - (A.x - A.px);

float dvy = (B.y - B.py) - (A.y - A.py);

float dx = B.px - A.px;

float dy = B.py - A.py;

// check if circles are already colliding

float sqRadiiSum = A.sqRadius + B.sqRadius;

float pp = dx*dx + dy*dy - sqRadiiSum;

if(pp < 0) { return true; }

// check if the circles are moving away from each other and hence can’t collide

float pv = dx*dvx + dy*dvy;

if(pv >= 0) { return false; }

// check if the circles can reach each other between the frames

float vv = dvx*dvx + dvy*dvy;

if((pv + vv) <= 0 && (vv + 2*pv + pp) >= 0) { return false; }

// if we've gotten this far then it’s possible for intersection if the distance between

// the circles is less than the radii sum when it’s at a minimum. Therefore find the time

// when the distance is at a minimum and test this

float tmin = -pv / vv;

return (pp + pv*tmin > 0);

}

As you can see the dynamic test is quite a bit more complex than the static test and this will be reflected in our performance. So is this efficiency loss worth the benefit of having 100% accurate collision? Well this really depends on many game dependant factors and is something you'll have to decide for yourself based on your project. I'll give you a rundown of the various implications though so that you are better equipped to make this decision. First of all we should think about what it means to the player to have a static system and let our engine miss collisions:

* The player is trying to shoot down a barrage of missiles before they hit him and destroy his ship. He has them perfectly lined up in his sights and lets the hot lead fly from his guns. In a dynamic system all the missiles will be destroyed and the player is saved thanks to his quick reactions and accurate aiming. In a static system some missiles might miraculously escape the defensive fire and wipe him out regardless of the fact that the player did everything right.

* The player lunges through a gap in the bullet fire to quickly collect a stream of medals left from his defeated foes. In a dynamic system the player successfully collects all the medals and then continues to focus his energies on the next wave. In a static system, to the player’s dismay he fails to pick up some of the medals in the stream even though he passed directly through them all and now has to make a second pass as the next wave descends upon him.

* The player his navigating his way through a dense bullet cloud but has miscalculated and surrounded himself by an inescapable wall of death. He grimaces waiting for the end knowing he's made a mistake. In a dynamic system he dies as expected whereas in a static system the player finds that he can sometimes escape by diving head first into the wall of death and if he's lucky come out unharmed.

As you can see from the first two examples, a static system

*can* create a frustrating and unfair game play experience for the player which will directly impact on the games playability which obviously we want to avoid. Although the third scenario might seem to work in the players favour at first, the static system has introduced an uncontrollable element of random chance into the core game mechanics. This will weaken the players trust in the game mechanics and implants the belief that doing well in the game is just as much due to random chance as skill. This will also harm the game play experience, especially over the longer term when people want to fight it out over the top spots on the score board. This mistrust is actually what is fundamentally wrong with all the examples but with different consequences in each case. The dynamic system in comparison will always give us the results we expect for all situations which creates a very solid trust in the game mechanics for the player and as a result increases their enjoyment of the game.

Note however that the aim is to create the illusion of accurate collision and if this is done well enough the player will know no different. Therefore although a static system will unavoidably miss some collisions the question you have to try and answer is 'will this happen often enough to be noticeable by the player?'. So how can we try and limit the number of missed collisions in a static system? Before I can answer this first of all we'll need an understanding of what effects our collision accuracy. When two circles pass through each other try and imagine them moving in very small steps and think about how many of those steps they are in contact (this is easier if you consider the relative motion so one circle is stationary relative to the other). The ratio of this number of colliding steps compared to the total number of steps is correlated to the chance a static system will correctly detect this collision. The following diagram shows the red circle moving through the green circle, the elongated red area being the total area swept out by the red circle during its motion and the yellow area is the area during which both circles are in contact. The top black line shows the total time for the motion and the bottom one the amount of time during which the circles are in contact. It’s the ratio of these two lines we're interested in which I'll refer to as the collision ratio.

Therefore whether a static system will be suitable for you or not is dependant on the typical collision ratio for your game's objects, which is in itself dependant on the objects' size, speed, and also the time between frames. As your objects get smaller, their speeds get faster, or your frame rate gets lower, the viability of a static system becomes less and less. Hence if small and fast objects are required for your game and you can’t raise the frame rate sufficiently to compensate then you should consider using a dynamic system. Keep in mind that if you go for a static system you will be constantly bound by these size, speed, and frame rate restrictions in order to keep it viable where as with a dynamic system you won’t have to worry about these issues. Any restrictions we can lift of our design process are always a good thing. There's one more implication of static systems I want to mention which is demonstrated in this diagram:

Here we see the collision ratios of two circles as they pass each other more and more off their centre line. As you can see, as the collision becomes more and more glancing our collision ratio drops and hence our static collision accuracy also drops. In fact with a static system our collision accuracy will always converge to zero as the collision becomes more glancing and hence no matter how big and slow our objects are and how high our frame rate is, total collision accuracy can never be achieved. In effect it’s like our collision shapes have become 'fuzzy' around the edges instead of being sharply defined. A dynamic system on the other hand is not effected by glancing collision and responds exactly the same as the head on collision case. Therefore a dynamic system gives total collision accuracy all the time regardless, well at least for isotropic shapes like circles. Most dynamic collision techniques don’t account for rotation and hence non isotropic shapes suffer from similar fuzzy edges but not quite to the same extent.

The advantages of using a dynamic system are quite extensive and can be very important, and the decision on whether a static system is viable or not isn't very clear cut. Therefore as a general rule I tend to say that if you can spare the cycles to run a dynamic system then do so. It is however horses for courses and if you really need the extra performance to extend your target market to lower spec machines for example, then maybe you will have to make the sacrifices and go with a static system. This isn't the end of the world though and if managed well enough will go un-noticed by the player.