Hacker News Reader

Comment by ori_b | Hacker News Reader

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/

View on HN

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

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.

IIRC

  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

With fixed acceleration a(n)=a(n+1) so the two methods are equivalent.

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

Interesting.

Especially the Leapfrog integrator seems cool:

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

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.

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.

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

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.

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

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.

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

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.

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

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.

And yet another reason why the serious competitors would turn off almost all graphics so that all you saw were colored boxes running around in colored boxes.

Reply on news.ycombinator.com