Making Collision Detection more efficient (C# XNA)

Question

I'm a fairly inexperienced programmer currently learning C# and trying to learn Game Design in general.

I'm using Microsoft's XNA framework to build a Galaga-esque Scrolling Shooter game. After a few rough trials in which I struggled with shoddy OOP structure, making some bad design choices, I've finally come up with a respectable start of an engine.

Presently I'm having problems with making collision detection not lag the game out. My current engine keeps all active game objects in a List object and cycles through each, checking if it collides with each other object. Needless to say, it could be a lot better.

Here's my collision checking, done in the ObjectHandler class.

public override void Update(GameTime gameTime)
    {
    ...
        //Handle collisions
        foreach (GameObject obj in Objects)
        {
            ICollideable e = obj as ICollideable;
            //Check if the object implements ICollideable
            if (e != null)
            {
                //Check collision with each other object
                foreach (GameObject obj2 in Objects)
                {
                    //Check if the second object implements ICollideable
                    ICollideable e2 = obj2 as ICollideable;
                    //check if they are in the same sector
                    if (e2 != null && SameSector(e.Sector,e2.Sector))
                    {
                        //Check if the collision masks interesect
                        //if so call each object's collision event
                        if (e.Mask.Intersects(e2.Mask))
                        {
                            e.CollisionEvent(e2);
                            e2.CollisionEvent(e);
                        }
                    }
                }
            }
        }
      ...
    }

Here's the SameSector function.

private bool SameSector(Point p1, Point p2)
    {
        if (Math.Abs(p1.X-p2.X)<=1 && Math.Abs(p1.Y-p2.Y)<=1)
            return true;
        else 
            return false;
    }

"Mask" here is a Rectangle object, which is part of the XNA framework. As you can see I've implemented a sort of spacial partitioning system, where each object sets which 60x60 square it's in. However, I'm not really sure that I've done anything useful as it takes just as much time to check if two objects are in the same sector (or adjacent sectors) as it does to check if they're colliding.

I've seen a question similar to this posted already, but it didn't quite satisfy my question. From it I did gather that a time management system is useful. I'll try to implement that eventually but as I'm still fairly new to programming, I'd like to optimize the collision checking itself before delving into more advanced design.

So, is there I way I can effectively optimize my current collision checking, or is what I have way off to begin with?

Answer 1

Spatial partitioning will only help you if you've implemented it in a way that doesn't require you to compare every object against every object in some way.

In your spatial partitioning grid, you want each grid cell to have some kind of membership list of objects within it, as well as for each object to be aware of what cell it's in. Then you only need to do comparisons between an object and all other objects within that cell and within immediately adjacent cells (because an object may overlap bounds). The downside is you now need to keep all this state updated.

I highly recommend the book Real-Time Collision Detection which covers several different broad-phase partitioning schemes in depth and their relative strengths and weaknesses, in addition to other CD topics. In addition to uniform grids, there are hierarchical grids, quadtrees, sweep and prune, and other techniques that may be more appropriate for you (sweep and prune might be particularly beneficial).