A good summary is here: http://gafferongames.com/game-physics/integration-basics/
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.
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.
Especially the Leapfrog integrator seems cool:
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.
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.
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.
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.
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.
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.
The whole point of dt is to deal with variable framerate.
Either way Tlark is right, you really don't want the game logic to be affected by framerate.
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.
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.
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).
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.
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.
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)
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)
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)
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).
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.
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.
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.
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.
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
(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.)
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.