2d Rectangle Collision Resolution

Question

My Journey...

I've long struggled with rectangle to rectangle collision resolution. I've been making games for almost 10 years and still have yet to find a foolproof, reliable strategy.

When doing research on 2d, rectangle to rectangle collision resolution, I find myself digging through piles of collision detection, or other topics that have nothing to do with my search for truth (circle to rectangle, other detection methods...) For me, detecting collision has never been the issue...

if player.x + player.width > box.x and
   player.x < box.x + box.width and
   player.y + player.height > box.y and
   player.y < box.y + box.height then
     // A collision has been detected...
     // But now I am lost.....

_{Assuming both the player and box objects are positioned at their upper left corner}

---

The Rectangular Paradox...

For those brave enough, there is the path of chaos, torture, and unknown horrors available... The road known as "creating your own". I have chosen to walk this path many times, never to find the answers I'm looking for. I'm sure I share some quarrels of this road with fellow developers.

At first you might think it a simple task: "Once you know the rectangles are overlapping, how difficult can it really be to push one out of the other?" Oh boy, how I miss that sweet innocence...

Let us say, the player in the above example is falling down on top of the box, and we want it to stop and be pushed back to the top of the box. Easy, right? We can just do a simple check if the player is above the box, and if so, push him up to the top.

// We know the player is overlapping with the box..
if player.y < box.y then
  player.y = box.y - player.height

Done. Tested and proven to work. But, let's say now we want the player to stop at the left side of the box as well..

if player.x < box.x then
  player.x = box.x - player.width

Looks like it should work fine right? But no. Upon testing you move the player to collide with the left side of the box, and bam. Suddenly, he has immediately moved to the top of the box.

Why? The player can be both above the box, and to the left of the box at the same time. So one seems to end up always being favored over the others. To mitigate this I have written 3 nested if statements, 50 line chunks of code for each side of the rectangle, and wasted near weeks of my life..

---

Conclusion

Although I walk my journey alone - I know there are others, battling the same demonic mystery of rectangle to rectangle collision resolution. And also.. Those who have conquered it...

I'm hoping someone can help me understand their solidified, proven methods of resolution. To help me and any other developers reading this right now, become level 100 devs.

---

I made a codepen for anyone who is interested to use as a playground for showcasing resolution methods.

Answer 1

The challenge you're facing is how to determine where the moving rectangle came from by looking at the current position of the moving rectangle and the rectangle it's crashing into, and as you're finding positions alone don't give that information. You have to look at the last movement of the moving rectangle to be able to just push it outside of the other one.

Here is a simple example* built into your codepen illustrating a simple way this can be done.

//*** DETECTING & RESOLVING COLLISION ***//
handleCollisions() {
  var player = this.player;

  // As long as they are colliding (Be careful for infinite loops)
  while (this.hasCollision()) {
    // get current x direction
    const xDir = this.getXDirection();
    // get current y direction
    const yDir = this.getYDirection();
    // move the player 1 unit back the direction it came from
    player.x -= xDir;
    player.y -= yDir;
  }
  ...
}
// returns true if the player is colliding with the box
hasCollision() {
  const player = this.player;
  const box = this.box;
  return (
    player.x + player.width / 2 > box.x - box.width / 2 &&
    player.x - player.width / 2 < box.x + box.width / 2 &&
    player.y + player.height / 2 > box.y - box.height / 2 &&
    player.y - player.height / 2 < box.y + box.height / 2
  );
}
// returns 1, -1, or 0 if not moving
getXDirection() {
  if (this.controls.isDown("right")) {
    return 1;
  } else if (this.controls.isDown("left")) {
    return -1;
  } else {
    return 0;
  }
}
// returns 1, -1, or 0 if not moving
getYDirection() {
  if (this.controls.isDown("up")) {
    return -1;
  } else if (this.controls.isDown("down")) {
    return 1;
  } else {
    return 0;
  }
}

Keep in mind this is just a starting point for the possibilities of resolving collisions like this. You could check direction and relative velocity of two moving rectangles to support both rectangles moving.

