Bounding box collision handling - not detection

Question

I had this working a week ago, but then I ended up breaking it. I can't get it working again. I have some 2D sprites, they're just rectangles. No rotation involved. I'm not looking for a way to detect collisions between them, I have that, and there's thousands of articles out there about it. What I can't find is any resource about what to do when you see a collision. All I want is for the sprites to not be allowed to overlap. No bouncing or anything. They just stop. Specifically right now I just have a player and some level tiles that he runs into.

It sounds simple, but it's not. It has to be very precise or weird things happen. I've been trying to fix this all day with strange mixed results. Sometimes my player gets stuck in the floor and can't move left or right. When I fix that, he can walk through blocks left or right.

So my current setup thinks like this: Try moving the player where he wants to go. Then ask the map if his tile collides with anything. If so, the map says how many pixels of overlap there are in each of the four directions. The tricky part now is how the player should react to those numbers. When he's on the ground, there's a 1 pixel overlap with the floor, in order for him to know that he's on the ground (otherwise he vibrates between falling and landing on the ground, because without the overlap he thinks there's nothing below him). This one pixel overlap means that the left and right edges are also embedded in the floor and so he can't move.

Is there a good method for getting everything sorted out, using one bounding box for the player? Would it be better to have a separate bounding box for each of his four sides?

Answer 1

One alternative to having the overlap with the ground would be to set his starting location to just over the ground; then always invoke the falling routine.

If his next falling portion would put him overlapping with a ground tile, set a field on the avatar 'is on ground' to true (assuming you need to track that for, say, jumping purposes), and set the y location of the avatar to just over the ground. While he would be constantly 'falling', it would be visually imperceptible.

Another alternative would be what you mentioned, where in you have 4 bounding boxes; the catch to this is you probably don't want the 4 individual corners to be members of any of the boxes; so, if the avatar image is 16x16px, treat it as 4 1x16px bounding boxes on each of the four sides. This will bring with it its own math headaches, but it would work.

As far as handling collisions and jumping; one item I would imagine would work would be to: break the movement into two discrete movement portions, a move on the x axis and a move on the y axis. If the move on the x axis is blocked by a wall, set x coordinate to the further position that is valid (so, x should be value which results in hugging of the wall/platform). Do similar with y axis. At this point, you can also change how speed is handled; setting x/y speed component to 0 if appropriate. This may not be desirable depending on the game feel you are looking for.

Answer 2

It sounds like you are trying to roll your own stuff, but I've been prototyping some stuff with Chipmunk Dynamics, a nice little 2D physics library that is open source so you can look and see how they do it if you want ideas.

http://code.google.com/p/chipmunk-physics/

Answer 3

When I fix that, he can walk through blocks left or right.

When at this stage are you sure you are getting correct results from collision detection on walking in to a block?

Then ask the map if his tile collides with anything. If so, the map says how many pixels of overlap there are in each of the four directions.

You use the data from this to disallow x motion if there is any x overlap in the direction of travel. Personally I would have overlap on the right return a positive and overlap on the left return negative then only allow x motion if xoverlap is zero or the sign is opposite from the direction of motion. Then for Y all you need to do is the same thing except check against 1 instead of zero.

Answer 4

I think I've got it. Mostly inspired by stonemetal's answer. My most recent flaw was that the player was able to "hook" onto walls, because his bounding box would be lodged in the wall by one pixel, and then it would land on the edge of the tile below, stopping him.

I solved everything by splitting up x and y motion. Since gravity is a y deal, I made x the priority. See if you're allowed to move horizontally, then cancel that motion if you can't. Then try vertical, and cancel it if you can't. The separation ensures that neither half gets false information from the other (like thinking that you're on the ground, a Y thing, because you're against a wall, which is an X thing). Thanks guys!

Answer 5

Here is a simple box collision test. It's obviously very simple, wait till you do polygon collision testing!

//! (collision detection)
inline BOOL Sprite::TestCollision(Sprite* pTestSprite)
{
  //! Get the collision box.
  RECT& rcTest = pTestSprite->GetCollision();

  //! box collision check.
  return m_rcCollision.left <= rcTest.right && rcTest.left <= m_rcCollision.right &&
         m_rcCollision.top <= rcTest.bottom && rcTest.top <= m_rcCollision.bottom;
}

