   2D Collision Detection, Using Speed, Your Ideas!?
  ]Hi, this is Again about collision detection. I hope this topic will be of use for a lot of people. I want to discus 2D collision detection. I am coding some 2D game where I have to check: 1)Ball (point) -- Rectangle Collision2)Rectangle – Rectangle CollisionMain problem in collision detection is the SPEED your object is moving with.So for example:If we have Ball Moving with the speed of 1, 2, 3, 4, 5 or 6, we might get proper collision detection on a rectangle in most of the cases, but if speed is over 8, then your collision detection might be messed up. Ball will just skip Rectangles or any other objects you are trying to check for collision.Here is a rough image of what happens when you change the speed:As you can see, when speed is changed to 8, Ball just skips the Rectangle position and does not detect any collision.So, Mr. HypnZA, here on the forums, suggested this method:for(i=0; i<MyBall.speed; ++i){    // do collision detection against MyBall.x + i and MyBall.y + i    // if there's a collision, destroy the brick and "bounce" the ball back (and set a "move" flag to false? let's call it "moveFlag")     Brick[x].isAlive = false;}// if a collision was NOT detected, move the ball to it's new positionif (moveFlag){    MyBall.x += MyBall.xDirection * MyBall.speed;    MyBall.y += MyBall.yDirection * MyBall.speed;}So the question would be, is that kind of for loop fast enough approach? What if we have let’s say 50 Objects on a screen in 1 given moment, that means:1)for loop 50 times2)for loop SPPED timesSo if speed is let’s say 8, then 8 * 50 = 400. So of course it will change as we will collide with some objects from time to time, so it will probably be 350 – 400 updates.So the question is: would that be fast enough, Isn't that just to many CPU cycles?Please leave your thoughts, suggestions and lets make this thread educational!Thanks a lot!Yuris.   
  For the types of tests you're talking about here (point-box, circle-box, box-box, etc.), I don't know that any sort of iterative approach is necessary. For each of these object pairs, exact continuous tests exist that are fairly efficient and will return the exact time of intersection (if any) along with additional information such as the collision point(s) and normals. These tests are 'single step' test, and don't require any iteration.   ;  The first trick in this situation is that rather than testing a moving circle against a rectangle, we can actually test a moving point against an expanded rectangle. To do this, we create a new rectangle whose sides have all been "pushed out" by the radius of the circle. The result of this collision test will be equivalent to the original collision test.Now that we have a moving point versus a rectangle, we can test the line segment created by the moving point against all sides of the rectangle to determine the exact time of collision. You can work out the math for this or just find it somewhere else. Check out this presentation for more information   ;Quote:Now that we have a moving point versus a rectangle, we can test the line segment created by the moving point against all sides of the rectangle to determine the exact time of collision.Are you saying that the circle-rectangle test can be expressed as a point-rectangle test? If so, this is incorrect. Expanding the original rectangle by the circle radius yields not another rectangle, but a 'rounded box' (i.e. a box with rounded corners). It is this shape that the swept point needs to be tested against (which is not difficult, but isn't quite as straightforward as the point-box test).   ;  The collision detection bible:http://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323/ref=sr_1_1?ie=UTF8&s=books&qid=1270741033&sr=8-1It has moving object collision detection tests in there among other stuff (:For each test it has information on, it presents the theory behind it, the math behind it, and source code if that's all you realy want to know about.Really great book   ;  That effect is called tunneling, and it's a (mostly) solved problem for most physics libraries.  Box2d, for example, uses Time of Impact estimations.However, even so, there's still chances at very high rates of travel, tunneling can still occur even with TOI calculations.  The trick there is to try and limit exceedingly rapid movement (via constraints or whatever).  I think Box2D does a good job of balancing speed with accuracy.http://box2d.org/manual.htmlSearch the page for "time of impact" and have a look.  It's open source (MIT) too so you could dig through the code and see how it's done.   