C# / XNA - Bounding Circle Collision (Micro) Optimization?

Question

I've been working on a simple space shooter, and have gotten to the point in the project where my terribly written code is actually slowing things down. After running EQATEC, I can see that the majority of the problem is in the icky check everything on everything collision detection. I was considering putting in a QuadTree, but the majority of the collisions are on asteroids, which do move around a lot (would require a lot of updating). My next alternative was micro-optimizing the collision check itself. Here it is:

    public bool IsCircleColliding(GameObject obj) //simple bounding circle collision detection check
    {
        float distance = Vector2.Distance(this.WorldCenter, obj.WorldCenter);
        int totalradii = CollisionRadius + obj.CollisionRadius;

        if (distance < totalradii)
            return true;
        return false;
    }

I've heard that Vector2.Distance involves a costly Sqrt, so is there any way to avoid that? Or is there a way to approximate the distance using some fancy calculation? Anything for more speed, essentially.

Also, slightly unrelated to the actual question, is there a good method (other than QuadTrees) for spatial partitioning of fast-moving objects?

redtuna redtuna · Accepted Answer · 2013-05-13T22:44:46

Compute the square of the distance instead of the actual distance, and compare that to the square of the collision threshold. That should be a bit faster. If most asteroids are the same size, you can reuse the same value for the collision threshold without recomputing it.

Another useful trick is to first do a simple check based on bounding boxes, and compute the distance only if the bounding boxes intersect. If they don't, then you know (for cheap) that the two objects aren't colliding.

C# / XNA - Bounding Circle Collision (Micro) Optimization?

1 Answers