Get subsequent element in list C#

Question

I have been asked to improve a given piece of code. The idea of the code is to take a list of objects, and with two foreach loops check if they collide. The code written in pseudo:

foreach (Entity object in objectList) 
    foreach (Entity object2 in objectList)
        if (object.collideWith(object2))
            Collision(object,object2)

For each object, it loops over each object - which is not efficient. Instead I should change it to "For each object, loop over every subsequent object". Im fairly new to C#, but this is how i imagened the soulution in pseudo:

foreach (Entity object in objectList) 
    if (object.collideWith(subsequent object))
        Collision(object, subsequent object)

This way, I'm only checking if an object collides with another once. But how do I get the "subsequent object" in my list?

I'm not quite sure how it would be useful in my case. Doesn't intersect take two lists and return the elements which are the same? I only have one list of objects. — Average_guy, Mar 20 '17 at 13:45
http://stackoverflow.com/questions/18547354/c-sharp-linq-find-duplicates-in-list — granadaCoder, Mar 20 '17 at 13:52

score 3 · Accepted Answer · answered Mar 20 '17 at 13:53

3

You can improve the code by eliminating the "lower half" of the cartesian product (provided that the collision relation is symmetric) as follows, using for loops instead of foreach loops.

for ( int i = 0; i < objectList.Count(); i++ )
{
    var iObj = objectList[i];
    for ( int j = i ; j < objectList.Count(); j++ )
    {
        var jObj = objectList[j];
        if ( iObj.collideWith(jObj) )
        {
            Collision( iObj, jObj );
        }
    }
}

This reduces the numbe rof collision checks roughly by a factor of 2. However, the runtime complexity is the same and the approach is difficult to implement with Linq.

answered Mar 20 '17 at 13:53

Codor

17,447
9
29
56

you're initializing j = i in your second loop, so on each pass through the second loop there will be an unnecessary comparison of each object to itself – Joe Irby Mar 20 '17 at 14:07
Excellent! This worked for me - however i added the following line: if (!iObj.Equals(jObj) && !jObj.Equals(_player)) This way the object don't compare to itself (not your fault since it wasn't part of my question). Thanks! – Average_guy Mar 20 '17 at 14:07
@JoeIrby Yes indeed, but I did this conciously as this comparison will also be done in the original question. – Codor Mar 20 '17 at 14:08
1

You'd probably be better off using the `Count` property rather than the `Count()` extension method. – Joe White Mar 20 '17 at 15:09

score 2 · Answer 2 · answered Mar 20 '17 at 13:50

"For each object, loop over every subsequent object"

for (int i = 0; i < objectList.Count - 1; i++)
{
  for (int j = i+1; j < objectList.Count; j++)
  {
    var obj1 = objectList[i];
    var obj2 = objectList[j];

    if (obj1.collideWith(obj2))
      Collision(obj1, obj2);
  }
}

Get subsequent element in list C#

2 Answers2