AABB collision resolution slipping sides

Question

So, I am currently reinventing the wheel (and learning a lot) by trying my hand at making a simple physics engine for my game engine. I have been searching the internet, trying (and failing) to fix my current problem. There are a lot of resources out there on the subject, but none of those that I have found seem to apply to my case.

THE PROBLEM IN SHORT: The collision resolution does not work as intended on some of the corners when two rectangles are colliding. How it fails varies based on the dimensions of the rectangles. What I am looking for is a "shortest overlap" kind of resolution for the collision or another fairly simple solution (I am open for suggestions!). (Scroll down for a better explaination and illustrations).

WARNING: The following code is probably not very efficient...

First of all, here is my physics loop. It simply loops through all of the game entities and checks if they collide with any other game entities. It is not efficient (n^2 and all of that), but it works for now.

updatePhysics: function(step) {
  // Loop through entities and update positions based on velocities
  for (var entityID in Vroom.entityList) {
    var entity = Vroom.entityList[entityID];
    if (entity.physicsEnabled) {
      switch (entity.entityType) {
        case VroomEntity.KINEMATIC:
          entity.pos.x += entity.vel.x * step;
          entity.pos.y += entity.vel.y * step;
          break;

        case VroomEntity.DYNAMIC:
          // Dynamic stuff
          break;
      }
    }
  }
  // Loop through entities and detect collisions. Resolve collisions as they are detected.
  for (var entityID in Vroom.entityList) {
    var entity = Vroom.entityList[entityID];
    if (entity.physicsEnabled && entity.entityType !== VroomEntity.STATIC) {
      for (var targetID in Vroom.entityList) {
        if (targetID !== entityID) {
          var target = Vroom.entityList[targetID];
          if (target.physicsEnabled) {
            // Check if current entity and target is colliding
            if (Vroom.collideEntity(entity, target)) {
              switch (entity.collisionType) {
                case VroomEntity.DISPLACE:
                  Vroom.resolveTestTest(entity, target);
                  break;
              }
            }
          }
        }
      }
    }
  }
},

Here is the code for the actual collision detection. This also seems to work alright.

collideEntity: function(entity, target) {
  if (entity.getBottom() < target.getTop() || entity.getTop() > target.getBottom() ||  entity.getRight() < target.getLeft() ||  entity.getLeft() > target.getRight()) {
    return false;
  }

  return true;
},

Here is where the problems start to pop up. I want the entity to simply be "pushed" out of the target entity and have the velocity set to 0. This works fine as long as both the entity and the target are perfect squares. If let's say the entity (the player figure in the gif) is a rectangle, then the collision will "slipp" when colliding the longest sides (the X axis) with the target (the square). If I swap the player dimensions so that it is short and wide, then the same problem appears for the Y axis instead.

resolveTestTest: function(entity, target) {
  var normalizedX = (target.getMidX() - entity.getMidX());
  var normalizedY = (target.getMidY() - entity.getMidY());
  var absoluteNormalizedX = Math.abs(normalizedX);
  var absoluteNormalizedY = Math.abs(normalizedY);

  console.log(absoluteNormalizedX, absoluteNormalizedY);

  // The collision is comming from the left or right
  if (absoluteNormalizedX > absoluteNormalizedY) {
    if (normalizedX < 0) {
      entity.pos.x = target.getRight();
    } else {
      entity.pos.x = target.getLeft() - entity.dim.width;
    }

    // Set velocity to 0
    entity.vel.x = 0;

    // The collision is comming from the top or bottom
  } else {
    if (normalizedY < 0) {
      entity.pos.y = target.getBottom();
    } else {
      entity.pos.y = target.getTop() - entity.dim.height;
    }

    // Set velocity to 0
    entity.vel.y = 0;
  }

},

Collision on the Y axis works with these shapes

Collision on the X axis slips with these shapes

What can I do to fix this slipping problem? I have been bashing my head against this for the last 5 days, so I would be immensely grateful if some one could help push me in the right direction!

Thank you :)

-- EDIT: --

The slipping also happens if only moving in one direction along the left or right side.

-- EDIT 2 WORKING CODE: -- See my answer below for an example of the working code!

