Chociaż zgadzam się z sentymentem: „nie przejmuj się, chyba że jest to udowodniony problem”, myślę, że warto o tym pomyśleć od samego początku: retro-montaż rozwiązania jest o wiele bardziej bolesny. I tak, tylko aktualizowanie „pobliskich” kafelków jest dobrym rozwiązaniem. Jednak wydajne przechowywanie i adresowanie przedmiotów w świecie gry jest bardzo ważne ze względu na wydajność.
To, o czym tak naprawdę myślisz, to rzadki zestaw danych: coś, w którym potencjalne indeksy są duże (lub nieograniczone), ale w rzeczywistości wykorzystywany jest tylko niewielki odsetek. Kluczową kwestią jest to, że nie wiesz dokładnie, która proporcja zostanie wykorzystana.
Standardowym rozwiązaniem rzadkiego problemu z zestawem danych jest oddzielenie indeksu / adresowalności od faktycznego przechowywania danych. Więc jeśli obiekt kafelkowy jest drogi, przechowuj go w zwartej formie (np. W płaskiej tablicy). Ale pozwól mu być indeksowany przez tańszy obiekt. W najprostszej postaci może to być macierz 2D (lub 3D), którą można łatwo indeksować według współrzędnych, ale każdy element w macierzy jest po prostu indeksem. Następnie używasz tego indeksu do wyszukiwania rzeczywistej zawartości kafelków w osobnej, zwartej tablicy. Jeśli zawartość kafelka jeszcze nie istnieje, dodaj je na końcu tablicy i zapisz indeks w macierzy 3D.
Rozwiązanie staje się bardziej złożone, jeśli chcesz wesprzeć usuwanie zawartości (ponieważ prowadzi to do fragmentacji tablicy zawartości), a jeśli zawartość kafelków jest tania, to dodatkowa waga indeksu (indeksy 32-bitowe lub 64-bitowe) prawdopodobnie przytłoczy oszczędności wynikające z nieprzechowywania każdej potencjalnej płytki. Jest to również dodatkowe wyszukiwanie, które obniży wydajność pamięci podręcznej.
Możesz uzyskać jeszcze większą wydajność przechowywania, wprowadzając dodatkowe warstwy pośrednie. Załóżmy, że organizujesz kafelki w kawałki, a ich fragmenty mają ziarnistość 64 x 64 x 64. Biorąc pod uwagę płytkę o wartości 125, 1, 132, wiesz, że należy ona do fragmentu (1,0,2). Masz więc świat, który składa się ze zwartej tablicy porcji i macierzy indeksów porcji (-1, jeśli porcja nie istnieje). Zawartość każdego fragmentu (jeśli jest obecny) to macierz indeksów kafelków 64x64x64 (-1, jeśli kafelek jeszcze nie istnieje) oraz zwarta tablica używanych kafelków. W ten sposób nie wypalasz ogromnej liczby indeksów kafelków dla kawałków, które nigdy nie są używane. Postępując zgodnie z tym podejściem i wybierając rozsądne liczby dla ziarnistości fragmentu, możesz masowo skalować swój wszechświat i kontrolować wykorzystanie pamięci. Właściwie, jeśli zrobisz kawałki o wymiarach 32 x 32 x 32,
Możesz także wykonywać podstępne sztuczki, na przykład używać bitów wysokiego rzędu lub indeksów kafelków, aby oznaczać coś wyjątkowego. Jeśli więc wpis w macierzy kafelków ma ustawiony górny bit, wówczas 31 niższych bitów nie oznacza indeksu kafelków, a zamiast tego oznacza „indeks wypaczenia” lub coś podobnego, i można to sprawdzić na osobnej liście aby znaleźć współrzędne, do których prowadzi.
Dlaczego nie możesz przechowywać miliona kafelków w pamięci? Nawet mój telefon ma 256 MB pamięci RAM; będzie milion pustych kafelków, 4-32 MB?
źródło