Prós e contras de diferentes integradores [fechado]

Ao criar coisas como física em jogos, você precisa de um integrador. Eu já vi a integração da Verlet mencionada em vários lugares como uma ótima alternativa à integração do Euler. Por exemplo, no famoso documento de Thomas Jakobsen . No entanto, neste artigo Glenn Fiedler escreve:

Em vez de apresentar a vasta gama de diferentes integradores que existem, vou direto ao assunto e vou direto ao melhor. Esse integrador é chamado de integrador de ordem 4 da Runge Kutta, também conhecido como RK4.

Então, aparentemente, não há bala de prata. Quais são os prós e os contras dos diferentes integradores? Em relação à simplicidade, velocidade, precisão, estabilidade, etc. Quais integradores são mais adequados para quais tipos de jogos? Quando você usaria o Verlet, o RK4 ou outros? Você deveria usar o Euler?

Prós e contras de ambos os métodos:

Prós RK4:

1. precisão (graças à sua melhor série de aproximações, produz uma precissão de 4ª ordem)
2. o amortecimento artificial / inerentemente induzido (um pouco como os métodos implícitos o fazem) adiciona estabilidade (ao passo que um simples passo de Euler não - ele faz o oposto, introduzindo energia fantasma que se acumula e pode mergulhar o sistema no caos)

Contras RK4:

1. despesa de computação: embora não seja tão exigente em comparação com métodos implícitos ou híbridos IMEX, o RK4 é 4 vezes mais caro que o Euler explícito, pois exige muito mais avaliações de funções. Isso é mostrado ao apontar para o limite da otimização.
2. ainda instável: dependendo dos tipos de forças envolvidas, o RK4 pode ser tão instável quanto Euler. Em média, o RK4 é um pouco mais estável e tende a tirar esse benefício de suas "habilidades" de amortecimento.
3. Não simplético: o amortecimento numérico tem um custo - você não pode simular sistemas onde energia / volume / etc. a perda não deve aplicar um efeito visível ao longo do tempo (por exemplo, Dinâmica Molecular, forças derivadas de campos potenciais, problemas variacionais)

Verlet Pros:

1. uma ou duas vezes a complexidade de uma etapa de Euler (dependendo do seu sabor de Verlet: posição ou velocidade).
2. simplético: economiza energia interna
3. precisão de segunda ordem: muitos jogos não exigem resultados de ponto flutuante de alta precisão e a segunda ordem é mais do que agradável aos olhos em um cenário de jogo (mais: foi usada em uma simulação de cenário que não é de jogo quando foi "descoberta", portanto não é tão ruim)

Contras Verlet:

1. estável, mas ainda assim: provavelmente o melhor método explícito em termos de estabilidade. Tende a ganhar vantagem quando restrições rígidas são adicionadas ao sistema, permitindo menos dores de cabeça ao implementar restrições projetadas em motores de dinâmica baseados em posição. Ele dispara para o infinito se o sistema for perturbado por grandes forças externas e nenhum amortecimento / atrito for adicionado. Mesmo assim, existem certos limites impostos numericamente ao tamanho das forças internas (mola), mas elas são mais altas, em média, do que o RK4 pode fazer
2. menor precisão: não é útil se você deseja estimativas de alta precissão
3. requer, em média, intervalos de tempo menores que o RK4 para algumas simulações (o RK4 se beneficia da precisão e do amortecimento interno)

Usar um sobre o outro depende do cenário. Se rigidez e grandes forças externas e energias virtuais forem um problema, considere outros métodos com a palavra "implícita" em sua descrição / título.

Observe que alguns autores / livros usam o termo Euler semi-implícito para um integrador Euler explícito real chamado método simplético de Euler (ou Euler Cromer) do qual Verlet é realmente derivado. Verlet também é chamado por algumas pessoas de "método de salto". O Velocity Verlet e o método do ponto médio são bastante semelhantes, pois uma estimativa em um intervalo de tempo det + 0.5*dté necessário para uma etapa do tipo preditor-corretor. Os métodos IMEX (implícito-explícito) também são usados ​​para nomear duas abordagens semelhantes, mas não idênticas: separar os cálculos em partes rígidas e não rígidas e usar diferentes integradores (o explícito para não rígido, implícito para rígido) OU resolver a velocidade com uma etapa de atualização implícita e atualize a posição de maneira explícita (este é um método híbrido semi-implícito que se enquadra na classe de métodos IMEX, porque as partes rígidas afetam mais o cálculo da aceleração). Os métodos implícitos são mais complicados e exigem a solução de um sistema de equações não lineares simultâneas para toda a configuração. Métodos implícitos são usados ​​para corpos deformáveis ​​e geralmente não são usados ​​para corpos rígidos dissociados.

Conforme declarado em um dos comentários, se você puder, não use Euler. Use o método do ponto médio, o Euler semi-implícito ou, à mesma despesa, a posição-Verlet. Todos eles têm precisão um pouco mais alta e sensivelmente mais estabilidade do que o integrador explícito Euler.

Leitura de mini-comparação recomendada :

http://wiki.vdrift.net/Numerical_Integration

As implementações de Euler tendem a ser muito rápidas, mas muito menos estáveis ​​que as alternativas. Runge Kutta é mais lento que Euler, mas muito mais preciso e estável.

Eu não sou muito conhecedor da integração do Verlet, então não tenho idéia de como ele se compara ao Euler e Runge Kutta.

Se você precisa que suas simulações sejam mais exatas, ou mesmo prova numericamente, o Runge Kutta é o melhor dos dois.

Se você precisa de física rápida e de baixo custo para um jogo simples, Euler é a melhor escolha.

Em primeiro lugar, acho que você deve usar o Euler até ter uma necessidade direta de usar um esquema de integração mais avançado. É rápido e fácil de implementar.

Se você tiver problemas de estabilidade, como sistemas de molas que nunca param, ou se sua simulação exigir um alto nível de precisão, comece a experimentar com os outros.

Um que eu não vi mencionado acima é o método do ponto médio, que é muito fácil de implementar e requer apenas uma etapa extra de integração.