3
\$\begingroup\$

I have a simple tennis game like Breakout. I have a ball, and a racquet made from a long rectangle. The ball bounces around the walls, and the game terminates when the ball hits the floor. To prevent this, I have a long racquet I can move horizontally that the ball can hit. Each time the ball hits the racquet, the speed of the ball increases.

The speed increases by adding to the number of pixels for each increment of the ball. This means that after a while (around 50 hits), the steps of the ball become quite long. The ball moves at 50 px per frame. With long steps, the ball might just jump over the racquet, and not detect collision.

To prevent this, I was thinking of incrementing the FPS, instead, and keeping the ball speed fixed. This would probably work, but I don't think changing the FPS is the right solution. How should I go about solving collision detection at higher speeds?

\$\endgroup\$
  • 2
    \$\begingroup\$ Increase the amount simulation step (like you suggest), make the paddle thicker, or detect if there is an intersection between the paddle, and the line segment formed by the ball's current position and the ball's previous frame position.. \$\endgroup\$ – Vaillancourt Feb 27 '17 at 19:50
  • \$\begingroup\$ if understand your last sentence: Let's say the ball is 100px above the paddle, and in the next frame the ball is 100px below the paddle, then because the line between the ball at the first frame, and the ball at the second step intersects the paddle, there would be a collision. That sounds very nice :) But! Wouldn't the ball bounce as if it hit the paddle 100px above the paddle? Maybe I should somehow 1 detect the collison, 2 move the ball to the paddle where it would have collided. Hmmm. Also thanks for your response :) \$\endgroup\$ – tore Feb 27 '17 at 19:57
  • 3
    \$\begingroup\$ Or calculate that the collision occurred at t = 0.5, so perform the 'bounce' at t = 0.5, and simulate what happens between t = 0.5 and t = 1.0: the ball will have bounced at the end of the frame. THB, I have never done this :P \$\endgroup\$ – Vaillancourt Feb 27 '17 at 20:02
  • \$\begingroup\$ Oh cool, I will play a bit with this :) thanks again! Unfortunately I can't upvote you yet :/ \$\endgroup\$ – tore Feb 27 '17 at 20:19
  • 1
    \$\begingroup\$ No worries, what I wrote is not an answer, it's just a comment. Maybe someone will come up with a real answer, or someone will suggest a duplicate :) \$\endgroup\$ – Vaillancourt Feb 27 '17 at 20:23
3
\$\begingroup\$

What you're looking for is called Continuous Collision Detection.

A simple implementation would be to do a raycast after each step to see if something was in between the two steps.

If you don't have access to physics simulations like raycasts, you could also slowly resolve the collision yourself over multiple iterations.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Did not know about raycast. Thank you for you response! \$\endgroup\$ – tore Mar 3 '17 at 18:06
1
\$\begingroup\$

Note: In the solution uses the previous position to check for collisions over multiple iterations. It is not perfect, I explain why.

Keep the old position

The key to detect if the ball has gone through an obstacle is to keep track of where it was, so you can check if the segment from where it was to where it is now intersects the obstacle.

To implement the check, you break down the obstacle into segments. For each one, you check if the segment formed by the old to the new position collides with it. Some optimizations are possible when the obstacles are axis-aligned rectangles.

That is enough to handle collisions with stationary obstacles. As far as the obstacle don't move, there is no problem.

The moving racquet

When you have a moving obstacle, it becomes trickier... if the obstacle approaches the ball from behind, the old position would be inside the obstacle before the ball itself. This will make the detection fail. In addition, this problem will happen even at small speed.

The solution is to work in the frame of reference of the obstacle. That way, for all uses and purposes, the obstacle is stationary. There is no need to convert the speed vector to the other system; all you need to convert is the segment from the old to the new position, then use that transformed segment to check for collisions.

The implementation is simple; add the displacement of the obstacle since the last update to the old position of the ball, et voila.

