C# XNA: Optimizing Collision Detection?

Question

I'm working on a simple demo for collision detection, which contains only a bunch of objects bouncing around in the window. (The goal is to see how many objects the game can handle at once without dropping frames.)

There is gravity, so the objects are either moving or else colliding with a wall.

The naive solution was O(n^2):

foreach Collidable c1:
      foreach Collidable c2:
             checkCollision(c1, c2);

This is pretty bad. So I set up CollisionCell objects, which maintain information about a portion of the screen. The idea is that each Collidable only needs to check for the other objects in its cell. With 60 px by 60 px cells, this yields almost a 10x improvement, but I'd like to push it further.

A profiler has revealed that the the code spends 50% of its time in the function each cell uses to get its contents. Here it is:

    // all the objects in this cell
    public ICollection<GameObject> Containing
    {
        get
        {
            ICollection<GameObject> containing = new HashSet<GameObject>();

            foreach (GameObject obj in engine.GameObjects) {
                // 20% of processor time spent in this conditional
                if (obj.Position.X >= bounds.X &&
                    obj.Position.X < bounds.X + bounds.Width &&
                    obj.Position.Y >= bounds.Y &&
                    obj.Position.Y < bounds.Y + bounds.Height) {

                    containing.Add(obj);
                }
            }

            return containing;
        }
    }

Of that 20% of the program's time is spent in that conditional.

Here is where the above function gets called:

    // Get a list of lists of cell contents
        List<List<GameObject>> cellContentsSet = cellManager.getCellContents();

        // foreach item, only check items in the same cell
        foreach (List<GameObject> cellMembers in cellContentsSet) {
            foreach (GameObject item in cellMembers) {
                 // process collisions
            }
        }


//...

    // Gets a list of list of cell contents (each sub list = 1 cell)
    internal List<List<GameObject>> getCellContents() {
        List<List<GameObject>> result = new List<List<GameObject>>();
        foreach (CollisionCell cell in cellSet) {
            result.Add(new List<GameObject>(cell.Containing.ToArray()));
        }
        return result;
    }

Right now, I have to iterate over every cell - even empty ones. Perhaps this could be improved on somehow, but I'm not sure how to verify that a cell is empty without looking at it somehow. (Maybe I could implement something like sleeping objects, in some physics engines, where if an object will be still for a while it goes to sleep and is not included in calculations for every frame.)

