Games Physics: Basics and Implementation of Predictive (or Continuous) Collision Detection

Few days ago, I wrote a post about why time based animations are better than frame based animations. However, in animations done as a function of time, some serious problems could arise. One of them is that your regular collision detection techniques might fail if the frame rate is lower than acceptable. Your object might pass through the walls or even fall through the floor!


This problem occurs if you are using basic collision detection techniques like calculating the intersection of object’s bounds per frame. Now suppose if you are making a game in which an object jumps from one platform to other and goes like that. If the frame rate is lower and the speed of the object is high, then the object might be above the platform in one frame and below the same platform in the next frame which will never satisfy your condition of true collision.

This problem can also be seen even with high frame rates combined with high object speeds. If you are facing this problem in your games, then you should definitely change the way you detect the collisions between two objects. The new way of collision that I will be talking about is known as predictive (or continuous or frame independant) collision detection. This requires future knowledge of your object’s coordinates but don’t worry, you won’t have to do any astrology kind of thing to achieve this! :P

Ordinary Collision Detection

If you are not sleepy yet, then let’s take a look on what is predictive collision detection. Now suppose (ugh!), okay don’t. This time, we’ll go through the code to understand this technique in a better way. Take a look at this ordinary method of collision detection:


function update() {
	paintCanvas();
	
	// Draw the platform
	platform.draw();
	
	// Move the ball
	ball.y += ball.vy;
	ball.vy += gravity;
	ball.draw();
	
	// Collision Time!
	if(
		(ball.y + ball.radius > platform.y) &&
		(ball.y + ball.radius < platform.y + platform.height)
		) {
			// Put the ball at top of the platform
			ball.y = platform.y - ball.radius;
			// .. and rebound the ball
			ball.vy *= -0.91;
		}
	
}

Pretty simple, the ball bounces back after hitting the platform. Here, I am just checking the lower edge of the ball in each frame, if it’s between the platform’s top edge and bottom edge then the collision is said to occur and we do our rebound. This might sound cute, but it’s not. Now let’s increase the velocity of the ball and see what happens.


(Click on the refresh icon on the embed above if you missed the show.)
As expected, the ball doesn’t bounce at all, it just passes through the platform! This is because the collision actually happened between two consecutive frames and we only saw the ball’s lower above the platform in one frame and then below the platform in the next frame. So, in canvas’s world, the collision never existed.

Predictive Collision Detection (or Sweep Testing)

Now this problem can be solved if we get to know about the future coordinates of the ball. By this, we’ll get the knowledge about when the ball will hit the platform in future and based on that, we’ll do our collision. This can be done by using some simple math calculations. We’ll just calculate the time required for the ball to reach the platform in the next frames.

If the velocity of the ball is 5px/frame and the distance between the platform and the ball is 30px, then the time it will take to reach the platform will be 6 frames (note that we are not considering gravity here). Now, if the speed is same and distance is 9px, then it is obvious that the collision will occur between the current and the next frame. So, we now have the knowledge about when the ball will hit the platform in future. This is how we’ll calculate the required time.

var speed = ball.vy + gravity, 
	distance = platform.y - ball.y + ball.r,
	time = distance / speed;

Here we are just calculating the time required by the ball to reach the platform. What we get from this time is

  • If 0 < time < 1, then the collision will occur between current and next frame.
  • If 1 < time < 2, then the collision will occur between next and the frame after that.
  • If 2 < time, then the collision will occur after next to next frame.

Here, we are only interested in the first case as the collision between the current and the next frame gets missed. Let's apply this to our previous code where the velocity of the ball was high and see what happens.


Now the collision is perfecto! Try giving the ball any speed you want and see the results. Please note that I lowered the bounce factor here so that you can clearly see the bouncing animation. Here's the code responsible for that:

function update() {
	paintCanvas();
	
	// Draw the platform
	platform.draw();
	
	// Move the ball
	ball.y += ball.vy;
	ball.vy += gravity;
	ball.draw();
	
	var speed = ball.vy + gravity, 
		distance = platform.y - (ball.y + ball.radius),
		time = distance / speed;
	
	// Predictive Collision Time!
	if(time > 0 && time < 1) {
		ball.y = platform.y - ball.radius;
		ball.vy *= -0.4;
	}
}

Isn't this easier than your regular collision detection techniques? Now for time based animations, you just need to convert the values in the function of time. If you remember the function from my last post, it looked something like this:

