c++ - 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.

Answer

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.