Circle-Rectangle collision in a tile map game

Question

I am making a 2D tile map based putt-putt game.

I have collision detection working between the ball and the walls of the map, although when the ball collides at the meeting point between 2 tiles I offset it by 0.5 so that it doesn't get stuck in the wall. This aint a huge issue though.

  if(y % 20 == 0) {
    y+=0.5;
  }

  if(x % 20 == 0) {
    x+=0.5;
  }

Collisions work as follows

1. Find the closest point between each tile and the center of the ball
2. If distance(ball_x, ball_y, close_x, close_y) <= ball_radius and the closest point belongs to a solid object, collision has occured
3. Invert X/Y speed according to side of object collided with

The next thing I tried to do was implement floating blocks in the middle of the map for the ball to bounce off of. When a ball collides with a corner of the block, it gets stuck in it. So I changed my determineRebound() function to treat corners as if they were circles. Here's that functon:

   `i and j are indexes of the solid object in the 2d map array. x & y are centre point of ball.`
   void determineRebound(int _i, int _j) {
     if(y > _i*tile_w && y < _i*tile_w + tile_w) {
        //Not a corner
        xs*=-1;
      } else if(x > _j*tile_w && x < _j*tile_w + tile_w) {
        //Not a corner
        ys*=-1;
      } else {
        //Corner       
        float nx = x - close_x;
        float ny = y - close_y;
        float len = sqrt(nx * nx + ny * ny);
        nx /= len;
        ny /= len;

        float projection = xs * nx + ys * ny;
        xs -= 2 * projection * nx;
        ys -= 2 * projection * ny;
      }
    }

This is where things have gotten messy. Collisions with 'floating' corners work fine, but now when the ball collides near the meeting point of 2 tiles, it detects a corner collision and does not rebound as expected.

I'm a bit in over my head at this point. I guess I'm wondering if I'm going about making this sort of game in the right way. Is a 2d tile map the way to go? If so, is there a problem with my collision logic and where am I going wrong?

Any advice/feedback would be great.

Answer 1

First of your problem is that you're not looking in a further perspective. The ball blocks itself on a wall - just move it 0.5 pixels away. Why not try to unblock it instead? Later you treat a corner like a circle (do you mean a point? If not, I don't understand the idea and it makes me dizzy when I try).

It's OK to do quick, dirty fixes and try if they work. But after every such fix you should consider changing your base - well, you actually did that by asking the question, so I'll better get to the answer:

You have some easy conditions for your ball colliding with terrain, because:

• terrain is made of squares, that are very easy to define mathematically, and therefore it's easy to detect collision (just check if X is higher then square's X but lesser then square's X plus square's width, then do same with it's Y and height)
• additionally squares are tiles, that is, you have a grid.

So we have a situation:

1. We assume the ball is never larger then a tile (or a cell of the grid)
2. Therefore our ball takes usually one, but sometimes up to 4 cells as the lower ball on the picture.
3. We first treat the ball as a cross. If we want the collision to be pixel-perfect, then we can't treat the ball as a square, because sometimes where square would take fourth cell with it's corner, a circle doesn't reach. On example picture, top ball treated as a square would take a cell on left and down from it, while it shouldn't.
4. To count if the ball takes fourth cell, we treat it like a circle. That's a little bit less or more tricky, depends on how accurate you want your collision detection to be. Solution for perfect accuracy is to check two points that extend most:

function xToGrid ( x:Number ):int {
    return Math.floor ( x / 20 );
}

function yToGrid ( y:Number ):int {
    return Math.floor ( y / 20 );
}

/**
 * assuming the ball is not bigger then tile/cell.
 */
function markTilesAsOccupiedByBall ( x:int, y:int, r:int ):void {
    var left:int = x - r;
    var right:int = x + r;
    var top:int = y - r;
    var bottom:int = y + r;

    var centerTileX:int = xToGrid ( x );
    var centerTileY:int = yToGrid ( y );

    var localPosX = x % 20;
    var localPosY = y % 20;

    var x1:Number;
    var y2:Number; 

    if ( localPosX < 10 ) x1 = localPosX;
    else x1 = 20 - localPosX;
    x1 += .1; //to actually go outside the cell

    if ( localPosY < 10 ) y2 = localPosY;
    else y2 = 20 - localPosY;
    y2 += .1; //to actually go outside the cell

    //Pitagoras: r^2 = x^2 + y^2
    // r*r = x1*x1 + y1*y1
    // we don't know y1
    // y1*y1 = r*r - x1*x1
    var y1:Number = Math.sqrt ( r * r - x1 * x1 );

    // r*r = x2*x2 + y2*y2
    // we don't know x2
    var x2:Number = Math.sqrt ( r * r - y2 * y2 );

    if ( localPosX < 10 ) {
        x1 = x - x1;
        x2 = x - x2;
    } else {
        x1 = x + x1;
        x2 = x + x2;
    }

    if ( localPosY < 10 ) {
        y1 = y - y1;
        y2 = y - y2;
    } else {
        y1 = y + y1;
        y2 = y + y2;
    }

    //it is possible that all below operations assign true to same tile!
    //You should delete duplicates especially for optimization,
    //but duplicates could also make some mechanisms trigger more than once
    tilesOccupied.clear();
    tilesOccupied.push ( [xToGrid(left), centerTileY] );
    tilesOccupied.push ( [xToGrid(right), centerTileY] );
    tilesOccupied.push ( [centerTileX, yToGrid(top)] );
    tilesOccupied.push ( [centerTileX, yToGrid(bottom)] );
    //the "corner":
    tilesOccupied.push ( [xToGrid(x1), yToGrid(y1)] );
    tilesOccupied.push ( [xToGrid(x2), yToGrid(y2)] );
}


