¿Por qué es RK4 mejor que la integración de Euler? [cerrado]

20

Al final de estas excelentes diapositivas , el autor compara todos los diferentes integradores presentados. De una forma u otra, todos se quedan cortos, excepto la Integración Euler mejorada y la Integración Runge Kutta 4 , que pasan todas las pruebas.

Supongo que debería mencionar que estoy trabajando en un juego 2D que no requiere mucha física. Tengo curiosidad por saber dónde la integración mejorada de Euler se quedaría corta y RK4 tendría que usarse en su lugar.

Mi juego consiste principalmente en gravedad simple (saltar y caer), movimiento a lo largo de los ejes X e Y, y colisión de caja delimitadora. ¿Vale la pena implementar RK4 o sería suficiente Euler mejorado? Veo muchas discusiones en las que los usuarios de Euler Integration son castigados, pero por lo que puedo ver, Euler mejorado es equivalente en cuestiones 2D simples. Me imagino que también sería más rápido.

physics rk4 integration John Tyler
fuente
fuera del tema, pero esas áreas son excelentes diapositivas, muy claras con los ejemplos y todo. Gracias por ese enlace!
Roy T.
Si esto está fuera de tema aquí, probablemente encajaría bien en Computational Science .
David Z
También: Integración Verlet corregida en el tiempo : se parece a Euler mejorado: demasiado flojo para darse cuenta si es exactamente lo mismo. TCV es excelente porque puede ser indulgente con su paso de tiempo fijo (otros integradores quieren un paso de tiempo fijo garantizado).
Jonathan Dickinson
1
No se puede editar: veo que lo menciona. No estoy seguro de si su implementación tiene errores en términos del requisito de condiciones iniciales como se describe en el artículo: pero nunca he visto ese problema de gravedad con mi implementación de TCV si calculo las condiciones iniciales correctamente.
Jonathan Dickinson

Respuestas:

15

Personalmente prefiero Velocity Verlet para la mayoría de las simulaciones. En mi experiencia con este método, es bastante adecuado para ecuaciones bastante rígidas. Parece que este método de "Euler mejorado" es bastante similar al de Velocity Verlet y se basa en una clase de métodos de integración conocidos como predictor-corrector . Puede leer muchas cosas sobre estos métodos hoy en día, comenzando con los "Grandes pasos en la simulación de telas" de David Baraff, donde el poder de los métodos implícitos realmente brilla. Su caída es que usted:

  1. tener que aproximarnos a jacobianos o hessianos y luego tener que
  2. calcular una cantidad justa de inversas de matriz por cuadro.

Entonces, si no eres un gurú de las matemáticas, podrías atascarte los dedos. Simplemente experimente con el método que desee y luego conéctese con el que parece funcionar mejor para usted. Simple no siempre es mejor, pero para framerates interactivos solo conozco una palabra: compromiso.

Algunos recursos adicionales que quizás desee ver:

Jakobsen es una especie de genio por proponer una idea tan simple para un problema pretencioso (su especialidad es la criptografía si no se confunde, pero logró demostrar la equivalencia matemática de su método a una clase de algoritmo iterativo Gauss-Seidel, que es convergente ) Por simplicidad, vaya a esto primero antes de profundizar en los métodos implícitos.

EDICIÓN MÁS TARDE : Recientemente recibí un documento sobre este tema del uso de integradores explícitos para la simulación de cuerpo blando o semirrígido y cuál es su impacto en el rendimiento y la calidad. Este documento debe servir como guía para elegir un determinado integrador, según el escenario.

teodron
fuente
1
+1 Esta fue en realidad una respuesta de muy buena calidad en términos de contenido: pero fue un poco demasiado difícil de digerir (muro de texto). Descubrí que un buen formato siempre ayuda a obtener votos positivos. Lo mejoré y espero que obtengas los votos que mereces.
Jonathan Dickinson el
Gracias Jonathan, lo hice apresuradamente, sin tener en cuenta el procedimiento "fácil de leer", pero tuve que mencionar esas pocas fuentes, ya que en realidad se usan con mucha frecuencia incluso hoy en día).
teodron
10

P: ¿Por qué utilizar el avanzado Runge Kutta?
A: Porque es muy exacto.

P: ¿Por qué no?
R: Debido a que estás haciendo un juego y no importa un motor de física muy exacto, solo tiene que ser lo suficientemente bueno como para engañar al jugador.

Por cierto, si tiene una fuerte amortiguación en la colisión, como lo haría la mayoría de los juegos de plataformas, un Euler simple está bien.

Le recomiendo encarecidamente que, a diferencia del código en la presentación, utilice una física de pasos fijos, lo que le ahorra algunos posibles fallos y le permite resolver el problema de que la pelota gane o pierda energía de una manera muy simple. Simplemente vaya al punto medio entre la integración explícita e implícita:

velocity += 0.5 * acceleration;
position += velocity;
velocity += 0.5 * acceleration;

Lo que la presentación no muestra es cómo manejar las colisiones para que los objetos no parezcan ir más allá de los límites. La solución simple a ese problema es usar una frecuencia de actualización alta. Una solución más compleja pero potencialmente de mejor desempeño es mover los objetos hacia atrás en el momento de la colisión, la implementación exacta depende del comportamiento físico deseado.

aaaaaaaaaaaa
fuente
1
+1 por "engañar al jugador", pero personalmente he explotado sistemas 'muy simples' debido a la integración de euler.
Jonathan Dickinson
@JonathanDickinson Diría que no se debe a la integración de Euler, sino a una combinación de circunstancias, la integración de Euler es solo una de ellas. Si tiene un ejemplo, estoy seguro de que puedo encontrar una manera de evitar la explosión de sistemas.
aaaaaaaaaaaa
Oh, está en algunas cosas realmente viejas de VB6 (cuando tenía literalmente unos 14) mías antes de aprender sobre RK / Verlet: ya ni siquiera tengo el código: lo que da una gran credibilidad al hecho de que podría haber sido algo más en la mezcla :).
Jonathan Dickinson el
1
Supongo que debería agregar que tan pronto como comience a jugar con la atracción entre los objetos en lugar de la simple gravedad, me parece razonable intensificar el método de integración, puede que no sea estrictamente necesario, pero si tiene la potencia de procesamiento, El único inconveniente es un código un poco más complejo.
aaaaaaaaaaaa
1

La presentación tiene error. ¡El método al que el presentador se refiere como "Euler mejorado" es en realidad el método Velocity Verlet!

Consulte aquí para obtener una fuente más autorizada: http://www.physics.udel.edu/~bnikolic/teaching/phys660/numerical_ode/node5.html

También las mismas ecuaciones están en Wikipedia .

Una mejora inmediata común sobre el método de Euler es el método de punto medio que el presentador probablemente tenía en mente, pero terminó confundiendo a Velocity Verlet como Euler mejorado. La única diferencia entre el método de punto medio y Velocity Verlet es que la velocidad es el promedio de la última y la próxima aceleración en lugar de depender solo de la última aceleración.

Shital Shah
fuente