Slow foreach loop to check for intersect

Question

I'm trying to make a loop where it returns whether or not a rectangle collides and then to which coords the rectangle should move to.

I'm calling my function like this:

rectangles2[i].rect = rectangleupdated(i, rectangles2);

And this is inside my function:

private Rectangle rectangleupdated(int i, List<rectList> rectangles2)
{
    //fills rectangles with rectangles to check intersect with
    BOTTOM = rectangles2[i].rect;
    BOTTOM_LEFT = rectangles2[i].rect;
    BOTTOM_RIGHT = rectangles2[i].rect;
    //bool to be set to false if intersects returns true
    bBOTTOM = true;
    bBOTTOM_LEFT = true;
    bBOTTOM_RIGHT = true;
    //move the intersect rectangles
    BOTTOM.Y++;
    BOTTOM_LEFT.Y++;
    BOTTOM_LEFT.X--;
    BOTTOM_RIGHT.Y++;
    BOTTOM_RIGHT.X++;

    foreach (rectList rects in rectangles2)
    {
        if (!rects.type.Contains("bg"))
        {
            if (rectangles2[i].rect.Y < 500)
            {
                if (BOTTOM.IntersectsWith(rects.rect))
                {
                    bBOTTOM = false;
                }
                else if (BOTTOM_LEFT.IntersectsWith(rects.rect))
                {
                    bBOTTOM_LEFT = false;
                }
                else if (BOTTOM_RIGHT.IntersectsWith(rects.rect))
                {
                    bBOTTOM_RIGHT = false;
                }
            }
            else
            {
                return rectangles2[i].rect;
            }
        }
    }
    if (bBOTTOM == true) return BOTTOM;
    else if (bBOTTOM_RIGHT == true) return BOTTOM_RIGHT;
    else if (bBOTTOM_LEFT == true) return BOTTOM_LEFT;
    return rectangles2[i].rect; 
}

I think I know a little bit why it's lagging so hard but I don't know how to fix it / make this code more usable.

Answer 1

You're not using the C# naming convention:

class ClassNamesShouldBePascalCase
{
    const CONTANTS_ARE_IN_ALL_CAPS;
    private _membersShouldStartWithAUnderScoreAndBeCamelCase; //_camelCase
    public PropertiesShouldBePascalCase {get; set;} //PascalCase

    public void PublicMethodsShouldBePascalCase
    {
        object methodLevelVariablesShouldBeCamelCase; //camelCase
    }
}
//The underscore for private variables is optional, but good practice.

---

Is there a reason you are using a custom class called rectList instead of using a List<Rectangle>, besides the type ? If there are more reasons, I recommend calling the class Rectangles, otherwise, just manage the Type separately.

---

Don't call your parameter rectangles2 ... rectangles, or values is a good name.

---

if (rectangles2[i].rect.Y < 500)

500 is a magic number, and should be declared somewhere else as a constant with a useful name, so that those reading it know what it is for.

---

Give your booleans more descriptive names like:

bool bottomHasCollision

bool hasCollisionBottom

---

Use the ternary operator to clean up your final return statement:

return bBOTTOM       ? BOTTOM :
       bBOTTOM_RIGHT ? BOTTOM_RIGHT :
       bBOTTOM_LEFT  ? BOTTOM_LEFT :
       rectangles2[i].rect;

---

If you could fix these things, and upload another question I'd be more inclided to review the performance of the program, however I will need to know more about the program and see some of the other classes. You should try saving the DateTime.Now at the beginning and end of the method, and various other places inside to track the performance to pinpoint what is taking so long. There is also software out there that can help you do that.

Edit:

I've taken the liberty to implement the code changes I was talking about above. Plus some others to make the code more concise.

private Rectangle Rectangleupdated(List<Rectangles> rectangles, int i)
{
    Rectangle rect = rectangles[i].Rectangle;

    //fills rectangles with rectangles to check intersect with
    bottom = bottomLeft = bottomRight = rect;

    //bool to be set to false if intersects returns true
    bottomFlagged = bottomLeftFlagged = bottomRightFlagged = true;

    //move the intersect rectangles
    bottom.Y++;

    bottomLeft.Y++;
    bottomLeft.X--;

    bottomRight.Y++;
    bottomRight.X++;

    foreach (Rectangles rects in rectangles)
    {
        if (rects.Type.Contains("bg") || rect.Y >= 500) continue;

        bottomFlagged     = bottomFlagged && !bottom.IntersectsWith(rects.Rectangle);
        bottomLeftFlagged = bottomLeft    && !bottomLeft.IntersectsWith(rects.Rectangle);
        bottomRight       = bottomRight   && !bottomRight.IntersectsWith(rects.Rectangle);
    }
    return bottomFlagged      ? bottom :
           bottomRightFlagged ? bottomRight :
           bottomLeftFlagged  ? bottomLeft :
           rect;
}