You may also want to compute the instantaneous velocity of the racquet, and add that to the speed of the ball... otherwise it feels odd that you push the racquet against the ball and it just sort of "sweeps it" without changing the speed. To clamp the speed added by the racquet is strongly advised!

WARNING: Do not allow the racquet to overlap the wall. If you trap the ball, and then push to the wall overlapping the racquet on it... well, the ball have literally no space to go. You either end up with an error, a ball going at "astronomical" speeds, or something like that. If the racquet is pushing the ball against the wall, make sure that the distance from the racquet to the wall is enough for the ball to be there!

Too many bounces

What will happen if the result of solving a collision places the ball inside of another obstacle? Well, you will have to solve collision again, and again, until, eventually, it solves it.

Sometimes the previous position of the ball is inside of an obstacle that is hitting it from behind, pushing the ball into another obstacle. On the next iteration, the ball will move out of that obstacle... into the one that hit it first... but the old position is inside of that obstacle!

To solve this, update the old position between iterations, by always placing it at the boundary of the last hit object.


Sometimes, that same situation happens at high speed. In particular it will happen if you are an obstacle towards the ball, adding speed to it (I told you to clamp it!). If the speed is, too high it will take too many iterations to solve the collision.

Too many iterations means performance degradation. I have opted to implement an upper bound to the number of iterations... the result is that you can push balls outside of the world. This happens, in particular, when the speed is astronomical (the distance the ball would cover in one update is larger than the size of the world).

Allowing a high enough number of iterations works in most cases. Testing advised.

Working implementation

The following code implements collision of "balls" with rectangular obstacles. Actually, it only uses point collision (the radius of the balls is ignored), you should be able to fix that.

The interface of the snippet is as follows:

  • To move the racquet: move the mouse pointer.

  • To add a ball: 1) define the position by clicking. 2) Define the speed by clicking in the position where the ball should be after 1 second.

  • To increase the speed: press "*"

  • To decrease the speed: press "/"

  • To reset the speed: press "."

  • To increase the update interval: press "+"

  • To decrease the update interval: press "-"

  • To reset the update interval: press "0"

The code implements a limit to the number of iterations used to solve collisions, and allows the racquet to transfer velocity to the balls. There is a chance that you can push a ball outside of the world.

Constraints:

  • The code will not allow the racquet to touch the walls of the world.
  • The code will not allow the update interval to reach zero.
  • The code... will allow you to set a negative speed multiplier and solve collisions in reverse!

var time = (new Date()).getTime(); // time in milliseconds
var racquetElement; // the svg rect for the racquet
var balls = []; // array with all the balls
var speedMultiplier = 1; // to make the world go faster!
var interval = 25; // requested milliseconds between updates
var control = {x: 50, y:50}; // Magical (no, actually the ugly GUI code below handles it)
var racquetObstacle = {x1: 0, x2: 100, y1: 0, y2: 100, x: 50, y:50}; // racquetObstacle controlled by the player
var obstacles = [
  {x1: -Infinity, x2: 0, y1: -Infinity, y2: Infinity}, // left wall
  {x1: 1000, x2: Infinity, y1: -Infinity, y2: Infinity}, // right wall
  {x1: -Infinity, x2: Infinity, y1: -Infinity, y2: 0}, // top wall
  {x1: -Infinity, x2: Infinity, y1: 1000, y2: Infinity}, // bottom wall
  racquetObstacle
]

