Wygląda na to, że chcesz się dowiedzieć o drzewach!
I mówię poważnie: jeśli obecnie zapętlasz tablicę wszystkich swoich kostek, naprawdę powinieneś przyjrzeć się różnym strukturom danych przestrzennych. W tym przypadku najlepszym sposobem na ponowne wyobrażenie sobie świata kostki jest drzewo.
Zanim przejdziemy do przyczyn, zastanówmy się nad naszym problemem. Szukamy rozwiązania, w którym przy możliwie jak najmniejszych kosztach możemy pobrać listę pobliskich kostek, z którymi gracz może się kolidować. Ta lista powinna być jak najmniejsza, ale jak najbardziej precyzyjna.
Teraz, aby określić tę strefę, musimy zmapować przestrzeń współrzędnych naszego gracza na przestrzeń współrzędnych mapy sześcianu; oznacza to, że musimy zamapować pozycję zmiennoprzecinkową odtwarzacza na dyskretny indeks wielowymiarowej tablicy kostek (przykładową notacją może być world[31][31][31], tj. dokładny środek dla tablicy wielowymiarowej 64 * 64 * 64).
Możemy po prostu obliczyć otaczające bloki przy użyciu tego samego dyskretnego indeksowania, być może próbkując tylko pobliskie kostki, ale nadal wymaga to ciągłego przeliczania i nie pozwala na obiekty, które nie są dyskretne w rozmieszczeniu (tj. Mogą nie być odwzorowane na kostkę mapa).
Idealną sytuacją jest zestaw wiader, które zawierają nasze zestawy kostek dla poszczególnych odcinków naszej mapy kostek, podzielone równo, więc zamiast ponownie obliczać otaczający obszar, po prostu wchodzimy i wychodzimy z tych stref . W przypadku wszelkich nietrywialnych obliczeń przechowywanie naszych danych w ten sposób może wyeliminować iterację wszystkich kostek i tylko tych pojedynczych zestawów, które są w pobliżu.
Pytanie brzmi: jak to zrealizować?
Dla świata 64 * 64 * 64 wyobraź sobie, że jest on podzielony na 8 * 8 * 8 stref . Oznacza to, że w twoim świecie będziesz miał 8 stref na oś (X, Y, Z). Każda z tych stref będzie zawierać 8 kostek, które można łatwo odzyskać dzięki temu nowemu uproszczonemu indeksowi.
Jeśli musisz wykonać operację na zestawie pobliskich kostek, zamiast iterować każdą kostkę w twoim świecie, możesz po prostu iterować po tych strefach , dzieląc maksymalną liczbę iteracji z oryginalnej 64 * 64 * 64 (262144) na tylko 520 (8 * 8 * 8 + 8).
Teraz pomniejszyć z tego świata stref i umieścić stref do większych Super strefach ; przy czym każda superstrefa zawiera 2 * 2 * 2 regularne strefy . Ponieważ twój świat zawiera obecnie 512 (8 * 8 * 8) stref , możemy podzielić 8 * 8 * 8 stref na 64 super-strefy (4 * 4 * 4) , dzieląc 8 stref przez 2 strefy na super-strefę . Zastosowanie tej samej logiki z góry spowodowałoby przekroczenie maksymalnej liczby iteracji z 512 na 8 w celu znalezienia superstrefy ; a następnie maksymalnie 64, aby znaleźć strefę postępowania(łącznie maks. 72)! Możesz zobaczyć, jak oszczędza to już wiele iteracji (262144: 72).
Jestem pewien, że teraz widzisz, jak przydatne są drzewa. Każda strefa jest gałęzią drzewa, a każda superstrefa jako gałąź poprzednia. Po prostu przemierzasz drzewo, aby znaleźć to, czego potrzebujesz; używając mniejszych zestawów danych, aby zminimalizować całkowity koszt
Poniższy schemat powinien pomóc w wizualizacji koncepcji. (zdjęcie z Wikipedii: Octrees ):
Zrzeczenie się:
W idealnej konfiguracji, jak powyżej, w której świat wokseli jest już ułożony w wielowymiarowej tablicy o stałym rozmiarze, możesz po prostu sprawdzić pozycję gracza, a następnie indeksować otaczające bloki kosztem O (1)! (Zobacz wyjaśnienie Olhovskysa) Ale staje się to trudniejsze, gdy zaczniesz rozważać, że twój świat rzadko ma ustaloną wielkość w grze wokselowej; i może być konieczne, aby struktura danych mogła ładować całe superstrefy z dysku twardego do pamięci. W przeciwieństwie do wielowymiarowej tablicy o stałym rozmiarze, drzewa pozwalają na to bez zbytniego czasu poświęcanego na algorytmy kombinacyjne.