-1

This is how I currently check collision for my tile map:

int[,] layer;

for (x = 0; ...)
{
    for (y = 0; ...)
    {
        //Do collision checks here, based on index.
    }
}

This is the alternative I'm thinking of:

List<Collision> collisions;

for (i = 0; i < collisions.Count; i++)
{
    //Check for "MovingObject to Collision" here.
}

I would assume that since I'm switching from two for loops to just one, it would be faster.

  1. Performance-wise, does it matter what I iterate through with a for loop?
  2. Out of curiosity, does it matter what I iterate through in a foreach loop?
Shyy Guy
  • 232
  • 3
  • 18
  • looping inside a loop ofcourse has a complexity of **O(n^2)** respective of looping once that has **O(n)**. but how are those both codes co-related to each other ? – Rohit Prakash Feb 11 '15 at 04:28
  • Since the inner code is not identical in the two cases, it is not possible to tell for sure. – NoChance Feb 11 '15 at 04:31
  • 1
    It's most efficient to have running code, and optimize where needed. – SimpleVar Feb 11 '15 at 04:38
  • 1
    If you're looking this hard at optimization, note that a 2d array is considerably slower than a 1d array: http://stackoverflow.com/a/468873/58158. – overslacked Feb 11 '15 at 06:06

1 Answers1

1

Both loops will take (nearly) the same time. Assumiong that most CPU cycles are needed for the calculations inside the loop (collision check in your case), the cycles for the loop itself (increment x, y) negligible.

In your for(x)/for(y) examle, the calculations are executed Length(x) * Length(y) times. In the for(collisions) you'll have to check the same number of collisions. It'll be hard to see any difference if you try to test performance of both loops.

The second method will allow for more elegance however:

foreach(var collision in collisions) ...

The number of cycles are (nearly) the same as with a for(i) loop. (Unmeasurable differences...)

As usual the trick to get it faster is a change in the algorithm:

  • Are there any possibilities to check a limited number of objects, collisions?
  • Any chance to use sorted lists of objects, for example to check close neighbors first?

This might change your Algorithm from O(n^2) to O(n) or even O(log n) which makes it really much faster.

DrKoch
  • 9,556
  • 2
  • 34
  • 43