function update()
{
  // get elapsed time from last iteration
  // divided by 1000 to get seconds
  let new_time = (new Date()).getTime();
  let elapsed = (new_time - time) / 1000.0;

  // Take the speed of the racquetObstacle
  racquetObstacle.deltaX = control.x - racquetObstacle.x;
  racquetObstacle.deltaY = control.y - racquetObstacle.y;
  // update the obstacle of the racquetObstacle
  racquetObstacle.x1 = control.x - 50;
  racquetObstacle.x2 = control.x + 50;
  racquetObstacle.y1 = control.y - 50;
  racquetObstacle.y2 = control.y + 50;
  // store the position to be able to compute next speed
  racquetObstacle.x = control.x; 
  racquetObstacle.y = control.y;

  // Iterate over the balls
  for (var ballIndex = 0; ballIndex < balls.length; ballIndex++)
  {
      let ball = balls[ballIndex];
      // Get old coordinates.
      let ox = ball.x, oy = ball.y;
      // Get the effective speed, including multiplier
      let speedX = ball.speedX * speedMultiplier, speedY = ball.speedY * speedMultiplier;
      // Compute new position for the ball
      ball.x = ball.x + speedX * elapsed;
      ball.y = ball.y + speedY * elapsed;
      // --------------
      // Obstacle collision
      // --------------
      let count = 0;
      do
      {
        count++;
        ball.collided = false;
        for (var obstacleIndex = 0; obstacleIndex < obstacles.length; obstacleIndex++)
        {
          let obstacle = obstacles[obstacleIndex];
          if (!("deltaX" in obstacle)) obstacle.deltaX = 0;
          if (!("deltaY" in obstacle)) obstacle.deltaY = 0;
          let oldX = ox + obstacle.deltaX, oldY = oy + obstacle.deltaY;
          let inHorizontalRange = ball.x > obstacle.x1 && ball.x < obstacle.x2;
          let inVerticalRange = ball.y > obstacle.y1 && ball.y < obstacle.y2;
          // check if we have collided with this obstacle
          // we have to check if we have passed any of the walls of the obstacle
          if (
            oldX < obstacle.x1 && ball.x > obstacle.x1 // entered from the left
            && inVerticalRange // in vertical range
          ){
            ox = obstacle.x1;
            ball.x = obstacle.x1 - (ball.x - obstacle.x1);
            ball.speedX = -ball.speedX + Math.min(1000, Math.max(-1000, obstacle.deltaX / elapsed));
            ball.collided = true;
          }
          if (
            oldX > obstacle.x2 && ball.x < obstacle.x2 // entered from the right
            && inVerticalRange // in vertical range
          ){
            ox = obstacle.x2;
            ball.x = obstacle.x2 + (obstacle.x2 - ball.x);
            ball.speedX = -ball.speedX + Math.min(1000, Math.max(-1000, obstacle.deltaX / elapsed));
            ball.collided = true;
          }
          if (
            oldY < obstacle.y1 && ball.y > obstacle.y1 // entered from the top
            && inHorizontalRange // in horizontal range
          ){
            oy = obstacle.y1;
            ball.y = obstacle.y1 - (ball.y - obstacle.y1);
            ball.speedY = -ball.speedY + Math.min(1000, Math.max(-1000, obstacle.deltaY / elapsed));
            ball.collided = true;
          }
          if (
            oldY > obstacle.y2 && ball.y < obstacle.y2 // entered from the bottom
            && inHorizontalRange // in horizontal range
          ){
            oy = obstacle.y2;
            ball.y = obstacle.y2 + (obstacle.y2 - ball.y);
            ball.speedY = -ball.speedY + Math.min(1000, Math.max(-1000, obstacle.deltaY / elapsed));
            ball.collided = true;
          }
        }
      } while (ball.collided && count < 1000);
      // update the ball
      ball.setAttribute("cx", ball.x);
      ball.setAttribute("cy", ball.y);
  }
  // update racquetObstacle
  if (racquetElement !== null)
  {
    racquetElement.setAttribute("x", control.x - 50);
    racquetElement.setAttribute("y", control.y - 50);
  }
  // update time
  time = new_time;
  setTimeout(update, interval);
}

