# Collision Detection for 2D

I am working on a simple game, where I need to do a collision detection of two Texture2D. The code I have written is:

bool perPixelCollission = false;
Texture2D texture1 = sprite1.Texture;
Texture2D texture2 = sprite1.Texture;
Vector2 position1 = new Vector2(sprite1.CurrentScope.X, sprite1.CurrentScope.Y);
Vector2 position2 = new Vector2(sprite2.CurrentScope.X, sprite2.CurrentScope.Y);

uint[] bitsA = new uint[texture1.Width * texture1.Height];
uint[] bitsB = new uint[texture2.Width * texture2.Height];

Rectangle texture1Rectangle = new Rectangle(Convert.ToInt32(position1.X), Convert.ToInt32(position1.Y), texture1.Width, texture1.Height);
Rectangle texture2Rectangle = new Rectangle(Convert.ToInt32(position2.X), Convert.ToInt32(position2.Y), texture2.Width, texture2.Height);

texture1.GetData<uint>(bitsA);
texture2.GetData<uint>(bitsB);

int x1 = Math.Max(texture1Rectangle.X, texture2Rectangle.X);
int x2 = Math.Min(texture1Rectangle.X + texture1Rectangle.Width, texture2Rectangle.X + texture2Rectangle.Width);

int y1 = Math.Max(texture1Rectangle.Y, texture2Rectangle.Y);
int y2 = Math.Min(texture1Rectangle.Y + texture1Rectangle.Height, texture2Rectangle.Y + texture2Rectangle.Height);

for (int y = y1; y < y2; ++y)
{
for (int x = x1; x < x2; ++x)
{
if (((bitsA[(x - texture1Rectangle.X) + (y - texture1Rectangle.Y) * texture1Rectangle.Width] & 0xFF000000) >> 24) > 20 &&
((bitsB[(x - texture2Rectangle.X) + (y - texture2Rectangle.Y) * texture2Rectangle.Width] & 0xFF000000) >> 24) > 20)
{
perPixelCollission = true;
break;
}
}
// Reduce amount of looping by breaking out of this.
if (perPixelCollission)
{
break;
}
}

return perPixelCollission;


But this code is really making the game slow. Where can I get some very good collision detection tutorial and code? What is wrong in this code?

## migrated from gaming.stackexchange.comJan 1 '11 at 12:35

This question came from our site for passionate videogamers on all platforms.

• Just a suggestion, but you might consider using the farseer physics engine. I'm assuming your just doing 2D and your using XNA. I've had pretty good experiences with it and it's fast enough usually. – Michael Coleman Jan 1 '11 at 22:12

One problem with this code that can cause a slow down is that you are testing every pixel between the two sprites... So it the sprites are not colliding and are, say, at opposite corners of the screen, you are darn near brute force checking each and every pixel on the screen.

Consider a simple rectangle/rectangle test instead or a separating axis test.... Much faster.

Check out page 3 of this article. It works for 2d or 3d: http://www.gamasutra.com/view/feature/3383/simple_intersection_tests_for_games.php

Split your collision test up in several steps:

1. quick check if two sprites might collides: Rectangle.Intersect(textureRectangle1, textureRectangle2)

2. your elaborate pixel collision check

Only perform step 2, if step 1 is true.

You also can return the collision result directly in the inner for loop, if it's true and always return false, if both loops finish without finding a collision.

This should speed up things considerably. But it will be slow if you have a lot of object to check (>100). Since n*(n-1) checks are done each frame.

Generate a quadtree for each image. The lowest cell size of the quadtree lets you determine the tradeoff between speed of collision test and precision. If the last size is 1, you get pixel-perfect collision detection, but you can often get away with 2x2 or even 5x5 cells, depending on the application.

Quadtree vs quadtree checks are probably log(n), and since the first check compares the top-level rectangles, it's in fact the same as the early rejection test you'd do if you used only pixel by pixel checks.

This approach is extremely flexible - with some work you can make it work for rotated and scaled textures as well (implement a axis-aligned-rect-to-rotated-and-scaled-rect test, and then transform each rectangle of both textures so that one is axis aligned)