Now as far as what to do to stop the sprite or bounce or whatever, it goes something like so: (Note: this case is checking collision against a boundary, but basically the same thing is performed with other objects). If it's just axis aligned box collision, all you have to do is align the collision object with the horizontal or vertical edge of the other collision object. If the object collides from the left side, align to the left edge of the other object. Simple. Change the velocities accordingly if you want rebounding or stopping.

In this example, I make test variables with the updated position and then do a collision test, then perform the routine below or just set the new position if no collision. So we are actually fixing it before the collision happens.

// Update the position
POINT ptNewPosition, ptSpriteSize, ptBoundsSize;
ptNewPosition.x = m_rcPosition.left + m_ptVelocity.x;
ptNewPosition.y = m_rcPosition.top + m_ptVelocity.y;
ptSpriteSize.x = m_rcPosition.right - m_rcPosition.left;
ptSpriteSize.y = m_rcPosition.bottom - m_rcPosition.top;
ptBoundsSize.x = m_rcBounds.right - m_rcBounds.left;
ptBoundsSize.y = m_rcBounds.bottom - m_rcBounds.top;

// Check the bounds
// Wrap?
if (m_baBoundsAction == BA_WRAP)
{
  if ((ptNewPosition.x + ptSpriteSize.x) < m_rcBounds.left)
   ptNewPosition.x = m_rcBounds.right;
  else if (ptNewPosition.x > m_rcBounds.right)
   ptNewPosition.x = m_rcBounds.left - ptSpriteSize.x;
  if ((ptNewPosition.y + ptSpriteSize.y) < m_rcBounds.top)
   ptNewPosition.y = m_rcBounds.bottom;
  else if (ptNewPosition.y > m_rcBounds.bottom)
   ptNewPosition.y = m_rcBounds.top - ptSpriteSize.y;
}
// Bounce?
else if (m_baBoundsAction == BA_BOUNCE)
{
  BOOL bBounce = FALSE;
  POINT ptNewVelocity = m_ptVelocity;
  if (ptNewPosition.x < m_rcBounds.left)
  {
   bBounce = TRUE;
   ptNewPosition.x = m_rcBounds.left;
   ptNewVelocity.x = -ptNewVelocity.x;
  }
  else if ((ptNewPosition.x + ptSpriteSize.x) > m_rcBounds.right)
  {
   bBounce = TRUE;
   ptNewPosition.x = m_rcBounds.right - ptSpriteSize.x;
   ptNewVelocity.x = -ptNewVelocity.x;
  }
  if (ptNewPosition.y < m_rcBounds.top)
  {
   bBounce = TRUE;
   ptNewPosition.y = m_rcBounds.top;
   ptNewVelocity.y = -ptNewVelocity.y;
  }
  else if ((ptNewPosition.y + ptSpriteSize.y) > m_rcBounds.bottom)
  {
   bBounce = TRUE;
   ptNewPosition.y = m_rcBounds.bottom - ptSpriteSize.y;
   ptNewVelocity.y = -ptNewVelocity.y;
  }
  if (bBounce)
   SetVelocity(ptNewVelocity);
}
// v0.1.1 (collision detection)
// Die?
else if (m_baBoundsAction == BA_DIE)
{
  if ((ptNewPosition.x + ptSpriteSize.x) < m_rcBounds.left || ptNewPosition.x > m_rcBounds.right
   || (ptNewPosition.y + ptSpriteSize.y) < m_rcBounds.top || ptNewPosition.y > m_rcBounds.bottom)
   return SA_KILL;
}
// v0.1.1 ----------------------
// Stop (default)
else
{
  if (ptNewPosition.x  < m_rcBounds.left || ptNewPosition.x > (m_rcBounds.right - ptSpriteSize.x))
  {
   ptNewPosition.x = max(m_rcBounds.left, min(ptNewPosition.x, m_rcBounds.right - ptSpriteSize.x));
   SetVelocity(0, 0);
  }
  if (ptNewPosition.y  < m_rcBounds.top || ptNewPosition.y > (m_rcBounds.bottom - ptSpriteSize.y))
  {
   ptNewPosition.y = max(m_rcBounds.top, min(ptNewPosition.y, m_rcBounds.bottom - ptSpriteSize.y));
   SetVelocity(0, 0);
  }
}