Pourquoi RK4 est-il meilleur que l'intégration d'Euler? [fermé]

À la fin de ces grandes diapositives , l'auteur compare tous les différents intégrateurs présentés. D'une manière ou d'une autre, ils échouent tous, à l'exception de l' intégration améliorée d'Euler et de l' intégration de Runge Kutta 4 , qui réussissent tous les deux.

Je suppose que je devrais mentionner que je travaille sur un jeu 2D qui n'est pas très intensif en physique. Je suis simplement curieux de savoir où l'amélioration de l'intégration d'Euler serait insuffisante et RK4 devrait être utilisé à la place.

Mon jeu consiste principalement en une simple gravité (sauter et tomber), un mouvement le long des axes X et Y et une collision de boîte englobante. Vaut-il la peine d'implémenter RK4 ou Improved Euler serait-il suffisant? Je vois de nombreuses discussions où les utilisateurs d'Euler Integration sont réprimandés, mais d'après ce que je peux voir, Improved Euler est quivalent dans les questions 2D simples. J'imagine que ce serait aussi plus rapide.

Personnellement, je préfère Velocity Verlet pour la plupart des simulations. D'après mon expérience avec cette méthode, elle convient parfaitement aux équations assez rigides. Il semble que cette méthode "Euler améliorée" soit assez similaire à celle de Velocity Verlet et s'appuie sur une classe de méthodes d'intégration connues sous le nom de prédicteur-correcteur . De nos jours, vous pouvez lire beaucoup de choses sur ces méthodes, à commencer par «Les grandes étapes de la simulation de tissu» de David Baraff où la puissance des méthodes implicites brille vraiment. Leur chute est que vous:

1. doivent se rapprocher des Jacobiens ou des Hessois, puis doivent,
2. calculer une bonne quantité d'inverses matriciels par image.

Donc, si vous n'êtes pas un gourou des mathématiques, vous pourriez vous coincer les doigts. Essayez simplement la méthode que vous souhaitez, puis choisissez celle qui semble la plus performante pour vous. La simplicité n'est pas toujours meilleure, mais pour les cadences interactives, je ne connais qu'un mot: compromis.

Quelques ressources supplémentaires que vous voudrez peut-être consulter:

• Jakobsen "Advanced Character Physics"
• James McCarthy "Comparaison des techniques de simulation utilisant des systèmes de particules"

Jakobsen est une sorte de génie pour avoir proposé une idée aussi simple de problème prétentieux (sa spécialité est la cryptographie, sinon en se trompant, mais il a réussi à prouver l'équivalence mathématique de sa méthode à une classe d'algorithme itératif de Gauss-Seidel, qui est convergent ). Pour plus de simplicité, optez pour cette première avant de vous plonger dans les méthodes implicites.

MODIFICATION PLUS TARD : J'ai récemment reçu un article sur cette question de l'utilisation d'intégrateurs explicites pour la simulation de corps souples ou semi-rigides et sur leurs performances et leur impact sur la qualité. Ce document devrait servir de guide pour choisir un certain intégrateur, selon le scénario.

Q: Pourquoi utiliser le Runge Kutta avancé?
R: Parce que c'est très exact.

Q: Pourquoi pas?
R: Parce que vous créez un jeu et qu'un moteur physique très précis n'a pas d'importance, il doit juste être assez bon pour tromper le joueur.

Soit dit en passant, si vous avez un fort amortissement en cas de collision, comme la plupart des plateformes, un simple Euler est très bien.

Je recommande fortement que contrairement au code de la présentation, vous utilisiez la physique à pas fixe, ce qui vous évite certains problèmes potentiels et vous permet de résoudre le problème de la balle qui gagne ou perd de l'énergie d'une manière très simple. Optez simplement pour un compromis entre l'intégration explicite et implicite:

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

Ce que la présentation ne montre pas, c'est comment gérer les collisions afin que les objets ne semblent pas dépasser les limites. La solution simple à ce problème consiste à utiliser une fréquence de mise à jour élevée. Une solution plus complexe mais potentiellement plus performante consiste à reculer les objets au moment de la collision, la mise en œuvre exacte dépend du comportement physique souhaité.

La présentation contient une erreur. La méthode appelée par le présentateur "Improved Euler" est en fait la méthode Velocity Verlet!

Voir ici pour une source plus fiable: http://www.physics.udel.edu/~bnikolic/teaching/phys660/numerical_ode/node5.html

Les mêmes équations sont également dans Wikipedia .

Une amélioration immédiate commune par rapport à la méthode d'Euler est la méthode Midpoint que ce que le présentateur avait probablement en tête, mais qui a fini par confondre Velocity Verlet avec Euler amélioré. La seule différence entre la méthode Midpoint et Velocity Verlet est que la vitesse est la moyenne de la dernière et de la prochaine accélération au lieu de simplement dépendre de la dernière accélération.