Collision detection shouldn't make object teleport up

Question

Solved, see bottom of post for final algorithm

Background: I am working on a 2D platformer using JS and the HTML canvas element. The level map is tile-based, but the player is not clamped to the tiles. I am using a collision detection algorithm outlined in "Tiny Platformer" on Code inComplete. It largely works except for one edge case (or ''ledge'' case).

The problem:

The player is falling down and also moving right, into the wall. As it falls, it teleports up to the height of the ledge. Instead the player should fall normally without teleporting.

Is there any way to change the algorithm to prevent this behavior? If not, can you suggest an alternate collision detection algorithm? Ideally any fix would not assume the player always falls down, because in the game the player's fall direction switches between up/down/left/right.

The algorithm:

1. The player's new position is calculated assuming no collisions. (Not shown in the code below)

2. A function called getBorderTiles takes an object (the player) and returns the tiles touching each of the player's 4 corners. Since the player is not bigger than a tile, those border tiles are necessarily the only tiles the player is touching. Note that some of these tiles may be the same. For example if the player is only occupying one column, the left-top/right-top tiles will be the same, as will the left-bottom/right-bottom tiles. If this happens, getBorderTiles still returns all four tiles, but some will be the same.

3. It checks these border tiles in the level map (a 2D array) to see if they are solid. If a tile is solid, the object is colliding with that tile.

4. It tests up/down/left/right collision. If the player is moving down and colliding with a down tile but not colliding with the corresponding up tile, the player is colliding down. If the player is moving left and colliding with a left tile but not colliding with the corresponding right tile, it's colliding left. Etc. Up/down checks are performed before left/right checks. The variables that store the border tiles are adjusted if there is an up/down collision before performing the left/right check. For example if the player collides down, it will be pushed into the up tiles, so the BL/BR tiles are now the same as the TL/TR tiles.

5. The player's x, y, and speed are adjusted based on the directions it's colliding in.

Why the algorithm fails:

The bottom right tile is solid but the top right isn't, so (step 4) the player collides down and (step 5) it's pushed up. Also, it collides with the BR tile but not BL, so it collides right and is pushed left. By the end, the player is rendered just above and to the left of the ledge. In effect it's teleported up.

Attempt at solution: I tried to fix this, but it only created another issue. I added a check so that the player only collides with a tile if it's some distance within that tile (say 3px). If the player was only barely in the BR tile, the algorithm would not register a down collision, so the player would not teleport up. However, if the player fell down onto ground in another scenario, it didn't acknowledge the collision until the player got pretty far into the ground. The player jittered when it fell a bit into the ground, got pushed back to the top of the ground, fell again, etc.

Thanks for reading this far. I really appreciate your feedback.

Current algorithm code:

var borderTiles = getBorderTiles(object), //returns 0 (a falsy value) for a tile if it does not fall within the level
      tileTL = borderTiles.topLeft,
      tileTR = borderTiles.topRight,
      tileBL = borderTiles.bottomLeft,
      tileBR = borderTiles.bottomRight,
      coordsBR = getTopLeftXYCoordinateOfTile(tileBR), //(x, y) coordinates refer to top left corner of tile
      xRight = coordsBR.x, //x of the right tile(s) (useful for adjusting object's position since it falls in middle of 4 tiles)
      yBottom = coordsBR.y, //y of the bottom tile(s) (useful for adjusting object's position since it falls in middle of 4 tiles)
      typeTL = tileTL ? level.map[tileTL.row][tileTL.col] : -1, //if tileTL is in the level, gets its type, otherwise -1
      typeTR = tileTR ? level.map[tileTR.row][tileTR.col] : -1,
      typeBL = tileBL ? level.map[tileBL.row][tileBL.col] : -1,
      typeBR = tileBR ? level.map[tileBR.row][tileBR.col] : -1,
      collidesTL = typeTL == TILETYPE.SOLID, //true if the tile is solid
      collidesTR = typeTR == TILETYPE.SOLID,
      collidesBL = typeBL == TILETYPE.SOLID,
      collidesBR = typeBR == TILETYPE.SOLID,
      collidesUp = false,
      collidesDown = false,
      collidesLeft = false,
      collidesRight = false;

