Time independent collision detection

Questions
, , , ,
1

I am working on collision detection for a project and I am worried that the update rate affects the collisions. Basically, the way how it currently works is I do kinematics with acceleration and velocity to find the final velocity and position. I then assume the player moves in a straight line to the final position, and raycast from a bunch of test points. If they detect a collision I offset the player so the test point is touching the wall. I then correct the velocity using the normal of the hit face, and then do it again to see if there is another collision.

All of this works, however it does not seem to be time accurate. If I have a player that is updating twice as many times per second as the other one, the one that is updating faster will stay in the exact same place as the normal one, except for usually upon hitting a wall. When they just run into a wall, the slower updating one will be put behind the faster updating one. Also, the velocities also get desynchronized when going over a corner.

I believe the problem is that the players don’t actually move in a straight line to their end point, they actually move along a parabola. I am wondering if to fix this I need to write a parabola caster, or whether I can just live with it be innacurate. This is for a multiplayer game, so I am worried about the server and the client getting desynchronized every time the client hits a wall.

2

You might be looking for a technique called Continuous Collision Detection (CCD)? Some physics engines (like ammo.js) have this option, others may not.

1 Like
3
  • there is no such thing as “time independent physics” or collision detection specifically. If you’re dealing with time-dependent things like velocity or acceleration - you have time dependence. There’s no way around it. At least with the currently known physics (yes, all of the currently known physics agrees with this).
  • There is such a thing as deterministic simulation. Most of the physics engines in competitive games run with a fixed step. Meaning that physics updates exactly X times per second of simulation. This way you can be sure that given state A and amount of time T - you will always end up in state B, no matter how many times you re-run the simulation.
  • CCD, what @donmccurdy has mentioned. This is not a deterministic solution by itself, it just makes sure you detect contacts more accurately. But it’s not 100% exact in general. Most of the time you only get exact contacts, forces still typically suffer from drift if your clock is not running in fixed step. That’s the nature of integration, to get exact solution to your physics simulation - you need to run infinitely many simulation steps per second. Imagine a normal integration, there’s a trapezoid approximation method, which splits the graph into fixed sections and measures areas of those sections by approximating them as trapezoids. Well physics sim is similar, in that it approximates a result of a simulation step, it doesn’t perform the full integration.

Hope this helps.

1 Like
4

How would I get my physics to update exactly X times per second? Is setTimeout exact enough?

5

You keep track of how much time has passed, and execute something like this:

let simulatedTime = performance.now()/1000;
const fixedStep = 0.015; //15ms

function update(){
     const timeNow = performance.now()/1000;
     while(timeNow > simulatedTime+fixedStep){
           // current time is ahead of the simulation time by more than the step size, advance the simulation forward
           sim.advance(fixedStep);
           simulatedTime += fixedStep;
     }
}

You can call update as often as you like. Even frame, every second, using setTimeout - whatever. That’s up to you.

I suggest you synchronize player input processing with the simulation update as well, to get most consistent result.