// --------------
// Ugly UI code
// --------------
var world;
function getNode(n, v){
  n = document.createElementNS("http://www.w3.org/2000/svg", n);
  for (var p in v) n.setAttributeNS(null, p, v[p]);
  return n;
}
jQuery(document).ready(function(){
  world = document.getElementById("world");
  racquetElement = document.getElementById("racquet");
  var tmp = null, arrow = null;
  $(world).on('mousemove', function(e){
    let x = e.pageX * 1000 / $(world).width(); let y = e.pageY * 1000 / $(world).height();
    if (arrow !== null){
      tmp.speedX = x - tmp.getAttribute("cx"); tmp.speedY = y - tmp.getAttribute("cy");
      arrow.setAttribute("x2", x); arrow.setAttribute("y2", y);
    }
    control.x = Math.min(949, Math.max(51, x)); control.y = Math.min(949, Math.max(51, y));
  });
  jQuery(world).click(function(e){
    if (tmp === null){
      let x = e.pageX * 1000 / $(world).width(); let y = e.pageY * 1000 / $(world).height();
      tmp = getNode('circle', {cx: x, cy: y, r:5}); tmp.x = x; tmp.y = y;
      arrow = getNode('line', {x1: x, x2: x, y1: y, y2: y, "stroke-width":1, stroke:"black"});
      world.appendChild(tmp); world.appendChild(arrow);
    }else{
      world.removeChild(arrow);
      balls.push(tmp);
      tmp = null; arrow = null;
    }
  });
  $(document).keypress(function(e){
    if (e.key === '+') interval += 25;
    if (e.key === '-') interval = Math.max(25, interval - 25);
    if (e.key === '0') interval = 25;
    if (e.key === '*') speedMultiplier += 0.1;
    if (e.key === '/') speedMultiplier -= 0.1;
    if (e.key === '.') speedMultiplier = 1;
  });
  setTimeout(update, interval);
});
body{margin:0}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<svg id="world" viewBox="0 0 1000 1000">
<rect id="racquet", x="0" y="0" width="100" height="100" fill="aqua" stroke:"black" stroke-width:"1">
</svg>

Open in full page for the best experience ;)


Bounce Order

There is a bug in the code above. If the ball is moving fast enough to collide with multiple objects, the first object in the list is the one that bounces it back... instead of the closes to the ball. Sometimes the bounce back will place the ball after one of the prior obstacles.

Instead of checking for each obstacle and moving the ball immediately, we should be picking the closest obstacle. Since we need to check distance, we really need to compute the collision point (instead of the "cheap" solution above).

I have also added a change of color to the racquet when a collision could not be resolved in the number of iterations given.

Improved version:

var time = (new Date()).getTime(); // time in milliseconds
var racquetElement; // the svg rect for the racquet
var balls = []; // array with all the balls
var speedMultiplier = 1; // to make the world go faster!
var interval = 25; // requested milliseconds between updates
var control = {x: 50, y:50}; // Magical (no, actually the ugly GUI code below handles it)
var racquetObstacle = {x1: 0, x2: 100, y1: 0, y2: 100, x: 50, y:50}; // racquetObstacle controlled by the player
var obstacles = [
  {x1: -Infinity, x2: 0, y1: -Infinity, y2: Infinity}, // left wall
  {x1: 1000, x2: Infinity, y1: -Infinity, y2: Infinity}, // right wall
  {x1: -Infinity, x2: Infinity, y1: -Infinity, y2: 0}, // top wall
  {x1: -Infinity, x2: Infinity, y1: 1000, y2: Infinity}, // bottom wall
  racquetObstacle
]

