# Collision Detection in 2D Games

Implementing per-pixel collision detection in a 2D game can be accomplished using a variety of methods:

1. Sprite image rotation, bounds intersection
2. Sprite translation, per-pixel comparison of of non-alpha-transparent pixels
3. Sprite translation, maintaining a bounding box, per-pixel comparison of of non-alpha-transparent pixels

The first method assumes that you are rendering your image verbatim, and the image is actually what you are manipulating. This is typically the way you’d be doing things in a Java Swing game. The bounding box of your sprite is effectively the bounding box of your image.

Here’s what that might look like:

```    if (sprite.boundingBox.intersects(otherSprite.boundingBox)) {
//collision!
}```

The second method utilizes matrix transforms (location, rotation, scaling) to figure out where and how to render pixels. This transformation is the most common scenario in C# XNA game development. Since you are essentially plotting pixels right to the screen, no bounding box exists. Each time your game loop runs, it’s necessary to ask the sprite where its pixels currently are and compare them with collidable pixels in the scene. This is VERY expensive, since you have to ask all your sprites on the screen for their current pixel information, ask your player sprite for its pixel information, and then do combinatorial math to determine if any non-alpha-transparent pixels are true for both sets of pixels.

Here’s what that might look like:

```public bool CollidesWith(Sprite entitySprite)
{
Matrix myMatrix = this.Sprite.GetMatrixTransform();
Matrix theirMatrix = entitySprite.GetMatrixTransform();

Color[,] myColorArray = this.Sprite.ColorArray;
Color[,] theirColorArray = entitySprite.ColorArray;

Matrix myMatrixToTheirs = myMatrix * Matrix.Invert(theirMatrix);

int myWidth = myColorArray.GetLength(0);
int myHeight = myColorArray.GetLength(1);
int theirWidth = theirColorArray.GetLength(0);
int theirHeight = theirColorArray.GetLength(1);

for (int x1 = 0; x1 < myWidth; x1++)
{
for (int y1 = 0; y1 < myHeight; y1++)
{
Vector2 pos1 = new Vector2(x1, y1);
Vector2 pos2 = Vector2.Transform(pos1, myMatrixToTheirs);

int x2 = (int)pos2.X;
int y2 = (int)pos2.Y;
if ((x2 >= 0) && (x2 < theirWidth) &&
(y2 >= 0) && (y2 < theirHeight) &&
(myColorArray[x1, y1].A > 0) &&
(theirColorArray[x2, y2].A > 0))
{
return true;
}
}
}

return false;
}```

The third method is essentially the previous method, with the optimization of a bounding box being maintained around your drawn pixels. Checking for a collision has an early-exit optimization, in that you first check which sprites bounding boxes intersect with eachother, and then only do the per-pixel collision detection on those sprites. This is a much better way to do things, and many orders of magnitude faster.

Here’s what that might look like:

```public bool CollidesWith(Sprite entitySprite)
{
if (!entitySprite.BoundingBox.Intersects(this.Sprite.BoundingBox))
{
return false;
}

...
//rest of above method here
...
}```

# Pixel, Texel, Voxel

I learned a few new terms today for graphics programming. Pixel is something everyone knows of course but Texel and Voxel are less known.

• A pixel is the single smallest point addressable on your screen.
• A texel is the smallest unit of whatever it is that you are drawing to the screen. It’s pixels are inferred based upon many factors (for example, scaling).
• A voxel is the smallest unit of 3D space that you are drawing. All the voxels being drawn in a 3D object are inferred based upon relation to other voxels (you specify points to define a volume).