Doing Game Gravity Right

http://www.niksula.hut.fi/~hkankaan/Homepages/gravity.html

by Charles__L • 14 years ago

296 81 14 years ago

niksula.hut.fi

chrismorgan• 14 years ago

This is known as the midpoint method.

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

ww520• 14 years ago

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

hyperlogic2• 14 years ago

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.

pfisch10• 14 years ago

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.

mikeash• 14 years ago

You'll have small variations at higher framerates too. Why not just avoid variation in this altogether? It's almost no extra work, and it makes things more consistent.

pfisch10• 14 years ago

You're also using floats to store the values. This seems silly and looks like it will be slightly slower to calculate.

Unless your game is running like garbage this will not matter. You are talking about a dt of something like 1/30 or 1/60

lalc• 14 years ago

Drops in framerate happen. Why not make a best effort for accuracy? Also, it's interesting and insightful.

eyfdhbvccx• 14 years ago

> Drops in framerate happen.

No, they don't.

Game logic should run at constant 60 or more fps, even when graphics framerate is lower: http://gafferongames.com/game-physics/fix-your-timestep/

But yes, it's an interesting article, and this method allows for a bit more accuracy.

jQueryIsAwesome5• 14 years ago

You wouldn't believe the amount of people who plays Sims 3 at 7 fps.

pfisch10• 14 years ago

Does sims 3 even have gravity?

robertfw• 14 years ago

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.

pfisch10• 14 years ago

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

teamonkey3• 14 years ago

On the PS2 you could adjust the roll and pitch of your car in midair. It was possible to do backflips.

tlarkworthy• 14 years ago

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.

charliesome• 14 years ago

It may still be wrong, but the point is that it's less wrong and it's not much extra effort.

rorrr• 14 years ago

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• 14 years ago

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.

anonymous• 14 years ago

Then the game runs in slow motion. There's not much you can do on a slow system.

Or if you mean that you may be forced to draw at (for instance) 55fps, then the solution is to precalculate the next physics frame and linearly interpolate between the previous and next frame when drawing.

Jare• 14 years ago

This problem involves performance, precision, code stability and player perception, so there are no hard and fast rules applicable everywhere, and certainly do not need always to be fixed in concrete. A game can mix variable dt and fixed dt in different subsystems (render, logic, physics, user input, network, ...).

I have even managed to dynamically change these settings and parameters on the fly: which subsystems use which method, the lower and upper limit for variable dt, number of iterations per render frame, and even value to use for fixed dt, all adjusting depending on framerate and state of the game.

A classic example of this is, during a big explosion you may need maximum precision on physics (fixed dt with low value), can afford variable dt on behaviour and interface (since stuff is just blowing up in the air), and can benefit from a low maximum dt that causes a bit of slow-motion (John Woo style!).

When you're doing multiplayer there's a lot less you can afford to change, because you need to keep timing sane and synced across clients & server. Everything depends on the game, the engine, the platform, and the dynamics of what the player is seeing.

ori_b• 14 years ago

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/

dylnclrk• 14 years ago

Verlet Integration is another way to solve this kind of DE (i.e. DEs related to kinetics) quickly and time-reversibly... https://en.wikipedia.org/wiki/Verlet_integration

hyperlogic2• 14 years ago

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.

ndonnellan• 14 years ago

Maybe there are other forces? Like air friction? I'm just guessing.

walrus• 14 years ago

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.

baq• 14 years ago

remember this is a game. gravity is only one of the forces present.

csense2• 14 years ago

I think the article is handling it this way for pedagogical reasons. It's more clearly in the realm of "Software Engineering" to say "This is what our solution's trying to approximate, and the easiest approximation causes practical problems, so this is a better way to approximate the same thing (in an only slightly more complicated way) by adding an extra term." The author's approach is easier to understand because it's merely a small patch on an existing design.

If you say "By the way, there's an exact solution to this, it involves something called Integrals that's usually the focus of at least three semesters of Calculus in college, but you can't really understand it without a few courses in Real Analysis, Differential Equations, and Numerical Methods..." then it seems like you're talking too much about Math instead of Software Engineering. As a result, you lose the audience whose main interest is making games for fun and profit, and don't care about math (or so they think). It's much harder to understand because it's a complete redesign of the integrator that relies on a non-trivial body of theory.

