11.2 Collision-handling

11.2 Collision-handling

Here's an overview of how the Pop Framework handles collisions.

1. Make a utility class for holding pairs of critters, and let this class specify which critter has the priority to control the behavior of a collision.

2. Maintain a collection of all pairs of critters that might meaningfully collide.

3. During each game step, iterate through this collection of candidate pairs.

4. For each candidate pair, collide the critters by letting the higher priority critter call its collide method on the other.

5. A critter's collide(pcritter) method checks if it's touching pcritter , and if so, changes the two critters' velocities and positions in a physically reasonable fashion. Child classes may override collide to alter the behavior.

We said a bit about (5) in the last section. In this section we'll figure out how to take care of steps (1) to (4).

The N -squared problem

If we have N critters, it would seem like there are N ² pairs of critters we might consider. But we can easily cut this by a little more than half, down to N * ( N “ 1) / 2. This is because, first of all, we don't have to worry about a critter colliding with itself, and, secondly, if we write our collision code symmetrically , then once A collides with B we don't need to turn around and carry out code for having B collide with A .

That is, if we think of listing the critter pairs in N rows of N columns each, we need only consider those (row, column) pairs for which the row number is strictly less than the column number. This way we cut down to a bit less than half of N ² . This is shown in Figure 11.1.

Figure 11.1. Halving the possible collision pairs

Of course half of N ² is still too big for many simulations “ remember that in the analysis of algorithms, any multiple of N ² is viewed as 'order of N ² ,' which is not considered to be a scalable kind of algorithm.

If we want to be able to run somewhat more complicated kinds of games , we need to find a way to prune down the collisions that we consider. Suppose, for instance, that you are running a PacMan-style game in which you have five active critters moving about in a maze made up of 45 walls. The possible collision pairs group like this.

¢ Active critter to active critter	(5 * 4) / 2 = 10 pairs
¢ Active critter to wall	(5 * 45) = 225 pairs
¢ Wall to wall	(45 * 44) / 2 = 990 pairs

If you ignore the wall “wall pairs, you have a quite feasible 235 possible collision pairs to consider per update, otherwise you have a taxing 1225 pairs. Although 235 sounds like a lot, the Pop Framework does fine up to about 500 pairs, but if you get into the thousands of pairs, the performance suffers noticeably.

Our solution is to maintain a collection that holds only the pairs of critters whose collisions we actually want to check. To further speed things up, we'll structure these pairs so that they automatically tell us which critter is to control the collision.

A collision-handling architecture

In this section we'll talk about the two new classes the Pop Framework uses to limit our collision-checking to the pairs that matter to us. The new classes are cColliderPair and cCollider . Figure 11.2 is a UML class diagram of their relationship to cGame and cCritter .

Figure 11.2. A collision-handling architecture

And here's how these classes realize the first three steps of the collision-handling process we outlined above.

1. The cColliderPair class has two cCritter * members called _ pcrittercaller and _ pcritterarg . We have a cColliderPair::collideThePair method that calls _pcrittercaller->collide(_pcritterarg).

2. The cCollider class holds a collection of cColliderPair objects. The cGame has a cCollider _pcollider object. Whenever you add a cCritter * pcritternew to the game, the cCollider::smartAdd method looks at all possible pairs that include the new pcritter and an existing critter in the game, creates appropriately ordered cColliderPair object for those pairs that matter, and adds the new cColliderPair objects to the _pcollider collection. Whenever a cCritter * pcritterdying is deleted, its destructor calls _pcollider-> removeReferencesTo(pcritterdying) to remove all pairs that mention pcritterdying .

3. In each update step, the cGame::collideStep method calls _pcollider- >iterateCollide() . The cCollider::iterateCollide() method calls the collideThePair for each cColliderPair .

Note that we didn't explain yet how smartAdd decides which pairs matter and how it decides, for these pairs, which critter should be the caller and which should be the argument for an eventual collide call. This is the topic of the following subsection.

Collision priority

As already discussed, the individual cCritter child classes have their own virtual collide(cCritter *pcritter) methods to determine whether the pair is touching, and what to do if they are touching. Given a pair (pA, pB) , should I call pA->collide(pB) , or should I call pB->collide(pA) ? Or should I not even try and collide the critters?

Our solution is to give the cCritter class a Real _collidepriority field and to give the cCritter class a collidesWith(cCritter *pcritterother) method that uses the _collidepriority information of the two critters involved. By 'priority' we mean that if pB has higher priority than pA , then, when we consider the pair (pA, pB) , we will call pB->collide(pA) instead of the other way around.

The default _collidepriority values are real numbers that have default values that are set for the various kinds of critters in the following (descending) order.

• Walls

• Bullets

• Player

• Other critters

