# how to keep display tick rate steady when using continuous collision detection?

(I've just found about this forum). I hope it is ok to repost my question again here. I posted this question at stackoverflow, but it looks like I might get better help here.

Here is the question:

I've implemented basic particles motion simulation with continuous collision detection.

But there is small issue in display.

Assume simple case of circles moving inside square. All elastic collisions. no firction. All motion is constant speed. No forces are involved, no gravity. So when a particle is moving, it is always moving at constant speed (in between collisions)

What I do now is this:

Let the simulation time step be 1 second (for example). This is the time step simulation is advanced before displaying the new state (unless there is a collision sooner than this).

At start of each time step, time for the next collision between any particles or a particle with a wall is determined. Call this the TOC time; let’s say TOC was .5 seconds in this case.

Since TOC is smaller than the standard time step, then the system is moved by TOC and the new system is displayed so that the new display shows any collisions as just taking place (say 2 circles just touched each other’s, or a circle just touched a wall)

Next, the collision(s) are resolved (i.e. speeds updated, changed directions etc..).

A new step is started. The same thing happens. Now assume there is no collision detected within the next 1 second (those 2 circles above will not be in collision any more, even though they are still touching, due to their speeds showing they are moving apart now), Hence, simulation time is advanced now by the full one second, the standard time step, and particles are moved on the screen using 1 second simulation time and new display is shown.

You see what has just happened: One frame ran for .5 seconds, but the next frame runs for 1 second, may be the 3rd frame is displayed after 2 seconds, may be the 4th frame is displayed after 2.8 seconds (because TOC was .8 seconds then) and so on.

What happens is that the motion of a particle on the screen appears to speed up or slow down, even though it is moving at constant speed and was not even involved in a collision.

i.e. Looking at one particle on its own, I see it suddenly speeding up or slowing down, becuase another particle had hit a wall.

This is because the display tick is not uniform. i.e. the frame rate update is changing, giving the false illusion that a particle is moving at non-constant speed while in fact it is moving at constant speed. The motion on the screen is not smooth, since the screen is not updating at constant rate.

I am not able to figure how to fix this. If I want to show 2 particles at the moment of the collision, I must draw the screen at different times. Drawing the screen always at the same tick interval, results in seeing 2 particles before the collision, and then after the collision, and not just when they colliding, which looked bad when I tried it.

So, how do real games handle this issue? How to display things in order to show collisions when it happen, yet keep the display tick constant? These 2 requirements seem to contradict each other’s.

Solution 1: You could work around that problem by rendering a trail of your particles. That will leave the impression they hit a wall or each other without needing to draw the frame in which the impact occurred and slowing down.

Solution 2: You would need to cleverly and subtly adjust particle speed so they only collide in discrete frames "rendering time" and not in x.5 or x.8 times like they do now.

The second thing I would suggest is to use an existing physics engine.

That problem never seems to be crucial when I use Box2D unless speeds are too high.

In which case I adjust speeds to prevent unattractive visuals like you mentioned.

You already know when the balls are going to collide, not introduce a tiny slowdown or speedup so they only collide on discrete frames and not in-between two frames.

I suggest a mix of both techniques. When you can adjust speed slightly, do that and always leave a blurry trail to leave the user with the impression that a hit occurred.

To predict a future collision and and slightly adjust speed in advance:

You can predict a future collision by testing each pair of particles like this:

Variables:

v1 = the velocity of the first particle.
p1 = the position of the first particle

v2 = the velocity of the second particle.
p2 = the position of the second particle

1. Sum up the speed of both particles : u = v1 + v2 (u is the some of their velocites)
2. Draw a line through one of the particles with the same angle as the velocity. a = u.y / u.y ; b = p1.y - a * p1.x ; The line is : y = ax + b;
3. Now use geometry to find the closest point on the line to p2.
4. If the distance in that point is greater than the some of their radiuses, predict no collision. Else move to step 5.
5. Check for the points where the distance between them is exactly the sum of their radiuses and use the nearest one as their point of collision.
6. Calculate how many frames it will take for them to collide by measuring the distance between p1 and the point you found on the line.
7. Lets say it takes 8.6 frames, you can now give them each a fake speed of v * 8.6/9 and they will collide in 9 frames. You can also slow them down(decelerate) them gradually so that it looks more natural. You would need to slow them down to a speed that averages with the current speed at v * 8.6/9.

Disadvantages in using this prediction system:

Complexity: O(n^2) so it should be used with a small number of particles.

Changing the particles speed may 'create new collisions' that would not have happened in the original speed. So it should only be used with sparse particle clouds.

• I like your solution 2. I think I will try it. It will only affect one frame in which there is a collision in-between. I will have to keep track of the 'fake' speed and the real speed for that one frame only, so no problem. I do not want to use an engine, since this is just for learning, and I'd like to learn how to do this. – nas Ns Oct 12 '12 at 19:01
• You can predict the collision in advance and use the fake speed in a more delicate way. I will elaborate. – wolfdawn Oct 13 '12 at 8:18

There is two options, depending on your physics engine:

## 1. Your physics engine can handle variable timestep

In this case, take the time since last update and feed it into the physics engine. Should the simulation end early due to collisions you subtract this time with the time the simulation actually ran for, and then repeat the simulation until you get to a small enough time remaining.

timeRemaining = timeSinceLastFrame
while (timeRemaining > 0)
timeReamining = timeRemaining - PhysicsUpdate(timeRemaining)


Depending on how well the physics engine can handle very small timesteps you might need to check for the remaining time being larger than (say) 0.1 seconds instead of 0 seconds. If you do this you might want to combine this answer with the next to make sure you don't drop fractions of a second all the time and thus run the simulation slower than normal speed:

## 2. Your physics engine cannot handle variable timesteps

While unlikely to be the case, since you already stated it can handle stopping early, to be complete I wanted to discuss this case.

In this case you want to minimize the difference between the actual simulation time, to the time taken per frame. To do this you keep track of the real time taken to reach this point, and subtract the simulated time from this each time you update.

realTime = realTime + timeSinceLastFrame
while (realTime > physicsEngineTimeStep)
realTime = realTime - PhysicsUpdate()


In this case, real time should be kept between the update calls, so if you get 0.5 second update due to ending early you would keep 0.5 for the next frame. Should the next frame run in 0.5 or less it will then do another update right away to catch up to real time. This would still produce some small changes in observed speeds, but since you keep correcting it will average out, the smaller the time step the less noticeable it will be (at the cost of taking longer to simulate no doubt).

You can also run a frame if the real time passed is larger than, say, 75% of a timestep, this allows the simulation to run ahead of actual time (leaving realTime as a negative value for the next frame) but it also allows it to catch up to real time before it falls behind with a full time step (one second in your example). This would reduce the slowdowns and make them somewhat less noticeable.

while (realTime > physicsEngineTimeStep * 0.75)


As mentioned in 1. above, you can combine both answers into one:

realTime = realTime + timeSinceLastFrame
while (realTime > physicsEngineMinimumTimeStep)
realTime = realTime - PhysicsUpdate(realTime)