Collision Detection for 2d game: Spatial Grid. Cocos2dx

Hello there,

At the beginning, we should say, that full collision detection implementation consists of two parts: broad-space and narrow-space detections.

  1. Broad-space: detection of objects in space which could potentially collide. So we don't need to calculate each x each collisions, which is very inefficient.
  2. Narrow-phase: determine where exactly our object collided with another object (it's part, side etc.).

In this post I will concentrate on broad-phase collision detection only using Spatial Grid. This implementation will also use little bit of Cocos2dx engine API. It's good 2d engine out there, and I am using it currently for my 2d games.

Overall idea is simple enough:
1. Create grid, which divides our space into squared chunks.
2. Register gameobjects within chunks from previous step.
3. Determine if two or more game objects are in the same chunk of space. If so, they can potentially collide.

For the beginning, here is short visual demo how our grid will work (red objects are ones that might collide):

CollisionDemo

Let's proceed straight to the definition of SpatialGrid class:

class SpatialGrid : public cocos2d::Ref
{

public:
    SpatialGrid(int sceneWidth, int sceneHeight, std::vector<cocos2d::Sprite*>& collisionObjects);
    std::vector<CollisionSpace*> spaces;
    void clearObjectsFromSpaces();
    void update(float dt);

    ~SpatialGrid();

private:
    int _colsAmount;
    int _rowsAmount;
    int _cellSize;
    int _sceneWidth;
    int _sceneHeight;

    std::vector<cocos2d::Sprite*>* _collisionObjects;
};

This class gets scene size and reference to container with game objects in scene as arguments. Then it constructs grid and runs it's main logic on every frame.

Except of references to cocos2d::Sprite class, which represents our gameobjects, there is also CollisionSpace type.
It's a tiny class for describing grid cells or separate chunks.

class CollisionSpace : public cocos2d::Rect
{
public:
    std::vector<cocos2d::Sprite*> objects;
    void clearObjects();
    CollisionSpace();
    ~CollisionSpace();

}; 

Each cell keeps two things:

  • container with references to game objects (Sprite types in my case) it posses.

  • tiny method which clears references to gameObjects from the space.

The only method of CollisionSpace type will look simple:

void CollisionSpace::clearObjects()
{
    objects.clear();
}

Back to SpatialGrid class. Here is constructor implementation which does three things:

  • creates cells in proper places.
  • adds cells to container, so we can keep them in place.
  • schedules update for this target. Cocos2dx related thing, which allows us to hook into engine update function from our class.

    SpatialGrid::SpatialGrid(int sceneWidth, int sceneHeight, std::vector<Sprite*>& collisionObjects)
    {
        _cellSize = sceneWidth / 5;
        _sceneWidth = sceneWidth;
        _sceneHeight = sceneHeight;
        _sceneWidth += _sceneWidth / 2;
        _sceneHeight += _sceneHeight / 2;
       _colsAmount = _sceneHeight / _cellSize;
       _rowsAmount = _sceneWidth / _cellSize;
       _collisionObjects = &collisionObjects;
    
    
       Director::getInstance()->getScheduler()->scheduleUpdate(this, -2, false);
    
    
       int tempX = 0;
       int tempY = 0;
    
    
       for(int k = 0; k < _colsAmount; k++)
       {
           for (int i = 0; i < _rowsAmount; i++)
           {
               auto cell = new CollisionSpace();
               cell->setRect(tempX, tempY, _cellSize, _cellSize);    
       spaces.push_back(cell);
               tempX += _cellSize;
           }
    
    
       tempX = 0;
       tempY += _cellSize;
       }
    }
    

Method which clears objects from cells (simply call clearObjects() on each instance of CollisionSpace)

    void SpatialGrid::clearObjectsFromSpaces()
    {
        for (int i = 0; i < 
    spaces.size(); i++)
        {
          spaces.at(i)->clearObjects();
        }
    }

And finally update function, where all the magic happens in three simple steps:

  • determine which objects are inside each cell;
  • register those objects within cells (add CollisionSpace objects references to the container);
  • clear all objects from cells at the beginning of the frame;

    void SpatialGrid::update(float dt) {
        clearObjectsFromSpaces();
       for (int i = 0; i < spaces.size(); i++)
       {
            for (int k = 0; k < _collisionObjects->size(); k++)
            {
                 if (_collisionObjects->at(k)->getBoundingBox().intersectsRect((cocos2d::Rect)*spaces.at(i)))
                 {
            spaces.at(i)->objects.push_back(_collisionObjects->at(k));
                 }
            }
        }
    }
    

Notes:

  • smaller space chunks you have - more precise system you get as an output. Though more resources needed for calculations (linear complexity).
  • this example builds grid for view port only. For indexing wider 2d space - another grid proportions has to be added to SpatialGrid class constructor.
  • I am using cocos2dx API for describing rects and render sprites.

Thanks for reading and hopefully soon I'll describe implementation for narrow-phase collision detection.