Programmers and physics

I’m sure it’s an age thing. Despite over 30 years of evidence to the contrary, I still think of programming as an adjunct to math and science, so I’m always shocked when I see things like this little writeup by Hannu Kankaanpää. It’s an explanation of how to write a program that tracks the motion of an object under the pull of gravity, and Hannu wrote it because he noticed that game programmers were often doing it wrong.

What’s shocking about it? Well, the equations Hannu presents have been around for about 300 years and are currently taught in high school physics classes. We’re not talking about a secret algorithm known only to ninja coders. That he felt the need to present them in tutorial fashion in 2004—and to present examples of how many (most?) programmers were using the wrong formulas—is an indictment of the sorry state of math and science knowledge among software “engineers” at the time. That it recently made it onto Pinboard’s Popular page, suggests that there’s been little improvement.

The article presents game programmers as a weird mix of sophistication and ignorance. Hannu refers to the common technique for calculating motion as Euler’s method. He must believe his audience knows that term, which implies a familiarity with numerical methods. And yet within the world of numerical analysis, Euler’s method is famous for two things:

  1. Its conceptual simplicity. It provides a gentle introduction to the numerical solution of differential equations.
  2. Its appalling accuracy. Initial value problems solved by Euler’s methods drift blithely away from the true solution.

I can only assume that programmers who use Euler’s method have never actually learned any numerical analysis, and have just been passing this crappy algorithm around without any understanding of how it works (and doesn’t work).

Even worse is the notion that a numerical solution is necessary, something that even Hannu falls prey to. The great thing about motion under gravity (or any constant acceleration) is that it has a perfectly simple analytical solution:

[v = v_0 + g t] [x = x_0 + v_0 t + \frac{1}{2} g t^2]

This works for any set of initial position and velocity, [x_0] and [v_0], and any time interval, [t], for as long as the only force acting on the object is gravity. You can use it as an incremental solution if you want,

[v_{i+1} = v_i + g \, \Delta t] [x_{i+1} = x_i + v_i \, \Delta t + \frac{1}{2} g (\Delta t)^2]

although you run the risk of accumulating small roundoff errors if you do. You can also rearrange the order of operations to make the calculation more efficient. But whatever the form you express it in, the solution is simple, straightforward, and has been known since the Principia. Worth more than a passing glance if you want your game to work like real life.

9 Responses to “Programmers and physics”

  1. Jasker says:

    And when the acceleration is not constant (like n-body gravitational systems, as is my pet interest) there’s all this:

    The again, on the biggest budget (and graphically state of the art) game of the year, I see dodgy rag-doll physics flinging men backwards and off a moving boat time after time, as though someone goofed relative motion. They seemed planted straight into the external (river) environment while still on the deck.

    Mind, it does have an actual swivel chair with apparently correct angular momentum (when shot, don’t try sitting on it, this is an FPS after all). Swings and, uh, turning circles.

  2. Arjan Boerma says:

    Doc, your final equation actually contains a hint for fixing the Euler method: if you do x:=x+v*Dt+a/2*Dt^2 instead of just x:=x+v*Dt (and if gravity is constant) then the integration error is zero. That second-order term (a/2*Dt^2) is negligible locally if Dt is small enough, but small local errors may still accumulate to a large global error, like Hannu shows in his first set of parabolas.

    By the way, although Hannu has that second-order term in his last paragraph, he also neglects it in the first part. That’s why in his second set of parabolas the 3 fps jump still doesn’t cover the same distance the 60 fps jump does.

    Regarding your main point, why don’t programmers just use the analytic solution? I’d guess that most game physics engines are built on a conceptual model that goes somewhat like “force leads to acceleration leads to a change in velocity leads to a change in position”. It’s difficult to break out of that incremental mindset.

  3. Clark says:

    What’s surprising is that I think most comp sci degrees require a class in numeric methods along with a reasonable lower division math track.

  4. Dr. Drang says:

    When I was young(er) and foolish and read Slashdot, I noticed that lots of programmers thought a CS degree (or any degree) was a waste of time. “Better to just get out there and code, man.” It’s like working in an auto repair shop instead of getting a mechanical engineering degree.

  5. Aristotle Pagaltzis says:

    What’s surprising is that you think game developers have CS degrees, Clark. :-) In the era of the small computer game publishers, essentially every game studio was a hobby-turned-business, and just about everyone in game programming was completely self-taught and often as not hadn’t even gone to college. That has probably changed with the precipitous increase in the complexity and budget of game development, and with the concomitant consolidation of the industry around a handful of behemoth studios. Back in those days, though, a lot of things like how to simulate gravity were passed as lore by word of mouth in just this tutorial form. Those tutorials were generally written by people who either had no background whatsoever in the subject, but tried something and found it to work, or else who had just enough to reverse-engineer the solutions of “luminaries” and try to boil down their gist so everyone else could use it. “Luminaries” were generally those with mathematical aptitude (and formal education) as well as programming chops – most famously, obviously, John Carmack. Notably, a lot of them did not come (primarily) from hobbyist teenage PC/HC game hacking, but as I later found out, had backgrounds connected in some way to the Unix and graphics workstation industry – i.e. they were coming from much more capable hardware, running much more sophisticated software, all built with the benefit of a lot of formal knowledge, and were shrinking those high-level approaches to within the limitations of PC hardware. To the self-taughts who started as gamers, maths was a means to an end, and in fact a necessary evil – though over time many would come to appreciate its usefulness to what they were trying to do.

    That very last point may highlight the real failure of education here.

  6. Dr. Drang says:

    Interesting that you point out Carmack as someone with mathematical chops, Aristotle. The example of bad gravity handling in Hannu’s article is from Quake.

    While I’m here, I suppose I should mention that Euler’s method does have one redeeming quality: it’s fast. And with lower-end hardware back in the old days, that may have overridden concerns about consistency and accuracy.

  7. Aristotle Pagaltzis says:

    I was thinking about that. It actually occurred to me while writing the comment, but then I neglected to mention it.

    One thing that has to be kept in mind is that especially in the ancient era before GPUs that outperform the CPU were commodity hardware, one goal of the applied mathematics going into graphics code was to find approaches that would decompose higher-order operations (starting with multiplication) that operated over time into series of additions or subtractions. (I.e. if you need to calculate d = i * x for each frame, and i increases by 1 for each frame, it was much cheaper to keep an accumulator and do d += y for each frame. And it’s still cheaper, though it doesn’t make as much of a difference any more.) Inaccurate approximations were an acceptable trade-off in pursuit of such reformulations of an equation.

    (It is hard nowadays to appreciate just how limited hardware resources were at the time. Quake 1 did full-screen texture-mapped 3D in softwareon a 486! (Granted the resolution was something else than what we think of as full-screen now. That’s just part of what is hard to appreciate now though – it was nevertheless immersive.))

  8. Arjan Boerma says:

    I don’t think performance is the reason people go for Euler integration. The extra cost of fixing it (for constant gravity specifically) is one addition per time step: adding $\frac{1}{2}g \Delta t^2$ to position. That’s just a number: it only needs to be recalculated when the time step size changes.

  9. Clark says:

    Yeah, I should have realized that. Back in the boom in computer game coding locally a bunch of people tried to recruit me because they didn’t understand simple physics. Probably should have taken the job but didn’t realize how dire the situation for programmers was.

    Still many programmers I know either have CS degrees or related degrees. Agree there’s lots of people more untrained out there too.