Tilemap collision resolution between two tiles

Question

I have a problem with collision resolution with my tilemap. I have a ball which collides off the tiles. The collisions work fine, except for when the collision happens between two tiles. Then my collision resolution gets glitchy, and the ball flies in a wrong direction. My ball is a rectangle, and the tiles are rectangles.

Here is a .gif which demonstrates the problem:

The ball should reflect off the tiles one at a time.

The algorithm works like this:

1. Apply movement, after which check and resolve collisions.
2. Find out the tiles the ball overlaps.
3. If the tile being checked is not passable:
   • Find out how much the ball is overlapping the tile's X and Y axes.
   • Resolve collision by moving the ball out of the tile only on the shallow axis. (Whichever axis is least penetrated).
   • Move on to the next tile.
4. If the tile being checked is passable, do nothing.

I have read that the problem with this minimum-displacement-technique is that after resolving a collision, it is possible that the ball could be moved to another collision. The fix should be, that just run the algorithm second time. I have tried this, but it did not help. Here is my collision handling code, in C++:

void PlayState::handleCollisions() {

// Get ball bounding box.
sf::FloatRect ballBounds = ball.sprite.getGlobalBounds();

// Find out the nearby tiles.
int leftTile = (int)floor((float)ballBounds.left / level1.TILE_WIDTH);
int rightTile = (int)ceil(((float)(ballBounds.left + ballBounds.width) / level1.TILE_WIDTH)) - 1;
int topTile = (int)floor((float)ballBounds.top / level1.TILE_HEIGHT);
int bottomTile = (int)ceil(((float)(ballBounds.top + ballBounds.height) / level1.TILE_HEIGHT)) - 1;

// For each potentially colliding tile,
for(int y = topTile; y <= bottomTile; ++y) {
    for(int x = leftTile; x <= rightTile; ++x) {

        // If this tile is collidable,
        TileCollision collision = getCollision(x, y);
        if(collision == Impassable) {

            // Determine collision depth (with direction) and magnitude.
            sf::FloatRect tileBounds = getTileBounds(x, y);
            sf::Vector2f depth = Collision::getIntersectionDepth(ballBounds, tileBounds);

            if(depth != sf::Vector2f(0, 0)) {
                float absDepthX = std::abs(depth.x);
                float absDepthY = std::abs(depth.y);

                // Resolve the collision along the shallow axis.
                if(absDepthY < absDepthX) {

                    // Resolve the collision along the Y axis.
                    ball.sprite.setPosition(ball.sprite.getPosition().x, ball.sprite.getPosition().y + depth.y);

                    // Perform further collisions with the new bounds.
                    sf::FloatRect ballBounds = ball.sprite.getGlobalBounds();

                    // Y-distance to the tile center.
                    if(distanceY < 0) {
                        std::cout << "Collided from TOP." << std::endl;
                        ball.velocity.y = -ball.velocity.y;
                    }
                    else {
                        std::cout << "Collided from BOTTOM." << std::endl;
                        ball.velocity.y = -ball.velocity.y;
                    }
                }
                else {
                    // Resolve the collision along the X axis.
                    ball.sprite.setPosition(ball.sprite.getPosition().x + depth.x, ball.sprite.getPosition().y);

                    // Perform further collisions with the new bounds.
                    sf::FloatRect ballBounds = ball.sprite.getGlobalBounds();

                    // X-distance to the tile center.
                    if(distanceX < 0) {
                        std::cout << "Collided from LEFT." << std::endl;
                        ball.velocity.x = -ball.velocity.x;
                    }
                    else {
                        std::cout << "Collided from RIGHT." << std::endl;
                        ball.velocity.x = -ball.velocity.x;
                    }
                }
            }
        }
    }
}
}  

I tried to run the algorithm second time, like this:

void PlayState::update(sf::Time deltaTime) {

    ball.update(deltaTime);

    handleCollisions();
    handleCollisions();
}

What can I do fix this?

Answer 1

The only correct way to do collision detection is to involve velocity vector in calculations.

You should test not only discrete positions but whole line between them. At least you'll be able to detect all collisions. E. g. one on a picture below is not detectable when you only test current position (marked 1 and 2)

" " "|2
 " " /<- second 'collision' point
" " /|
___/_|
  /^--collision point
 1

You should know at least current and previous coordinate (which is current minus velocity by delta t). So you have to compute coordinates of possible collision points, find, which one is closer to start and then recalculate path after collision point.

ADD: How to find and compute collision points.

first, you have to find which edges your ball crosses. For rectangular grid it is not too difficult: if previous and current coordinate is in different row (column) then row (column) edge is crossed.

  |     |      |     |      |   1 |     |     | 1
--+-----+--  --+-----+--  --+-----+-- --+-----+--
  |   1 |      |     | 1    |     |     |     |
  | 0   |      |  0  |      |  0  |     | 0   |
--+-----+--  --+-----+--  --+-----+-- --+-----+--
  |     |      |     |      |     |     |     |
none crossed    column        row         both

Then you should solve ball trajectory equation (x0, y0 -- previous point, vx, vy -- velocity) against collision edge equation (x = xc -- crossed vertical edge coordinate):

x = x0 + t⋅vx    y = y0 + t⋅vy   x = xc

and vertical wall with equation x = xc, to find yc = y (y coordinate) and tc = t (time) of collision you'll need to solve equation

t = (xc - x0)/vx   y = y0 +t⋅vy (time and y coord of collision)

For horisontal edges same apply with x and y swapped.

When both x and y edges are crossed select one which crossed earlier (have less t)

           |  1
           | /
           |/                   Here, point a is a row collision
          b*<---                            b is a column collision
          /|                     t[a] should be less than t[b]
        a/ |                       because is closer to trajectory start
   -----*--+-------- xc[row]
       /   |
      0    |
           |
          yc[col]

Ofcourse, when you calculate one collision and update coords and velocity you should recalculate collision as there may be more of them:

 ----*--+
    / \ |
   0   \|
        *
       /|
      1

Answer 2

I have implemented similar collision detection in a flash game from scratch. I found that it was easier and more accurate to model the ball as a single point, and its path as a vector. To allow for the desired size of the ball -- radius r padding was added to the edges of the boxes.

The problem becomes detecting the intersection of the line segment of the ball (ptFrom..ptTo) and the nearby blocks. If multiple intersections, use the one nearest ptFrom. Repeat the collision detection using the reflected remainder of the line segment until there are no more collisions.