De Runge-Kutta (RK4) l'intégration de la physique du jeu

Question

Gaffer sur les Jeux a un excellent article sur l'utilisation de RK4 intégration pour le meilleur de la physique du jeu. La mise en œuvre est simple, mais les mathématiques derrière il me confond. Je comprends dérivés et intégrales sur un plan conceptuel, mais je n'ai pas manipulé des équations dans un long moment.

Voici le poids de Gaffer mise en œuvre:

void integrate(State &state, float t, float dt)
{
     Derivative a = evaluate(state, t, 0.0f, Derivative());
     Derivative b = evaluate(state, t+dt*0.5f, dt*0.5f, a);
     Derivative c = evaluate(state, t+dt*0.5f, dt*0.5f, b);
     Derivative d = evaluate(state, t+dt, dt, c);

     const float dxdt = 1.0f/6.0f * (a.dx + 2.0f*(b.dx + c.dx) + d.dx);
     const float dvdt = 1.0f/6.0f * (a.dv + 2.0f*(b.dv + c.dv) + d.dv)

     state.x = state.x + dxdt * dt;
     state.v = state.v + dvdt * dt;
}

Quelqu'un peut-il expliquer en termes simples comment RK4 œuvres? Plus précisément, pourquoi sommes-nous en calculant la moyenne des dérivés en 0.0f, 0.5f, 0.5f, et 1.0f? Comment la moyenne de dérivés jusqu'à la 4ème ordre différent de faire une simple intégration d'euler avec un petit timestep?

---

Après la lecture de la accepté de répondre ci-dessous, et plusieurs autres articles, j'ai une compréhension sur la façon dont RK4 œuvres. Pour répondre à mes propres questions:

Quelqu'un peut-il expliquer en termes simples comment RK4 œuvres?

