I'm wanting to do a 2d game, using lots of small circles. The player will control one of these circles, while the rest will be static.
How do I go about avoiding tunneling, without dropping my FPS detrimentally?

I considered multiple collision checks per frame, using smaller time steps, but I think I'd prefer a different more accurate method. I've even looked into several physics engines, but most of them try to cover more advanced collision possibilities rather than accurately handling the simple stuff.



Thanks for any help,
Mythics

Mythics:

I'm wanting to do a 2d game, using lots of small circles. The player will control one of these circles, while the rest will be static.
How do I go about avoiding tunneling, without dropping my FPS detrimentally?

I considered multiple collision checks per frame, using smaller time steps, but I think I'd prefer a different more accurate method. I've even looked into several physics engines, but most of them try to cover more advanced collision possibilities rather than accurately handling the simple stuff.



Thanks for any help,
Mythics

If I understand you right, maybe your best bet is to use radius collision checks, but also elimating the quadrants of the screen where a collision is not possible (like a sweep and prune algorithm). If I had 2 sprites with a Vector2 position property and a collision radius (that you define) you can quickly check for collision like so:

Vector2 posDiff = pos - other.pos;

float distance = posDiff.Length();

return (distance < collisionRadius + other.collisionRadius);

The best method would probably be to use XNA’s built in methods. Use either a BoundingSphere (putting 0 for the z axis, effectively making it 2D) or a BoundingBox depending on the orientation of the sprite. For straight lines (such as the sides of the screen) a BoundingBox would probably be best as it can fit it perfectly.

To check for collision, use the Intersects method of the sphere and pass it another sphere (or Bounding Box) you want to test against.

Ex.

There are a couple of methods I am familiar with of going about checking for collisions.

Brute Force: Check everything against everything. Set up two for loops and loop through all objects in your scene, checking each object against every other one. This will effectively tell you if there is a collision (using the BoundingSphere or BoundingBox model I described above) and it is extremely simple to implement, though incredibly slow for a large number of objects.

Screen Partitioning: This one is a good deal more complex, but has the potential to be an order of magnitude faster. Split the screen into smaller cells, and place an object into its closest cell(s).  Next run a brute force on each cell, where the brute force algorithm only checks the contents of its specific cell.

If we're talking 2D here then would your FPS drop that dramtically if you brute forced it?

You mentioned a lot of other circles coming into it, are we to understand they are all listed in some way? If so, a foreach loop would determine that if anything in the list of your smaller circles Intersected your 'Player circle' the appropriate method/function could be called.

If you are going to be dealing with a hell of alot of sprites and you did notice a drop in FPS, then I'd go with LotusXP's and Werewolf696's suggestion of Quadrants, break the screen down and only check for collisions if your Player is in that sector. Having said that, you said the smaller circles would be static, how do you intent the smallers ones to behave to one either? If you intend for them to pass right through each other then the Quadrant method works fine, but if you intent to have them bounce off one another etc, then I don't think the Quadrant method will be much good to you as you'll have to constantly check every circle located in your worldspace.

**How do I go about avoiding tunneling**


Comparing the radius of one circle with the radius of another circle does great for static collision detection, but I'm talking dynamic collision detection.

If the circles are moving very quickly, one circle can 'skip over' another circle from frame to frame without a collision being detected, even though one should have existed.


That's why I mentioned potentially doing multiple collision tests of the same two objects during a single frame. As an example, moving the objects half their actual velocity while checking for collisions after every movement (a total of twice per frame). I just believe that's a tacky way to do it, when there should be a mathematical process that's just more advanced.

You can use the separating axis theorem (which is what the radius test is), and project along the axis of movement.  That axis being: Vector2.Normalize(CircleA.velocity - CircleB.velocity)

If you're not already familiar with SAT, read these:
http://www.metanetsoftware.com/technique/tutorialA.html
http://uk.geocities.com/olivier_rebellion/ (2D swept+overlap polygonal collision and response)

I see…

I believe one solution I have read about (but not personally implemented) is to draw a ray from the object’s previous location to the object’s current location. Test this ray against your spheres, and you should be able to generate a collision, as the ray extends through the object’s entire path during that frame.

That would only take care of the movement of one of the circles.  You could project rays from each circle and see if the rays intersect, but that only covers the centers, and not the full area of the circle.  I think projecting onto the axis of movement and looking for overlap would be much easier.