I would however like to see your Rectangle and rectList classes, to understand where the pain points might be.

Answer 2

Are you sure you really should use else if here? I think that you just need to use if. Because another rect can collide with both bottom, bottom-left, and bottom-right at the same time.

if (BOTTOM.IntersectsWith(rects.rect))
{
    bBOTTOM = false;
}
else if (BOTTOM_LEFT.IntersectsWith(rects.rect))
{
    bBOTTOM_LEFT = false;
}
else if (BOTTOM_RIGHT.IntersectsWith(rects.rect))
{
    bBOTTOM_RIGHT = false;
}

Now, I believe however that there is a more efficient method to do this. I'd like to call it...

More math, less code

Instead of using code and testing collisions, use more math and methods that are available on the Rectangle objects and do calculations with them.

Pseudocode following for how I believe you can do this. I don't have time to work out the exact code in C# (partially because I'm no C# expert). I am not sure how much more efficient it will be, and I'm not entirely sure if it will work, but I believe it should be correct and work:

The idea here is to calculate the union of all the rectangle intersections you will get by moving.

MovingRect = the rectangle you want to move
MovingRect.y++
intersection = empty rectangle
for each (`rect` in all other rectangles) {
    if (rect intersects with MovingRect) {
        thisIntersection = calculate how much / where it intersects: See link below
        intersection = union of intersection with thisIntersection: See link below
        if the width of the intersection is two or more, then you can't move at all.
    }
}
check the size and position of the `intersection` rectangle:
  if it's size is nonexistent (i.e. empty rectangle), then you are free to move down one step
  else if it's width is 2 or more, then you are unable to move at all
  else if it's position is in the lower-left area of your rectangle, move right one step
  else if it's position is in the lower-right area of your rectangle, move left one step
  else throw an AssertionError because something is apparently wrong with this logic.

Links:

For the calculation of the intersection area

For the union of rectangles

Answer 3

The only change I can recommend without knowing more about what you're trying to accomplish is to add in a conditional to the end of the foreach loop (E: actually it would be better to put this in after the if's in the conditionals, since the boolean values will only be different if that code has executed, updated to reflect that):

if (rectangles2[i].rect.Y < 500)
{
    ...

    if (!bBOTTOM && !bBOTTOM_RIGHT && !bBOTTOM_LEFT)
    { return rectangles2[i].rect; }
}

To avoid looping through rectangles even when we already know that there isn't a space for it.

As for the rest of it, without knowing what you're trying to accomplish it would be difficult. Your algorithm only moves the rectangles into a new space if a spot above, to the left, or to the right is completely open. Is this exactly the behavior you would need? There are other algorithms that would work that you could use to simply shift all the rectangles away from eachother, but not necessarily into an empty space with each run. That would go something like this:

foreach (rectList rects in rectangles2)
{
    if (!rects.type.Contains("bg"))
    {
        if (rectangles2[i].rect.Y < 500)
        {
            if (rectangles2[i].rect.IntersectsWith(rects.rect))
            {
                Rectangle returnRect = rectangles2[i].rect;
                if (rects.rect.X < rectangles2[i].rect.X)
                { returnRect.X++; }
                else if (rects.rect.X > rectangles2[i].rect.X)
                { returnRect.X--; }
                if (rects.rect.Y < rectangles2[i].rect.Y)
                { returnRect.Y++; }
                else if (returnRect.Y > rectangles2[i].rect.Y)
                { returnRect.Y--; }
                return returnRect;
            }
        }
    }
}

return rectangles2[i].rect;

This would return a rectangle shifted away from the first rectangle found to intersect with it. Something to this tune might work faster than what you're using, depending on if it would fit your needs.

I would also recommend that public properties of objects like rects (which seems to be of type 'rectList' but only have a single rectangle associated with it?) be named in PascalCase, much easier to read.