{"id":845,"date":"2024-03-01T13:00:53","date_gmt":"2024-03-01T07:30:53","guid":{"rendered":"http:\/\/codetheory.in\/?p=845---726dd011-09f1-4d64-b16d-87273932e677"},"modified":"2024-03-01T13:00:53","modified_gmt":"2024-03-01T07:30:53","slug":"game-physics-basics-and-implementation-of-predictive-collision-detection","status":"publish","type":"post","link":"https:\/\/codetheory.in\/game-physics-basics-and-implementation-of-predictive-collision-detection\/","title":{"rendered":"Games Physics: Basics and Implementation of Predictive (or Continuous) Collision Detection"},"content":{"rendered":"
<\/p>\n
Few days ago, I wrote a post<\/a> 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!<\/p>\n <\/p>\n 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<\/strong>. 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! \ud83d\ude1b<\/p>\n 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<\/strong>:<\/p>\n 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.<\/p>\n (Click on the refresh icon on the embed above if you missed the show.) 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.<\/p>\n <\/p>\n 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.<\/p>\n Here we are just calculating the time required by the ball to reach the platform. What we get from this time is<\/p>\n 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.<\/p>\n 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:<\/p>\n 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<\/a>, it looked something like this:<\/p>\n Now the new code will look like this and your time based animations will have the perfect collisions.<\/p>\n Update<\/strong>: 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<\/a> with random delta times just to confirm that it works with variable delta times too.<\/p>\n Update #2<\/strong>: Previous code<\/a> 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<\/a> for pointing that out, I've updated the function below accordingly. Here's<\/a> the code if you want to check the demonstration in variable framerates. <\/p>\n 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<\/p>\n","protected":false},"excerpt":{"rendered":" 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 … Continue reading “Games Physics: Basics and Implementation of Predictive (or Continuous) Collision Detection”<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[13,40,12],"tags":[14,16,15,8,67,66],"_links":{"self":[{"href":"https:\/\/codetheory.in\/wp-json\/wp\/v2\/posts\/845"}],"collection":[{"href":"https:\/\/codetheory.in\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codetheory.in\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codetheory.in\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/codetheory.in\/wp-json\/wp\/v2\/comments?post=845"}],"version-history":[{"count":41,"href":"https:\/\/codetheory.in\/wp-json\/wp\/v2\/posts\/845\/revisions"}],"predecessor-version":[{"id":184723,"href":"https:\/\/codetheory.in\/wp-json\/wp\/v2\/posts\/845\/revisions\/184723"}],"wp:attachment":[{"href":"https:\/\/codetheory.in\/wp-json\/wp\/v2\/media?parent=845"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codetheory.in\/wp-json\/wp\/v2\/categories?post=845"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codetheory.in\/wp-json\/wp\/v2\/tags?post=845"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nThis 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. <\/p>\nOrdinary Collision Detection<\/h2>\n
<\/pre>\n
\r\nfunction update() {\r\n\tpaintCanvas();\r\n\t\r\n\t\/\/ Draw the platform\r\n\tplatform.draw();\r\n\t\r\n\t\/\/ Move the ball\r\n\tball.y += ball.vy;\r\n\tball.vy += gravity;\r\n\tball.draw();\r\n\t\r\n\t\/\/ Collision Time!\r\n\tif(\r\n\t\t(ball.y + ball.radius > platform.y) &&\r\n\t\t(ball.y + ball.radius < platform.y + platform.height)\r\n\t\t) {\r\n\t\t\t\/\/ Put the ball at top of the platform\r\n\t\t\tball.y = platform.y - ball.radius;\r\n\t\t\t\/\/ .. and rebound the ball\r\n\t\t\tball.vy *= -0.91;\r\n\t\t}\r\n\t\r\n}\r\n<\/pre>\n
<\/pre>\n
\nAs 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.<\/p>\nPredictive Collision Detection (or Sweep Testing)<\/h2>\n
\r\nvar speed = ball.vy + gravity, \r\n\tdistance = platform.y - ball.y + ball.r,\r\n\ttime = distance \/ speed;\r\n<\/pre>\n
\n
0 < time < 1<\/code>, then the collision will occur between current and next frame.<\/li>\n
1 < time < 2<\/code>, then the collision will occur between next and the frame after that.<\/li>\n
2 < time<\/code>, then the collision will occur after next to next frame.<\/li>\n<\/ul>\n
<\/pre>\n
\r\nfunction update() {\r\n\tpaintCanvas();\r\n\t\r\n\t\/\/ Draw the platform\r\n\tplatform.draw();\r\n\t\r\n\t\/\/ Move the ball\r\n\tball.y += ball.vy;\r\n\tball.vy += gravity;\r\n\tball.draw();\r\n\t\r\n\tvar speed = ball.vy + gravity, \r\n\t\tdistance = platform.y - (ball.y + ball.radius),\r\n\t\ttime = distance \/ speed;\r\n\t\r\n\t\/\/ Predictive Collision Time!\r\n\tif(time > 0 && time < 1) {\r\n\t\tball.y = platform.y - ball.radius;\r\n\t\tball.vy *= -0.4;\r\n\t}\r\n}\r\n<\/pre>\n
\r\nfunction f2T(Delta, Speed) {\r\n\treturn (Speed * Delta) * (60 \/ 1000); \r\n}\r\n<\/pre>\n
\r\nfunction update() {\r\n\tnow = new Date().getTime();\r\n\tnew_delta = now - then;\t\r\n\tif(!old_delta)\r\n\t\told_delta = new_delta;\r\n\t\r\n\tthen = now;\r\n\tpaintCanvas();\r\n\t\r\n\t\/\/ Draw the platform\r\n\tplatform.draw();\r\n\t\r\n\t\/\/ Move the ball\r\n\tball.y += f2T(old_delta, ball.vy); \r\n\tball.vy += f2T(old_delta, gravity); \r\n\tball.draw();\r\n\t\r\n\told_delta = new_delta;\r\n\t\r\n\tvar speed = f2T(new_delta, ball.vy), \r\n\t\t\tdistance = platform.y - (ball.y + ball.radius),\r\n\t\t\t\ttime = distance \/ speed;\r\n\t\r\n\tif(time >= 0 && time <= 1) {\r\n\t\tball.y = platform.y - ball.radius;\r\n\t\tif (ball.vy > 0)\r\n\t\t\tball.vy *= - 0.4;\r\n\t}\r\n}\r\n<\/pre>\n