Euler tiene la culpa de que no te pases el vídeojuego

Para los que no lo conozcan, Doom Quake es un vídeojuego de hace ya unos cuantos años de disparos en primera persona. Para quien no tenga ni idea de lo que digo, el jugador sólo veía en la pantalla de su ordenador una mano sujetando un arma, y el escenario del juego se movía desde un punto de vista en primera persona.

Este vídeojuego tenia un motor de simulación de la física de juego llamado Id Tech, del cual hubo varias ediciones. Este motor lo llevaron otros juegos, como el Quake o Wolfenstein, Pero resulta curioso un fallo que tenía el Doom Quake1:

Una de las cosas básicas que hay que simular en todo juego donde hay que correr, saltar, matar criaturas, etc... es la gravedad del mundo (ya sea Tierra u otra). ¿Cómo programarías la gravedad en un vídeojuego? La gravedad es un valor concreto de aceleración, y constante. Por lo tanto, ¿cómo calcularíais la posición en cada instante a partir de la aceleración instantánea?

Quizás se os ocurra esto:

Fijémonos en la velocidad: La velocidad en un instante es igual a la velocidad en el instante anterior + la gravedad* un intervalo de tiempo. Este intervalo ha de ser pequeño, de décimas o centésimas de segundo. 

A esto se le llama integración numérica de Euler. Sirve para pasar de la aceleración del juego a la posición. Si graficamos la posición según la fórmula de arriba, tendremos:

Lo cual es totalmente incorrecto. La gráfica ideal que buscamos es la siguiente. 

De hecho, si el intervalo de tiempo (dt) es muy grande en la fórmula incorrecta, o las imágenes por segundo que es capaz de procesar el ordenador son bajas, nos encontraremos con que el protagonista de Doom no salta lo mismo. ¡Lo cual hacía que en algunos ordenadores se pudiera pasar el juego y en otros no!

Cuanto más grande es el dt, más corto o bajo era el salto. Este despropósito se puede corregir de una manera sencilla:

Y así, el área integrada es la siguiente. Este área es exactamente igual que la que hay dos más arriba (con lo cual, es la gráfica correcta). Debajo de la línea están encerradas las mismas áreas.

La integración de Euler es la manera más simple de pasar de integrar numéricamente. Se sigue usando mucho, pero no sirve para todos los procesos. De hecho, una de las expresiones más usadas al respecto es only idiots use Euler integration (fuente).

A la hora de implementar un algoritmo de integración en un videojuego o una simulación física, hay que tener en cuenta estas características (fuente):

- Precisión

- Conservación de la energía

- Estabilidad

Euler tiene un grave problema de precisión y tampoco conserva la energía. No lo hace tampoco una alternativa muy usada, el algoritmo de Runge-Kutta4. Sí que lo hacen el método de Verlet, Newmark y Gauss-Runge-Kutta implícito. Estos métodos que conservan la energía se denominan symplectic (en inglés).

De hecho, ahora mismo la mayoría de videojuegos y simuladores pueden usar un motor como Physx, cuyos algoritmos conservan la energía (fuente). 

Echemos un vistazo a qué hacen RK4 y qué hace Verlet.

El primero tiene fama de ser un algoritmo difícil de implementar (sobre todo en según qué industria y con qué objetivo):

La ecuación principal de Runge-Kutta es y(n+1) = y(n) + un incremento formado por k1, k2, k3, k4, cuyas fórmulas están descritas abajo. Estos coeficientes son el resultado de la función que estamos analizando para distintos valores de t, y.  

¿Y qué hay de Verlet? Estrictamente, no vamos a ver la integración de Verlet, sino la integración de velocidad de este matemático (fuente).

Y este algoritmo no depende de los fraps per second, tal y como demuestran aquí, comparando Euler vs Verlet.

¿No os parecen todos los métodos muy parecidos? Pues así es. Euler y Verlet forman parte de una familia de métodos llamados Runge Kutta (concretamente, son RK1 y RK2). 

No dejéis de ver los enlaces que cito abajo, y esta presentación donde se comparan gravedad, fricción y resistencia aerodinámica de una manera muy gráfica según distintos métodos.

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

http://gafferongames.com/game-physics/integration-basics/

https://www.reddit.com/r/programming/comments/15f4qc/on_using_rk4_over_euler_to_integrate_for_physics/

http://www.adrianboeing.com/pal/papers/p281-boeing.pdf

http://codeflow.org/entries/2010/aug/28/integration-by-example-euler-vs-verlet-vs-runge-kutta/

https://news.ycombinator.com/item?id=4934855

http://www.niksula.hut.fi/~hkankaan/Homepages/gravity.html
http://www.richardlord.net/presentations/physics-for-flash-games
http://lolengine.net/blog/2011/12/14/understanding-motion-in-games