# When and how should I update my collision grid?

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);
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();
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;
}

{
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();
}

{
}

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);
}


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.

• How should I handle individual update? For example if I had separate grid for all stationary entities, say 4000 of those, and then 1 of them is destroyed. How should I handle that single update, instead of rebuilding the whole grid everytime? Find cell where that entity is and remove from container? – warbaque Dec 17 '13 at 3:20
• @KlausHelenius: yes. remove from old location, add to new location (which may be the same location). you may or may not end up with faster code if you detect the position is the same and don't do the remove/add cycle for that object. – Sean Middleditch Dec 17 '13 at 6:33
• I actually came to following solution: when I query grid for nearbyEntities I remove that entity from grid at the same time and mark entity removed. And when I do grid update I re add all removed entities. – warbaque Dec 17 '13 at 8:40
• @KlausHelenius: that... works. Not ideally, but perfection is the enemy of success. :) – Sean Middleditch Dec 17 '13 at 8:50

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.

• So Clear() would remove only dynamic objects from grid and update would add only those? How should I handle scenarios when stationary objects are deleted? – warbaque Dec 17 '13 at 0:54
• You can instead have a container to store references to any physics object that need to be updated. See Sean's answer. – RandyGaul Dec 17 '13 at 1:44