XNA Part 9 - Pixel Based Collisions

Let me start by saying that the XNA Creators Club tutorials on collisions are really good and a lot of what I have learned so far has come from them. Check them out!

So on to pixel based collisions. You can of course collide on any data based in the pixels, but in our case we will look at the "Alpha" value. For those of you who are not familiar with the channels in a color, we represent color values with different components. There are several different ways to represent color, but in our case we will be using ARGB. The 'RGB' part should be familiar, this is the Red Green and Blue components of our color. The 'A' part stands for the Alpha, which is simply how opaque your color is. Where 0 is completely transparent and 255 is completely opaque. Notice that the values are between 0 and 255. This is because the 4 values are represented by the 'byte' data type which is an 8 bit integer type. 8 bits can hold 256 values and therefore in this case represent the numbers 0-255.

So the idea behind our pixel based collision is this: we look at the bounds of the 2 objects that we want to test and if they overlap, we examine the overlapping pixels in each image. If a pixel in both images is not transparent and overlapping, a collision has happened.

Now of course it will be up to you if you test for both pixels being 0 alpha for non-collisions or if you allow partial transparency to equal non-collision (i.e. both pixels have to be 255 alpha to collide rather than both being 0 to not collide).

Lets look at how we do this in our code.

We will store our pixel data in an array of Color objects for ease of use. So I'm going to add a Color[] to my GameObject.

public Color[] pixelData;

and in my constructor I am going to initialize it and load it up with my sprite's data.

pixelData = new Color[sprite.Width * sprite.Height]; 
sprite.GetData<color>(pixelData);

So we create the size of our pixelData array to be the sprite's height times width and then call the sprite's GetData method using the color type template and passing it the pixelData array to receive the data. Now we should have a lovely array filled will the pixel values of our sprite.

Now that we have pixel data to compare, we will rewrite our Intersects function to take it into account. We will take out our reference to the rectangle intersects() method. and start with our empty method.

public bool Intersects(GameObject b) { }

First we need to determine what the bounds of interection are. So we compare the tops and sides of the 2 rectangles. Remember that Y goes the opposite direction then we might think, so the top of a rectangle is a smaller number than the bottom. So we will compare the Top of a and b and see which one has a bigger value, meaning which one is LOWER on the screen. So in this case b's Top is a bigger number than a's Top since b's Top is lower on the screen than a's (confusing isn't it). So to find the lowest object Top on the screen we compare and choose the maximum Top between the 2 objects. You should also see that in this image b.Top is the top of our collision area.

int Top = Math.Max(Bounds.Top, b.Bounds.Top);

We also want the highest bottom on the screen so we look for the minimum value of a and b's Bottom.

int Bottom =  
        Math.Min(Bounds.Bottom,
                 b.Bounds.Bottom);

Left and Right are easier since it moves in a more intuitive way. So we want the biggest Left and the smallest Right.

int Left = Math.Max(Bounds.Left,b.Bounds.Left);
int Right = Math.Min(Bounds.Right, b.Bounds.Right);

Now we can loop though using these values and extract the pixelData from the 2 GameObjects and compare them.

for (int y = Top; y < Bottom; y++)
            {
                for (int x = Left; x < Right; x++)
                {

You will see the the for loops will not execute if top > bottom. That way, if the lowest top on the screen is below the highest bottom (ie the object are completely above and below each other) the loops will not happen. Then if they are vertically able to collide but horizontally not able to collide we don't execute the body of the inner loop. But if both work we get to the meat.

To discover where in the array of pixels we need to calculate where a particular pixel is. The pixels were stored by each row. So in this image we have our GameObjects textures as 8x8 grids. pixelData[0] through pixelData[7] would contain the first row. [8] though [15] would contain the next. So conviently we can do a little math to get us to our pixel. We take the row we want to access (starting at 0) and multiply by the width of the row (in this case 8) to give us the starting pixel in a row. Then we simply add the number of the pixel in the row we want to access (starting at 0) to that number and we have the index of the pixel we are looking for. Therefore our pixel index within a sprite becomes

pixelData [ rowNumber*rowWidth+colNumber ]

Now that we know how to access a given pixel how to we use the data we have to find the overlapping pixels and thier data. As we can see in this image, our x value would be starting at pixel 7 of the screen but only index 5 of object a and index 0 of object b. Since we can get the left value of object a (which is 2), we can subtract that from the value of x (7) and get the horizontal pixel index we need in object a (5). That would become our "colNumber" in our index formula. We determine our rowNumber in the same way with the y value. We get the distance of the y value from the "Top" of a by subtracting a's Top from the value of y. This gives us our rowNumber. We would then take the width of a as the rowWidth; so our formula for finding the pixel in a would be

Color colA = pixelData[(y - Bounds.Top) *
                  Bounds.Width + (x - Bounds.Left)]; 
Color colB = b.pixelData[(y - b.Bounds.Top) * 
                  b.Bounds.Width + (x - b.Bounds.Left)];

Then we compare the colors and decide if they are a collision.

if (colA.A != 0 && colB.A != 0) 
{
    return true;
}

Since it only takes one pixel for a collision, the first time we hit, we finish. After the loops you will want to add a return false if it makes it all the way through without a collision.

Now if you run this again with some objects that have transparency, you should find that they will only intersect when their pixels line up rather than their bounding boxes.

One caveat, this only applies to non-rotated, non-scaled textures. When we come back to collisions again, we will talk about how to handle those situations. But that will not be for a little while.

Thanks big time to the XNA creators club tutorial on Pixel based collisions, it was my primary learning source while preparing to write this post.