54
\$\begingroup\$

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

\$\endgroup\$
2

6 Answers 6

64
\$\begingroup\$

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.

\$\endgroup\$
16
  • 2
    \$\begingroup\$ @PizziraniLeonardo: You can use (a variant of) velocity Verlet just fine even for velocity-dependent forces; see my edit above. \$\endgroup\$ Nov 1, 2012 at 21:55
  • 2
    \$\begingroup\$ Literature does not give this interpretation of Velocity Verlet a different name. It relies on a predictor-corrector strategy, as also stated in this paper fire.nist.gov/bfrlpubs/build99/PDF/b99014.pdf . \$\endgroup\$
    – teodron
    Nov 2, 2012 at 15:13
  • 3
    \$\begingroup\$ @Unit978: That depends on the game, and specifically on the physics model it implement. The force(time, position, velocity) in my answer above is just shorthand for "the force acting on an object at position moving at velocity at time". Typically, the force would depend on things like whether the object is in freefall or sitting on a solid surface, whether any other nearby objects are exerting a force on it, how fast it's moving over a surface (friction) and/or through a liquid or gas (drag), etc. \$\endgroup\$ Nov 23, 2014 at 11:10
  • 1
    \$\begingroup\$ @Fabio: Not really. What we're doing is applying the full force once, then recalculating the force at the new location (and time and velocity), and adjusting the velocity change by half of the difference between the new and the old force. Thus, the total change in velocity is, in effect, the average of the new and the old force (divided by mass). Here's a diagram that might (maybe) make it a bit clearer. \$\endgroup\$ Aug 9, 2015 at 21:01
  • 2
    \$\begingroup\$ @WolfgangSchreurs: Not on those three lines, it isn't. But quite often you do want to know what time it is in your physics simulation. Basically, the "output" of the code is a (time, position, velocity) tuple, indicating that the simulated object(s) at time t are at position x and moving with velocity v. It's then up to the rest of your code to take that output and do something with it, like detecting collisions, drawing the objects on the screen and possibly interpolating between consecutive time steps to make the animation smoother. \$\endgroup\$ Nov 30, 2020 at 16:28
14
\$\begingroup\$

Every update loop of your game, do this:

if (collidingBelow())
    gravity = 0;
else gravity = [insert gravity value here];

velocity.y += gravity;

For instance, in a platformer, once you jump gravity would be enabled (collidingBelow tells you whether or not there is ground right below you) and once you hit the ground it would be disabled.

Besides this, to implement jumps, then do this:

if (pressingJumpButton() && collidingBelow())
    velocity.y = [insert jump speed here]; // the jump speed should be negative

And pretty obviously, in the update loop you also have to update your position:

position += velocity;
\$\endgroup\$
7
  • 6
    \$\begingroup\$ What do you mean? Just pick your own gravity value and since it changes your velocity, not just your position, it looks natural. \$\endgroup\$
    – Pecant
    Aug 9, 2011 at 12:37
  • 1
    \$\begingroup\$ I dislike turning off gravity ever. I think that gravity should be constant. The thing that should change (imho) is your ability to jump. \$\endgroup\$ Aug 26, 2011 at 15:20
  • 2
    \$\begingroup\$ If it helps, think of it as 'falling' rather than actually 'gravity'. The function as a whole controls whether or not the object is falling due to gravity. Gravity itself exists just as that [insert gravity value here]. So in that sense, gravity is constant, you just don't use it for anything unless the object is airborne. \$\endgroup\$ Aug 26, 2011 at 16:01
  • 2
    \$\begingroup\$ This code is frame-rate dependent, which isn't great, but if you have a constant update then you're laughing. \$\endgroup\$
    – tenpn
    Aug 26, 2011 at 16:09
  • 1
    \$\begingroup\$ -1, sorry. Adding velocity and gravity, or position and velocity, that just does not make sense. I understand the shortcut you're doing, but it's wrong. I would hit any student or trainee or colleague doing that with the largest cluebat I could find. Consistency of units does matter. \$\endgroup\$ Nov 2, 2012 at 0:52
9
\$\begingroup\$

A proper frame-rate independent* newtonian physics integration:

Vector forces = 0.0f;

// gravity
forces += down * m_gravityConstant; // 9.8m/s/s on earth

// left/right movement
forces += right * m_movementConstant * controlInput; // where input is scaled -1..1

// add other forces in for taste - usual suspects include air resistence
// proportional to the square of velocity, against the direction of movement. 
// this has the effect of capping max speed.

Vector acceleration = forces / m_massConstant; 
m_velocity += acceleration * timeStep;
m_position += velocity * timeStep;