Answer 1

The important logical error you have made is this line:

if (absoluteNormalizedX > absoluteNormalizedY) {

This only works if both entities are square.

Consider a near-extremal case for your X-slipping example: if they almost touch at the corner:

Although the diagram is a little exaggerated, you can see that absoluteNormalizedX < absoluteNormalizedY in this case - your implementation would move on to resolve a vertical collision instead of the expected horizontal one.

---

Another error is that you always set the corresponding velocity component to zero regardless of which side the collision is on: you must only zero the component if is it in the opposite direction to the collision normal, or you won't be able to move away from the surface.

---

A good way to overcome this is to also record the collided face(s) when you do collision detection:

collideEntity: function(entity, target) {
   // adjust this parameter to your liking
   var eps = 1e-3;

   // no collision
   var coll_X = entity.getRight() > target.getLeft() && entity.getLeft() < target.getRight();
   var coll_Y = entity.getBottom() > target.getTop() && entity.getTop() < target.getBottom();
   if (!(coll_X && coll_Y)) return 0;

   // calculate bias flag in each direction
   var bias_X = entity.targetX() < target.getMidX();
   var bias_Y = entity.targetY() < target.getMidY();

   // calculate penetration depths in each direction
   var pen_X = bias_X ? (entity.getRight() - target.getLeft())
                      : (target.getRight() - entity.getLeft());
   var pen_Y = bias_Y ? (entity.getBottom() - target.getUp())
                      : (target.getBottom() - entity.getUp());
   var diff = pen_X - pen_Y;

   // X penetration greater
   if (diff > eps)
      return (1 << (bias_Y ? 0 : 1));

   // Y pentration greater
   else if (diff < -eps) 
      return (1 << (bias_X ? 2 : 3));

   // both penetrations are approximately equal -> treat as corner collision
   else
      return (1 << (bias_Y ? 0 : 1)) | (1 << (bias_X ? 2 : 3));
},

updatePhysics: function(step) {
   // ...
            // pass collision flag to resolver function
            var result = Vroom.collideEntity(entity, target);
            if (result > 0) {
              switch (entity.collisionType) {
                case VroomEntity.DISPLACE:
                  Vroom.resolveTestTest(entity, target, result);
                  break;
              }
            }
   // ...
}

Using a bit flag instead of a boolean array for efficiency. The resolver function can then be re-written as:

resolveTestTest: function(entity, target, flags) {
  if (!!(flags & (1 << 0))) {  // collision with upper surface
      entity.pos.y = target.getTop() - entity.dim.height;
      if (entity.vel.y > 0)  // travelling downwards
         entity.vel.y = 0;
  } 
  else
  if (!!(flags & (1 << 1))) {  // collision with lower surface
      entity.pos.y = target.getBottom();
      if (entity.vel.y < 0)  // travelling upwards
         entity.vel.y = 0;
  }

  if (!!(flags & (1 << 2))) {  // collision with left surface
      entity.pos.x = target.getLeft() - entity.dim.width;
      if (entity.vel.x > 0)  // travelling rightwards
         entity.vel.x = 0;
  } 
  else
  if (!!(flags & (1 << 3))) {  // collision with right surface
      entity.pos.x = target.getRight();
      if (entity.vel.x < 0)  // travelling leftwards
         entity.vel.x = 0;
  }
},

Note that unlike your original code, the above also allows corners to collide - i.e. for velocities and positions to be resolved along both axes.

Answer 2

MY WORKING CODE

So with some help and guidance from the amazing @meowgoesthedog I finally got on the right track and found what I was looking for. The problem (as @meowgoesthedog pointed out) was that my code was really only going to work with squares. The solution was to check the intersection of the colliding bodies and solve based on the shortest intersection. Note: this will probably not be a suitable solution if you need accurate physics with small and fast moving objects. The code for finding the intersection depth is based on this: https://github.com/kg/PlatformerStarterKit/blob/0e2fafb8dbc845279fe4116c37b6f2cdd3e636d6/RectangleExtensions.cs which is related to this project: https://msdn.microsoft.com/en-us/library/dd254916(v=xnagamestudio.31).aspx.

Here is my working code:

My physics loop has not been changed much, except for some better names for some functions.

updatePhysics: function(step) {
  // Loop through entities and update positions based on velocities
  for (var entityID in Vroom.entityList) {
    var entity = Vroom.entityList[entityID];
    if (entity.physicsEnabled) {
      switch (entity.entityType) {
        case VroomEntity.KINEMATIC:
          entity.pos.x += entity.vel.x * step;
          entity.pos.y += entity.vel.y * step;
          break;

        case VroomEntity.DYNAMIC:
          // Dynamic stuff
          break;
      }
    }
  }
  // Loop through entities and detect collisions. Resolve collisions as they are detected.
  for (var entityID in Vroom.entityList) {
    var entity = Vroom.entityList[entityID];
    if (entity.physicsEnabled && entity.entityType !== VroomEntity.STATIC) {
      for (var targetID in Vroom.entityList) {
        if (targetID !== entityID) {
          var target = Vroom.entityList[targetID];
          if (target.physicsEnabled) {
            // Check if current entity and target is colliding
            if (Vroom.collideEntity(entity, target)) {
              switch (entity.collisionType) {
                case VroomEntity.DISPLACE:
                  Vroom.resolveDisplace(entity, target);
                  break;
              }
            }
          }
        }
      }
    }
  }
},

The collision detection remains the same as well.

collideEntity: function(entity, target) {
  if (entity.getBottom() < target.getTop() || entity.getTop() > target.getBottom() ||  entity.getRight() < target.getLeft() ||  entity.getLeft() > target.getRight()) {
    return false;
  }

  return true;
},

Here is the code that basically fixes the problem. The comments in the code should explain what it does pretty well.

getIntersectionDepth: function(entity, target) {
  // Calculate current and minimum-non-intersecting distances between centers.
  var distanceX = entity.getMidX() - target.getMidX();
  var distanceY = entity.getMidY() - target.getMidY();
  var minDistanceX = entity.halfDim.width + target.halfDim.width;
  var minDistanceY = entity.halfDim.height + target.halfDim.height;

  // If we are not intersecting at all, return 0.
  if (Math.abs(distanceX) >= minDistanceX || Math.abs(distanceY) >= minDistanceY) {
    return {
      x: 0,
      y: 0,
    };
  }

  // Calculate and return intersection depths.
  var depthX = distanceX > 0 ? minDistanceX - distanceX : -minDistanceX - distanceX;
  var depthY = distanceY > 0 ? minDistanceY - distanceY : -minDistanceY - distanceY;

  return {
    x: depthX,
    y: depthY,
  };
},

Here is the updated resolving function. It now takes intersection depth in to account when determining axis of collision and then uses the sign of the intersection depth for the colliding axis when determining the direction to resolve.

resolveDisplace: function(entity, target) {
  var intersection = Vroom.getIntersectionDepth(entity, target);
  if (intersection.x !== 0 && intersection.y !== 0) {
    if (Math.abs(intersection.x) < Math.abs(intersection.y)) {
      // Collision on the X axis
      if (Math.sign(intersection.x) < 0) {
        // Collision on entity right
        entity.pos.x = target.getLeft() - entity.dim.width;
      } else {
        // Collision on entity left
        entity.pos.x = target.getRight();
      }

      entity.vel.x = 0;
    } else if (Math.abs(intersection.x) > Math.abs(intersection.y)) {
      // Collision on the Y axis
      if (Math.sign(intersection.y) < 0) {
        // Collision on entity bottom
        entity.pos.y = target.getTop() - entity.dim.height;
      } else {
        // Collision on entity top
        entity.pos.y = target.getBottom();
      }

      entity.vel.y = 0;
    }
  }
},

Thank you all for your help!

Answer 3

The problem may be that you're correcting both X and Y collision based on the same position:

1. Player is at a certain position. Let's check collision.
2. Player's bottom right corner overlaps top left corner of object.
3. X position is corrected: Player is moved to the left.
4. Player's bottom right corner overlaps top left corner of object.
5. Y position is corrected: Player is moved up.
6. End result: The player is moved up and to the left.

You probably need to "get" the player's position again, between checks.