In response to a comment about not being able to slide along an edge here is a link to an enhanced version of this same method that allows sliding along edges when colliding. All that changed was to separate the X and Y checks into separate loops. I hope this helps demonstrate how easily this basic method can be enhanced to meet specific needs.

*Please note that this is not a perfect implementation. Right now the player will clip into the box until you release the move command; however that is a matter of changing this check to happen before rendering, and I would consider that off topic for this question as of now.

Answer 2

I don't know if there is a perfect method, at least not anything I have found, but I can show you what I did that worked for me.

Start by getting the inside rectangle of the collision. This is the rectangle created by the two overlapping rectangles. If the language you are using doesn't have a function that returns this you will need to figure out how to get the value. You can use the connecting points and one corner from each colliding rectangle to get the data you will need for the inside rectangle.

If the inside rectangle's width is less then the hight then your going to adjust the x coordinate of the moving rectangle, else you will adjust the y coordinate. If you get a tie your going to have to pick one depending on whether you use (less then) or (less then or equals to) when comparing the inside rectangles width and hight.

Next figure out which corners of the moving rectangle are outside the intersecting rectangle. Based on that you will know if you have to adjust (up or down) or (left or right). For instance say the (width of the inside rectangle is less than the hight) and (the top right and bottom right points of the moving rectangle are outside the intersecting rectangle) then adjust the moving rectangle's x coordinate to the right.

You will run into a problem wall sliding like this depending on how you iterate over the tiles. If your wall sliding and collide with another tile it could push you back from the direction you are heading. To fix this calculate the areas of the inside rectangles created by the multiple collisions with the multiple tiles. Adjust for the largest area. Do not make all adjustments from all collisions. Only adjust for the collision that creates an inside rectangle with the largest area. Then check for more collisions after you update the location of the moving rectangle and only make further adjustments if there are collisions with the new location.

This method avoids having to deal with what direction things are moving and figures it out based on the collision points. If you have thin rectangles this method may not work for you. But if you're using tiles it can work well.

Answer 3

This is probably the problem I struggled with most in the development of both major versions of Scrolling Game Development Kit. So here I will try to describe what the central function that addresses your problem in SGDK2 is doing. It's all wrapped up in a function called ReactToSolid. This function actually doesn't deal strictly with rectangles because SGDK2 allows tiles that are shaped like slopes too.

Before diving into the code, I should explain some of the variables you'll see:

• x - The raw horizontal coordinate of the left side of a sprite. I say raw because this is not an integer and can store a position between pixels to help track, for example, a slow moving sprite that hasn't reached the next pixel yet.
• y - The raw vertical coordinate of the top of the sprite.
• PixelX - The truncated horizontal coordinate (round down to integer)
• PixelY - The truncated vertical coordinate
• dx - The horizontal velocity of the sprite used to determine where the sprite should move next
• dy - The vertical velocity of the sprite
• ProposedPixelX - The next value of PixelX based on current values of x and dx (in other words, x+dx rounded down)
• ProposedPixelY - The next value of PixelY

The rest of the variables will be explained afterward.

And a some general points about this function:

• This function alters the dx and dy properties of a sprite so that when it moves (adjusts its x and y properties by adding dx and dy) it will avoid solid areas of the background.
• This function assumes that the sprite is not already overlapping any solids because once the sprite is overlapping a solid, you've lost a lot of information about how you should avoid the solid based on where you came from. If it is already overlapping, the behavior tends to be that solid edges going through the sprite are ignored.

The code:

