2d Collision detection libgdx

Question

The Logic

The player which is a cube (32 by 32 pixels) checks if their is a cell next to it that has the name Wall. (This is done using a tileset).

To do this collision check I made four checks in this order:

• Is their a wall under the player.
• Is their a wall to the left of the player.
• Is their a wall to the right of the player.
• Is their a wall above the player.

If the player for example touches the wall to the left of him The x coordinates of the player are set to the tile right of the wall(cell) that was collided with.

The Problem

If for example I move the player left, the loop will first check for a collision under the player however this makes the player move up if their is a wall to the left of the player which he is touching. (Note: it doesn't always do this only if the player moved enough pixels to the left). The player should have just stopped moving to the left. Moving up was not desired.

Experiments

I tried adding the left and right check for collision first. This way the bottom check should not see the cell. This made the player teleport to the left and right of the cell the player was currently on because gravity has time now to drag the player down enough pixels. (The player is always affected by gravity and I rather not change this for it wouldn't make sense for an entity like the player to not be affected by it).

Making the movement speed of the player smaller. This did have an affect which was more desired but the players movement speed should not be effected at all as a fix.

The Code

Collision detection code

    // Floor collision
    if (map.isWall(xCoordinates, yCoordinates - 1) || map.isWall(xCoordinates + 31, yCoordinates - 1))
        yCoordinates = ((int)(yCoordinates / 32) * 32) + 32;

    // Left collision
    if (map.isWall(xCoordinates - 1, yCoordinates) || map.isWall(xCoordinates - 1, yCoordinates + 32)) {
        xCoordinates = ((int)((xCoordinates - 1) / 32) * 32) + 32;
        canMoveLeft = false;
    } else
        canMoveLeft = true;

    // Right collision
    if (map.isWall(xCoordinates + 32, yCoordinates) || map.isWall(xCoordinates + 32, yCoordinates + 32)) {
        xCoordinates = ((int)(xCoordinates / 32) * 32);
        canMoveRight = false;
    } else
        canMoveRight = true;

    // Roof collision
    if (map.isWall(xCoordinates, yCoordinates + 32) || map.isWall(xCoordinates + 31, yCoordinates + 32)) {
        canGoUp = false;
    }

The isWall function

public Cell getCellByPixel(float cellPositionX, float cellPositionY) {  

    if (cellPositionX >= 0 && cellPositionY >= 0)
        if (tileid.getCell((int)cellPositionX / 32, (int)cellPositionY / 32) != null)
            return tileid.getCell((int)cellPositionX / 32, (int)cellPositionY / 32 );

    return null;
}

private TiledMapTile getTileByPixel(float cellPositionX, float cellPositionY) {
    if (getCellByPixel(cellPositionX, cellPositionY) != null)
        if (getCellByPixel(cellPositionX, cellPositionY).getTile() != null)
            return getCellByPixel(cellPositionX, cellPositionY).getTile();

    return null;
}

// Check if the cell has a tile with the property of Wall. We can see this in the tsx file.
public boolean isWall(float cellPositionX, float cellPositionY) {
    if (getTileByPixel(cellPositionX, cellPositionY) != null)
        if (getTileByPixel(cellPositionX, cellPositionY).getProperties().get("Wall") != null)
            return true;

    return false;
}

Player movement

private void Movement() {
    if (canMoveLeft)
        if (Gdx.input.isKeyPressed(Keys.A) || Gdx.input.isKeyPressed(Keys.LEFT))
            xCoordinates -= (playerMovementSpeed * Gdx.graphics.getDeltaTime());

    if (canMoveRight)
        if (Gdx.input.isKeyPressed(Keys.D) || Gdx.input.isKeyPressed(Keys.RIGHT))
            xCoordinates += (playerMovementSpeed * Gdx.graphics.getDeltaTime());
}

Answer 1

A different approach for collision resolution

Good question, your workflow seems to be the: (1) move the player, (2) check if the player is inside a wall, and (3) try to push the player out of the wall if he is inside of it.

A possible issue here, is that once you are inside of a wall, you're never really sure where to push the player to. Furthermore, really fast-moving objects (such as bullets) might be able to jump through walls altogether (e.g. if your wall is 32px wide, and the bullet is traveling 128px per frame).

A different approach could be the following: (1) check if there is a wall where the player would be placed, (2.A) if there is no wall, move the player, or (2.B) if there is a wall, don't move the player.

This resolves the first issue, where to put the player when he ends up inside a wall. However, we can still move through walls if the player is moving too fast. Additionally, the player won't stop right next to the wall. E.g. if the player is moving 8px per frame, and he is 4px away from the wall, he will stop right there (as he would end up inside the wall), whereas you actually want him to stop right next to the wall at a 0px distance.

Poor man's approach to pixel perfect collisions

A simple way to resolve this issue that works on walls of any shape (even slanted ones) is to perform multiple collision checks. E.g. if your player object is moving at 8px per frame, instead of collision checking one 8px movement, you would check 8 1px movements. This way the player could decide to make 4 1px movements, until he is snug against the wall, and not perform the next 4 1px movements. In terms of code, you would be replacing this:

if (CollisionAt(player.x + 8, player.y) == false) { 
  player.x += 8;
}

by this:

for(int i = 0; i < 8; i++) {
  if (CollisionAt(player.x + 1, player.y) == false) { 
    player.x += 1;
  }
}

Obviously, once you hit the wall, you can stop your for-loop as all succeeding collision checks will yield a collision:

for(int i = 0; i < 8; i++) {
  if (CollisionAt(player.x + 1, player.y) == false) { 
    player.x += 1;
  } else {
    break;
  }
}

Additionally, you probably want both horizontal and vertical movement. You could simply perform those in succession, which means collision checking is performed in an L-shape (similar to the movement of a knight in chess). Usually this is a fine approximation for true diagonal movement. Let's say your velocity vector is composed of velocityX and velocityY, the code becomes:

for(int i = 0; i < velocityX; i++) {
  if (CollisionAt(player.x + sign(velocityX), player.y) == false) { 
    player.x += sign(velocityX);
  } else {
    break;
  }
}
for(int i = 0; i < velocityY; i++) {
  if (CollisionAt(player.x, player.y + sign(velocityY)) == false) { 
    player.y += sign(velocityY);
  } else {
    break;
  }
}

where the sign(x) function is 1 for a positive x and -1 for a negative x. The above approach resolves the problem of jumping through walls when moving too fast, as all intermediate positions are checked. Additionally, it also makes your character stop right next to walls. Even better, your character wil even stop snug to corners when performing diagonal movement, similar to "wall sliding" in FPS games.

A possible improvement

The above is a "poor-man's approach" however, as it becomes more computationally expensive the faster your player moves. Unless your game contains thousands of player characters, you are probably just fine.

A more optimized approach would be to use mathematical equations to find the collision-points for various kinds of geometry in one shot. For example, the problem of finding the collision point between two rectangles, where one is traveling along a defined movement vector can be solved in one equation. Many equations exist for various shapes and purposes. I personally read Collision Detection in Interactive 3D Environments by Gino van den Bergen and found it a great resource for the mathematics behind collision detection. If you search for "collision detection/resolution" or "physics engine development" you'll find a lot of nice alternatives.

Using these equations, your movement codes becomes something along the lines of:

float closestCollision = inf;
for(Wall wall : allWallsInTheGame) {
  float t = FindEntryPoint(player, wall, velocityVector);
  if (t < closestCollision) {
    closestCollision = t;
  }
}
player.position += t * velocityVector; 

Where FindEntryPoint() caculates how far you can move along the velocity vector before hitting an object. If it returns 0, it means you are instantly hitting a wall, if it returns 1 it means you can travel over the full vector.

This is a lot faster, as you are only iterating over all walls once, rather then once for every 1px movement. After all, the CollisionAt() function in the poor man's solution has to iterate over all walls as well.

Solution to your problem

To summarize all of the above: a simple approach would be to make multiple small 1px movements. Rather then trying to solve the problem when the player ends up inside a wall, you could check before making the move. This approach is fine, but definitely not optimized. For an optimized solution you want to use one-shot equations for finding collision entry points.