RK4 tire parti du fait que nous pouvons obtenir une bien meilleure approximation d'une fonction si nous utilisons ses d'ordre supérieur dérivés plutôt que de juste la première ou de la seconde dérivée. C'est pourquoi la série de Taylor converge beaucoup plus rapidement que d'Euler des approximations. (jetez un oeil à la animation sur le côté droit de l' page)

Plus précisément, pourquoi sommes-nous en calculant la moyenne des dérivés en 0.0f, 0.5f, 0.5f, et 1.0f?

Le Runge-Kutta méthode est une approximation d'une fonction qui des échantillons de produits dérivés de plusieurs points dans un timestep, contrairement à la Taylor la série dont seuls les échantillons de produits dérivés d'un point unique. Après l'échantillonnage ces instruments dérivés, nous avons besoin de savoir comment peser chaque échantillon pour obtenir l' approximation la plus proche possible. Un moyen facile de le faire est de choisir les constantes qui coïncident avec les Les séries de Taylor, qui est de savoir comment le les constantes de Runge-Kutta d'équation sont déterminés.

Cet article fait plus de clarté moi. Remarquez comment (15) est le Taylor l'extension de la série tout en (17) est le De Runge-Kutta de dérivation.

Comment est calcul de la moyenne des dérivés jusqu'à la 4ème ordre différent de faire une simple intégration d'euler avec un petit timestep?

Mathématiquement, il converge beaucoup plus rapide que de faire beaucoup d'Euler des approximations. Bien sûr, avec assez de Euler approximations, nous pouvons obtenir l'égalité des la précision de RK4, mais le calcul de l' puissance nécessaire n'a pas à justifier que l' Euler.

Answer 1

Cela peut être un peu simpliste, donc la mesure réelle de mathématiques, mais conçu comme un guide intuitif de Runge-Kutta d'intégration.

Étant donné une certaine quantité, à un moment t1, nous voulons savoir la quantité à un autre temps t2. Avec une équation différentielle du premier ordre, nous pouvons savoir que le taux de variation de cette quantité à t1. Il n'y a rien d'autre que nous pouvons savoir avec certitude; le reste est dans le doute.

Euler, l'intégration est la façon la plus simple à deviner: linéaire de l'extrapoler à partir de t1 à t2, à l'aide de l'connus avec précision les taux de variation en t1. Généralement, cela donne une mauvaise réponse. Si t2 est loin d't1, cette extrapolation linéaire échouera correspondre à une courbure dans la réponse idéale. Si nous prenons de nombreuses petites étapes de t1 à t2, nous aurons le problème de la soustraction des valeurs similaires. Les erreurs d'arrondi va ruiner le résultat.

Nous avons donc affiner notre supposition. Une façon est d'aller de l'avant et de faire une extrapolation linéaire de toute façon, alors en espérant qu'il n'est pas trop loin de la vérité, de l'utilisation de l'équation différentielle pour calculer une estimation du taux de variation à t2. Cette moyenne avec l' (précis) taux de variation à t1, représente le mieux la typique de la pente de la vraie réponse entre t1 et t2. Nous nous en servons pour faire une nouvelle extrapolation linéaire à partir de t1 à t2. Il n'est pas évident si l'on doit prendre à la moyenne simple, ou de donner plus de poids à la vitesse à t1, sans faire le calcul pour estimer les erreurs, mais il y a un choix ici. En tout cas, c'est une meilleure réponse que Euler donne.

Peut-être mieux, faire notre première extrapolation linéaire à un point dans le temps à mi-chemin entre t1 et t2, et l'utilisation de l'équation différentielle pour calculer le taux de variation de là. Cela donne à peu près une bonne réponse comme étant la moyenne vient d'être décrit. Puis l'utiliser pour une extrapolation linéaire à partir de t1 à t2, puisque notre but est de trouver la quantité au t2. C'est le milieu de l'algorithme.

Vous pouvez imaginer à l'aide de la mi-estimation ponctuelle du taux de variation de faire un autre extrapolation linéaire de la quantité de t1 du milieu. Avec l'équation différentielle, on obtient une meilleure estimation de la pente, il n'. Avec cela, nous finissons par extrapolation à partir de t1 tout le chemin à t2 où nous voulons une réponse. C'est l'algorithme de Runge Kutta.

Pourrions-nous faire une troisième extrapolation du milieu? Bien sûr, il n'est pas illégal, mais une analyse détaillée montre que la diminution de l'amélioration, de telle sorte que d'autres sources d'erreur dominer le résultat final.

De Runge-Kutta s'applique à l'équation différentielle de la intial point t1, deux fois pour le milieu, et une fois à la finale de point de t2. Dans l'entre-deux points sont une question de choix. Il est possible d'utiliser d'autres points entre t1 et t2 pour la fabrication de ces meilleures estimations de la pente. Par exemple, nous pourrions utiliser t1, un point un tiers du chemin vers t2, un autre 2/3 de la voie vers t2, et à t2. La pondération de la moyenne des quatre dérivés seront différentes. Dans la pratique, cela n'aide pas vraiment, mais pourrait avoir une place dans le test, car il doit donner la même réponse, mais fournira un ensemble différent d'erreurs d'arrondi.

Answer 2

La moyenne pondérée est un développement en série de Taylor de l'expansion. Il y a une très bonne explication ici.

Answer 3

Quant à votre question de savoir pourquoi: je me souviens d'une fois la rédaction d'un chiffon simulateur où le tissu a été une série de ressorts interconnectés au niveau des nœuds. Dans le simulateur, la force exercée par le ressort est proportionnelle à savoir dans quelle mesure le ressort est étiré. La force provoque l'accélération du nœud, ce qui provoque de vitesse qui se déplace le nœud qui s'étend du printemps. Il y a deux intégrales (intégration de l'accélération pour obtenir la vitesse, et l'intégration de la vitesse pour obtenir la position) et si elles sont inexactes, erreurs de boule de neige: Trop d'accélération provoque trop de vitesse qui provoque trop d'étirement qui provoque encore plus d'accélération, ce qui rend tout le système instable.

Il est difficile d'expliquer sans graphique, mais je vais essayer: Disons que vous avez f(t), où f(0) = 10, f(1) = 20), et f(2) = 30.

Une bonne intégration de f(t) sur l'intervalle 0 < t < 1 serait vous donner la surface sous le graphe de f(t) sur cet intervalle.

Le rectangle de la règle de l'intégration se rapproche de celle de la surface d'un rectangle où la largeur est le delta dans le temps et la longueur est la nouvelle valeur de f(t), donc dans l'intervalle 0 < t < 1 , il produira 20 * 1 = 20, et dans l'intervalle suivant 1

Maintenant, si vous étiez à tracer ces points et tracer une ligne à travers eux, vous verrez que c'est effectivement triangulaire, avec une surface de 30 (unités), et donc l'intégration d'Euler est insuffisante.

Pour obtenir une estimation plus exacte de la surface (intégrale), vous pouvez prendre de plus petits intervalles de t, en évaluant par exemple, f(0), f(0,5), f(1), f(1.5) et f(2).

Si vous êtes toujours en me suivant, la méthode RK4 est alors simplement une manière d'estimer les valeurs de f(t) pour t0 < t < t0+dt inventé par des gens plus intelligents que moi-même pour obtenir des estimations précises de l'intégrale.

(mais comme d'autres l'ont dit, lire l'article de Wikipedia pour une explication plus détaillée. RK4 est dans la catégorie de l'intégration numérique)

Answer 4

RK4 dans le sens le plus simple est de faire une approximation de la fonction qui est basé sur 4 des dérivés et de point pour chaque pas de temps: Votre état initial au point de départ, Une première approximation à la pente B basée sur les données du point A au votre temps à l'étape/2 et la pente à partir d'Un, un troisième approximation de C , qui a une valeur de correction pour la pente à B afin de refléter les changements de forme de votre fonction, et enfin une dernière pente basée sur la correction de la pente au point C.

Donc, fondamentalement, cette méthode permet de calculer à l'aide d'un point de départ, une moyenne de milieu qui a des corrections construit en deux parties pour s'adapter à la forme, et un doublement corrigé point de terminaison. Cela rend la contribution effective de chaque point de données 1/6 1/3 1/3 et 1/6, de sorte que la plupart de votre réponse est basée sur vos corrections pour la forme de votre fonction.

Il s'avère que l'ordre d'un RK approximation (Euler est considéré comme un RK1) correspond à la manière de son exactitude des échelles avec des petits pas de temps.

La relation entre RK1 approximations est linéaire, donc pour 10 fois la précision que vous obtenez près de 10 fois meilleure convergence.

Pour RK4, 10 fois la précision te rapporte environ 10^4 fois meilleure convergence. Donc, même si votre calcuation temps augmente de façon linéaire en RK4, il augmente votre précision polynomialement.

Answer 5

J'imagine que c'est utilisé pour calculer un point précis dans une forme circulaire. Je stumbeled sur ce terme dans un jeu appelé Univers bac à sable, et remarqué que lorsque vous l'allumez ou l'éteignez, il serait de rendre les chemins derrière les planètes polyvalent. Je pourrais imaginer le vent ayant une autre force de poussée de vêtements de différentes manières... à mettre dans le contexte de l'habillement et des jeux