function update()
{
  // get elapsed time from last iteration
  // divided by 1000 to get seconds
  let new_time = (new Date()).getTime();
  let elapsed = (new_time - time) / 1000.0;

  // Take the speed of the racquetObstacle
  racquetObstacle.deltaX = control.x - racquetObstacle.x;
  racquetObstacle.deltaY = control.y - racquetObstacle.y;
  // update the obstacle of the racquetObstacle
  racquetObstacle.x1 = control.x - 50;
  racquetObstacle.x2 = control.x + 50;
  racquetObstacle.y1 = control.y - 50;
  racquetObstacle.y2 = control.y + 50;
  // store the position to be able to compute next speed
  racquetObstacle.x = control.x; 
  racquetObstacle.y = control.y;

  // Iterate over the balls
  for (var ballIndex = 0; ballIndex < balls.length; ballIndex++)
  {
      let ball = balls[ballIndex];
      // Get old coordinates.
      let ox = ball.x, oy = ball.y;
      // Get the effective speed, including multiplier
      let speedX = ball.speedX * speedMultiplier, speedY = ball.speedY * speedMultiplier;
      // Compute new position for the ball
      ball.x = ball.x + speedX * elapsed;
      ball.y = ball.y + speedY * elapsed;
      // --------------
      // Obstacle collision
      // --------------
      let count = 0;
      let collision = null;
      do
      {
        count++;
        collision = null;
        for (var obstacleIndex = 0; obstacleIndex < obstacles.length; obstacleIndex++)
        {
          let obstacle = obstacles[obstacleIndex];
          if (!("deltaX" in obstacle)) obstacle.deltaX = 0;
          if (!("deltaY" in obstacle)) obstacle.deltaY = 0;
          let oldX = ox + obstacle.deltaX, oldY = oy + obstacle.deltaY;
          let inHorizontalRange = ball.x > obstacle.x1 && ball.x < obstacle.x2;
          let inVerticalRange = ball.y > obstacle.y1 && ball.y < obstacle.y2;
          // check if we have collided with this obstacle
          // we have to check if we have passed any of the walls of the obstacle
          if (
            oldX < obstacle.x1 && ball.x > obstacle.x1 // entered from the left
            && inVerticalRange // in vertical range
          ){
            let candidate = {x: obstacle.x1, y: oy + obstacle.x1 * (ball.y - oy)/(ball.x - ox), direction: "left", deltaX: obstacle.deltaX, deltaY: obstacle.deltaY};
            candidate.distance = Math.sqrt((candidate.x - ox) * (candidate.x - ox) + (candidate.y - oy) * (candidate.y - oy));
            if (collision === null || collision.distance > candidate.distance)
            {
              collision = candidate;
            }
          }
          if (
            oldX > obstacle.x2 && ball.x < obstacle.x2 // entered from the right
            && inVerticalRange // in vertical range
          ){
            let candidate = {x: obstacle.x2, y: oy + obstacle.x2 * (ball.y - oy)/(ball.x - ox), direction: "right", deltaX: obstacle.deltaX, deltaY: obstacle.deltaY};
            candidate.distance = Math.sqrt((candidate.x - ox) * (candidate.x - ox) + (candidate.y - oy) * (candidate.y - oy));
            if (collision === null || collision.distance > candidate.distance)
            {
              collision = candidate;
            }
          }
          if (
            oldY < obstacle.y1 && ball.y > obstacle.y1 // entered from the top
            && inHorizontalRange // in horizontal range
          ){
            let candidate = {y: obstacle.y1, x: ox + obstacle.y1 * (ball.x - ox)/(ball.y - oy), direction: "top", deltaX: obstacle.deltaX, deltaY: obstacle.deltaY};
            candidate.distance = Math.sqrt((candidate.x - ox) * (candidate.x - ox) + (candidate.y - oy) * (candidate.y - oy));
            if (collision === null || collision.distance > candidate.distance)
            {
              collision = candidate;
            }
          }
          if (
            oldY > obstacle.y2 && ball.y < obstacle.y2 // entered from the bottom
            && inHorizontalRange // in horizontal range
          ){
            let candidate = {y: obstacle.y2, x: ox + obstacle.y2 * (ball.x - ox)/(ball.y - oy), direction: "top", deltaX: obstacle.deltaX, deltaY: obstacle.deltaY};
            candidate.distance = Math.sqrt((candidate.x - ox) * (candidate.x - ox) + (candidate.y - oy) * (candidate.y - oy));
            if (collision === null || collision.distance > candidate.distance)
            {
              collision = candidate;
            }
          }
        }
        if (collision === null)
        {
          break;
        }
        else
        {
          if (collision.direction === "left")
          {
            ox = collision.x - collision.deltaX;
            ball.x = collision.x - (ball.x - collision.x);
            ball.speedX = -ball.speedX + Math.min(1000, Math.max(-1000, collision.deltaX / elapsed));
          }
          else if (collision.direction === "right")
          {
            ox = collision.x - collision.deltaX;
            ball.x = collision.x + (collision.x - ball.x);
            ball.speedX = -ball.speedX + Math.min(1000, Math.max(-1000, collision.deltaX / elapsed));
          }
          else if (collision.direction === "top")
          {
            oy = collision.y - collision.deltaY;
            ball.y = collision.y - (ball.y - collision.y);
            ball.speedY = -ball.speedY + Math.min(1000, Math.max(-1000, collision.deltaY / elapsed));
          }
          else if (collision.direction === "bottom")
          {
            oy = collision.y - collision.deltaY;
            ball.y = collision.y + (collision.y - ball.y);
            ball.speedY = -ball.speedY + Math.min(1000, Math.max(-1000, collision.deltaY / elapsed));
          }
        }
      } while (count < 10000);
      if (count === 10000)
      {
        racquetElement.setAttribute("fill", "red");
      }
      // update the ball
      ball.setAttribute("cx", ball.x);
      ball.setAttribute("cy", ball.y);
  }
  // update racquetObstacle
  if (racquetElement !== null)
  {
    racquetElement.setAttribute("x", control.x - 50);
    racquetElement.setAttribute("y", control.y - 50);
  }
  // update time
  time = new_time;
  setTimeout(update, interval);
}

