Categories
General

Predictive collision detection techniques

In preparation for my upcoming Flash game programming training courses, I’m getting my head back into game physics, and I so I thought I’d share some useful collision detection methods I’ve discovered over the last few years.

Reactive collision detection

Collision detection in Flash games often occurs after things have moved. So you have a circle (usually a 2D representation of a ball) and you’re moving it towards a vertical line on the side of the screen (representing a wall). Every frame, you update its position and check whether it’s overlapping the wall.

Which is great, but of course if the ball is moving fast it may go from one side of the wall all the way to the other side between frames and no collision is detected. One way to get around this is to split up the movement of the ball into small segments and run this check several times between frames. This seems pretty inelegant to me so I have always strived to use predictive collision detection methods where my maths knowledge has allowed me! (This is also known as sweep testing, frame independent or continuous collision detection (CCD)).

Predicting when things will collide before you move them

So rather than just check whether the ball is intersecting with the wall between renders, we actually check the velocity of the ball to see at what point in time it would hit the wall if it continued in the direction it’s going.

If the ball is moving at 10 pixels per frame and the wall is 30 pixels away then we know that we will hit it in 3 frames. And if the wall is 15 pixels away we know that we will hit it at some point between the next frame and the frame after.

But if it’s 5 pixels away then we know that the ball will hit the wall exactly half way between the last frame and the next. And more importantly we know that the collision occurred after the ball had moved half of its velocity. So not only do we know when the collision occurred, we also can work out where the ball is when it collided.

So imagine this code is running between frames :

 

// the distance from the wall to the ball
distance = wallX-(ballX+radius); 

// timeHit is the time that the ball will hit the wall in frames: 0 is now, 
// 1 is the next frame, 2 is the frame after that
timeHit = distance / velX; 

// if timeHit is between 0 and 1 we know that the ball will hit the wall 
// within this update
if((timeHit>0) && (timeHit<1))
{
   // we have a collision! As the hit time is between 0 and 1 we can 
   // multiply the velocity by that number to find the collision point
   ballX += (velX*timeHit); 
   ballY += (velY*timeHit); 

   // at this point we would do a collision reaction, here's a simple 
   // bounce assuming the ball is on the left and the wall is on the right
   velX *= -1; 
}

Moving the ball to its collision point

The really great thing about this method is that you genuinely find out where the collision happened as opposed to discovering an intersection and then trying to work out how to move your objects back to stop them overlapping.

IMG_8171

Of course this is a very basic example, and it may be that simpler methods would suffice in this case. But as we get into more complex examples you’ll see exactly how valuable this technique can be.

Coming next – predicting collisions between circles.

22 replies on “Predictive collision detection techniques”

Will be interesting to read continuation. Will you cover cases when such analytical approach leads to cases when infinite amounts of collisions happen(for example case of bouncing ball)?

Hmm. Hmm. I wonder then how you are doing that. I mean that you have some time step lets say 1. At moment 1 your ball is before the wall and at moment 2 after the wall and trough math you can determine that at some moment in between ball touches wall. So you move ball to that moment and resolve collision. What’s next? You leave it there as if whole time step passed or you move it further for time that is left from collision till end of time step?

@wonder-whyer That’s a very good point and I’ll be talking about that in a later post. I find it visually pleasing to see an object touching anything it collides with so I’ll move it to that point, work out the new velocity, and then move to the next frame. I most often work with frames, rather than strictly adhering to a timer. I know there are many other ways, but this is my personal preference. Cheers!

Okey I see 🙂 Well that explains why you do not have that problem I mentioned before. It brings some others in some cases like in tight spaces balls that move very fast by numbers will move slower because their maximal speed will be limited by distance from wall to wall. Usually it is not a problem tough as you rarely need such fast balls 🙂

I find that it’s simpler to reduce the bounding box to simple vectors with dot products and then calculate movement along that vector. You can minimize the number of hit tests you have to do.

great article. didn’t know how to deal with that until now. but it makes me wonder how this formula would altered to detect collisions between multiple moving objects, each with different velocities.

thanks.

[…] and Marc Binsted for their help and code examples. Seb has written a few interesting articles about Predictive collision detection techniques and Predicting circle line collisions that I highly recomend. At first Vector Math blew my mind, […]

Problem with this formula is that you have to actually check in which direction is the ball moving, as if you do your distance and timeHit only once at the begining of movement and then the ball starts moving in other direction than a wall is, it will at some point in time bounce anyway. And to use distance formula for x, y every frame is not so speedy anymore as it contains trigs.

I’m not sure I understand Dawid, you don’t need trig in this example. Or are you using a non-perpendicular line? In which case you can look at the code in the next part of this for a non-trig vector-only solution. Which is super fast.

Seb

Great code…

it works in my code for the right wall, but I have trouble coding it for the left wall, like, for example in the left wall in a pool game…

whats the trick?

[…] has written a few interesting articles about Predictive collision detection techniques and Predicting circle line collisions which i highly recomend a read. At first Vector math blew my […]

[…] monsters, or see if I can wrap my head around predictive collision detection. I’ll be reading this article for […]

First, thanks for the code. It is simple and understandable, but I had minor problems with the operation. Replacing this piece of code:

if ((timeHit> 0) & & (timeHit = 0) & & (timeHit <= 1))

or:
if (Math.abs (timeHit) <1)

improved performance. Thank you again.

I’m not sure that’s quite right. t needs to be between 0 and 1. I’m not sure where you got :

if ((timeHit> 0) & & (timeHit = 0) & & (timeHit 0) && (timeHit0) && (timeHit<=1))

just in case the collision occurs exactly on the frame.

cheers!

Seb

Google Translator mixed up my code. I checked the original code at random speeds, and sometimes the ball flew over the lines. For example, at a speed equal to 1:) Adding “=”( =) improved action:

if((timeHit>=0) && (timeHit<=1))

or abs:

if (Math.abs (timeHit) <1)

Comments are closed.