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:
The player's new position is calculated assuming no collisions. (Not shown in the code below)
A function called
getBorderTilestakes 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,getBorderTilesstill returns all four tiles, but some will be the same.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.
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.
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;
}
}