# Sweep & prune broadphase algorithm

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]
}
}
}


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?

• 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. – iSR5 Oct 27 '20 at 18:35
• Alright, I will give it a try. Thanks! – AudioGuy Oct 27 '20 at 18:39

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.

• 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!!! – AudioGuy Oct 27 '20 at 18:52
• 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. – Jeff Oct 27 '20 at 18:54
• 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 :-( – AudioGuy Oct 27 '20 at 18:58