public virtual bool ReactToSolid()
{
   Debug.Assert(this.isActive, "Attempted to execute ReactToSolid on an inactive sprite");
   if (m_solidity == null)
      throw new System.ApplicationException("Attempted to execute ReactToSolid on sprite without solidity defined");
   bool hit = false;
   double dyOrig = dy;
   double dxOrig = dx;

   int ProposedPixelY2 = (int)Math.Ceiling(y + dy);
   int SolidPixelWidth = SolidWidth + (int)Math.Ceiling(x) - PixelX;
   if (dy > 0)
   {
      int ground = layer.GetTopSolidPixel(new System.Drawing.Rectangle(PixelX, PixelY + SolidHeight, SolidPixelWidth, ProposedPixelY2 - PixelY), m_solidity);
      if (ground != int.MinValue)
      {
         // Do integer arithmetic before double otherwise strange rounding seems to happen
         dy = ground - SolidHeight - y;
         hit = true;
      }
   }
   else if (dy < 0)
   {
      int ceiling = layer.GetBottomSolidPixel(new System.Drawing.Rectangle(PixelX, ProposedPixelY, SolidPixelWidth, PixelY - ProposedPixelY), m_solidity);
      if (ceiling != int.MinValue)
      {
         // Do integer arithmetic before double otherwise strange rounding seems to happen
         dy = ceiling + 1 - y;
         hit = true;
      }
   }

   if (dx > 0)
   {
      int ProposedPixelX2 = (int)Math.Ceiling(x + dx);
      int PixelX2 = (int)Math.Ceiling(x);
      int rightwall = layer.GetLeftSolidPixel(new System.Drawing.Rectangle(PixelX2 + SolidWidth, ProposedPixelY, ProposedPixelX2 - PixelX2, SolidHeight), m_solidity);
      bool hitWall = false;
      if (rightwall != int.MinValue)
      {
         int maxSlopeProposedY = (int)(y + dy - dx);
         int slopedFloor = layer.GetTopSolidPixel(new System.Drawing.Rectangle(PixelX2 + SolidWidth, maxSlopeProposedY + SolidHeight, ProposedPixelX2 - PixelX2, ProposedPixelY - maxSlopeProposedY), m_solidity);
         if (slopedFloor != int.MinValue)
         {
            int ceiling = layer.GetBottomSolidPixel(new System.Drawing.Rectangle(PixelX2, slopedFloor - SolidHeight, SolidWidth, ProposedPixelY + SolidHeight - slopedFloor), m_solidity);
            if ((ceiling == int.MinValue) && (RidingOn == null))
            {
               int rightwall2 = layer.GetLeftSolidPixel(new System.Drawing.Rectangle(PixelX2 + SolidWidth, slopedFloor - SolidHeight, ProposedPixelX2 - PixelX2, SolidHeight), m_solidity);
               if (rightwall2 == int.MinValue)
                  // Do integer arithmetic before double otherwise strange rounding seems to happen
                  dy = dyOrig = slopedFloor - SolidHeight - 1 - y;
               else
                  hitWall = true;
            }
            else
               hitWall = true;
         }
         else
         {
            maxSlopeProposedY = (int)(y + dy + dx);
            int slopedCeiling = layer.GetBottomSolidPixel(new System.Drawing.Rectangle(PixelX2 + SolidWidth, ProposedPixelY, ProposedPixelX2 - PixelX2, maxSlopeProposedY - ProposedPixelY), m_solidity);
            if (slopedCeiling != int.MinValue)
            {
               slopedCeiling++;
               int floor = layer.GetTopSolidPixel(new System.Drawing.Rectangle(PixelX2, ProposedPixelY + SolidHeight, SolidWidth, slopedCeiling - ProposedPixelY), m_solidity);
               if ((floor == int.MinValue) && (RidingOn == null))
               {
                  int rightwall2 = layer.GetLeftSolidPixel(new System.Drawing.Rectangle(PixelX2 + SolidWidth, slopedCeiling, ProposedPixelX2 - PixelX2, SolidHeight), m_solidity);
                  if (rightwall2 == int.MinValue)
                     dy = dyOrig = slopedCeiling - y;
                  else
                     hitWall = true;
               }
               else
                  hitWall = true;
            }
            else
               hitWall = true;
         }
         if (hitWall)
         {
            // Do integer arithmetic before double otherwise strange rounding seems to happen
            dx = rightwall - SolidWidth - x;
         }
         hit = true;
      }
   }
   else if (dx < 0)
   {
      int leftwall = layer.GetRightSolidPixel(new System.Drawing.Rectangle(ProposedPixelX, ProposedPixelY, PixelX - ProposedPixelX, SolidHeight), m_solidity);
      bool hitWall = false;
      if (leftwall != int.MinValue)
      {
         int maxSlopeProposedY = (int)(y + dy + dx);
         int slopedFloor = layer.GetTopSolidPixel(new System.Drawing.Rectangle(ProposedPixelX, maxSlopeProposedY + SolidHeight, PixelX - ProposedPixelX, ProposedPixelY - maxSlopeProposedY), m_solidity);
         if (slopedFloor != int.MinValue)
         {
            int ceiling = layer.GetBottomSolidPixel(new System.Drawing.Rectangle(PixelX, slopedFloor - SolidHeight, SolidWidth, ProposedPixelY + SolidHeight - slopedFloor), m_solidity);
            if ((ceiling == int.MinValue) && (RidingOn == null))
            {
               int leftwall2 = layer.GetRightSolidPixel(new System.Drawing.Rectangle(ProposedPixelX, slopedFloor - SolidHeight, PixelX - ProposedPixelX, SolidHeight), m_solidity);
               if (leftwall2 == int.MinValue)
                  // Do integer arithmetic before double otherwise strange rounding seems to happen
                  dy = dyOrig = slopedFloor - SolidHeight - 1 - y;
               else
                  hitWall = true;
            }
            else
               hitWall = true;
         }
         else
         {
            maxSlopeProposedY = (int)(y + dy - dx);
            int slopedCeiling = layer.GetBottomSolidPixel(new System.Drawing.Rectangle(ProposedPixelX, ProposedPixelY, PixelX - ProposedPixelX, maxSlopeProposedY - ProposedPixelY), m_solidity);
            if (slopedCeiling != int.MinValue)
            {
               slopedCeiling++;
               int floor = layer.GetTopSolidPixel(new System.Drawing.Rectangle(PixelX, ProposedPixelY + SolidHeight, SolidWidth, slopedCeiling - ProposedPixelY), m_solidity);
               if ((floor == int.MinValue) && (RidingOn == null))
               {
                  int leftwall2 = layer.GetRightSolidPixel(new System.Drawing.Rectangle(ProposedPixelX, slopedCeiling, PixelX - ProposedPixelX, SolidHeight), m_solidity);
                  if (leftwall2 == int.MinValue)
                     dy = dyOrig = slopedCeiling - y;
                  else
                     hitWall = true;
               }
               else
                  hitWall = true;
            }
            else
               hitWall = true;
         }
         if (hitWall)
         {
            // Do integer arithmetic before double otherwise strange rounding seems to happen
            dx = leftwall + 1 - x;
         }
         hit = true;
      }
   }

   dy = dyOrig;

   int ProposedSolidPixelWidth = SolidWidth + (int)Math.Ceiling(x + dx) - ProposedPixelX;
   if (dy > 0)
   {
      ProposedPixelY2 = (int)Math.Ceiling(y + dy);
      int ground = layer.GetTopSolidPixel(new System.Drawing.Rectangle(ProposedPixelX, PixelY + SolidHeight, ProposedSolidPixelWidth, ProposedPixelY2 - PixelY), m_solidity);
      if (ground != int.MinValue)
      {
         // Do integer arithmetic before double otherwise strange rounding seems to happen
         dy = ground - SolidHeight - y;
         hit = true;
      }
   }
   else if (dy < 0)
   {
      int ceiling = layer.GetBottomSolidPixel(new System.Drawing.Rectangle(ProposedPixelX, ProposedPixelY, ProposedSolidPixelWidth, PixelY - ProposedPixelY), m_solidity);
      if (ceiling != int.MinValue)
      {
         // Do integer arithmetic before double otherwise strange rounding seems to happen
         dy = ceiling + 1 - y;
         hit = true;
      }
   }

   if (hit && !double.IsNaN(LocalDX))
      LocalDX += dx - dxOrig;

   return hit;
}

