Plusy i minusy różnych integratorów [zamknięte]

Podczas tworzenia rzeczy takich jak fizyka w grach potrzebujesz integratora. Widziałem, że integracja Verleta wspominała kilka miejsc jako doskonałą alternatywę dla integracji Eulera. Na przykład w słynnym dokumencie Thomasa Jakobsena . Jednak w tym artykule Glenn Fiedler pisze:

Zamiast przedstawiać ci szeroką gamę różnych integratorów, które istnieją, zamierzam przejść do sedna i przejść od razu do najlepszych. Ten integrator nazywa się integratorem Runge Kutta 4, znanym również jako RK4.

Więc najwyraźniej nie ma srebrnej kuli. Jakie są zalety i wady różnych integratorów? Jeśli chodzi o prostotę, szybkość, dokładność, stabilność itp. Które integratory są najbardziej odpowiednie dla jakich rodzajów gier? Kiedy użyjesz Verlet, RK4 lub innych? Czy powinieneś kiedykolwiek użyć Eulera?

Plusy i minusy obu metod:

Zalety RK4:

1. dokładność (dzięki lepszej serii aproksymacji daje prekursję 4. rzędu)
2. sztuczne / z natury indukowane tłumienie (trochę tak, jak robią to metody ukryte) dodaje stabilności (podczas gdy prosty krok Eulera tego nie robi - robi wręcz przeciwnie, wprowadzając energię ducha, która gromadzi się i może pogrążyć system w chaosie)

Wady RK4:

1. koszt obliczeń: choć nie jest to wymagające w porównaniu z metodami niejawnymi lub hybrydowymi metodami IMEX, RK4 jest 4 razy droższy niż jawny Euler, ponieważ wymaga o wiele większej liczby ocen funkcji. Pokazuje to, gdy dążysz do najnowocześniejszej optymalizacji.
2. wciąż niestabilny: w zależności od rodzaju zaangażowanych sił RK4 może być tak samo niestabilny jak Euler. Średnio RK4 jest nieco bardziej stabilny i zwykle czerpie tę korzyść z posiadanych „umiejętności” tłumienia.
3. Brak symplektyczności: tłumienie numeryczne wiąże się z pewnym kosztem - nie można symulować systemów, w których energia / objętość / itp. utrata nie powinna stosować widocznego efektu w czasie (np. dynamika molekularna, siły pochodzące z pola potencjału, problemy wariacyjne)

Verlet Plusy:

1. raz lub dwa razy złożoność kroku Eulera (w zależności od smaku Verleta: pozycja lub prędkość).
2. symplektyczny: oszczędza energię wewnętrzną
3. dokładność drugiego rzędu: wiele gier nie wymaga wyników zmiennoprzecinkowych o wysokiej precyzji, a drugie zamówienie jest więcej niż przyjemne dla oka w scenariuszu gry (a ponadto: zostało użyte w symulacji scenariusza innego niż gamingowy, gdy zostało „odkryte”, więc nie jest tak źle)

Wady Verleta:

1. stabilny, ale nadal: prawdopodobnie najlepszy wyraźny sposób pod względem stabilności. Ma tendencję do zdobywania przewagi, gdy twarde ograniczenia są dodawane do systemu, co pozwala na mniejszy ból głowy podczas wdrażania rzutowanych ograniczeń w silnikach dynamiki opartej na pozycji. Wyrusza w nieskończoność, jeśli układ jest zakłócany dużymi siłami zewnętrznymi i nie dodaje się tłumienia / tarcia. Mimo to istnieją pewne narzucone liczbowo ograniczenia, jak duże mogą być siły wewnętrzne (sprężynowe), ale są one średnio wyższe niż to, co może zrobić RK4
2. niższa dokładność: nieprzydatna, jeśli chcesz mieć wysoką dokładność
3. wymaga średnio krótszych przedziałów czasowych niż RK4 dla niektórych symulacji (RK4 korzysta zarówno z dokładności, jak i wewnętrznego tłumienia)

Używanie jednego nad drugim zależy od scenariusza. Jeśli sztywność, duże siły zewnętrzne i wirtualne energie stanowią problem, rozważ inne metody zawierające słowo „niejawne” w ich opisie / tytule.

Zauważ, że niektórzy autorzy / książki używają terminu pół-niejawny Euler dla rzeczywistego jawnego integratora Eulera zwanego symplektyczną metodą Eulera (lub Euler Cromer), z którego faktycznie pochodzi Verlet. Verlet jest również przez niektórych nazywany „metodą przeskoku”. Velocity Verlet i metoda punktu środkowego są dość podobne od oszacowania na krok czasut + 0.5*dtjest wymagany dla kroku przypominającego korektor predyktora. Metody IMEX (niejawnie jawne) są również używane do nazwania dwóch podobnych, ale nie identycznych podejść: rozdziel obliczenia na części sztywne i niesztywne i użyj na nich różnych integratorów (jawne dla niesztywnych, niejawne dla sztywnych) LUB rozwiąż dla prędkość z niejawnym krokiem aktualizacji i aktualizuj pozycję w sposób jawny (jest to hybrydowa metoda niejawna, która spada na klasę metod IMEX, ponieważ sztywne części najbardziej wpływają na obliczenia przyspieszenia). Metody niejawne są bardziej kłopotliwe i wymagają rozwiązania układu równań nieliniowych dla całej konfiguracji. Metody niejawne są stosowane w przypadku brył odkształcalnych i zwykle nie są stosowane w przypadku brył sztywnych odsprzęgniętych.

Jak stwierdzono w jednym z komentarzy, jeśli możesz, nie używaj Eulera. Użyj metody punktu środkowego, częściowo niejawnego Eulera lub, przy tym samym koszcie, pozycji-Verleta. Wszystkie mają nieco wyższą dokładność i znacznie większą stabilność niż wyraźny integrator Eulera.

Zalecany odczyt mini-porównania:

http://wiki.vdrift.net/Numerical_Integration

Implementacje Eulera są zwykle bardzo szybkie, ale znacznie mniej stabilne niż alternatywy. Runge Kutta jest wolniejszy niż Euler, ale o wiele bardziej precyzyjny i stabilny.

Nie mam zbyt dużej wiedzy na temat integracji Verleta, więc nie mam pojęcia, jak wypada ona przeciwko Eulerowi i Runge Kutcie.

Jeśli potrzebujesz dokładniejszej symulacji lub nawet dowodu numerycznego, Runge Kutta jest lepszym rozwiązaniem.

Jeśli potrzebujesz prostej, taniej fizyki do prostej gry, Euler jest lepszym wyborem.

Przede wszystkim myślę, że powinieneś używać Eulera, dopóki nie doświadczysz bezpośredniej potrzeby użycia bardziej zaawansowanego schematu integracji. Jest szybki i łatwy do wdrożenia.

Jeśli wystąpią problemy ze stabilnością, takie jak układ sprężyn, które nigdy nie zatrzymują się lub jeśli twoja symulacja wymaga wysokiego poziomu dokładności, zacznij eksperymentować z innymi.

Jedną z tych, których nie widziałem powyżej, jest metoda punktu środkowego, która jest bardzo łatwa do wdrożenia i wymaga tylko jednego dodatkowego kroku integracji.