function f2T(Delta, Speed) {
	return (Speed * Delta) * (60 / 1000); 
}

Now the new code will look like this and your time based animations will have the perfect collisions.

Update: I forgot to include the calculation of delta in the below function like in my previous post but I've done so. Also, I created a fork here with random delta times just to confirm that it works with variable delta times too.

Update #2: Previous code had some problems with variable delta times as the collision was depending upon the current delta time rather than the previous delta time. Thanks to ajuc for pointing that out, I've updated the function below accordingly. Here's the code if you want to check the demonstration in variable framerates.

function update() {
	now = new Date().getTime();
	new_delta = now - then;	
	if(!old_delta)
		old_delta = new_delta;
	
	then = now;
	paintCanvas();
	
	// Draw the platform
	platform.draw();
	
	// Move the ball
	ball.y += f2T(old_delta, ball.vy); 
	ball.vy += f2T(old_delta, gravity); 
	ball.draw();
	
	old_delta = new_delta;
	
	var speed = f2T(new_delta, ball.vy), 
			distance = platform.y - (ball.y + ball.radius),
				time = distance / speed;
	
	if(time >= 0 && time <= 1) {
		ball.y = platform.y - ball.radius;
		if (ball.vy > 0)
			ball.vy *= - 0.4;
	}
}

I hope you are still awake and understood the whole concept behind predictive collision detection. This technique doesn't apply only to HTML5 games, so don't worry if you are facing this problem in your flash games, you can still use this. I will be posting more about games physics / art (less theory and more practical) so that you can be the next gamedev champion! :D

Share:

13 thoughts on “Games Physics: Basics and Implementation of Predictive (or Continuous) Collision Detection

  1. Chuck

    I’ve been trying to make a low-end clone of Breakout after watching Gyrostorms HTML5 tutorial videos on Youtube and this (and the last article) are exactly what I needed to read. Also, love the style of your walkthrough with the examples!

    Reply
  2. Ryan

    Aren’t we still depending on the frame rate in the final example code? We’re updating the ball by a set amount every frame, so a low framerate would have the ball moving slower.

    Reply
  3. Rezoner

    Very well explained – however despite reading the previous article I find this frames/second unit quite awkward. I think pixels/second is more often measurement;


    var velocity = 100; /* pixels per second */

    function update(delta) {
    something.x += velocity * delta / 1000;
    }

    Reply
  4. ajuc

    I think its still possible to miss the collision with the last version of the update function. The problem is – we update the position of the ball with delta0, then we check for the collision in the next frame with delta0, then we calculate next delta (delta1), and we update the ball position with delta1. If delta0 was small, but delta1 was big (maybe there was some explosion that was too expansive for our computer to draw) – it’s possible to miss the collision.

    I think we should remember the delta from last update function call, and move the ball position with it, and only then we should calculate the new delta?

    Here’s more detailed description of the problem: http://www.reddit.com/r/programming/comments/15ogun/predictive_collision_detection_techniques_overview/c7osyfh

    Reply
    1. Kushagra Agarwal Post author

      Actually, I tried with variable frame rates and my solutions still works. The thing is, I forgot to include how I calculated the delta in that function but I’ve updated it so it must be the thing that made you confused. Here’s the link to the test I did on variable frame rates.

      Reply
      1. ajuc

        Try your example with changed line

        fps = 30 + Math.random() * 30;

        to

        fps = 5 + Math.random() * 55;

        On my computer it skips the collision half the time.

        It’s only problem on computers with very varied fps, and it only will happen when the huge difference between frames happen at just right distance from the obstacle. But it’s easy to repair this – use delta from previous invocation to move object.

        Reply
        1. ajuc

          I’ve reorganized it a little to better understand it. I meant to use old_delta for movement, and new_delta for checking for collisions.

          Here is OK:
          http://cssdeck.com/labs/h3zuewav

          Here is with error:
          http://cssdeck.com/labs/epvqu73v

          I added code to make platform blue when ball is below the platform, because when youre in diffrent tab/window the simulation is paused, and after you switch, the ball gets faster then light (cause of huge delta:) ) and bounces over the top of the window :)

          Greetings.

          Reply
  5. ajuc

    No problem.

    Also now when I think of it we’re not checking if we can move anything in the first frame :) That makes the ball skip the platform if you run the test in new tab, and swith to the tab after a while (cause the first delta is big enough to move below the platform).

    No program is ever done :)

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *


*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>