Praca z dużą ilością kostek. Poprawiasz wydajność?

Edycja: Podsumowując pytanie, mam świat oparty na wokselach (styl Minecraft (Dzięki Communist Duck)), który cierpi z powodu słabej wydajności. Nie jestem pozytywny co do źródła, ale chciałbym uzyskać wszelkie porady, jak się go pozbyć.

Pracuję nad projektem, w którym świat składa się z dużej liczby kostek (dałbym wam liczbę, ale są to światy zdefiniowane przez użytkownika). Mój testowy to około (48 x 32 x 48) bloków.

Zasadniczo te bloki same w sobie nic nie robią. Po prostu tam siedzą.

Zaczynają być używane, gdy chodzi o interakcję gracza.

Muszę sprawdzić, z jakimi sześcianami wchodzi interakcja myszy użytkownika (najechanie myszką, kliknięcie itp.) Oraz wykrywanie kolizji podczas ruchu gracza.

Teraz na początku miałem ogromne opóźnienie, przechodząc przez każdy blok.

Udało mi się zmniejszyć to opóźnienie, zapętlając wszystkie bloki i znajdując, które bloki znajdują się w określonym zakresie postaci, a następnie zapętlając tylko te bloki w celu wykrycia kolizji itp.

Nadal jednak mam depresyjne 2 kl./s.

Czy ktoś ma jakieś pomysły na to, jak mogę zmniejszyć to opóźnienie?

Btw, używam XNA (C #) i tak, to jest 3d.

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.

Zgadzam się z odpowiedzią Daniela, że ​​iteracja przez duże ilości pudeł jest najbardziej prawdopodobną przyczyną, i że dzięki partycjonowaniu przestrzennemu możesz znacznie przyspieszyć grę - ale problem może być także gdzie indziej i możesz marnować swój czas .

Aby znacznie zwiększyć szybkość gry, musisz profilować swój kod. Określ, gdzie jest wąskie gardło, pozwoli to na wprowadzenie największych ulepszeń.

Istnieje wiele sposobów profilowania kodu, możesz utworzyć własną klasę analizy wydajności (która mogłaby skorzystać z klasy Stopwatch (MSDN) ) lub użyć PIX, aby uzyskać ogólne pojęcie o tym, jak zajęty jest procesor / procesor graficzny .

Możesz również umieścić znaczniki zdarzeń PIX w kodzie, które będą wyświetlane jako kolorowe regiony w odczytach PIX. Nie ma oficjalnego interfejsu C # dla tych funkcji, ale ten wątek pokazuje, jak samemu stworzyć interfejs C #.

Jeśli twój odtwarzacz jest duży w stosunku do wielkości kostek, prawdopodobnie potrzebujesz oktawy lub innej struktury podziału przestrzennego, jak sugerują inni.

Jeśli jednak twój gracz jest mały w stosunku do wielkości kostek, prawdopodobnie najszybszym sposobem na wykrycie kolizji z kostkami jest proste liniowe przeszukanie obszaru wokół gracza.

Ponieważ twój gracz ma mniej niż 1 kostkę, musisz tylko przetestować, czy nie ma kolizji z sąsiadującymi 27 kostkami.

Zakłada się, że przechowujesz kostki w tablicy, w której możesz indeksować, z jednym miejscem w tablicy dla każdej kostki.

Jak zauważyli inni, musisz wyprofilować swój kod, aby zobaczyć, co naprawdę cię spowalnia.

Gdybym jednak musiał zgadywać, powiedziałbym, że prawdopodobnie sprawdzasz losowanie każdej kostki, co zdecydowanie byłoby twoim wąskim gardłem. Aby to naprawić, powinieneś przyjrzeć się instancjom geometrii.

Jeszcze jedna sugestia, aby przyspieszyć: Twoje bloki są w przybliżeniu naprawione - oznacza to, że gracz nie może zderzyć się z większością z nich. Dodaj wartość logiczną do bloków wskazujących, czy są one narażone, czy nie. (Można to przeliczyć, patrząc na sąsiadów.) Blok, który nie jest odsłonięty, nie musi być sprawdzany pod kątem kolizji.

To oczywiste, że Minecraft robi coś podobnego - uderzyłem kiedyś nieobciążoną bryłę, która dała mi widok na świat - mogłem patrzeć przez twardą ziemię, wszystko, co się pokazało, to otwarte przestrzenie (druga strona były one odsłoniętą powierzchnią i dlatego zostały renderowane).

Miałem ten problem z moim silnikiem wokseli.

Rozwiązanie: (Dużo prostsze niż oktety) Zamiast zapętlać wszystkie bloki, wystarczy użyć równania, aby określić pozycję bloku w tablicy bloków.

BlockIndex = (x * WorldWidth * WorldHeight) + (z * WorldHeight) + y;

Jeśli chcesz sprawdzić, czy istnieje blok:

Blocks[BlockIndex].Type > -1;

Lub jednak określasz, czy blok istnieje.