software engineering - How can I implement gravity?

How can I implement gravity? Not for a particular language, just pseudocode...

Answer

As others have noted in the comments, the basic Euler integration method described in tenpn's answer suffers from a few problems:

• 
  

  Even for simple motion, like ballistic jumping under constant gravity, it introduces a systematic error.

  
  


• 
  

  The error depends on the timestep, meaning that changing the timestep changes object trajectories in a systematic way that may be noticed by players if the game uses a variable timestep. Even for games with a fixed physics timestep, changing the timestep during development can noticeably affect the game physics such as the distance that an object launched with a given force will fly, potentially breaking previously designed levels.

  
  


• 
  

  It doesn't conserve energy, even if the underlying physics should. In particular, objects that should oscillate steadily (e.g. pendulums, springs, orbiting planets, etc.) may steadily accumulate energy until the whole system blows apart.

  
  

Fortunately, it's not hard to replace Euler integration with something that is almost as simple, yet has none of these problems — specifically, a second-order symplectic integrator such as leapfrog integration or the closely related velocity Verlet method. In particular, where basic Euler integration updates the velocity and position as:

acceleration = force(time, position) / mass;
time += timestep;
position += timestep * velocity;
velocity += timestep * acceleration;

the velocity Verlet method does it like this:

acceleration = force(time, position) / mass;
time += timestep;
position += timestep * (velocity + timestep * acceleration / 2);
newAcceleration = force(time, position) / mass;
velocity += timestep * (acceleration + newAcceleration) / 2;

If you have multiple interacting objects, you should update all their positions before recalculating the forces and updating the velocities. The new acceleration(s) can then be saved and used to update the position(s) on the next timestep, reducing the number of calls to force() down to one (per object) per timestep, just like with the Euler method.

Also, if the acceleration is normally constant (like gravity during ballistic jumping), we can simplify the above to just:

time += timestep;

position += timestep * (velocity + timestep * acceleration / 2);
velocity += timestep * acceleration;

where the extra term in bold is the only change compared to basic Euler integration.

Compared to Euler integration, the velocity Verlet and leapfrog methods have several nice properties:

• 
  

  For constant acceleration, they give exact results (up to floating point roundoff errors, anyway), meaning that ballistic jump trajectories stay the same even if the timestep is changed.

  
  


• 
  
  

  They are second order integrators, meaning that, even with varying acceleration, the average integration error is only proportional to the square of the timestep. This can allow for larger timesteps without compromising accuracy.

  
  


• 
  

  They are symplectic, meaning that they conserve energy if the underlying physics do (at least as long as the timestep is constant). In particular, this means that you won't get things like planets spontaneously flying out of their orbits, or objects attached to each other with springs gradually wobbling more and more until the whole thing blows up.

  
  

Yet the velocity Verlet / leapfrog method are nearly as simple and fast as basic Euler integration, and certainly much simpler than alternatives like fourth-order Runge-Kutta integration (which, while generally a very nice integrator, lacks the symplectic property and requires four evaluations of the force() function per time step). Thus, I would strongly recommend them for anyone writing any sort of game physics code, even if it's as simple as jumping from one platform to another.

---

Edit: While the formal derivation of the velocity Verlet method is only valid when the forces are independent of the velocity, in practice you can use it just fine even with velocity-dependent forces such as fluid drag. For best results, you should use the initial acceleration value to estimate the new velocity for the second call to force(), like this:

acceleration = force(time, position, velocity) / mass;
time += timestep;
position += timestep * (velocity + timestep * acceleration / 2);
velocity += timestep * acceleration;
newAcceleration = force(time, position, velocity) / mass;
velocity += timestep * (newAcceleration - acceleration) / 2;

I'm not sure if this particular variant of the velocity Verlet method has a specific name, but I've tested it and it seems to work very well. It's not quite as accurate as fouth-order Runge-Kutta (as one would expect from a second-order method), but it's much better than Euler or naïve velocity Verlet without the intermediate velocity estimate, and it still retains the symplectic property of normal velocity Verlet for conservative, non-velocity-dependent forces.

Edit 2: A very similar algorithm is described e.g. by Groot & Warren (J. Chem. Phys. 1997), although, reading between the lines, it seems that they sacrificed some accuracy for extra speed by saving the newAcceleration value computed using the estimated velocity and reusing it as the acceleration for the next timestep. They also introduce a parameter 0 ≤ λ ≤ 1 which is multiplied with acceleration in the initial velocity estimate; for some reason, they recommend λ = 0.5, even though all my tests suggest that λ = 1 (which is effectively what I use above) works as well or better, with or without the acceleration reuse. Maybe it's got something to do with the fact that their forces include a stochastic Brownian motion component.