// --------------
// Ugly UI code
// --------------
var world;
function getNode(n, v){
  n = document.createElementNS("http://www.w3.org/2000/svg", n);
  for (var p in v) n.setAttributeNS(null, p, v[p]);
  return n;
}
jQuery(document).ready(function(){
  world = document.getElementById("world");
  racquetElement = document.getElementById("racquet");
  var tmp = null, arrow = null;
  $(world).on('mousemove', function(e){
    let x = e.pageX * 1000 / $(world).width(); let y = e.pageY * 1000 / $(world).height();
    if (arrow !== null){
      tmp.speedX = x - tmp.getAttribute("cx"); tmp.speedY = y - tmp.getAttribute("cy");
      arrow.setAttribute("x2", x); arrow.setAttribute("y2", y);
    }
    control.x = Math.min(949, Math.max(51, x)); control.y = Math.min(949, Math.max(51, y));
  });
  jQuery(world).click(function(e){
    if (tmp === null){
      let x = e.pageX * 1000 / $(world).width(); let y = e.pageY * 1000 / $(world).height();
      tmp = getNode('circle', {cx: x, cy: y, r:5}); tmp.x = x; tmp.y = y;
      arrow = getNode('line', {x1: x, x2: x, y1: y, y2: y, "stroke-width":1, stroke:"black"});
      world.appendChild(tmp); world.appendChild(arrow);
    }else{
      world.removeChild(arrow);
      balls.push(tmp);
      tmp = null; arrow = null;
    }
  });
  $(document).keypress(function(e){
    if (e.key === '+') interval += 25;
    if (e.key === '-') interval = Math.max(25, interval - 25);
    if (e.key === '0') interval = 25;
    if (e.key === '*') speedMultiplier += 0.1;
    if (e.key === '/') speedMultiplier -= 0.1;
    if (e.key === '.') speedMultiplier = 1;
  });
  setTimeout(update, interval);
});
body{margin:0}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<svg id="world" viewBox="0 0 1000 1000">
<rect id="racquet", x="0" y="0" width="100" height="100" fill="aqua" stroke:"black" stroke-width:"1">
</svg>

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ hey! thank you for such an in dept answer! For a beginner like me, I will need some time to understand the code and apply it to my project. Thank you again :) \$\endgroup\$ – tore Mar 3 '17 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.