Collision Detection in 2D Games

03 Apr 2011. comments

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

Sprite image rotation, bounds intersection

The first method assumes that you’re rendering your image verbatim and the image is actually what you are manipulating. This is typically how I do things in a 2D Java Swing game. The bounding box of your sprite is effectively the bounding box of your image.

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

Sprite translation, per-pixel comparison of of non-alpha-transparent pixels

The second method utilizes matrix transforms (location, rotation, scaling) to figure out where and how to render pixels. 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 math to determine if any non-alpha-transparent pixels are true for both sets of pixels.

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;  
}

Sprite translation, maintaining a bounding box, per-pixel comparison of of non-alpha-transparent pixels

The third method is essentially the previous method except with the optimization of a maintained bounding box 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 much more efficient and an order 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  
  ...  
}

comments

Tagged: algorithms game development graphics xna

2017 Ben Lakey

The words here do not reflect those of my employer.