flyosity• 14 years ago

Just a note here that this person's blog is utterly amazing for folks just getting into game physics-related programming. All the articles are gold.

teamonkey3• 14 years ago

> This is still Euler integration

Actually it's a form of Verlet integration, which performs much better than Euler's method while being much cheaper than RK4.

Euler's method does not perform well with any form of acceleration and should not be used when acceleration is present. The equations here will remain accurate under constant gravity.

jheriko• 14 years ago

actually this is the 'midpoint' method. verlet is different in that it negates needing the first order term altogether, which is instead gotten at any instant from the previous and current position (zeroth order term).

but yes, verlet is much more powerful for game physics, especially when coupled with constraints since it allows all kinds of non-trivial behaviour (angular momentum) to fall out.

lloeki• 14 years ago

> This is still Euler integration, which has poor accuracy whenever the derivative varies with time.

Which is why decoupling the physics delta from the rendering framerate is important. The author mentions Quake (id Tech 1, 2 or 3 ?), and I seem to recall id Tech 4 (Doom 3) was the first id Tech engine that implemented that.

shabble• 14 years ago

I have a vague recollection that it was fixed or mostly eliminated in Quake 3. It was definitely still an issue in Quake 2, and one relatively well-known cheap trick was leading people towards particularly architecturally dense parts of the map and using a weapon such as the hyper-blaster, which was a high rate of fire laser gun for some unfortunate reason was implemented as a discrete particle/projectile for each shot. This would sometimes slow down the opponent(s) significantly enough to make a difference.

There were also special moves, especially rocket jumps, and double-jumps that were impossible <60fps, and got easier towards 100+ (This being in the days of 200MHz pentiums and software rendering, "Monster 3D 4MB", and intense envy of those who could afford 2x 12MB Voodoo II cards.

rom16384• 14 years ago

RK4 is indeed a popular and standard method. However for this particular equation or other equations with a conserved quantity a Symplectic integrator [1] should be used, as they are much better at keeping the numerical solution close to the real solution since they conserve the quantity of interest (energy, etc.).

[1] https://en.wikipedia.org/wiki/Symplectic_integrator

Gravityloss2• 14 years ago

Interesting.

Especially the Leapfrog integrator seems cool:

http://en.wikipedia.org/wiki/Leapfrog_integration

csense2• 14 years ago

RK4 is hard to write. Symplectic integrator looks even harder. (I'm not familiar with symplectic integration, but I've just read the Wikipedia article and it's not immediately obvious how to go from the math in the article to working code. I have written an RK4 integrator in the past, and the RK4 Wikipedia article looks like it's much easier to apply if you're writing the integrator for a physics engine.)

Euler, Euler midpoint, and Verlet are all very easy to code.

Also, you have to keep in mind the operation count versus the numerical stability. For the case under discussion -- constant acceleration -- Euler midpoint is perfectly suitable, as it gives the same answer as an exact analytical solution for the case where x(t) and y(t) are quadratic polynomials. RK4 or the like would only result in longer and slower code with no actual benefit in this particular application.

tzs• 14 years ago

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• 14 years ago

I'm between doing that course or doing this one: http://ocw.mit.edu/courses/mathematics/18-03sc-differential-...

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• 14 years ago

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.

Trufa• 14 years ago

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• 14 years ago

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.

lnanek2• 14 years ago

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.

jpatokal• 14 years ago

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

mikevm• 14 years ago

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".

Xcelerate• 14 years ago

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• 14 years ago

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)

brianchu• 14 years ago

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.

raldi2• 14 years ago

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

Garoof4• 14 years ago

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.)

raldi2• 14 years ago

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

Strilanc• 14 years ago

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• 14 years ago

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.

podperson• 14 years ago

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).

martinced• 14 years ago

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.

JabavuAdams2• 14 years ago

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.

snake_plissken• 14 years ago

right vs left sided delta summations. calc 1.

Doing Game Gravity Right

Related Stories