A confusing boolean return

Hey guys, I've been going through this book about game programming and found a collision detection function that I just can't understand how it evaluates the expression and still works correctly. I realize there's a game programming section of the boards, but I think this is more of a general C++ matter.

Code:

---

BOOL Sprite::TestCollision(Sprite* pTestSprite)
{
    RECT& rcTest = pTestSprite->GetCollision();
    return m_rcCollision.left <= rcTest.right &&
                rcTest.left <= m_rcCollision.right &&
                m_rcCollision.top <= rcTest.bottom &&
                rcTest.top <= m_rcCollision.bottom;
}

---

This is supposed to test if either of two rectangles have collided at any point. Returning true for a collision, returning false for no collision What I can't understand is, why the && operator? In my mind, for all of the expressions to be true, both rectangles would have to be literally on top of each other in all points. But, the function returns true if any part of one rectangle touches any part of the other rectangle.

Lets break it down a bit:

Code:

---

BOOL Sprite::HorizontalCollision(const RECT& rcTest)
{
    return m_rcCollision.left <= rcTest.right &&
                rcTest.left <= m_rcCollision.right;
}

BOOL Sprite::VerticalCollision(const RECT& rcTest)
{
    return m_rcCollision.top <= rcTest.bottom &&
                rcTest.top <= m_rcCollision.bottom;
}

BOOL Sprite::TestCollision(Sprite* pTestSprite)
{
    RECT& rcTest = pTestSprite->GetCollision();
    return HorizontalCollision(rcTest) &&
            VerticalCollision(rcTest);
}

---

With me so far? The rectangles might overlap horizontally but one is below the other, or they might overlap vertically but one is to the right of the other, thus both conditions need to be satisfied (hence the && in TestCollision).

Given the vertical and horizontal tests are the same (just different variable names) lets look at just HorizontalCollision.

Forget thinking about where they do overlap and think about the two cases where they don't overlap, for a moment. There may be four ways that they do overlap, but there are only two ways that they do not overlap. Either one rectangle has both of its edges to the left of the other rectangle or it has both edges to the right of it. Here's how those two cases look, left-to-right:

Code:

---

m_rcCollision.Left    m_rcCollision.Right    rcTest.Left            rcText.Right        //case 1

rcTest.Left            rcText.Right            m_rcCollision.Left    m_rcCollision.Right //case 2

---

We know any rectangle has its left edge and right edge the correct way around, so to detect the above cases all we need to check is the middle two items of the four:

Code:

---

is m_rcCollision.Right < rcTest.Left //case 1
or
is rcText.Right < m_rcCollision.Left // case 2

---

Now remember that we want the opposite case, where it does overlap, not where it doesn't. So we apply DeMorgan's Law:
A or B <==> !(!A and !B)
In other words, negate both expressions, and toggle the operator beteen 'or' and 'and'.
Starting with:

Code:

---

m_rcCollision.Right < rcTest.Left || (rcText.Right < m_rcCollision.Left)

---

this becomes:

Code:

---

!(m_rcCollision.Right < rcTest.Left) && !(rcText.Right < m_rcCollision.Left)

---

Simplify to remove the negation... !(A<B) is the same as A >= B:

Code:

---

m_rcCollision.Right >= rcTest.Left && rcText.Right >= m_rcCollision.Left

---

Flip the expresions over (since B>=A is the same as A<=B):

Code:

---

m_rcCollision.left <= rcTest.right && rcTest.left <= m_rcCollision.right

---

And there we have it!

I guess you could say that the function looks for the absense of ways in which the rectangles do not overlap, rather than looking for the presence of ways in which they do overlap.

Ah! I see it now. I was under the assumption that each of the four expressions were all checking for a collision, which didn't make sense, for all of them to return true. I see now that, in the case of a collision, two of the expressions say "these two sides overlap", while the other two are saying "If these two sides overlap, their opposite sides must not overlap". In which case, all the expressions would return true and the function would give you the right results. Thanks Malc! =D More often than not, while teaching myself C++, it's certain calculations and how one arrives at them that throw me off more than the language itself. I've never taken any math past Algebra II, almost ten years ago. Maybe it's time to put down the C++ book, and pick up the math book : )