0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Philipp May 26 '16 at 11:44
  • \$\begingroup\$ 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. \$\endgroup\$ – Celarix May 26 '16 at 11:46
  • \$\begingroup\$ How did you determine the virtual method calls are the problem? Have you profiled the code? \$\endgroup\$ – craftworkgames May 27 '16 at 4:25
  • \$\begingroup\$ 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. \$\endgroup\$ – Celarix May 27 '16 at 12:56
1
\$\begingroup\$

Check broad-phase collision detection. Example link

That would reduce the collision detection cost. Then figure out WHAT causes your performance drop. Virtual method calls themselves are not that expensive - 1000 of them in a frame will definitely NOT cause a slideshow. Perhaps the message system is slow? The message creation copies data by value? etc etc.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the link, it's very helpful. I have a primitive form of broad-phase collision detection already - sprites are placed into small cells and only sprites within the same cells are checked for collision. Looking at my profiler, after adding about 100 sprites that eventually occupied an area roughly 8 cells wide, it seems the most expensive thing is getting an enumerator for the sprites in the same cells as the sprite we're checking, which is odd. \$\endgroup\$ – Celarix May 26 '16 at 11:52
  • \$\begingroup\$ @Celarix Can you share the relevant code? \$\endgroup\$ – Dan May 26 '16 at 15:42
  • \$\begingroup\$ Code added to OP. \$\endgroup\$ – Celarix May 27 '16 at 1:27
  • \$\begingroup\$ So to find out which items are near an item, you check every single item. That's bad (well, it's terrible, but I don't want to be too harsh :) ). A dead-easy version of what you should be doing: 1) when you determine the cells that an item is in, store a reference of the item in each cell. 2) when you want to find out which items are near an item, just query the nearby cells for all references. This way, you don't go through the item list for every item. That's O(N^2), aka unnecessarily-bad \$\endgroup\$ – Babis May 27 '16 at 10:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.