4
\$\begingroup\$

My game engine uses the following broadphase collision detection algorithm:

internal void SweepAndPrune()
{
    // First: order all objects from left to right on the x-axis:
    IOrderedEnumerable<GameObject> axisList = _gameObjects.OrderBy(x => x.LeftRightMost.X);

    // loop through all objects:
    for(int i = 0; i < axisList.Count(); i++)
    {
        // For each object, iterate over all the subsequent objects in the list
        // and find out if there are overlaps on the x-axis:
        for(int j = i+1; j < axisList.Count(); j++)
        {
            GameObject a = axisList.ElementAt(i);
            GameObject b = axisList.ElementAt(j);
            if(b.Left > a.Right)
            {
                // if their is no overlap, then the rest will not overlap as well.
                // might as well stop the inner loop here:
                break;
            }
            // if there is an overlap, add A to B's list 
            // and B to A's list of potential collisions.
            // [every object's list of collision candidates is 
            // cleared before the next frame]
            a._collisionCandidates.Add(b);
            b._collisionCandidates.Add(a);
        }
    }
}

The problem is, this algorithm slows down the performance by a lot if there are > 50 objects on screen. Also, the list of GameObject instances (_gameObjects) needs to get sorted another time per frame because I need to order the objects by their distances from the camera (background objects need to get rendered first because of transparency!).

Is there anything I can do to speed things up?

\$\endgroup\$
2
  • \$\begingroup\$ for starter, you could convert axisList to list or array, and use .Count or .Length instead of Count() , then replace ELementAt with regular index axisList[i]. This would give you some performance boost, the rest would be outside the loop scope I guess. \$\endgroup\$ Commented Oct 27, 2020 at 18:35
  • \$\begingroup\$ Alright, I will give it a try. Thanks! \$\endgroup\$ Commented Oct 27, 2020 at 18:39

1 Answer 1

Reset to default
4
\$\begingroup\$

An IEnumerable (and IOrderedEnumerable) represents a question, not an answer. axisList is not really a list -- it is a question asking "What is the sequence of elements from _gameObjects ordered by X value?". So every time you do this:

            GameObject a = axisList.ElementAt(i);
            GameObject b = axisList.ElementAt(j);

You are answering the question "What is the ith element in that ordering". Which means it needs to re-order the sequence on every iteration! Your outer loop ends up being hugely expensive (O(n^3 log(n)) if my math checks out); you certainly don't need to do that.

You should cache the result of the ordering and re-use it in your loop. Change this

IOrderedEnumerable<GameObject> axisList = _gameObjects.OrderBy(x => x.LeftRightMost.X);

to this:

var orderedByX = _gameObjects.OrderBy(x => x.LeftRightMost.X).ToList();

.ToList() will evaluate the OrderBy query and return a flattened "answer" that you can keep reusing, and as a bonus it has O(1) lookup so ElementAt is fast -- you could even change ElementAt(i) to [i] to make that more clear.

\$\endgroup\$
3
  • \$\begingroup\$ Holy moly! My game loop just went from 16.4ms to 1.9ms with 100 objects on screen. In debug mode! This is the biggest performance increase I have ever seen. I feel so stupid! Thank you both Jeff and iSR5 for helping me. Special thanks to Jeff for elaborating. Wow! I am stunned!!! \$\endgroup\$ Commented Oct 27, 2020 at 18:52
  • 1
    \$\begingroup\$ And if _gameObjects doesn't change often relative to how often your algorithm runs, you could even just re-sort it every time it changes rather than every time you run your algorithm. Or use a SortedList for _gameObjects which does that for you automatically. \$\endgroup\$ Commented Oct 27, 2020 at 18:54
  • \$\begingroup\$ I am very grateful for your enthusiasm! I will try that as well. Hell, I wish there was something that I could help YOU with - but you seem to be a lot more experienced than I am :-( \$\endgroup\$ Commented Oct 27, 2020 at 18:58

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.