When and how should I update my collision grid?

Question

When and how should I update my collision grid?

Current implementation:

1. buildGrid(): add all entities with collision to the grid
2. handleCollision(timePerFrame, entities): handle all collisions
3. grid.clear(): clear grid

If I have for example 4000 stationary entities and only 20 moving entities, I remove and add 4000 entities to the grid every update for no reason.

What would be the good way to update only cells that require updating?

Only idea that I have currently is that after collision check I remove moving entities from the grid and during buildGrid() I add only moving entities to the grid.

All help is welcome.

Grid implementation

// CollisionGrid Cell
class Cell
{
    public:
        typedef std::set<Entity*> Container;

    public:
        void        setNeighbours(Cell* left, Cell* right, Cell* up, Cell* down);
        void        addEntity(Entity* entity);
        Container   getNearbyEntities() const;
        void        clear();

    private:
        void        appendEntitiesTo(Container& entities) const;

    private:
        Container   mEntities;

    protected:
        Cell*       mLeft;
        Cell*       mRight;
        Cell*       mUp;
        Cell*       mDown;
};


// CollisionGrid
class CollisionGrid
{
    public:
                            CollisionGrid(float sceneWidth, float sceneHeight, float cellSize);

        void                clear();
        void                addEntity(Entity* entity);
        Cell::Container     getNearbyEntities(Entity* entity);

    private:
        int                 getIdForPosition(const sf::Vector2f position);

    public:
        int                 mCols;
        int                 mRows;
        std::vector<Cell>   mCells;

    private:
        float               mSceneWidth;
        float               mSceneHeight;
        float               mCellSize;
};


// CollisionGrid Cell
void Cell::setNeighbours(Cell* left, Cell* right, Cell* up, Cell* down)
{
    mLeft = left;
    mRight = right;
    mUp = up;
    mDown = down;
}


void Cell::addEntity(Entity* entity)
{
    mEntities.insert(entity);
}


Cell::Container Cell::getNearbyEntities() const
{
    Container entities = mEntities;

    if (mLeft != nullptr)
        mLeft->appendEntitiesTo(entities);
    if (mRight != nullptr)
        mRight->appendEntitiesTo(entities);
    if (mUp != nullptr)
        mUp->appendEntitiesTo(entities);
    if (mDown != nullptr)
        mDown->appendEntitiesTo(entities);

    return entities;
}


void Cell::clear()
{
    mEntities.clear();
}


void Cell::appendEntitiesTo(Container& entities) const
{
    entities.insert(mEntities.begin(), mEntities.end());
}


// CollisionGrid
CollisionGrid::CollisionGrid(float sceneWidth, float sceneHeight, float cellSize)
: mSceneWidth(sceneWidth)
, mSceneHeight(sceneHeight)
, mCellSize(cellSize)
, mCols((int)floor(sceneWidth / cellSize))
, mRows((int)floor(sceneHeight / cellSize))
{
    mCells = std::vector<Cell>(mCols*mRows);

    for (int id = 0; id < mCols*mRows; ++id)
    {
        Cell* left = nullptr;
        Cell* right = nullptr;
        Cell* up = nullptr;
        Cell* down = nullptr;

        if (id % mCols > 0)
            left = &mCells[id - 1];
        if (id % mCols < mCols - 1)
            right = &mCells[id + 1];
        if (id > mCols - 1)
            up = &mCells[id - mCols];
        if (id < mCols * (mRows - 1))
            down = &mCells[id + mCols];

        mCells[id].setNeighbours(left, right, up, down);
    }
}


void CollisionGrid::clear()
{
    for (Cell& cell : mCells)
        cell.clear();
}


void CollisionGrid::addEntity(Entity* entity)
{
    mCells[getIdForPosition(entity->position)].addEntity(entity);
}


Cell::Container CollisionGrid::getNearbyEntities(Entity* entity)
{
    return mCells[getIdForPosition(entity->position)].getNearbyEntities();
}


int CollisionGrid::getIdForPosition(const sf::Vector2f position)
{
    return int(floor(position.x / mCellSize) + floor(position.y / mCellSize) * mCols);
}

Answer 1

An option that is fairly prevalent in game development is to make use of a dirty flag or dirty list. Assuming you must delay the update of your grid and can't just do it when an object moves, this is the most efficient option you'll have.

Whenever an object moves, add it to the dirty list if its dirty flag is not already set. When it's time to update the grid, iterate over only the dirty list and do any logic with them as appropriate. Remember that two stationary objects cannot have their collision state change, so you only need to check for collisions between a dirty object and the others in its local area and you only need to update the grid for dirty objects. Clear the object's dirty flag after updating it. After the dirty list is updated, clear it. The result is that objects that are not moving incur zero overhead and all the moving objects can have any movement/collision logic executed in one batch, which tends to be faster.

Note that the dirty "list" does not have to be a linked list. The usual option I fall back to is an unsorted array/vector of pointers or handle IDs. You need only the collection of objects that have changed with no particular order, so pick the most efficient data structure you can for storing that collection.

Answer 2

I don't see why you can't have a linked list of all dynamic objects. This way all you need to do is re-insert all dynamic objects into the grid each frame. When you create a physics object you should be able to specify whether it is static or dynamic. This way you can have two separate lists to iterate over dynamic or static objects.

If you want the best performance you should consider using an intrusively linked list, so that you don't do any separate allocations of linked list nodes.