The reasons for our priorities are roughly this. The cCritterWall has a special collide method which correctly bounces things off the sides and corners of a rectangular wall. Ordinarily we would not expect a wall to be damaged by a bullet. As was mentioned above, the cCritterBullet has a special collide which checks if an object it touches is in the category of a target for the bullet. If it is a target object, the bullet damages it and then dies. Otherwise the bullet carries out a normal cCritter::collide . And the normal cCritter::collide is designed to correctly simulate the physics of colliding disks. The cCritterArmedPlayer has a special collide method that can call damage if a player is sensitive to collisions.

We also need to account for the fact that some pairs of critters aren't meant to collide at all. To handle all this, we give the cCritter class a virtual int cCritter::collidesWith(cCritter *pcritterother) method that can return the following values.

• cCollider::DONTCOLLIDE = 2;

• cCollider::COLLIDEASCALLER = 1;

• cCollider::COLLIDEASARG = -1;

• cCollider::COLLIDEEITHERWAY = 0;

The basic cCritter::collidesWith method compares the _collidepriority values and returns an appropriate code number. The cCritterWall::collidesWith(cCritter *pcritterother) is overridden to return DONTCOLLIDE if pcritterother happens to be a cCritterWall .

Finally, the cCollider::smartAdd method is implemented as follows .

 void cCollider::smartAdd(cCritter *pcritter, cCritter* pcritterother)  {      int collideswith = pcritter->collidesWith(pcritterother);      int othercollideswith = pcritterother->collidesWith(pcritter);      if (collideswith == cCollider::DONTCOLLIDE  othercollideswith          == cCollider::DONTCOLLIDE)      return; /* Don't collide if either          one is unwilling, even if the other was willing. */      if (collideswith == cCollider::COLLIDEASCALLER  collideswith          == cCollider::COLLIDEEITHERWAY )          AddTail(new cColliderPair(pcritter, pcritterother));      else //(collideswith == cCollider::COLLIDEASARG)          AddTail(new cColliderPair(pcritterother, pcritter));      //ASSERT(collideswith == -othercollideswith);          /* We chose the collision type codes to make this ASSERT          likely at this point, but it might not always be true. Only          comment it in for testing. Do note that we bail before we          hit it if either type is DONTCOLLIDE. */  } 

Note that smartAdd will only add the necessary pairs, and that it will add them ordered in the right way, with the caller first and the argument second.

Array or list? An N -cubed issue

It remains to discuss how we iterate though the collection of pairs in a cCollider collection. This depends on whether we implement the cCollider collection as an array or as a linked list. Which is to be preferred? As you will already have noticed if you looked enough to see the ' AddTail ' in the block of code just above, we're going to use a list.

For most programmers, the natural inclination is to use arrays, simply because lists have a reputation for being hard to use. Some of us have acquired a lingering fear of lists and hash tables from a formative bad experience in a data structures course! But, thanks to templates and collection classes, the more sophisticated data structures are easy and safe to use, and we can afford to pick the correct data structure for any given situation.

As it turns out, you want to use a list and not an array for the collection that holds your set of possible collision pairs. Here's why. Say you have N critters “ for purposes of discussion let's say N is 20 “ and let's suppose that each critter wants to collide with all of the others, making roughly 200 collision pairs ( N ² / 2). Now say you want to delete one of the critters. This means deleting roughly N member pairs from an array of N ² /2 members; that is, deleting 20 members from a 200 member array.

Now, when you delete something from the beginning of an array, you typically have to move down all of the higher-indexed elements. In other words, removing the first member of a 200 member array requires about 200 steps and removing the first member of an array of size N ² /2 takes about N ² /2 steps. Removing 20 members from a 200 member array could take roughly 4000 steps, and removing N members from an array of size N ² /2 takes on the order of N ³ /2 steps.

You realize, of course, that an order- N ³ /2 algorithm is very bad news! For 40 critters, you'd have an order of 32,000 steps “ all this just to delete one single critter. Why, again, does it make so much work? Because you have to delete every pair the critter was involved in, and if the pairs are in an array, then every time you delete a pair from the array you have to move all of the higher-indexed array members.

With a list you don't get into this problem, because deleting a member from a list is an operation of a small, constant expense, no matter where in the list the member occurs. It's just a matter of fixing up a couple of ' next ' and 'previous' pointers.

So we implement the cCollider as a linked list; specifically we let it inherit from the MFC class CPtrList “ well, actually, we use a type-safe template variant of CPtrList called CTypedPtrList<CObList, cColliderPair*> . If you've ever implemented a linked list, you'll recall that you have to be a little careful about not corrupting the next and previous pointers “ by using the built-in MFC List template we avoid having to worry about getting these details right. This is a good example of why, in object-oriented software engineering, we like to use classes that we don't have to write ourselves .

One last thought. We iterate through the entire cCollider list with every update, and iterating through an array is slightly faster than iterating through a list. Would it be better, after all, to have used an array? Well, no. The thing is, you want your game to run in a uniform fashion. You don't want it to race along and then suddenly slow down every time you shoot something. The (actually all but undetectable) slowdown of doing a single iteration sequence per update as a list instead of as an array is a fair price to pay for not having the game lag when a critter's destroyed .