Adam's Portfolio

Shufflin' Bones: Part I

June 21, 2004

For my wife’s last birthday, I gave her a set of dominoes. There’s nothing she likes more than to wipe the floor with me at a table game. While receiving my regular beating at a round of Mexican Train, I began thinking it would be more fun for me to recreate this game on a digital scale, perhaps to the extent to incorporate multi-player competition.

Then my wife can beat the entire extended family located throughout the country in one fair swoop. She liked the idea, so now we can proceed.

Skipping a lot of initial planning (which will unfold as this set of entries continues) we’ll start with the most basic requirement of any game of dominoes: shuffling.

Shuffling could be thought as a few simple steps. 1. Randomly place the pieces, or “bones” as often called; 2. detect collision on each; 3. move if necessary. Randomly placing the bones would not be so challenging. What would be difficult however is detecting if they were placed on top one another, thus partially hiding the pieces.

I began researching various ways that developers had implemented collision detection in Flash and stumbled upon the Separating Axis Theorem (SAT). About the same time of this writing, Metanet Sofware released this outstanding tutorial explaining how they implemented it for their showcase game, N. The physics engine developed by Metanet Software is quite complex and very suitable for imitating physical phenomena. However it would be overkill for a simplistic use, such as shuffling dominoes.

In short, SAT states that given two convex shapes, if we can find an axis along which the projection of the two shapes does not overlap, then the shapes don’t overlap. In 2D, each of these potential separating axes is perpendicular to one of the faces (edges) of each shape.

Since dominoes are rectangular in shape, there are four axes that must be tested. If we find an axis along which the objects don’t overlap, we don’t have to continue testing the rest of the axes. Let’s consider an example:

figure 1

In figure 1, we see that in testing the first two axes of the 3-6 bone we discover overlaps; no separating axis exists. Therefore we must continue testing the axes of the second shape.

figure 2

Now we see that the y-axis of the 2-5 bone reveals a separating axis, hence no collision.

You may have noticed at this point that because the second bone was at a different rotation, we had to re-orient our testing axes to that of the local axes of the 2-5 bone. This is referred to as Oriented Bounding Box (OBB) testing. Had both bones been oriented to that of the world’s coordinate system (or Stage’s for that matter) we would only have had to limit our tests to two since all edges are inline with a respective world axis. This is known as Axis-Aligned Bounding Box (AABB) testing.

Let’s now move onto some code to show you how we’ll implement collision detection with this model.

function detectCollision(bone1:MovieClip, bone2:MovieClip):Boolean {
 return (testAxes(bone1, bone2))?(testAxes(bone2, bone1)):false;
}
function testAxes(control:MovieClip, variable:MovieClip):Boolean {
 var cCoords = control.getBounds();
 var vCoords = variable.getBounds(control);
 var cWidth = Math.abs(cCoords.xMax);
 var cHeight = Math.abs(cCoords.yMax);
 var cCenterX = cWidth/2;
 var cCenterY = cHeight/2;
 var vWidth = vCoords.xMax-vCoords.xMin;
 var vHeight = vCoords.yMax-vCoords.yMin;
 var vCenterX = vCoords.xMin+(vWidth/2);
 var vCenterY = vCoords.yMin+(vHeight/2);
 // x-axis
 if (((vWidth/2)+(cWidth/2))<(Math.abs(vCenterX-cCenterX))) {
  return false;
 }
 // y-axis
 if (((vHeight/2)+(cHeight/2))<(Math.abs(vCenterY-cCenterY))) {
  return false;
 }
 return true;
}

The detectCollision() method is the parent method and is used to compare two bones for collision. It in turn will call the testAxes() method to first compare one bone to another using the former’s coordinate system. If a separating axis is not found, the function is called again, reversing the bones. This being the final test, the returned value is the result for collsion detection.

The block within testAxes() is where things become a little hairy. The goal here is to return true the instant a separating axis is found. As mentioned earlier, we begin by comparing the first bone (control) to the second (variable) using its coordinate system.

A great majority of our work is handled by Flash’s getBounds() method. This method returns an object with four properties that are the minimum and maximum x and y coordinate values of a movieclip instance using another movieclip’s target coordinate space. Figure 3 will help explain what we will receive from the first two statements in testAxes() when the 3-6 bone is the control and the 2-5 bone is the variable. Note: When a target coordinate space is not specified when using getBounds(), the calling movieclip will use it’s own.

figure 3

Using the values we just now received we’ll generate a few more needed values, namely the width, height, and center points of each bone. With these values we can then search for a separating axis along the x and y axes. We accomplish this with a little geometry: Given a single axis, if the sum of half the projected widths of each shape is greater than the projected distance between their centers, then a separating axis exists.

I don’t know if that can be classified as a mathematical theorem, but it works in this case.

So in our code, we first test the x-aixs as the projected axis. If no separating axis is found, then the y-axis. If our results still return false, we then repeat the procedure reversing the variable and control roles (Figure 4 shows how the new resulting values are obtained). If still no separating axis is found after each test, then the bones are colliding.

figure 4

Media 1 is a simple example of the script in action. Click the rotate button to randomly turn the bones and drag them over one another to see the results.

Media 1

Now that we can detect if bones are colliding, we’ll need to develop a reaction to a positive detection. Stay tuned for Part 2 where we’ll discuss how all the bones for a Double 12 set will be generated and properly shuffled using what we’ve covered thus far.

Posted in Flash/ActionScript, Games

Comments

Jot your thoughts