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.
