Doing Game Gravity Right(niksula.hut.fi) |
Doing Game Gravity Right(niksula.hut.fi) |
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.
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.
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.
Midpoint
v(n+1) = v(n) + a(n)*dt
x(n+1) = x + v(n)*dt + 0.5*a(n)*dt^2
Velocity Verlet
v(n+1) = v(n) + 0.5*[a(n)+a(n+1)]*dt
x(n+1) = x + v(n)*dt + 0.25*[a(n)+a(n+1)]*dt^2
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.
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.
Also, it's very important to people's perceptions of performance (whoa) to maintain a consistent frame-rate. The variations are much more noticeable than the absolute rate. Finally, on lots of hardware, you can't actually display at 59Hz, say. You'll either be at 60 or 30, and will oscillate between the two in a most annoying way.
You are already storing all these values in floats which is inherently inaccurate. Also if the dt becomes very large you have bigger problems than gravity anyway.
Like, you probably would believe the amount of people playing Quake Live at 7 fps.
Plus there is a lot of things you don't know; maybe he haves the minimum requirements but he is running a lot of background process because he installed a bunch of things he doesn't use.
And with a constant delta, if you choose it right, it can be easier to get collision detection right. You can possibly get away with checking if two things are colliding with each other right this tick instead of checking if they might have run through each other between ticks. With variable delta, if you want to get it right, you might have to check where things where half a frame ago and such, and at that point it might be easier to just check more often instead.
And I think you should probably ask the same question about variable deltaTime. Assuming that coupling rendering and game logic is not some best practice that you should default to, why would you want variable deltaTime? (There may or may not be some good answers to that, and maybe it totally depends on the game and so on.)
One good argument for variable dT is if you do enough logic such that game time may be a major performance bound. If on a machine that is running fixed dT cannot perform all computation in the allotted time, then the game will get behind schedule, and how do you resolve the problem of having a wall clock 10, 100, or more frames ahead of simulated time when you can't keep up. In that regard variable dT degrades more gracefully.
Sure, it makes some things easier, but it comes at some cost.
During the far majority of use cases the timestep is fine, and you are just creating deadweight by doing this. Plus I guess you are now doing tunneling checks as well to create further deadweight for the rare occasion when someone has framerate issues.
I am looking at this in the sense that I would actually implement this in a game I make, and I would not because the upside of doing this is basically "if the game is already fucked I want it to be maybe not as fucked but still having many other big issues with pretty much every other component of the game logic", vs a bunch of deadweight when the game is running correctly, which should be 99.5% of use cases.
Am I adding assumptions here? I guess so but they are real ones for real game developers. Unless you are doing something very unusual these would be your concerns.
This is not an academic exercise for me like it maybe is for you and most of the commenters it seems like.
My point originally was about this statement of yours, that is purely conceptual and you skew the discussion to address the other part of your comment (or you through that was the point but didn't explain so in your answers)
But anyway, one assumption is that every game should have a fixed gamestep, in many single player games (real single player games) you don't want to do that, because is preferable that the user can see the ball coming to the player than to magically appear behind the player even if that is "timely correct"; the ball/interface going slow is a lot less frustrating that losing without realizing why. Platformers for PC with (virtual) high speed movements come to mind as a common example of this.
Even multiplayer games suffer of this; in most online FPS if the server suddenly slows down all the players start experiencing lag and everyone looks like they are "teleporting"; with a not-fixed-timestep you could slow everyone down so the problem becomes a lot less frustrating because the player still have complete control and understanding of their in-game character; just a bit slow-mo until the server speeds up to normal. The teleporting should be used only to sync with the server when the client connection is the one with problems updating.
I can't think of a framework that doesn't have a fixed timestep except for maybe gamemaker or some of the simpler frameworks. Maybe some of the html5 stuff is non-fixed timestep but that is a field that is just coming into its own right now.
None of the bigger 2d or 3d physics engines today that I know of use a non-fixed timestep.
In platformers with high speed movements fixed timesteps are even more important because of tunneling. You can often account for tunneling in some of the better physics engines but it is sloooow.
In fps games there is a lot of interpolation going on with the server correcting player and object positions. If the server lags you and everything else is going to teleport no matter what. The server is not even accepting your control input at that point so either you are going to desync or you are going to teleport when the server tells you your real position. Generally in fps games only critical physics objects are being server corrected anyway, this is usually a small fraction of the physics objects. For example if an enemy fires a rocket at you that is not usually server corrected. If you get hit in the server calculations then you got hit whether or not you think you dodged it client side.
My point is that if the server hiccups your jump being slightly off is not the big problem, The big problem is that the controls are unresponsive. Also when the server hiccups it is rarely the actual fixed timestep serverside that is your problem, it is the internet. If your computer hiccups then it is not updating positions from the server so all critical objects are going to teleport. Could there maybe be slightly less teleporting on non-player controlled critical physics objects? Maybe so but if you are losing that many timesteps than things are going to jump around on your screen no matter what because your framerate is like 5.
Why would server lag effect FPS? I can only see how it would effect the reported positions of the other players because you aren't getting updates to changes in their movement. Server lag should never effect your FPS.