Blazor Gamedev &#8211; part 12: collision detection

Blazor Gamedev – part 12: collision detection

Hi All! Welcome back to part 12 of our Blazor 2d Gamedev series. Today we’re going to see how we can handle collision detection in an efficient way.

Last time we improved our assets loading code, adding a JSON structure holding the list of each asset in our game.

I’ve made a lot of changes to the codebase, and I’ll probably write more about them in the next posts, but today we’ll focus on collision detection.

Today’s example is already available here, take your time to check it. You should see something like this:

You can move the spaceship with the arrow keys and if you happen to hit an asteroid, both of you will disappear.

The main idea is that when two bounding boxes intersect, their GameObjects are colliding. Easy peasy.

When we have just a few entities in our game this is fairly easy, we could simply use two nested loops and check each pair, leading to an O(n^2) complexity.

</figure>

Unfortunately, this approach doesn’t scale very well when the number of entities increases drastically.

Imagine what would happen if we have more asteroids or we start shooting and we have to deal with each bullet.

So what we can do? Well, one alternative (and there are many) is to use a divide-et-impera approach. We’ll have two main steps, B_uild_ and Check.

When building we start by dividing the screen into a regular grid.

void BuildBuckets()
{
    var rows = _game.Display.Size.Height / _bucketSize.Height;
    var cols = _game.Display.Size.Width / _bucketSize.Width;
    _buckets = new CollisionBucket[rows, cols];

    for (int row = 0; row &lt; rows; row++)
    for (int col = 0; col &lt; cols; col++)
    {
        var bounds = new Rectangle(
            col * _bucketSize.Width,
            row * _bucketSize.Height,
            _bucketSize.Width, 
            _bucketSize.Height);
        _buckets[row, col] = new CollisionBucket(bounds);
    }
    
    var colliders = FindAllColliders();
    foreach (var collider in colliders)
    {
        RefreshColliderBuckets(collider);
    }
}

Each cell represents a “bucket”, containing the bounding boxes of our entities:

class CollisionBucket
{   
    public HashSet&lt;BoundingBoxComponent> Colliders { get; } = new();
   
    public Rectangle Bounds { get; init; }
}

The FindAllColliders() method is a simple DFS on the SceneGraph, returning all the GameObjects with a Bounding Box.

Entities can belong to multiple buckets (they might be crossing cells or have a bigger bounding box):

void RefreshColliderBuckets(BoundingBoxComponent collider)
{
    if (!_bucketsByCollider.ContainsKey(collider.Owner.Id))
        _bucketsByCollider[collider.Owner.Id] = new List&lt;CollisionBucket>();

    foreach (var bucket in _bucketsByCollider[collider.Owner.Id])
        bucket.Remove(collider);

    _bucketsByCollider[collider.Owner.Id].Clear();

    var rows = _buckets.GetLength(0);
    var cols = _buckets.GetLength(1);
    var startX = (int) (cols * ((float) collider.Bounds.Left / _game.Display.Size.Width));
    var startY = (int) (rows * ((float) collider.Bounds.Top / _game.Display.Size.Height));

    var endX = (int) (cols * ((float) collider.Bounds.Right / _game.Display.Size.Width));
    var endY = (int) (rows * ((float) collider.Bounds.Bottom / _game.Display.Size.Height));

    for (int row = startY; row &lt;= endY; row++)
    for (int col = startX; col &lt;= endX; col++)
    {
        if (!_buckets[row, col].Bounds.IntersectsWith(collider.Bounds))
            continue;
        
        _bucketsByCollider[collider.Owner.Id].Add(_buckets[row, col]);
        _buckets[row, col].Add(collider);
    }
}

We start by clearing the list of buckets for the entity. Then we compute the indices of the bounding boxes containing the vertexes of the bounding box. This way we can avoid looping over the entire grid, but only on a small window.

At this point we can loop over the cells, check if they actually contain the bounding box and if so, we assign the entity to it.

Now, every time an entity moves we update the entity’s buckets list by calling RefreshColliderBuckets() on it. Then we can check for collisions only with the active entities in the same bucket:

void CheckCollisions(BoundingBoxComponent bbox)
{
    var buckets = _bucketsByCollider[bbox.Owner.Id];
    foreach (var bucket in buckets)
    {
        bucket.CheckCollisions(bbox);
    }
}

class CollisionBucket
{   
    public void CheckCollisions(BoundingBoxComponent bbox)
    {
        foreach (var collider in _colliders)
        {
            if (collider.Owner == bbox.Owner || 
                !collider.Owner.Enabled ||
                !bbox.Bounds.IntersectsWith(collider.Bounds))
                continue;

            collider.CollideWith(bbox);
            bbox.CollideWith(collider);
        }
    }
}