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://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
http://www.richardlord.net/presentations/physics-for-flash-games
http://lolengine.net/blog/2011/12/14/understanding-motion-in-games
Doom es un mal ejemplo, en el juego original (Vainilla Doom) tanto el 1 como el 2 no se puede saltar... ¡no hay tecla de salto!. La función de salto fue introducida mucho después mediante el uso de "sourceports"
ResponderEliminarOtras curiosidades mas visibles en el IdTech2 que en el 1, es la capacidad de encadenar saltos, los cuales son cada vez mas largos, o que avanzando en Diagonal, se avanza mas rápido que de frente o lateralmente (strafe)
ResponderEliminarY lo que comentas de la gravedad si esta muy presente en el Quake1, el salto que hay que hacer para escoger el modo de juego "hard" es imposible en ordenadores lentos de la época (a no ser que hicieras el truco de correr en diagonal).
¿Por qué se usa el método numérico de Euler (o cualquier otro) para programar las ecuaciones del movimiento si ya conocemos la solución exacta? posición(t)=0.5*gravedad*t^2+velocidad_inicial*t+posición_inicial
ResponderEliminares que el enfoque es otro. Hay que pensar numéricamente. En un instante de tiempo, tienes una pos, vel, accel. Y en el siguiente, otra. En cada momento tienes valores distintos. Para eso sirve.
ResponderEliminarLo que tú planteas es una ecuación general, pero que no es aplicable según te entiendo a este caso. Sirve para predecir posición en cada instante, pero para eso estás dando por hecho que la velocidad y la aceleración no varían. Y en un vídeojuego, eso no es verdad. Por ejemplo.