Thread: A confusing boolean return

  1. #1
    Registered User wtaplin's Avatar
    Join Date
    Dec 2009
    Posts
    13

    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.

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    Last edited by iMalc; 06-17-2010 at 12:44 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User wtaplin's Avatar
    Join Date
    Dec 2009
    Posts
    13
    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 : )
    Last edited by wtaplin; 06-17-2010 at 03:09 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. A basic optimization request...
    By feeder74 in forum C++ Programming
    Replies: 27
    Last Post: 05-05-2010, 07:17 AM
  2. Compiling C in Visual Studio 2005
    By emanresu in forum C Programming
    Replies: 3
    Last Post: 11-16-2009, 04:25 AM
  3. Why only 32x32? (OpenGL) [Please help]
    By Queatrix in forum Game Programming
    Replies: 2
    Last Post: 01-23-2006, 02:39 PM
  4. Pong is completed!!!
    By Shamino in forum Game Programming
    Replies: 11
    Last Post: 05-26-2005, 10:50 AM
  5. Certain functions
    By Lurker in forum C++ Programming
    Replies: 3
    Last Post: 12-26-2003, 01:26 AM