//down and up
      if (object.vy < 0 && ((collidesTL && !collidesBL) || (collidesTR && !collidesBR))) {
        collidesUp = true;
        /*The object is pushed out of the bottom row, so the bottom row is now the top row. Change the collides__
        variables as this affects collision testing, but is it not necessary to change the tile__ variables. */
        collidesTL = collidesBL;
        collidesTR = collidesBR;
      } else if (object.vy > 0 && ((collidesBL && !collidesTL) || (collidesBR && !collidesTR))) {
        collidesDown = true;
        /*The object is pushed out of the bottom row, so the bottom row is now the top row. Change the collides__
        variables as this affects collision testing, but is it not necessary to change the tile__ variables. */
        collidesBL = collidesTL;
        collidesBR = collidesTR;
      }

      //left and right
      if (object.vx < 0 && ((collidesTL && !collidesTR) || (collidesBL && !collidesBR))) {
        collidesLeft = true;
      } else if (object.vx > 0 && ((collidesTR && !collidesTL) || (collidesBR && !collidesBL))) {
        collidesRight = true;
      }

      if (collidesUp) {
        object.vy = 0;
        object.y = yBottom;
      }
      if (collidesDown) {
        object.vy = 0;
        object.y = yBottom - object.height;
      }
      if (collidesLeft) {
        object.vx = 0;
        object.x = xRight;
      }
      if (collidesRight) {
        object.vx = 0;
        object.x = xRight - object.width;
      }

UPDATE: Solved with maraca's solution. The algorithm is below. Basically it tests (x then y) and resolved collisions, and then it tests (y then x) and resolves collisions that way. Whichever test results in the player moving a shorter distance is the one that ends up being used.

Interestingly it requires a special case for when the player is colliding in both the top and left direction. Perhaps this relates to the fact that the player's (x, y) coordinate is on its top left corner. In this case, the test that results in the player moving a LONGER distance should be used. It is clear in this gif:

The player is the black box and the yellow box represents where the player would be if it had used the other test (the test that resulted in the player moving a longer distance). Ideally the player shouldn't move into the wall, and instead it should be where the yellow box is. Thus in this scenario the longer-distance test should be used.

Here's the quick and dirty implementation. It is not at all optimized but hopefully it shows the algorithm's steps pretty clearly.

function handleCollision(object) {
  var borderTiles = getBorderTiles(object), //returns 0 (a falsy value) for a tile if it does not fall within the level
      tileTL = borderTiles.topLeft,
      tileTR = borderTiles.topRight,
      tileBL = borderTiles.bottomLeft,
      tileBR = borderTiles.bottomRight,
      coordsBR = getTopLeftXYCoordinateOfTile(tileBR), //(x, y) coordinates refer to top left corner of tile
      xRight = coordsBR.x, //x of the right tile(s) (useful for adjusting object's position since it falls in middle of 4 tiles)
      yBottom = coordsBR.y, //y of the bottom tile(s) (useful for adjusting object's position since it falls in middle of 4 tiles)
      typeTL = tileTL ? level.map[tileTL.row][tileTL.col] : -1, //if tileTL is in the level, gets its type, otherwise -1
      typeTR = tileTR ? level.map[tileTR.row][tileTR.col] : -1,
      typeBL = tileBL ? level.map[tileBL.row][tileBL.col] : -1,
      typeBR = tileBR ? level.map[tileBR.row][tileBR.col] : -1,
      collidesTL = typeTL == TILETYPE.SOLID, //true if the tile is solid
      collidesTR = typeTR == TILETYPE.SOLID,
      collidesBL = typeBL == TILETYPE.SOLID,
      collidesBR = typeBR == TILETYPE.SOLID,
      collidesUp = false,
      collidesDown = false,
      collidesLeft = false,
      collidesRight = false,
      originalX = object.x, //the object's coordinates have already been adjusted according to its velocity, but not according to collisions
      originalY = object.y,
      px1 = originalX,
      px2 = originalX,
      py1 = originalY,
      py2 = originalY,
      vx1 = object.vx,
      vx2 = object.vx,
      vy1 = object.vy,
      vy2 = object.vy,
      d1 = 0,
      d2 = 0,
      conflict1 = false,
      conflict2 = false,
      tempCollidesTL = collidesTL,
      tempCollidesTR = collidesTR,
      tempCollidesBL = collidesBL,
      tempCollidesBR = collidesBR;

  //left and right
  //step 1.1
  if (object.vx > 0) {
    if (collidesTR || collidesBR) {
      vx1 = 0;
      px1 = xRight - object.width;
      conflict1 = true;
      tempCollidesTR = false;
      tempCollidesBR = false;
    }
  }
  if (object.vx < 0) {
    if (collidesTL || collidesBL) {
      vx1 = 0;
      px1 = xRight;
      conflict1 = true;
      tempCollidesTL = false;
      tempCollidesBL = false;
      collidesLeft = true;
    }
  }
  //step 2.1
  if (object.vy > 0) {
    if (tempCollidesBL || tempCollidesBR) {
      vy1 = 0;
      py1 = yBottom - object.height;
    }
  }
  if (object.vy < 0) {
    if (tempCollidesTL || tempCollidesTR) {
      vy1 = 0;
      py1 = yBottom;
      collidesUp = true;
    }
  }
  //step 3.1
  if (conflict1) {
    d1 = Math.abs(px1 - originalX) + Math.abs(py1 - originalY);
  } else {
    object.x = px1;
    object.y = py1;
    object.vx = vx1;
    object.vy = vy1;
    return; //(the player's x and y position already correspond to its non-colliding values)
  }

  //reset the tempCollides variables for another runthrough
  tempCollidesTL = collidesTL;
  tempCollidesTR = collidesTR;
  tempCollidesBL = collidesBL;
  tempCollidesBR = collidesBR;

  //step 1.2
  if (object.vy > 0) {
    if (collidesBL || collidesBR) {
      vy2 = 0;
      py2 = yBottom - object.height;
      conflict2 = true;
      tempCollidesBL = false;
      tempCollidesBR = false;
    }
  }
  if (object.vy < 0) {
    if (collidesTL || collidesTR) {
      vy2 = 0;
      py2 = yBottom;
      conflict2 = true;
      tempCollidesTL = false;
      tempCollidesTR = false;
    }
  }
  //step 2.2
  if (object.vx > 0) {
    if (tempCollidesTR || tempCollidesBR) {
      vx2 = 0;
      px2 = xRight - object.width;
      conflict2 = true;
    }
  }
  if (object.vx < 0) {
    if (tempCollidesTL || tempCollidesTL) {
      vx2 = 0;
      px2 = xRight;
      conflict2 = true;
    }
  }
  //step 3.2
  if (conflict2) {
    d2 = Math.abs(px2 - originalX) + Math.abs(py2 - originalY);
    console.log("d1: " + d1 + "; d2: " + d2);
  } else {
    object.x = px1;
    object.y = py1;
    object.vx = vx1;
    object.vy = vy1;
    return;
  }

  //step 5
  //special case: when colliding with the ceiling and left side (in which case the top right and bottom left tiles are solid)
  if (collidesTR && collidesBL) {
    if (d1 <= d2) {
      object.x = px2;
      object.y = py2;
      object.vx = vx2;
      object.vy = vy2;
    } else {
      object.x = px1;
      object.y = py1;
      object.vx = vx1;
      object.vy = vy1;
    }
    return;
  }
  if (d1 <= d2) {
    object.x = px1;
    object.y = py1;
    object.vx = vx1;
    object.vy = vy1;
  } else {
    object.x = px2;
    object.y = py2;
    object.vx = vx2;
    object.vy = vy2;
  }
}

