Możesz zobaczyć swój system tak, jakby składał się z szeregu stanów i funkcji, gdzie funkcja f[j]
z wejściem x[j]
zmienia stan systemu s[j]
w stan s[j+1]
, tak jak:
s[j+1] = f[j](s[j], x[j])
Stan jest wyjaśnieniem całego twojego świata. Lokalizacje gracza, lokalizacja wroga, wynik, pozostała amunicja itp. Wszystko, czego potrzebujesz, aby narysować ramkę gry.
Funkcja to wszystko, co może wpłynąć na świat. Zmiana ramki, naciśnięcie klawisza, pakiet sieciowy.
Dane wejściowe to dane pobierane przez funkcję. Zmiana ramki może zająć trochę czasu od ostatniego przejścia, naciśnięcie klawisza może obejmować faktyczny naciśnięty klawisz, a także to, czy naciśnięto klawisz Shift.
Ze względu na to wyjaśnienie przyjmuję następujące założenia:
Założenie 1:
Ilość stanów dla danego przebiegu gry jest znacznie większa niż liczba funkcji. Prawdopodobnie masz setki tysięcy stanów, ale tylko kilkadziesiąt funkcji (zmiana ramki, naciśnięcie klawisza, pakiet sieciowy itp.). Oczywiście ilość danych wejściowych musi być równa liczbie stanów minus jeden.
Założenie 2:
Koszt przestrzenny (pamięć, dysk) przechowywania pojedynczego stanu jest znacznie większy niż koszt przechowywania funkcji i jej danych wejściowych.
Założenie 3:
Czasowy koszt (czas) przedstawienia stanu jest podobny lub tylko o jeden lub dwa rzędy wielkości dłuższy niż koszt obliczenia funkcji w stanie.
W zależności od wymagań twojego systemu powtórek istnieje kilka sposobów na wdrożenie systemu powtórek, więc możemy zacząć od najprostszego. Zrobię też mały przykład, używając gry w szachy, zapisanej na kawałkach papieru.
Metoda 1:
Store s[0]...s[n]
. To jest bardzo proste, bardzo proste. Z powodu założenia 2 koszt przestrzenny jest dość wysoki.
W przypadku szachów można to osiągnąć poprzez narysowanie całej planszy dla każdego ruchu.
Metoda 2:
Jeśli potrzebujesz tylko powtórki do przodu, możesz po prostu zapisać s[0]
, a następnie zapisać f[0]...f[n-1]
(pamiętaj, że jest to tylko nazwa identyfikatora funkcji) i x[0]...x[n-1]
(jakie były dane wejściowe dla każdej z tych funkcji). Aby odtworzyć, po prostu zacznij od s[0]
i oblicz
s[1] = f[0](s[0], x[0])
s[2] = f[1](s[1], x[1])
i tak dalej...
Chcę tutaj zrobić małą adnotację. Kilku innych komentatorów powiedziało, że gra „musi być deterministyczna”. Każdy, kto to powie, musi ponownie wziąć Computer Science 101, ponieważ chyba że twoja gra ma być uruchamiana na komputerach kwantowych, WSZYSTKIE PROGRAMY KOMPUTEROWE SĄ DETERMINISTYCZNE¹. Właśnie dlatego komputery są tak niesamowite.
Ponieważ jednak Twój program najprawdopodobniej zależy od programów zewnętrznych, od bibliotek po faktyczną implementację procesora, upewnienie się, że funkcje zachowują się tak samo między platformami, może być dość trudne.
Jeśli używasz liczb pseudolosowych, możesz albo zapisać wygenerowane liczby jako część danych wejściowych x
, albo zapisać stan funkcji prng jako część swojego stanu s
i jej implementację jako część funkcji f
.
W przypadku szachów można to osiągnąć poprzez narysowanie początkowej planszy (która jest znana), a następnie opisanie każdego ruchu, mówiąc, który kawałek poszedł gdzie. Tak przy okazji, tak właśnie to robią.
Metoda 3:
Teraz najprawdopodobniej chcesz móc zagrać w swoją powtórkę. Oznacza to, że obliczyć s[n]
dla dowolnego n
. Korzystając z metody 2, musisz obliczyć, s[0]...s[n-1]
zanim będziesz mógł obliczyć s[n]
, co zgodnie z założeniem 2 może być dość wolne.
Aby to zaimplementować, metoda 3 jest uogólnieniem metod 1 i 2: zapisz f[0]...f[n-1]
i x[0]...x[n-1]
podobnie jak metoda 2, ale także zapisz s[j]
dla wszystkich j % Q == 0
dla danej stałej Q
. Mówiąc prościej, oznacza to, że przechowujesz zakładkę w jednym z każdego Q
stanu. Na przykład Q == 100
przechowujeszs[0], s[100], s[200]...
Aby obliczyć s[n]
arbitralnie n
, najpierw ładujesz poprzednio zapisane s[floor(n/Q)]
, a następnie oblicz wszystkie funkcje od floor(n/Q)
do n
. Co najwyżej będziesz obliczał Q
funkcje. Mniejsze wartości Q
są szybsze do obliczenia, ale zajmują znacznie więcej miejsca, podczas gdy większe wartości Q
zużywają mniej miejsca, ale obliczanie trwa dłużej.
Metoda 3 z Q==1
jest taka sama jak metoda 1, podczas gdy metoda 3 z Q==inf
jest taka sama jak metoda 2.
W przypadku szachów można to osiągnąć poprzez losowanie każdego ruchu, a także jednego na każde 10 plansz (dla Q==10
).
Metoda 4:
Jeśli chcesz, aby odwrócić powtórka, można zrobić małą odmianą metody 3. Załóżmy Q==100
, a chcesz obliczyć s[150]
poprzez s[90]
odwrotnie. W przypadku niezmodyfikowanej metody 3 konieczne będzie wykonanie 50 obliczeń, aby uzyskać, s[150]
a następnie 49 dodatkowych obliczeń, aby uzyskać s[149]
itd. Ale ponieważ już obliczono, s[149]
aby uzyskać s[150]
, możesz utworzyć pamięć podręczną s[100]...s[150]
przy s[150]
pierwszym obliczeniu , a następnie jesteś już s[149]
w pamięci podręcznej, gdy musisz ją wyświetlić.
Musisz tylko zregenerować pamięć podręczną za każdym razem, gdy musisz obliczyć s[j]
, j==(k*Q)-1
dla dowolnego z nich k
. Tym razem zwiększenie Q
spowoduje mniejszy rozmiar (tylko dla pamięci podręcznej), ale dłuższe czasy (tylko do odtworzenia pamięci podręcznej). Optymalną wartość Q
można obliczyć, jeśli znasz rozmiary i czasy wymagane do obliczenia stanów i funkcji.
W przypadku szachów można to osiągnąć poprzez narysowanie każdego ruchu, a także jednego na każde 10 plansz (dla Q==10
), ale wymagałoby to również narysowania osobnego kawałka papieru, 10 ostatnich obliczonych przez ciebie plansz.
Metoda 5:
Jeśli stany po prostu zajmują zbyt dużo miejsca lub funkcje zajmują zbyt dużo czasu, możesz stworzyć rozwiązanie, które faktycznie implementuje (a nie podróbki) odwrotne odtwarzanie. Aby to zrobić, musisz utworzyć funkcje odwrotne dla każdej z posiadanych funkcji. Wymaga to jednak, aby każda z twoich funkcji była zastrzykiem. Jeśli jest to wykonalne, to dla f'
oznaczenia odwrotności funkcji f
obliczanie s[j-1]
jest tak proste, jak
s[j-1] = f'[j-1](s[j], x[j-1])
Zauważ, że tutaj zarówno funkcja, jak i dane wejściowe j-1
nie są j
. Ta sama funkcja i dane wejściowe byłyby tymi, których użyłbyś podczas obliczeń
s[j] = f[j-1](s[j-1], x[j-1])
Tworzenie odwrotności tych funkcji jest trudną częścią. Jednak zwykle nie można, ponieważ niektóre dane stanu są zwykle tracone po każdej funkcji w grze.
Ta metoda, jak jest, może odwrócić obliczenia s[j-1]
, ale tylko jeśli masz s[j]
. Oznacza to, że możesz oglądać powtórkę tylko od tyłu, zaczynając od momentu, w którym postanowiłeś ją odtworzyć wstecz. Jeśli chcesz odtwarzać wstecz z dowolnego miejsca, musisz to połączyć z metodą 4.
W przypadku szachów nie można tego zrealizować, ponieważ przy danej planszy i poprzednim ruchu możesz wiedzieć, który pionek został przeniesiony, ale nie skąd.
Metoda 6:
Wreszcie, jeśli nie możesz zagwarantować, że wszystkie twoje funkcje są zastrzykami, możesz zrobić małą sztuczkę, aby to zrobić. Zamiast zwracania przez każdą funkcję tylko nowego stanu, możesz także zwrócić odrzucone dane:
s[j+1], r[j] = f[j](s[j], x[j])
Gdzie r[j]
są odrzucone dane. A następnie utwórz funkcje odwrotne, aby pobierały odrzucone dane:
s[j] = f'[j](s[j+1], x[j], r[j])
Oprócz f[j]
i x[j]
musisz także przechowywać r[j]
dla każdej funkcji. Jeszcze raz, jeśli chcesz móc szukać, musisz przechowywać zakładki, na przykład metodą 4.
W przypadku szachów byłaby to ta sama metoda, co metoda 2, ale w przeciwieństwie do metody 2, która mówi tylko, który kawałek idzie, gdzie trzeba, musisz również zapisać, skąd pochodzi każdy kawałek.
Realizacja:
Ponieważ działa to dla wszystkich rodzajów stanów, z wszystkimi rodzajami funkcji, dla konkretnej gry, możesz przyjąć kilka założeń, które ułatwią wdrożenie. W rzeczywistości, jeśli zaimplementujesz metodę 6 z całym stanem gry, nie tylko będziesz mógł odtworzyć dane, ale także cofnąć się w czasie i wznowić odtwarzanie od dowolnego momentu. To byłoby całkiem niesamowite.
Zamiast przechowywać cały stan gry, możesz po prostu przechowywać absolutne minimum wymagane do narysowania danego stanu i serializować te dane co ustalony czas. Twoje stany będą serializacjami, a twój wkład będzie teraz różnicą między dwiema serializacjami. Kluczem do tego jest to, że serializacja powinna się nieznacznie zmienić, jeśli stan świata również się zmieni. Ta różnica jest całkowicie odwracalna, więc wdrożenie metody 5 z zakładkami jest bardzo możliwe.
Widziałem to zaimplementowane w niektórych głównych grach, głównie do natychmiastowego odtwarzania ostatnich danych, gdy wystąpi zdarzenie (frag w FPS lub wynik w grach sportowych).
Mam nadzieję, że to wyjaśnienie nie było zbyt nudne.
¹ Nie oznacza to, że niektóre programy zachowują się tak, jakby były niedeterministyczne (takie jak MS Windows ^^). Poważnie, jeśli możesz stworzyć niedeterministyczny program na deterministycznym komputerze, możesz być całkiem pewien, że jednocześnie zdobędziesz medal Fields, nagrodę Turinga, a prawdopodobnie nawet Oscara i Grammy za wszystko, co jest warte.