O obsłudze liczb zmiennoprzecinkowych w sposób deterministyczny
Zmienny punkt jest deterministyczny. Cóż, powinno być. To skomplikowane.
Istnieje mnóstwo literatury na temat liczb zmiennoprzecinkowych:
I jak są problematyczne:
Dla streszczenia. Przynajmniej w jednym wątku te same operacje z tymi samymi danymi, zachodzące w tej samej kolejności, powinny być deterministyczne. Dlatego możemy zacząć od martwienia się o dane wejściowe i zmiany kolejności.
Jednym z takich danych wejściowych, które powodują problemy, jest czas.
Przede wszystkim zawsze należy obliczyć ten sam czas. Nie mówię, żeby nie mierzyć czasu, mówię, że nie przejdziesz czasu do symulacji fizyki, ponieważ zmiany w czasie są źródłem hałasu w symulacji.
Dlaczego mierzysz czas, jeśli nie przekazujesz go do symulacji fizyki? Chcesz zmierzyć czas, który upłynął, aby wiedzieć, kiedy należy wywołać krok symulacji, i - zakładając, że korzystasz ze snu - ile czasu spać.
A zatem:
- Zmierz czas: tak
- Wykorzystaj czas w symulacji: Nie
Teraz zmiana kolejności instrukcji.
Kompilator może zdecydować, że f * a + b
jest to to samo, co b + f * a
jednak może mieć inny wynik. Może również skompilować się do fmadd lub może zdecydować, że weźmie wiele takich linii, które się to zdarzy, razem i napiszę je za pomocą SIMD lub innej optymalizacji, o której nie mogę teraz myśleć. I pamiętajmy, że chcemy, aby te same operacje odbywały się w tej samej kolejności, dlatego chcemy kontrolować, co się dzieje.
I nie, użycie double nie uratuje cię.
Musisz się martwić kompilatorem i jego konfiguracją, w szczególności synchronizować liczby zmiennoprzecinkowe w sieci. Musisz uzyskać wersje, aby zgodzić się na to samo.
Prawdopodobnie pisanie zestawu byłoby idealne. W ten sposób decydujesz, którą operację wykonać. Może to jednak stanowić problem w przypadku obsługi wielu platform.
A zatem:
Przypadek liczb stałych
Ze względu na sposób, w jaki pływaki są reprezentowane w pamięci, duże wartości stracą precyzję. Przyczyną jest to, że utrzymywanie małych wartości (zacisk) łagodzi problem. Zatem nie ma wielkich prędkości i nie ma dużych pomieszczeń. Co oznacza również, że możesz używać dyskretnej fizyki, ponieważ masz mniejsze ryzyko tunelowania.
Z drugiej strony będą się kumulować małe błędy. Więc obetnij. Mam na myśli, skaluj i rzutuj na liczbę całkowitą. W ten sposób wiesz, że nic się nie buduje. Będą operacje, które możesz wykonać pozostając przy typie liczby całkowitej. Kiedy musisz wrócić do zmiennoprzecinkowego, rzucasz i cofasz skalowanie.
Uwaga Mówię skalę. Chodzi o to, że 1 jednostka będzie faktycznie reprezentowana jako potęga dwóch (na przykład 16384). Cokolwiek to jest, uczyń go stałym i używaj go. Zasadniczo używasz go jako stałego numeru punktu. W rzeczywistości, jeśli można użyć znacznie lepszych liczb stałych z pewnej niezawodnej biblioteki.
Mówię obcięty. Jeśli chodzi o problem z zaokrąglaniem, oznacza to, że nie możesz ufać ostatniej części wartości uzyskanej po obsadzie. Tak więc, zanim rzucasz skalę, aby uzyskać nieco więcej niż potrzebujesz, a następnie ją obetnij.
A zatem:
- Zachowaj małe wartości: Tak
- Ostrożne zaokrąglanie: tak
- Stałe numery punktów, jeśli to możliwe: Tak
Czekaj, dlaczego potrzebujesz zmiennoprzecinkowego? Czy nie możesz pracować tylko z typem całkowitym? Och, racja. Trygonometria i promieniowanie. Możesz obliczyć tabele dla trygonometrii i radiacji i upiec je w swoim źródle. Lub możesz zaimplementować algorytmy użyte do obliczenia ich za pomocą liczb zmiennoprzecinkowych, z wyjątkiem użycia liczb stałych w zamian. Tak, musisz zrównoważyć pamięć, wydajność i precyzję. Jednak możesz trzymać się z dala od liczb zmiennoprzecinkowych i pozostać deterministycznym.
Czy wiesz, że robili takie rzeczy na oryginalnym PlayStation? Proszę spotkać mojego psa, łatki .
Nawiasem mówiąc, nie mówię, żebym nie używał zmiennoprzecinkowego grafiki. Tylko dla fizyki. Oczywiście, pozycje będą zależeć od fizyki. Jednak, jak wiadomo, zderzacz nie musi pasować do modelu. Nie chcemy widzieć wyników obcinania modeli.
Dlatego: UŻYWAJ STAŁYCH NUMERÓW PUNKTOWYCH.
Żeby było jasne, jeśli możesz użyć kompilatora, który pozwala ci określić, jak działają zmiennoprzecinkowe, i to ci wystarczy, możesz to zrobić. To nie zawsze jest opcja. Poza tym robimy to dla determinizmu. Stałe numery punktów nie oznaczają, że nie ma błędów, w końcu mają ograniczoną precyzję.
Nie sądzę, aby „ustalony numer punktu był trudny” jest dobrym powodem, aby go nie używać. A jeśli chcesz mieć dobry powód, aby z nich korzystać, to determinizm, w szczególności determinizm na różnych platformach.
Zobacz też:
Dodatek : Sugeruję, aby świat był mały. Powiedziawszy to, oba OP i Jibb Smart poruszają kwestię, że odejście od pływaków początkowych ma mniejszą precyzję. Będzie to miało wpływ na fizykę, która będzie widoczna znacznie wcześniej niż krawędź świata. Stałe liczby punktowe, no cóż, mają ustaloną precyzję, będą wszędzie tak samo dobre (lub złe, jeśli wolisz). Co jest dobre, jeśli chcemy determinizmu. Chciałbym również wspomnieć, że sposób, w jaki zwykle uprawiamy fizykę, ma właściwość wzmacniania małych odmian. Zobacz efekt motyla - fizyka deterministyczna w The Incredible Machine and Contraption Maker .
Kolejny sposób uprawiania fizyki
Myślałem, że powodem, dla którego mały błąd w precyzji w liczbach zmiennoprzecinkowych jest wzmacniany, jest to, że wykonujemy iteracje na tych liczbach. Na każdym etapie symulacji bierzemy wyniki ostatniego etapu symulacji i robimy na nich różne rzeczy. Kumulacja błędów na szczycie błędów. To jest twój efekt motyla.
Nie sądzę, abyśmy zobaczyli, że jedna kompilacja korzystająca z jednego wątku na tej samej maszynie daje inną wydajność przy tym samym wejściu. Jednak na innej maszynie może to zrobić inna wersja.
Istnieje argument za przetestowaniem tam. Jeśli zdecydujemy dokładnie, jak powinny działać, i będziemy mogli przetestować na sprzęcie docelowym, nie powinniśmy wypuszczać kompilacji, które mają inne zachowanie.
Istnieje jednak również argument za niedziałaniem poza domem, który gromadzi tyle błędów. Być może jest to okazja do uprawiania fizyki w inny sposób.
Jak zapewne wiesz, istnieje ciągła i dyskretna fizyka, obie pracują nad tym, o ile każdy obiekt przesunąłby się w czasie. Jednak ciągła fizyka ma środki, aby dowiedzieć się o chwili zderzenia, zamiast sondować różne możliwe momenty, aby sprawdzić, czy doszło do zderzenia.
Proponuję zatem: użyj technik ciągłej fizyki, aby dowiedzieć się, kiedy nastąpi kolejne zderzenie każdego obiektu, z dużym krokiem czasowym, znacznie większym niż w przypadku jednego kroku symulacji. Następnie bierzesz najbliższą chwilę kolizji i zastanawiasz się, gdzie wszystko będzie w tej chwili.
Tak, to dużo pracy z jednego kroku symulacji. Oznacza to, że symulacja nie rozpocznie się natychmiast ...
... Możesz jednak przeprowadzić symulację kilku kolejnych kroków symulacji bez sprawdzania kolizji za każdym razem, ponieważ już wiesz, kiedy nastąpi następna kolizja (lub że kolizja nie nastąpi w dużym czasie). Co więcej, błędy skumulowane w tej symulacji są nieistotne, ponieważ gdy symulacja osiągnie duży czas, po prostu umieszczamy wcześniej obliczone pozycje.
Teraz możemy wykorzystać budżet czasu, który wykorzystalibyśmy do sprawdzania kolizji na każdym etapie symulacji, aby obliczyć kolejną kolizję po tej, którą znaleźliśmy. Oznacza to, że możemy symulować z wyprzedzeniem, korzystając z dużego czasu. Zakładając, że świat ma ograniczony zasięg (nie będzie to działać w przypadku dużych gier), powinna istnieć kolejka przyszłych stanów do symulacji, a następnie każda ramka, którą interpolujesz od ostatniego stanu do następnego.
Argumentowałbym za interpolacją. Biorąc jednak pod uwagę, że istnieją przyspieszenia, nie możemy po prostu interpolować wszystkiego w ten sam sposób. Zamiast tego musimy interpolować, biorąc pod uwagę przyspieszenie każdego obiektu. W tym przypadku moglibyśmy po prostu zaktualizować pozycję w ten sam sposób, co robimy dla dużego timepeptu (co oznacza również, że jest mniej podatny na błędy, ponieważ nie użylibyśmy dwóch różnych implementacji dla tego samego ruchu).
Uwaga : Jeśli wykonujemy te liczby zmiennoprzecinkowe, takie podejście nie rozwiązuje problemu obiektów zachowujących się inaczej, im dalej są od początku. Jednak prawdą jest, że precyzja jest tracona w miarę oddalania się od źródła, ale nadal jest deterministyczna. W rzeczywistości dlatego nawet nie wspomniał o tym pierwotnie.
Uzupełnienie
Od OP w komentarzu :
Chodzi o to, że gracze będą mogli zapisać swoje maszyny w jakimś formacie (np. Xml lub json), aby rejestrować pozycję i obrót każdego elementu. Ten plik XML lub JSON zostanie następnie wykorzystany do odtworzenia komputera na komputerze innego gracza.
Więc nie ma formatu binarnego, prawda? Oznacza to, że musimy się również martwić, niezależnie od tego, czy odzyskane liczby zmiennoprzecinkowe odpowiadają oryginałowi. Zobacz: Ponownie odwiedzono Float Precision: Przenośność dziewięciocyfrowa