Optimizing Collisions

While Pong is not collision heavy, a game framework should have reasonably efficient collision handling. In its v0.1.0 state, SimpleECS collision handling was a brute force double for loop. This is a \(O(n^2)\) implementation where every single collider is checked against each other for collision.

    // O(n^2) basic implementation. See quad trees for performance improvement.
    for (int i = 0; i < colliderList.size(); ++i)
    {
        for (int j = 0; j < colliderList.size(); ++j)
        {
            if (j == i) continue;
            if (getCollisionInfo(collide))
            {
                // [Resolve Collision]
            }
        }
    }

Before implementing a more optimized version, I created a simple client scene that’s populated by an adjustable number of agents with colliders and PhysicsBodies as well as an average FPS counter to visually see any potential improvements.

A 3 agent scene's framerate reachs upwards of 3000fps. However this quickly declines as agents are introduced. In a scene with a mere ~400 agents, frame rate struggles at 30 fps. We can also observe bugs in the collision resolution causing objects to stick together.

Spatial Grid Implementation

To significantly reduce the amount of collision checks necessary I implemented a coarse grid data structure whereby the screen is split into multiple grid cells each containing updated references to colliders that reside in that section of the screen (termed a “cell” in code snippits).

While this adds slight overhead in needing to update the grid every frame, it significantly decreases the number of collision checks necessary, as only colliders inside the same cell need to be checked against each other for potential collision.

The complexity is still technically \(O(n^2)\) but the performance benefits from a simple implementation of the grid is very observable in the client test scene. The ~1000 agent scene with the naive implementation that runs at ~5fps now runs at a smooth 1000 frames.

The following is a general overview of the implementation, which was developed from referencing the spatial grid concept outlined in CMU’s course in game development. While it’s unlikely that this is even close to an optimal implementation of spatial grid collision detection (having seen claims of scenes with millions of agents running at 60+fps), but even then the performance benefits it brought over a brute force implementation was very noticeable and pretty satisfying.

Grid data structure

/*
* Define a spacial grid to segment possible colliding objects
*/
class ColliderGrid
{
public: 
    /* 
    * Construct grid 
    */
    ColliderGrid(const int r, const int c);

    /*
    * Add a collider to this grid
    */
    void registerCollider(Collider*);

    /*
    * Remove a collider from this grid
    */
    void removeCollider(Collider*);

    /*
    * Update collider grid positions
    */
    void updateGrid();

    /*
    * Get number of cells
    */
    int size();

    /*
    * Get the number of colliders in a given cell
    */
    int cellSize(int index);

    /*
    * Get the colliders populating a given cell
    */
    const std::unordered_set<Collider*>& const getCellContents(const int index);

    /*
    * Get the colliders populating single out of bounds cell
    */
    const std::unordered_set<Collider*>& const getOutBoundContent();

    /*
    * Get the bounds of a given cell
    */
    void getCellBounds(Collider::AABB& output, const int& index);

private:
    /*
    * Add a collider to this grid
    */
    void insertToGrid(Collider*);

    /*
    * Populate grid based on internal list of colliders.
    */
    void populateGrid();

    int cellWidth, cellHeight;
    int numRow, numColumn;

    // index x = c + r * numColumn;
    std::vector<std::unordered_set<Collider*>> grid;

    std::unordered_set<Collider*> outbounds;

    // list of all colliders
    std::unordered_set<Collider*> colliderList;
};

// Update spatial grid references based on collider positions 
colliderGrid.updateGrid();

// Iterate through every cell
for (int i = 0; i < colliderGrid.size(); ++i)
{
    // Only brute force check colliders contained by each cell
    for (auto& colliderA : colliderGrid.getCellContents(i))
    {
        for (auto& colliderB : colliderGrid.getCellContents(i))
        {
            if (colliderA == colliderB) continue;
            resolveCollision(colliderA, colliderB);
        }
    }
}