The Collision in Subverdant

The goal with the CollisionManager in Subverdant was to be efficient, usable and simple.

Efficiency

Each level in Subverdant has tens of thousands of tiles, so the Rect-on-Rect O(n^2) algorithm quickly becomes a bottleneck. Instead of Rects I used Points for collision detection against tiles. Since tiles are in a neat grid, we can just divide the position with the tile size to find out which tile we are colliding with:

VECTOR2UI tilePos{
  static_cast<Ti>(locatorPosition.myX / ourTileWidth), 
  static_cast<Ti>(locatorPosition.myY / ourTileHeight)};
eCollisionTileType type = GetTile(tilePos);
NotifyLocator(i, type, tilePos);

Memory efficiency

Since there are four types of tiles in Subverdant, the smallest number of bits we can describe them with is 2:

The method above relies on allocating one big tile grid in memory. If each tile was an int (32 bits), we would be wasting 30 bits for each tile, even where there are no tiles. Instead I used bit arithmetic to fit each tile into 2 bits:

eCollisionTileType CollisionManager::GetTile(VECTOR2UI aPosition) const
{
  const Ti tileIndex = aPosition.myY * myLevelSize.myX + aPosition.myX;
  const Ti tileByte = tileIndex / ourTilesPerByte;
  const unsigned char bitIndex =
    (ourTilesPerByte - tileIndex % ourTilesPerByte - 1) * ourTileBits;

  TB tile = myTiles[tileByte] >> bitIndex;
  TB maskByte = 1;
  for (Sz i = 0; i < ourTileBits; i++)
    maskByte *= 2;
  maskByte--;
  return static_cast<eCollisionTileType>(tile & maskByte);
}

void CollisionManager::PutTile(eCollisionTileType aType, VECTOR2UI aPosition)
{
  const Ti tileIndex = aPosition.myY * myLevelSize.myX + aPosition.myX;
  assert(tileIndex < myLevelSize.myX * myLevelSize.myY && "put tile outside of level");
  const Ti tileByteIndex = tileIndex / ourTilesPerByte;
  const unsigned char bitIndex =
    (ourTilesPerByte - tileIndex % ourTilesPerByte - 1) * ourTileBits;

  // begin by clearing the bits
  TB clearByte = 1;
  for (Sz i = 0; i < ourTileBits; i++)
    clearByte *= 2;
  clearByte = ~((clearByte - 1) << bitIndex);
  myTiles[tileByteIndex] &= clearByte;
  // then set the bits using OR
  TB wByte = static_cast<TB>(aType) << bitIndex;
  myTiles[tileByteIndex] |= wByte;
}

While this was extremely efficient for tile collision, I still implemented Rect-Rect collision alongside the Points, because it was useful for stuff like enemies.

Usability

When Points or Rects are created, an Observer pointer is stored alongside the collision object. When a collision is detected, notifications are immediately sent using virtual function calls to the Observer pointer. These notifications are Entry, Collision and Exit. The Entry- and Exit notifications require storing some extra state in the CollisionManager, but are convenient to have.

Entities are given a "handle" to the created collision object, which is a wrapped pointer that they can use to move the Point or Rect. Collision objects and all their state is stored in linear arrays, so when a collision object somewhere in the middle of the array is removed, it is replaced with the last collision object to avoid shuffling the entire array. This makes the handle of the last collision object's observer suddenly invalid, so it is notified that the collision object has expired, and is sent a new handle as argument to the virtual function call.

Results & Reflections

This implementation performed very well in Subverdant. It never caused performance issues. However, removing the virtual function calls and instead reporting an array of results from the collision detection should have improved performance even more.

I'm happy with the usability of the interface, with the exception of how virtual functions cluttered the header definitions of various classes.

I spent ~16 hours total writing this code, and considering how well it performed, I think it was worth it. I also managed to make the source code readable and the constants modifiable. Debugging was difficult though, much due to gameplay programmers sometimes forgetting to replace expired collision objects.

Overall, I am happy with the collision detection's performance, but I could have used a different solution to handle the results.