# Fast, accurate 2d collision

I'm working on a 2d topdown shooter, and now need to go beyond my basic rectangle bounding box collision system.

I have large levels with many different sprites, all of which are different shapes and sizes. The textures for the sprites are all square png files with transparent backgrounds, so I also need a way to only have a collision when the player walks into the coloured part of the texture, and not the transparent background.

I plan to handle collision as follows:

1. Check if any sprites are in range of the player
2. Do a rect bounding box collision test
3. Do an accurate collision (Where I need help)

I don't mind advanced techniques, as I want to get this right with all my requirements in mind, but I'm not sure how to approach this. What techniques or even libraries to try. I know that I will probably need to create and store some kind of shape that accurately represents each sprite minus the transparent background.

I've read that per pixel is slow, so given my large levels and number of objects I don't think that would be suitable. I've also looked at Box2d, but haven't been able to find much documentation, or any examples of how to get it up and running with SFML.

-

1. Step one, create a grid and update it for every object that moves.
2. Only check for collisions between objects in the same squares.
3. Check if the bounding box of the objects intersects (their containing rectangle).
4. Check for pixel perfect collision using a low res version of the outline(see Game Physics).
5. Do a normal check of the outline tracing as described in Game Physics (Q 2)

Step 1:

Create a grid 2d array. Every object knows which squares it occupies by it's x,y position and it's width and height. If an object is moved away, it clears itself from the old square and updates the new square that it's occupying.

This only takes O(n) in total for n objects. For any specific object O(1).

Step 2:

Run all the checks for collisions between objects in the same squares. No need to run tests for collisions between objects in different squares. An object can occupy up to four squares if it is of average size. This means very few checks.

Step 3:

Check for intersection between the objects rectangles. If no intersection exists, stop.

Step 4:

Check for pixel perfect collisions between the outlines of the objects only inside the area of intersection. It should be fast enough. If not, create a low res 2d-boolean array and check it first, if you find collisions there, you would only need to check a small segment in the high res 2d-array saving you some precious time.

Please read this for concept on how to split your game world into a grid of squares:

Making an efficient collision detection system

Please read this for intuition on how to detect pixel perfect collisions.

Game physics / 2D Collision detection AS3

You can improve performance significantly:

1. Saving a low res (1 / 16) version of the outline to check against first.

2. Only checking in the area where the two rects intersect.

3. by dividing the outline roughly into segments, and only checking for collisions between segments first.

Please feel welcome to comment and I will elaborate.

-
As Arthur said, replace your steps 1. and 2. with a grid, and as for accurate collision-detection, You could use a low resolution version of your images. – Markus von Broady Oct 14 '12 at 18:37
And if you really need, you also could use a similar technique to my answer here: gamedev.stackexchange.com/questions/38481/… – Markus von Broady Oct 14 '12 at 18:47
Markus points out a good idea. You should use a 2d-boolean array or a 1d-array that is treated as 2d and you could save 1/2 1/4 1/8 low- res versions of that array to speed things up. This will probably not be necessary as computation on 2d-boolean arrays is very fast. It is still a useful tool to have. – zehelvion Oct 14 '12 at 18:52
If the player is entirely contained inside one square on the grid, you can check only against objects in that square. The player may be in four adjacent squares at once. Is that what you mean? If you mean the intersection between rectangles, yes, you only need to check for collisions if they intersect. – zehelvion Oct 14 '12 at 20:46
I hope the update helps clear things up. Once you have some code written you can post it in code review and link us for comments. codereview.stackexchange.com – zehelvion Oct 14 '12 at 21:26