Answer 1

It happens because you first detect collisions in both directions and afterwards you adjust the position. "up/down" is updated first (direction of gravity). Adjusting "left/right" first will only make the problem worse (after each fall you might be teleported right or left).

The only quick and dirty fix I could come up with (gravitation-invariant):

1. Calculate the collision of the two relevant points in one direction (e.g. when going left only the left two points matter). Then adjust speed and position in that direction.

2. Calculate the collision of the two (adjusted) relevant points in the other direction. Adjust position and speed of that directin on collision.

3. If there was no collision in step 1. then you can persist the changes and return. Otherwise calculate the distance dx + dy compared to the original position before step 1.

4. Repeat step 1. to 3. but this time you start with the other direction first.

5. Do the change with the smaller distance (unless you already found a good change in step 3.).

EDIT: Example

sizes: sTile = 50, sPlayer = 20
old position (fine, top-left corner): oX = 27, oY = 35
speeds: vX = 7, vY = 10
new position: x = oX + vX = 34, y = oY + vY = 45  =>  (34, 45)
solid: tile at (50, 50)

1.1. Checking x-direction, relevant points for positive vX are the ones to the right:
     (54, 45) and (54, 65). The latter gives a conflict and we need to correct the
     position to p1 = (30, 45) and speed v1 = (0, 10).

2.1. Checking y-direction based on previous position, relevant points: (30, 65) and
     (50, 65). There is no conflict, p1 and v1 remain unchanged.

3.1. There was a conflict in step 1.1. so we cannot return the current result
     immediately and have to calculate the distance d1 = 4 + 0 = 4.

1.2. Checking y-direction first this time, relevant points: (34, 65) and (54, 65).
     Because the latter gives a conflict we calculate p2 = (34, 30) and v2 = (7, 0).

2.2. Checking x-direction based on step 1.2., relevant points: (54, 30) and (54, 50).
     There is no conflict, p2 and v2 remain unchanged.

3.2. Because there was a conflict in step 1.2. we calculate the distance d2 = 15.

5.   Change position and speed to p1 and v1 because d1 is smaller than d2.