Tweak gravityConstant, movementConstant and massConstant until it feels right. It is an intuitive thing and can take a while to get feeling great.

It's easy to extend the forces vector to add new gameplay - for instance add a force away from any nearby explosion, or towards black holes.

*edit: these results will be wrong over time, but may be "good enough" for your fidelity or aptitude. See this link http://lol.zoy.org/blog/2011/12/14/understanding-motion-in-games for more info.

\$\endgroup\$
7
  • 4
    \$\begingroup\$ Don't use Euler integration. See this article by Glenn Fiedler which explains the problems and solutions better than I could. :) \$\endgroup\$ Aug 26, 2011 at 16:18
  • 1
    \$\begingroup\$ I understand how Euler is inaccurate over time, but I think there are scenarios where it doesn't really matter. As long as the rules are consistent for everyone, and it "feels" right, it's fine. And if you're just learning about phyiscs, it's very easy to remember and implmenet. \$\endgroup\$
    – tenpn
    Aug 26, 2011 at 16:28
  • \$\begingroup\$ ...good link though. ;) \$\endgroup\$
    – tenpn
    Aug 26, 2011 at 16:35
  • 4
    \$\begingroup\$ You can fix most of the issues with Euler integration simply by replacing position += velocity * timestep above with position += (velocity - acceleration * timestep / 2) * timestep (where velocity - acceleration * timestep / 2 is simply the average of the old and new velocities). In particular, this integrator gives exact results if acceleration is constant, as it typically is for gravity. For better accuracy under varying acceleration, you can add a similar correction to the velocity update to get velocity Verlet integration. \$\endgroup\$ Oct 31, 2012 at 12:55
  • \$\begingroup\$ Your arguments make sense, and the inaccuracy is often not a big deal. But you should not claim it is a “proper frame-rate independent” integration, because it just isn’t (framerate independent). \$\endgroup\$ Nov 2, 2012 at 0:48
6
\$\begingroup\$

If you want to implement gravity on a slightly bigger scale, you can use this kind of calculation each loop:

for each object in the scene
  for each other_object in the scene not equal to object
    if object.mass * other_object.mass / object.distanceSquaredBetweenCenterOfMasses(other_object) < epsilon
      abort the calculation for this pair
    if object.mass is much, much bigger than other_object.mass
      abort the calculation for this pair
    force = gravitational_constant
            * object.mass * other_object.mass
            / object.distanceSquaredBetweenCenterOfMasses(other_object)
    object.addForceAtCenterOfMass(force * object.normalizedDirectionalVectorTo(other_object))
  end for loop
end for loop

For even bigger (galactic) scales, gravity alone won't suffice to create "real" motion though. The interaction of star systems is to a significant and very visible extent dictated by Navier-Stokes equations for fluid dynamics, and you'll have to keep the finite speed of light - and thus, gravity - in mind too.

\$\endgroup\$
1
  • \$\begingroup\$ This is a very clear definition of how to apply this. Do you have any more examples such a site? Or are you just amazing at explaining things? \$\endgroup\$
    – Glycerine
    Dec 24, 2019 at 20:13
1
\$\begingroup\$

The code provided by Ilmari Karonen is almost correct, but there is a slight glitch. You actually compute the acceleration 2 times per tick, this does not follow the textbook equations.

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

The following mod is correct:

time += timestep;
position += timestep * (velocity + timestep * acceleration / 2);
oldAcceletation = acceleration; // Store it
acceleration = force(time, position) / mass;
velocity += timestep * (acceleration + oldAcceleration) / 2;

Cheers'

\$\endgroup\$
1
  • \$\begingroup\$ I think you're wrong, as acceleration depends on velocity \$\endgroup\$
    – super
    Oct 31, 2017 at 14:24
-4
\$\begingroup\$

Pecant's answser ignored frame time, and that makes your physics behavior differently from time to time.

If you are going to make a very simple game, you can make your own little physics engine -- assign mass and all kinds of physics parameters for every moving object, and do collision detection, then update their position and velocity every frame. In order to accelerate this progress, you need to simplify the collision mesh, reduce calls of collision detection, etc. In most cases, that's a pain.

It's better to use physics engine like physix, ODE and bullet. Any of them will be stable and efficient enough for you.

http://www.nvidia.com/object/physx_new.html

http://bulletphysics.org/wordpress/

\$\endgroup\$
2
  • 4
    \$\begingroup\$ -1 Unhelpful response that does not answer the question. \$\endgroup\$ Aug 10, 2011 at 7:39
  • 4
    \$\begingroup\$ well, if you want to adjust it for time, you can just scale the velocity by the elapsed time from the last update(). \$\endgroup\$
    – Pecant
    Aug 14, 2011 at 1:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .