
Doing Game Gravity Right - Charles__L
http://www.niksula.hut.fi/~hkankaan/Homepages/gravity.html
======
ori_b
This is still Euler integration, which has poor accuracy whenever the
derivative varies with time. The standard numerical integration method is 4th
order Runge Kutta. RK4 is also popular for solving many forms of differential
equations.

A good summary is here: <http://gafferongames.com/game-physics/integration-
basics/>

~~~
hyperlogic
Correct me if I'm wrong, there is no reason to numerically integrate this.
This is not a differential equation. The integral solution is a simple
function that can just be evaluated.

~~~
walrus
Leaving it as a differential equation gives you some room to experiment more
easily. For example, suppose you want to add a swimming mechanic to your game:
you might end up with a completely different closed form solution, but if you
left it as a differential equation it could just be a couple extra additive
terms.

------
tlarkworthy
you are still doing it wrong. dt should not be affected by framerate.
<http://gafferongames.com/game-physics/fix-your-timestep/>

use an accumulator to have a fixed dt no matter the framerate. With a variable
step size you risk all kinds of weird bugs linked to the hard to debug
rendering context. The size of dt should be consider a system parameter, tuned
for your game and __fixed in concrete __.

~~~
rorrr
So what happens when the OS doesn't return to your process in _dt_ time?

The whole point of _dt_ is to deal with variable framerate.

~~~
paulhodge
When your game does regain control, it can run the simulation for N steps
(however many it usually does for the given dt), then finally render the scene
using the latest state. (so the game will appear to pause, then skip ahead).
Or it can try to play catch-up, it does 1 tick and render at a time, but with
a reduced delay between frames until it's "caught up". (so the game will
pause, then appear fast-forwarded for a bit).

Either way Tlark is right, you really don't want the game logic to be affected
by framerate.

------
JabavuAdams
This is still basically wrong for general game physics. I.e. you should _not_
blindly follow the author's suggestion to use it for all forces.

It _happens_ to be an exact solution for one very specific situation -- the
case of a constant force that is always applied. In this case, unvarying
gravity with no air resistance.

This is typically one of the first things you learn in a Classical Mechanics
course, because they can teach it using just Kinematics (the definitions of
displacement, velocity, and acceleration) before introducing Dynamics
(forces).

To prove it, you can just integrate the definition of acceleration twice and
recognize that the integration constants are your initial position and
velocity.

If the time-step changes or if forces are due to input, or other changing
factors then this is still a pretty terrible method.

Ah ... I should clarify ... the method is not so terrible, but rather the
author's explanation and rationale are. Basically, it slightly improves on one
little piece of the puzzle, and completely ignores the real issues like fixed
time steps, render/physics/network/game logic loop decoupling, and stiff
systems.

FWIW, I shipped two hit games this year that only used Euler integration and
worse hacks. It made life painful, though.

------
tzs
Udacity has a course, "Differential Equations in Action", that's about
numerical solutions of equations of motion and other differential equations
from physics, biology, and so on.
<http://www.udacity.com/overview/Course/cs222/CourseRev/1>

~~~
pvarangot
I'm between doing that course or doing this one:
[http://ocw.mit.edu/courses/mathematics/18-03sc-
differential-...](http://ocw.mit.edu/courses/mathematics/18-03sc-differential-
equations-fall-2011/)

Anyone has any insight into the strenghts and weaknesses of each one? I've
been unable to find any comprehensive review online about them. I don't have
time to do both simultaneously, but can do one first and the other later or
alternate between them.

I don't have a strong calculus background though I'm above the average
"programmer" or compsci graduate. I'm interested in simulation and numerical
problems (specially finite element method) but theoretical background is
welcome when its not overwhelming (i.e. when its there for you to understand
but its not the focus of the course).

~~~
EliRivers
The Python necessary for the Udacity one is a bit of a pig if you've never
coded in Python before. They help out a lot by essentially presenting complete
programmes with you needing only to fill out some extra calculations, so you
can concentrate on the important bit, but nonetheless if you're used to being
able to identify the type of an object by looking at its creation point it's a
bit of a mystery to begin with, especially since the first module uses 2D
arrays to represent location and velocity - there are some handy Python
functions to turn them into distances/vectors from various points, but if
you're not familiar with them you'll spend too much time wrestling with Python
instead of thinking about the DEs.

There's also the occasional big gap here and there between the video lecture
and what you're expected to do (indeed, sometimes it's actually quite tricky
to just work out what you're expected to do, despite the helpful comments in
the code - I've found that the hardest aspect is not solving the problem, but
getting a clear picture of the question being asked and translating the
solution into python). For language reference, I am an experienced coder in C
and C-related languages (C++ and non-Cocoa Obj-C).

Still, it's early days and I expect these things will be ironed out over time.

------
brianchu
For other simple methods of numerical integration, look at the Trapezoidal
Rule and Simpson's Rule, two staples of high school (or college) calculus.

Since we're talking about gaming, it bears noting that Box2D (and most physics
engines, for that matter) uses the Semi-implicit Euler method
(<http://en.wikipedia.org/wiki/Symplectic_Euler_method>). The author of Box2D
mentions that this is a better method than Verlet integration because
calculating friction requires knowing velocity.

------
Xcelerate
This same thing is used in molecular dynamics simulations. For instance, there
is an algorithm called RESPA that is used to break integrations of different
types of particle interactions into appropriate timestep intervals. Bond
vibrations must be calculated much more frequently than non-bonded
interactions.

The algorithm (reversible RESPA) is formally derived from the Liouville
operator (which governs the time evolution of any property):

    
    
        A(t) = exp(iLt) * A(0)
    

For instance, A(t) can be position or momentum. The Liouville operator must be
symmetric in order to generate a reversible numerical integration algorithm.

The result of all this is basically that:

    
    
        p(t + ∆t/2) = p(t) + ∆t/2 F(r(t))
        r(t + ∆t) = r(t) + ∆t p(t + ∆t/2)
        p(t + ∆t) = p(t + ∆t/2) + ∆t/2 F(r, t + ∆t)
    

where p is momentum, r is position, and F is force.

~~~
zbyszek
This was also colloquially known as the "leapfrog" algorithm and is the
simplest of a class of integrators that are symmetric (in simulation time) and
symplectic which are crucial properties for some simulations. I take it that
RESPA is the partitioning of the time evolution operator into components with
different force gradients, and the application of different integration
schemes to those components. One can also generalise leapfrog to integrate the
momentum (or some part) with n steps of dt/n.

The metric used to describe their accuracy is the degree to which they violate
the conservation of energy, which can be shown to be an odd integral power of
the timestep dt per step [0]. The error in leapfrog goes like the 3rd power.

Higher order integration schemes can be derived e.g. [1]. They may not be
useful in practice, depending on the cost of computing the individual terms
and the accumulation of finite precision errors. But the known scaling
behaviour provides a nice way of verifying the calculation of the evolution
operators. Another nice thing to do is to compute the "round trip", i.e.
integrate forwards in time, and then backwards. With a symmetric integrator
you should end up where you started in terms of position, momentum and energy,
regardless of step size, so computing a suitable difference and seeing how it
scales with trajectory length can be informative. (e.g. one can compute a
Lyapunov exponent from such round-trips to see if the underlying dynamics are
chaotic).

[0] McLachlan and Atela, Nonlinearity 5 (1992)
<http://www.massey.ac.nz/~rmclachl/si.ps> (PS) [1] M. Creutz, A. Gocksch;
Phys. Rev. Lett. 63 (1989) <http://thy.phy.bnl.gov/~creutz/mypubs/pub106.pdf>
(PDF)

------
chrismorgan
This is known as the midpoint method.

<http://en.wikipedia.org/wiki/Midpoint_method>

------
podperson
It's an interesting post, but perhaps a simpler way of looking at the whole
thing is you should be using average velocity over the time elapsed rather
than the just-calculated new velocity.

This becomes:

velocity_new = velocity_old + acceleration * time_elapsed

position_new = position_old + (velocity_old + velocity_new) * 0.5 *
time_elapsed

It makes immediate, intuitive sense (at least it does to me) and doesn't
require even thinking about differential equations (at least for constant
forces).

------
lnanek2
His improved graph actually still doesn't hit the peak at all frame rates. The
right way to do things from the usability perspective would be the calculate
the peak and make sure the player can hit exactly that at some point.
Otherwise areas that are supposed to be reachable may not be, as he says. The
code for that wold be a lot more complex, though, so it may be the wrong thing
from a business perspective, spending large amounts of your dev time on a
small edge case of users and user situations.

------
ww520
TIL that I have been doing acceleration calculation all wrong over the years.
Thanks for the insight.

~~~
hyperlogic
I'm a gamedev and I actually use this as in interview question. Getting people
to understand this distinction is the difference between pass and fail.

------
Strilanc
You can cut down the amount of error even further by not iterating. Instead of
iteratively updating the height, just store the initial position, velocity and
time. You still compute the current position as pi + vi * dt - a * dt * dt/2,
but intermediate results are discarded to avoid compounding floating point
errors.

Of course, you will need to update the initial position/velocity/time whenever
the jump is interrupted or modified. The reduction in error is also quite
small.

~~~
dalke
That assumes that there are no other forces. Your solution doesn't handle
momentum changes (throwing an object, or taking a bullet, or being close to an
explosion) while in the air, and it assumes that there's no maximum or
terminal velocity in the game. It also becomes trickier to compute when your
objects hit other objects.

You say that "you will need to update the initial [state vector] whenever the
jump is interrupted or modified" - that's exactly what numerical integration
does. So your solution seems like it would use a closed-form solution for some
cases, and numerical integration for others, which would make the dynamics
code easily twice as complicated.

While switching from Euler to leapfrog integration is a couple of lines of
change, for a better approximation.

------
pfisch
Why does this even matter? If you have a large delta time then your game is
fucked anyway. Collision detection will likely also be broken and the game is
unplayably choppy anyway so it doesn't even matter.

~~~
robertfw
I remember a car trick (do a barrel roll) in GTA San Andreas that for the life
of me I could not accomplish. I found out that this variable physics was
likely the problem - I dropped the graphics settings to minimum, and I was
able to do the trick.

This is on a quad core, 8GB ram, 1GB video card machine - it's no slouch - but
the subtle difference was enough to make my task impossible.

~~~
pfisch
Is this worth making the whole game run slower all the time for everyone? That
is what you are talking about here.

~~~
ncallaway
This is incorrect. The suggested approach makes the game significantly more
accurate adding 3 multiplications and an addition. This does not make the game
noticeably slower. If you're concerned about 3 multiplications and an addition
you're going to need to show me some profiler data that shows this as a
specific bottle-neck in the game-logic.

~~~
pfisch
No, you are talking about adding all of these operations per object in the
game world.

It doesn't stop at gravity either. Virtually everything in the game world is
moving via acceleration. If you were going to do this in a consistent manner
you would need to do this for every single physics calculation for every
single game world object.

You are correct that you would have to profile it to determine how much of an
issue it would be but it sounds like potentially a lot of deadweight to add to
the game. Especially since when games slow down it is often due to having a
lot of objects in the gameworld simultaneously.

------
Trufa
What id don't understand is, wouldn't this be only half more correct? I'm not
really sure if my question makes sense.

~~~
jws
It isn't that they cut the interval by half. It happens that for constant
acceleration, this midpoint happens to lay on the actual solution. Notice that
there is only one summing of position, and two of velocity.

------
jpatokal
This isn't exactly a new development, as the article in question was first
posted on May 13th, 2000.

~~~
mikevm
Even if something was first published in 1969, some of us are seeing it for
the first time. Anyhow, no one was claiming that this was a "new development".

------
raldi
Can someone explain the jumping parabola graphs? I can't make sense of the
description.

~~~
Garoof
X is time, Y is height. So something like, X time after hitting the jump
button, the guy is Y above the ground.

(Or you can pretend that the guy is moving towards the right at constant
speed, and jumping, and the points in the graphs are the different positions
he'll be at :)

(Edit: I'm not very sure about the pictures to the left though. Maybe higher
jumps/longer time or somethingsomething.)

~~~
raldi
Yeah, I don't get the difference between the left and right sides of the two
graphs either.

~~~
njharman
I believe the only difference is in units. Left showing delta time. right
showing FPS.

~~~
Garoof
Yeah, but shouldn't a delta of 1/3s be the same as 3fps? But the 1/3s to the
left does not look like the 3fps to the right.

And it does say that the picture to the right is just like in Quake. So I was
guessing that maybe the one to the left is not. Like, it has higher initial
velocity and max height, and longer time spent in the air. Like the picture to
the right is a jump that lasts for <1s while the one to the left is a way
longer one.

Would be nice to have like axes with labels and things on them.

------
snake_plissken
right vs left sided delta summations. calc 1.

------
martinced
There are several ways to do "game gravity right" and not just one answer.

For example some games have entirely reproducible game states which depends on
only two things: the seed given to the PRNG and the inputs made the player
(and the time at which they happened).

There are a lot of games (probably most of them) which have gravity but which
aren't "real" physics simulation and/or which do definitely not need a "real"
physics simulation to be, well, fun games.

Some of them do simply use integer-math and precomputed "gravity lookup
tables" entirely consisting of integers. You then use the time elapsed to know
where you should look in your table and you can of course compute a value
"between two lookup indices".

The advantage of integer math (either using gravity lookup table or not),
compared to floating-point math, is that your game engine can stay
deterministic even if the floating-point numbers implementation vary from one
platform / virtual machine to the other.