function detectCollision ():void {
    markTilesAsOccupiedByBall ( ball.x, ball.y, ball.radius );
    for ( var i:int = 0; i < tilesOccupied.length; i++ ) {
        if ( grid [ tilesOccupied[i][0], tilesOccupied[i][4] ] == GridType.WALL ) {
            //make some action
        }
    }
}

You should substitute '20' literals with some CELL_WIDTH constant. Keep in mind this could be optimized a lot, but I didn't want e.g. mess with minus signs, because the equations would be a lot less readable if I did.

As for collision-resolution I would move the circle back as in another answer I made. As the question was deleted, I'll just paste it here:

1. Get a list of nearby rectangles.
2. Iterate through each of them:
   1. If you collide with the red rectangle, move the green rectangle outside of it's boundaries (is very easy with rectangles) - in the way where it came from (vector opposite to original movement vector).
   2. Check which property (x or y) you changed more, and change the other respectively (in the example you have -x;-y vector, then if you increased y by 10, you also need to increase y by 10 to make sure you're backing up to a position where there's surely room for your rectangle)
3. If you moved player Rectangle, go to point 2. and check for collisions again.

4. If you want playerRectangle not to lose full momentum when hitting a wall, you can update it's vx and vy by smoothEffectX and smoothEffectY and repeat.

   

   The code not tested nor optimized, but still is fast and should show you the idea.

   //main actors in the drama:
   var possiblyCollidingRectangles:Array;
   var playerRectangle:Rectangle;
   var vx:int;
   var vy:int;
   var smoothEffectX:int;
   var smoothEffectY:int;
   //Math.abs ( vx ) == Math.abs ( vy )
   
   // [...]
   
   playerRectangle.x += vx;
   playerRectangle.y += vy;
   var movedBack:Boolean = false;
   do {
      for each ( var rect:Rectangle in possiblyCollidingRectangles ) {
         if ( collides (rect, playerRectangle) ) {
            var boundaries:Boundaries = rect.getBoundaries();
            var x:int = getHorizontalBoundary ( boundaries );
            var y:int = getVerticalBoundary ( boundaries );
            movePlayerRectangleBack ( x, y );
            movedBack = true;
         }
   } while ( movedBack );
   
   function getHorizontalBoundary ( boundaries:Boundaries ):int
   {
      if ( vx > 0 ) return boundaries.left;
      else return boundaries.right;
   }
   
   function getVerticalBoundary ( boundaries:Boundaries ):int
   {
      if ( vy > 0 ) return boundaries.top;
      else return boundaries.bottom;
   }
   
   function movePlayerRectangleBack ( x:int, y:int ):void
   {
      var newX:int;
      var newY:int;
   
      if ( vx > 0 ) newX = x - playerRectangle.width; //I assume registration point of rectangle is in it's top-left corner
      else newX = x;
   
      if ( vy > 0 ) newY = y - playerRectangle.height;
      else newY = y;
   
      var dx:int = playerRectangle.x - newX;
      var dy:int = playerRectangle.y - newY;
   
      var newDX:int=
      var newDY:int;
      if ( Math.abs(dx) > Math.abs(dy) ) {
         if ( sameSign() ) newDY = dx;
         else newDY = -dx;
         smoothEffectY = newDY - dy; //maybe dy - newDY, not sure
      } else {
         if ( sameSign() ) newDX = dy;
         else newDX = -dy;
         smoothEffectX = newDX - dx; //maybe dx - newDX, not sure
      }
   
      playerRectangle.x += newDX;
      playerRectangle.y += newDY;
   }
   
   function sameSign ():Boolean //is playerRectangle's vx and vy both negative or both positive?
   {
      return (playerRectangle.vx < 0 && playerRectangle.vy < 0) || (playerRectangle.vx >= 0 && playerRectangle.vy >= 0)
      // or just !(playerRectangle.vx < 0 XOR playerRectangle.vy < 0)
   }
   

Now, I know in your case it's a ball. It's a little harder, but here's how you should do it:

• take the vector (x speed, and y speed) and compute angle from it: var angle:Number = Math.Atan2 ( vx, vy );
• detect if ball approached the square from top, bottom, left or right
• either use cosinus(angle) * ball.radius to offset the ball from square horizontally, or sinus(angle) * ball.radius to offset it vertically, depending on 'through which square's border it came'

And the last point of your question, how to detect ball's callision with a rotated square (I assume it's rotated)

Well, it's even harder. not much, if you understand that you define a square by 4 lines: x1=square.x; x2=square.x+square.width; y1=square.y; y2=square.y+square.width; And a rotated square by also 4 lines: x1=square.x+cosinus(square.angle)*y; x2=square.x+cosinus(square.angle)+square.width; etc.

And you define a circle by: x = Math.abs ( Math.sqrt(r*r-y*y) ) or y = Math.abs ( Math.sqrt(r*r-x*x) )