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

20

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

John Tyler
la source
hors sujet, mais ces superbes diapositives, très claires avec les exemples et tout. Merci pour ce lien!
Roy T.
Si c'est vraiment hors sujet ici, ce serait probablement un bon choix pour la science informatique .
David Z
Aussi: Intégration Verlet corrigée dans le temps - ressemble à Euler amélioré: trop paresseux pour savoir si c'est exactement la même chose. TCV est génial car vous pouvez être indulgent avec votre pas de temps fixe (d'autres intégrateurs veulent un pas de temps fixe garanti).
Jonathan Dickinson
1
Impossible de modifier: je vois qu'il le mentionne. Je ne sais pas si son implémentation est buggée en termes de conditions initiales telles que décrites par l'article: mais je n'ai jamais vu ce problème de gravité avec mon implémentation de TCV si je calcule correctement les conditions initiales.
Jonathan Dickinson

Réponses:

15

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

teodron
la source
1
+1 C'était en fait une réponse de très bonne qualité en termes de contenu: mais c'était un peu trop difficile à digérer (mur de texte). J'ai trouvé qu'un bon formatage aide toujours à obtenir des votes positifs. Je l'ai amélioré et j'espère que vous obtiendrez les votes positifs que vous méritez.
Jonathan Dickinson
Merci Jonathan, je l'ai fait à la hâte, sans tenir compte de la procédure "conviviale", mais j'ai dû mentionner ces quelques sources car elles sont vraiment très fréquemment utilisées même aujourd'hui).
teodron
10

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

aaaaaaaaaaaa
la source
1
+1 pour "tromper le joueur" - mais j'ai personnellement vu des systèmes "très simples" exploser à cause de l'intégration d'Euler.
Jonathan Dickinson
@JonathanDickinson Je dirais que ce n'est pas à cause de l'intégration d'Euler, mais plutôt à cause d'un mélange de circonstances, l'intégration d'Euler n'étant que l'une d'entre elles. Si vous avez un exemple, je suis sûr que je peux trouver un moyen d'éviter l'explosion des systèmes.
aaaaaaaaaaaa
Oh, c'est sur de très vieux trucs VB6 (quand j'avais littéralement environ 14 ans) avant d'apprendre le RK / Verlet - je n'ai même plus le code: ce qui donne une grande crédibilité au fait qu'il aurait pu être autre chose dans le mélange :).
Jonathan Dickinson
1
Je suppose que je devrais ajouter que dès que vous commencez à jouer avec l'attraction entre les objets plutôt qu'avec la simple gravité, il me semble raisonnable d'intensifier la méthode d'intégration, cela peut ne pas être strictement nécessaire, mais si vous avez la puissance de traitement, seul inconvénient est un code légèrement plus complexe.
aaaaaaaaaaaa
1

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.

Shital Shah
la source