1. The first major check for dy>0 and dy<0 is to determine whether we should be looking for a floor versus a ceiling to determine whether the sprite will be blocked from moving downward or upward.
2. Inside that block, the sprite's vertical velocity is adjusted to stop at the floor or ceiling that it is about to hit. GetTopSolidPixel and GetBottomSolidPixel are functions that return the vertical coordinate of the topmost or bottom-most solid pixel within the specified rectangle. Notice that we're not including the sprite rectangle itself in the area being checked because the sprite should not be overlapping solid already. We're just checking the rectangle that the edge of the sprite is moving through. Also notice that we use a variation ProposedPixelY2 because we want to be sure to check the bottom of the sprite's lowest pixel when looking downward to avoid rounding errors.
3. In the next blocks concerning dx>0 and dx<0 we are basically doing the same check horizontally instead of vertically. But because hills add a lot of complexity, there's a lot more code. Since you're probably not concerned with hills much, I'll try to focus on the rectangular portion of the code.
4. When we check for int.MinValue we're basically checking whether no solid pixel edge was found on the background layer in the requested rectangle. int.MinValue is returned when no solid pixel was found. So basically, if we skip all the slope logic, we are matching the edge of the sprite to the left or right wall toward which it is headed if one was found. (Technically we're adjusting the sprite's dx so that it will match after its position is next updated.) The vast majority of the code here deals with sloped floors and ceilings, which I will ignore.
5. Next we are restoring the original vertical velocity (dy = dyOrig) and re-applying the ceiling and ground check, but this time taking into account not only the vertical movement of the sprite, but also the corrected horizontal movement. We also account for the fact that the sprite is 1 pixel wider when sitting between pixels. Honestly, this code has gotten so refined over the weeks of trial and error that formed it that I can't necessarily explain in detail all the reasons this had to be done, but here's my best attempt:
   • The earlier ground/ceiling check needed to be done ignoring the horizontal velocity because we weren't sure what it would be yet. But we needed a good approximation of the corrected vertical velocity in order to compute a good horizontal velocity. Landing on a floor may cause the sprite to land at a height where it can hit a wall even though it would not have hit that wall if the floor weren't there (if the sprite is taller than 1 tile or is approaching a sloped ceiling).
   • The later ground/ceiling check needed to be done so that the sprite's vertical velocity would be properly adjusted after taking into account the effect of walls on the expected horizontal location of the sprite.
   • The original vertical velocity dyOrig is used as a starting point because the earlier check that was done was not conclusive and we want to basically start over now that we know a good horizontal velocity.
6. The last bit of code dealing with LocalDX only applies when the sprite is riding on top of another sprite (LocalDX is the velocity of the sprite relative to the sprite on which it is riding). The relative velocity is updated according the the change that was applied to the absolute velocity. This prevents platforms from being used as a means to travel through walls. (The vertical equivalent of this logic is in a different function because hitting a floor or ceiling while riding a platform causes the sprite to stop riding.)

Answer 4

Why? The player can be both above the box, and to the left of the box at the same time.

Solve the collision at each axis separately:

• Object moved - test intersection.
• Solve the collision at the horizontal axis based on the direction the object came from, if the object was moving horizontally (hspeed != 0). If the object came from left to right, move the object to the left of the intersected rectangle, if the object came from right to left, move object to the right of the intersected rectangle.
• Horizontal axis solved. Now test intersection again, with the updated position (after solving the horizontal axis), but for the vertical axis.
• Repeat the process of solving the collision, but for the vertical axis.

Another problem is this approach:

if player.x < box.x then
      player.x = box.x - player.width

because:

.---.                  .---.
| A | - - - - - - >  .-|-A |
`---´                | B-|-´
                     `---´

See that object A collide with B, but A was so fast, that it went almost past B, ending up at the right of B. Since your solution doesn't take in consideration the direction the object comes from, only the relative position between the two objects, the result will be incorrect: your algorithm will result (wrongly) in this:

     .---.
.---.| A |
| B |`---´
`---´

Do like in the steps I mentioned, considering the motion of the object.