# How to combat exponential growth in sprite messaging?

In my 2D platformer game, I have a number of sprites moving around the world. When two sprites collide with each other, I calculate how deep the collision is and then call a virtual method on both sprites that lets them handle the collision (for instance, a fireball would kill the other sprite).

Each sprite is checked for collision against each other sprite "near" it. "Nearness" is determined through my lazy Quadtree which is really just a list of evenly-sized cells that objects are sorted into.

However, the number of virtual method calls (or messages) increases exponentially with the number of sprites colliding at once, leading to <1fps with only about 120 sprites onscreen. If three sprites overlap each other, six messages need to be send. Four sprites need 12 messages, and twenty sprites need 380.

Just checking for collisions can be costly, even with the game world being divided into cells - if 30 sprites are in the same cell, 900 collision checks are required.

Now, I don't expect 120 onscreen sprites to be the norm - it'd probably be closer to 20, but I'm really concerned with how little range there is between playable and slideshow.

I strongly suspect that if I really want each sprite to message each other, there's no way to do any better than N*(N-1)/2 messages. Is there anything I can do to reduce the costs?

Edit: On request, here's the relevant code:

foreach (var collidableSprite in Sprites.GetItemsNearItem(sprite))
{
if (Object.ReferenceEquals(collidableSprite, sprite)) { continue; }

BoundingRectangle hitboxA = sprite.Hitbox;
BoundingRectangle hitboxB = collidableSprite.Hitbox;

Vector2 intersectA = hitboxA.GetIntersectionDepth(hitboxB);
Vector2 intersectB = hitboxB.GetIntersectionDepth(hitboxA);

if (!intersectA.IsNaN() && !intersectB.IsNaN())
{
sprite.HandleSpriteCollision(collidableSprite, intersectA);
collidableSprite.HandleSpriteCollision(sprite, intersectB);
}
}


Essentially, for each sprite in the world, for each sprite near this sprite (in the same grid cell(s)), check to see if there's an intersection and how deep it is. If there is, call the collision handlers on both sprites.

internal IEnumerable<T> ItemsInCells(SparseCellRange range)
{
foreach (T item in items)
{
if (GetCellsItemIsIn(item).Equals(range))
{
yield return item;
}
}
}

internal IEnumerable<T> GetItemsNearItem(T item)
{
SparseCellRange range = GetCellsItemIsIn(item);

return ItemsInCells(range);
}


Here's the code that checks for nearness. The SparseCellRange is a pair of Vector2 instances for TopLeft and BottomRight cell numbers.

• Why do you need sprites to send messages to the other sprites it collided with when those other sprites will also detect the collision on their own? Commented May 26, 2016 at 11:44
• Ideally, each collision pair between two sprites would only be handled once, but I don't know how to do that without making a list of every sprite checked this frame, and lists are expensive when you make them once per sprite per frame. Commented May 26, 2016 at 11:46
• How did you determine the virtual method calls are the problem? Have you profiled the code? Commented May 27, 2016 at 4:25
• The virtual method calls are not (typically) the problem, but my profiler indicated that my intersection-depth method calls were through the roof - up to 2 million calls per frame with ~120 sprites onscreen. If every sprite overlapped, a similar number of virtual calls would take place. Commented May 27, 2016 at 12:56