What can I do to optimize this? (Also, I'm new to C# - are there any other glaring stylistic errors?)

When the game starts lagging out, the objects tend to be packed fairly tightly, so there's not that much motion going on. Perhaps I can take advantage of this somehow, writing a function to see if, given an object's current velocity, it can possibly leave its current cell before the next call to Update()

UPDATE 1 I decided to maintain a list of the objects that were found to be in the cell at last update, and check those first to see if they were still in the cell. Also, I maintained an area of the CollisionCell variable, when when the cell was filled I could stop looking. Here is my implementation of that, and it made the whole demo much slower:

    // all the objects in this cell
    private ICollection<GameObject> prevContaining;
    private ICollection<GameObject> containing;
    internal ICollection<GameObject> Containing {
        get {
            return containing;
        }
    }

    /**
     * To ensure that `containing` and `prevContaining` are up to date, this MUST be called once per Update() loop in which it is used.
     * What is a good way to enforce this?
     */ 
    public void updateContaining()
    {
        ICollection<GameObject> result = new HashSet<GameObject>();
        uint area = checked((uint) bounds.Width * (uint) bounds.Height); // the area of this cell

        // first, try to fill up this cell with objects that were in it previously
        ICollection<GameObject>[] toSearch = new ICollection<GameObject>[] { prevContaining, engine.GameObjects };
        foreach (ICollection<GameObject> potentiallyContained in toSearch) {
            if (area > 0) { // redundant, but faster?
                foreach (GameObject obj in potentiallyContained) {
                    if (obj.Position.X >= bounds.X &&
                        obj.Position.X < bounds.X + bounds.Width &&
                        obj.Position.Y >= bounds.Y &&
                        obj.Position.Y < bounds.Y + bounds.Height) {

                        result.Add(obj);
                        area -= checked((uint) Math.Pow(obj.Radius, 2)); // assuming objects are square
                        if (area <= 0) {
                            break;
                        }
                    }
                }
            }
        }
        prevContaining = containing;
        containing = result;
   }

UPDATE 2 I abandoned that last approach. Now I'm trying to maintain a pool of collidables (orphans), and remove objects from them when I find a cell that contains them:

    internal List<List<GameObject>> getCellContents() {
        List<GameObject> orphans = new List<GameObject>(engine.GameObjects);
        List<List<GameObject>> result = new List<List<GameObject>>();
        foreach (CollisionCell cell in cellSet) {
            cell.updateContaining(ref orphans); // this call will alter orphans!
            result.Add(new List<GameObject>(cell.Containing)); 
            if (orphans.Count == 0) {
                break;
            }
        }
        return result;
    }

    // `orphans` is a list of GameObjects that do not yet have a cell
    public void updateContaining(ref List<GameObject> orphans) {
        ICollection<GameObject> result = new HashSet<GameObject>();

        for (int i = 0; i < orphans.Count; i++) {
            // 20% of processor time spent in this conditional
            if (orphans[i].Position.X >= bounds.X &&
                orphans[i].Position.X < bounds.X + bounds.Width &&
                orphans[i].Position.Y >= bounds.Y &&
                orphans[i].Position.Y < bounds.Y + bounds.Height) {

                result.Add(orphans[i]);
                orphans.RemoveAt(i);
            }
        }

        containing = result;
    }

This only yields a marginal improvement, not the 2x or 3x I'm looking for.

UPDATE 3 Again I abandoned the above approaches, and decided to let each object maintain its current cell:

    private CollisionCell currCell;
    internal CollisionCell CurrCell {
        get {
            return currCell;
        }
        set {
            currCell = value;
        }
    }

This value gets updated:

    // Run 1 cycle of this object
    public virtual void Run()
    {
        position += velocity;
        parent.CellManager.updateContainingCell(this);
    }

CellManager code:

private IDictionary<Vector2, CollisionCell> cellCoords = new Dictionary<Vector2, CollisionCell>();
    internal void updateContainingCell(GameObject gameObject) {
        CollisionCell currCell = findContainingCell(gameObject);
        gameObject.CurrCell = currCell;
        if (currCell != null) {
            currCell.Containing.Add(gameObject);
        }
    }

    // null if no such cell exists
    private CollisionCell findContainingCell(GameObject gameObject) {

        if (gameObject.Position.X > GameEngine.GameWidth
            || gameObject.Position.X < 0
            || gameObject.Position.Y > GameEngine.GameHeight
            || gameObject.Position.Y < 0) {
            return null;
        }

        // we'll need to be able to access these outside of the loops
        uint minWidth = 0;
        uint minHeight = 0;

        for (minWidth = 0; minWidth + cellWidth < gameObject.Position.X; minWidth += cellWidth) ;
        for (minHeight = 0; minHeight + cellHeight < gameObject.Position.Y; minHeight += cellHeight) ;

        CollisionCell currCell = cellCoords[new Vector2(minWidth, minHeight)];

        // Make sure `currCell` actually contains gameObject
        Debug.Assert(gameObject.Position.X >= currCell.Bounds.X && gameObject.Position.X <= currCell.Bounds.Width + currCell.Bounds.X,
            String.Format("{0} should be between lower bound {1} and upper bound {2}", gameObject.Position.X, currCell.Bounds.X, currCell.Bounds.X + currCell.Bounds.Width));
        Debug.Assert(gameObject.Position.Y >= currCell.Bounds.Y && gameObject.Position.Y <= currCell.Bounds.Height + currCell.Bounds.Y,
            String.Format("{0} should be between lower bound {1} and upper bound {2}", gameObject.Position.Y, currCell.Bounds.Y, currCell.Bounds.Y + currCell.Bounds.Height));

        return currCell;
    }

I thought this would make it better - now I only have to iterate over collidables, not all collidables * cells. Instead, the game is now hideously slow, delivering only 1/10th of its performance with my above approaches.

The profiler indicates that a different method is now the main hot spot, and the time to get neighbors for an object is trivially short. That method didn't change from before, so perhaps I'm calling it WAY more than I used to...

Answer 1

It spends 50% of its time in that function because you call that function a lot. Optimizing that one function will only yield incremental improvements to performance.

Alternatively, just call the function less!

You've already started down that path by setting up a spatial partitioning scheme (lookup Quadtrees to see a more advanced form of your technique).

A second approach is to break your N*N loop into an incremental form and to use a CPU budget.

You can allocate a CPU budget for each of the modules that want action during frame times (during Updates). Collision is one of these modules, AI might be another.

Let's say you want to run your game at 60 fps. This means you have about 1/60 s = 0.0167 s of CPU time to burn between frames. No we can split those 0.0167 s between our modules. Let's give collision 30% of the budget: 0.005 s.

Now your collision algorithm knows that it can only spend 0.005 s working. So if it runs out of time, it will need to postpone some tasks for later - you will make the algorithm incremental. Code for achieving this can be as simple as:

const double CollisionBudget = 0.005;

Collision[] _allPossibleCollisions;
int _lastCheckedCollision;

void HandleCollisions() {

    var startTime = HighPerformanceCounter.Now;

    if (_allPossibleCollisions == null || 
        _lastCheckedCollision >= _allPossibleCollisions.Length) {

        // Start a new series
        _allPossibleCollisions = GenerateAllPossibleCollisions();
        _lastCheckedCollision = 0;
    }

    for (var i=_lastCheckedCollision; i<_allPossibleCollisions.Length; i++) {
        // Don't go over the budget
        if (HighPerformanceCount.Now - startTime > CollisionBudget) {
            break;
        }
        _lastCheckedCollision = i;

        if (CheckCollision(_allPossibleCollisions[i])) {
            HandleCollision(_allPossibleCollisions[i]);
        }
    }
}

There, now it doesn't matter how fast the collision code is, it will be done as quickly as is possible without affecting the user's perceived performance.

Benefits include:

• The algorithm is designed to run out of time, it just resumes on the next frame, so you don't have to worry about this particular edge case.
• CPU budgeting becomes more and more important as the number of advanced/time consuming algorithms increases. Think AI. So it's a good idea to implement such a system early on.
• Human response time is less than 30 Hz, your frame loop is running at 60 Hz. That gives the algorithm 30 frames to complete its work, so it's OK that it doesn't finish its work.
• Doing it this way gives stable, data-independent frame rates.
• It still benefits from performance optimizations to the collision algorithm itself.
• Collision algorithms are designed to track down the "sub frame" in which collisions happened. That is, you will never be so lucky as to catch a collision just as it happens - thinking you're doing so is lying to yourself.