Jak to zrobili: Miliony płytek w Terraria


45

Pracowałem nad silnikiem gry podobnym do Terrarii , głównie jako wyzwanie, i chociaż doszedłem do wniosku, że tak naprawdę, nie mogę się skupić na tym, jak radzą sobie z milionami interaktywnych / możliwych do zebrania płytek gra ma kiedyś. Utworzenie około 500 000 kafelków, czyli 1/20 tego, co jest możliwe w Terrarii , w moim silniku powoduje spadek szybkości klatek z 60 do około 20, nawet jeśli nadal wyświetlam kafelki tylko na widoku. Pamiętaj, że nie robię nic z kafelkami, tylko utrzymuję je w pamięci.

Aktualizacja : Dodano kod, aby pokazać, jak to robię.

Jest to część klasy, która obsługuje płytki i rysuje je. Zgaduję, że winowajcą jest część „foreach”, która iteruje wszystko, nawet puste indeksy.

...
    public void Draw(SpriteBatch spriteBatch, GameTime gameTime)
    {
        foreach (Tile tile in this.Tiles)
        {
            if (tile != null)
            {
                if (tile.Position.X < -this.Offset.X + 32)
                    continue;
                if (tile.Position.X > -this.Offset.X + 1024 - 48)
                    continue;
                if (tile.Position.Y < -this.Offset.Y + 32)
                    continue;
                if (tile.Position.Y > -this.Offset.Y + 768 - 48)
                    continue;
                tile.Draw(spriteBatch, gameTime);
            }
        }
    }
...

Również tutaj jest metoda Tile.Draw, która mogłaby również zrobić z aktualizacją, ponieważ każda płytka używa czterech wywołań metody SpriteBatch.Draw. Jest to część mojego systemu autotilowania, co oznacza rysowanie każdego rogu w zależności od sąsiadujących płytek. tekstury_ * są prostokątami, są ustawiane raz na poziomie tworzenia, a nie każdej aktualizacji.

...
    public virtual void Draw(SpriteBatch spriteBatch, GameTime gameTime)
    {
        if (this.type == TileType.TileSet)
        {
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position, texture_tl, this.BlendColor);
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position + new Vector2(8, 0), texture_tr, this.BlendColor);
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position + new Vector2(0, 8), texture_bl, this.BlendColor);
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position + new Vector2(8, 8), texture_br, this.BlendColor);
        }
    }
...

Każda krytyka lub sugestie dotyczące mojego kodu są mile widziane.

Aktualizacja : Dodano rozwiązanie.

Oto ostatnia metoda Level.Draw. Metoda Level.TileAt sprawdza po prostu wprowadzone wartości, aby uniknąć wyjątków OutOfRange.

...
    public void Draw(SpriteBatch spriteBatch, GameTime gameTime)
    {
        Int32 startx = (Int32)Math.Floor((-this.Offset.X - 32) / 16);
        Int32 endx = (Int32)Math.Ceiling((-this.Offset.X + 1024 + 32) / 16);
        Int32 starty = (Int32)Math.Floor((-this.Offset.Y - 32) / 16);
        Int32 endy = (Int32)Math.Ceiling((-this.Offset.Y + 768 + 32) / 16);

        for (Int32 x = startx; x < endx; x += 1)
        {
            for (Int32 y = starty; y < endy; y += 1)
            {
                Tile tile = this.TileAt(x, y);
                if (tile != null)
                    tile.Draw(spriteBatch, gameTime);

            }
        }
    }
...

2
Czy jesteś absolutnie pewien, że renderujesz tylko to, co jest w widoku kamery, co oznacza kod do określenia, co należy renderować poprawnie?
Cooper

5
Framerrate spada z 60 do 20 fps, tylko z powodu przydzielonej pamięci? To bardzo mało prawdopodobne, musi być coś nie tak. Jaka to platforma? Czy system zamienia pamięć wirtualną na dysk?
Maik Semder,

6
@Drackir W tym przypadku powiedziałbym, że jest źle, jeśli istnieje nawet klasa kafelków, powinna wystarczyć tablica liczb całkowitych o odpowiedniej długości, a gdy jest pół miliona obiektów, narzut OO nie jest żartem. Przypuszczam, że można robić z przedmiotami, ale o co chodzi? Tablica liczb całkowitych jest bardzo prosta w obsłudze.
aaaaaaaaaaaa

3
Ojej! Iterowanie wszystkich płytek i sprawdzanie Draw cztery razy na każdym z nich, który jest widoczny. Zdecydowanie możliwe są tutaj pewne ulepszenia ....
thedaian

11
Nie potrzebujesz wszystkich wymyślnych partycji, o których mowa poniżej, aby renderować tylko to, co jest widoczne. To jest mapa tilem. Jest już podzielony na zwykłą siatkę. Wystarczy obliczyć kafelek w lewym górnym rogu ekranu iw prawym dolnym rogu i narysować wszystko w tym prostokącie.
Blecki

Odpowiedzi:


56

Czy podczas renderowania przechodzisz przez wszystkie 500 000 płytek? Jeśli tak, prawdopodobnie spowoduje to część twoich problemów. Jeśli zapętlisz pół miliona kafelków podczas renderowania i pół miliona kafelków podczas wykonywania aktualizacji na nich, to zapętlasz miliony kafelków w każdej klatce.

Oczywiście są na to sposoby. Możesz wykonać tiki aktualizacji podczas renderowania, oszczędzając w ten sposób połowę czasu spędzonego na przeglądaniu wszystkich kafelków. Ale to wiąże twój kod renderujący i kod aktualizacji razem w jedną funkcję i jest to na ogół ZŁA POMYSŁ .

Możesz śledzić kafelki znajdujące się na ekranie i tylko przechodzić przez nie (i renderować). W zależności od rzeczy, takich jak rozmiar kafelków i rozmiar ekranu, może to z łatwością zmniejszyć liczbę kafelków, które trzeba przejść przez pętlę, a to zaoszczędziłoby sporo czasu przetwarzania.

Wreszcie, być może najlepszą opcją (większość dużych gier na świecie to robi), jest podzielenie terenu na regiony. Podziel świat na kawałki, powiedzmy, 512x512 kafelków i ładuj / zwalniaj regiony, gdy gracz zbliży się do regionu lub będzie z niego bardziej oddalony. Dzięki temu nie musisz zapętlać odległych kafelków, aby wykonać dowolny tik aktualizacji.

(Oczywiście, jeśli twój silnik nie wykonuje żadnego zaznaczenia aktualizacji na kafelkach, możesz zignorować część tych odpowiedzi, która o nich wspomina).


5
Część regionu wydaje się interesująca, jeśli dobrze pamiętam, tak to robi Minecraft, jednak to nie działa z tym, jak rozwija się teren w Terrarii, nawet jeśli nie jesteś w pobliżu, na przykład rozrzucanie trawy, kaktusy i tym podobne. Edycja : O ile oczywiście nie uwzględniają czasu, który upłynął od ostatniej aktywności regionu, a następnie wykonują wszystkie zmiany, które miałyby miejsce w tym okresie. To może faktycznie zadziałać.
William Mariager,

2
Minecraft zdecydowanie używa regionów (i późniejszych gier Ultima, i jestem pewien, że wiele gier Bethesda tak robi). Nie jestem pewien, w jaki sposób Terraria radzi sobie z terenem, ale prawdopodobnie albo zastosują upływ czasu do „nowego” regionu, albo przechowują całą mapę w pamięci. Ten ostatni wymagałby dużego użycia pamięci RAM, ale większość współczesnych komputerów sobie z tym poradzi. Mogą być również inne opcje, o których nie wspomniano.
thedaian

2
@MindWorX: Wykonanie wszystkich aktualizacji po ponownym załadowaniu nie zawsze działało - przypuśćmy, że masz całą jałową powierzchnię, a potem trawę. Odchodzisz na wieki, a potem idziesz w kierunku trawy. Kiedy blok z trawą się ładuje, łapie i rozprzestrzenia się w tym bloku, ale nie rozprzestrzenia się na bloki, które są już załadowane. Takie rzeczy postępują DUŻO wolniej niż gra - zaznacz tylko niewielki podzbiór kafelków w jednym cyklu aktualizacji i możesz żyć odległym terenem bez obciążania systemu.
Loren Pechtel,

1
Jako alternatywę (lub uzupełnienie) do „nadrabiania zaległości”, gdy region zbliża się do gracza, możesz zamiast tego mieć osobną symulację iteracyjną dla każdego odległego regionu i aktualizować go wolniej. Możesz zarezerwować czas na każdą ramkę lub uruchomić go w osobnym wątku. Na przykład możesz zaktualizować region, w którym znajduje się gracz oraz 6 sąsiednich regionów w każdej ramce, ale także zaktualizować 1 lub 2 dodatkowe regiony.
Lewis Wakeford,

1
Dla każdego, kto się zastanawia, Terraria przechowuje całe dane kafelków w tablicy 2d (maksymalny rozmiar to 8400 x 2400). Następnie używa prostej matematyki, aby zdecydować, którą sekcję kafelków wyrenderować.
FrenchyNZ

4

Widzę tutaj jeden wielki błąd, którego nie rozwiązały żadne odpowiedzi. Oczywiście nigdy nie powinieneś rysować i iterować więcej płytek niż potrzebujesz. Mniej oczywiste jest to, jak faktycznie definiujesz kafelki. Jak widzę, stworzyłeś klasę kafelków, ja też zawsze to robiłem, ale to ogromny błąd. Prawdopodobnie masz w tej klasie wszystkie funkcje, co powoduje wiele niepotrzebnego przetwarzania.

Powinieneś tylko powtarzać, co jest naprawdę konieczne do przetworzenia. Zastanów się, czego naprawdę potrzebujesz do płytek. Aby rysować, potrzebujesz tylko tekstury, ale nie chcesz iterować rzeczywistego obrazu, ponieważ są one duże do przetworzenia. Możesz po prostu utworzyć int [,] lub nawet niepodpisany bajt [,] (jeśli nie oczekujesz więcej niż 255 tekstur kafelków). Wystarczy powtórzyć te małe tablice i użyć przełącznika lub instrukcji if, aby narysować teksturę.

Więc co musisz zaktualizować? Rodzaj, zdrowie i obrażenia wydają się wystarczające. Wszystkie z nich mogą być przechowywane w bajtach. Dlaczego więc nie utworzyć takiej struktury dla pętli aktualizacji:

struct TileUpdate
{
public byte health;
public byte type;
public byte damage;
}

Możesz użyć tego typu do narysowania kafelka. Abyś mógł odłączyć ten jeden (stworzyć własną tablicę) od struktury, aby nie powtarzać niepotrzebnych pól zdrowia i obrażeń w pętli losowania. Aby zaktualizować cel, powinieneś rozważyć szerszy obszar niż tylko ekran, aby świat gry był bardziej żywy (byty zmieniają pozycję poza ekranem), ale do rysowania rzeczy potrzebujesz tylko widocznego kafelka.

Jeśli zachowasz powyższą strukturę, zajmie to tylko 3 bajty na płytkę. Jest to więc idealne rozwiązanie dla celów oszczędnościowych i pamięciowych. Dla prędkości przetwarzania tak naprawdę nie ma znaczenia, czy używasz int, czy bajtu, czy nawet long int, jeśli masz system 64-bitowy.


1
Tak, późniejsze wersje mojego silnika ewoluowały, aby z niego korzystać. Głównie w celu zmniejszenia zużycia pamięci i zwiększenia prędkości. Typy ByRef są powolne w porównaniu z tablicą wypełnioną strukturami ByVal. Mimo to dobrze, że dodałeś to do odpowiedzi.
William Mariager

1
Tak, natknąłem się na to, szukając losowych algorytmów. Natychmiast zauważyłem, gdzie używasz własnej klasy kafelków w kodzie. To bardzo częsty błąd, kiedy twoja nowa. Miło widzieć, że nadal jesteś aktywny, odkąd opublikowałeś to 2 lata temu.
Madmenyo

3
Nie trzeba albo healthalbo damage. Możesz przechowywać niewielki bufor ostatnio wybranych lokalizacji kafelków i obrażenia na każdym z nich. Jeśli wybierany jest nowy kafelek i bufor jest pełny, stocz z niego najstarszą lokalizację przed dodaniem nowej. Ogranicza to liczbę kafelków, które można wydobywać jednocześnie, ale i tak jest to z grubsza ograniczone #players * pick_tile_size. Możesz zachować tę listę dla każdego gracza, jeśli to ułatwi. Rozmiar ma znaczenie dla prędkości; mniejszy rozmiar oznacza więcej płytek w każdej linii pamięci podręcznej procesora.
Sean Middleditch,

@SeanMiddleditch Masz rację, ale nie o to chodziło. Chodziło o to, aby zatrzymać się i pomyśleć, co naprawdę potrzebujesz, aby narysować kafelki na ekranie i wykonać obliczenia. Ponieważ OP wykorzystywał całą klasę, stworzyłem prosty przykład, prosty idzie daleko w postępach w nauce. Odblokuj teraz mój temat dotyczący gęstości pikseli, oczywiście jesteś programistą, który próbuje spojrzeć na to pytanie okiem artysty z CG. Ponieważ ta strona jest również dla CG do gier afaik.
Madmenyo

2

Istnieją różne techniki kodowania, których można użyć.

RLE: Więc zacznij od współrzędnej (x, y), a następnie policz, ile takich samych kafelków istnieje obok siebie (długość) wzdłuż jednej z osi. Przykład: (1,1,10,5) oznaczałoby, że zaczynając od współrzędnej 1,1, obok siebie znajduje się 10 płytek typu płytki 5.

Ogromna tablica (mapa bitowa): każdy element tablicy trzyma typ kafelka znajdujący się w tym obszarze.

EDYCJA: Właśnie natknąłem się na to doskonałe pytanie: funkcja losowego generowania mapy?

Generator hałasu Perlin wydaje się być dobrą odpowiedzią.


Nie jestem do końca pewien, czy odpowiadasz na zadane pytanie, ponieważ mówisz o kodowaniu (i szumie perlina), a pytanie wydaje się dotyczyć problemów z wydajnością.
thedaian

1
Korzystając z odpowiedniego kodowania (np. Szumu perlin), nie możesz się martwić o jednoczesne trzymanie wszystkich kafelków w pamięci. Zamiast tego po prostu poprosisz koder (generator szumów), aby powiedział ci, co ma się pojawić przy danej współrzędnej. Tutaj jest równowaga między cyklami procesora a zużyciem pamięci, a generator szumów może pomóc w tym równoważeniu.
Sam Axe,

2
Problem polega na tym, że jeśli tworzysz grę, która pozwala użytkownikom modyfikować teren w jakiś sposób, po prostu używając generatora hałasu do „przechowywania”, informacja nie działałaby. Ponadto generowanie szumów jest dość drogie, podobnie jak większość technik kodowania. Lepiej jest oszczędzać cykle procesora dla rzeczywistych elementów rozgrywki (fizyka, kolizje, oświetlenie itp.) Szum Perlina jest świetny do generowania terenu, a kodowanie jest dobre do zapisywania na dysku, ale w tym przypadku są lepsze sposoby obsługi pamięci.
thedaian

Jednak bardzo dobry pomysł, podobnie jak thedaian, użytkownik oddziałuje na teren, co oznacza, że ​​nie mogę matematycznie odzyskać informacji. I tak spojrzę na hałas perlin, aby wygenerować teren podstawowy.
William Mariager,

1

Prawdopodobnie powinieneś podzielić tilemap jak już sugerowano. Na przykład ze strukturą Quadtree, aby pozbyć się jakiegokolwiek potencjalnego przetwarzania (np. Nawet zwykłego zapętlenia) niepotrzebnych (niewidocznych) płytek. W ten sposób przetwarzane jest tylko to, co może wymagać przetworzenia, a zwiększenie rozmiaru zestawu danych (mapa kafelków) nie powoduje praktycznego spadku wydajności. Oczywiście przy założeniu, że drzewo jest dobrze wyważone.

Nie chcę brzmieć nudno ani nic, powtarzając „stare”, ale podczas optymalizacji zawsze pamiętaj o korzystaniu z optymalizacji obsługiwanych przez Twój zestaw narzędzi / kompilator, powinieneś z nimi trochę poeksperymentować. I tak, przedwczesna optymalizacja jest źródłem wszelkiego zła. Zaufaj swojemu kompilatorowi, w większości przypadków wie lepiej niż Ty, ale zawsze, zawszemierz dwa razy i nigdy nie polegaj na szacunkach. Nie chodzi o szybką implementację najszybszego algorytmu, o ile nie wiesz, gdzie jest rzeczywiste wąskie gardło. Dlatego powinieneś użyć profilera, aby znaleźć najwolniejsze (gorące) ścieżki kodu i skupić się na ich eliminacji (lub optymalizacji). Niska znajomość architektury docelowej jest często niezbędna do wyciśnięcia wszystkiego, co ma do zaoferowania sprzęt, więc przestudiuj te pamięci podręczne procesora i dowiedz się, czym jest predyktor gałęzi. Zobacz, co twój profiler mówi ci o pamięci podręcznej / trafieniach / brakach w gałęzi. Jak pokazuje użycie jakiejś formy struktury danych drzewa, lepiej mieć inteligentne struktury danych i głupie algorytmy, niż na odwrót. Dane są najważniejsze, jeśli chodzi o wydajność. :)


+1 za „przedwczesna optymalizacja jest źródłem wszelkiego zła” Jestem tego winna :(
thedaian

16
-1 poczwórne? Nieco przesada? Gdy wszystkie kafelki mają taki sam rozmiar w takiej grze 2D (która dotyczy terrariów), niezwykle łatwo jest ustalić, który zakres płytek jest na ekranie - jest to tylko skrajnie lewy górny (na ekranie) kafelki w prawym dolnym rogu.
BlueRaja - Danny Pflughoeft

1

Czy nie chodzi o zbyt wiele losowań? Jeśli umieścisz wszystkie kafelki map na jednym obrazie - atlas kafelków, nie będzie przełączania tekstur podczas renderowania. A jeśli wszystkie twoje płytki zostaną podzielone na jedną siatkę, należy je narysować za jednym razem.

O dynamicznym dodawaniu ... Może drzewo quadowe nie jest takim złym pomysłem. Zakładając, że płytki umieszczane są w liściach, a węzły bez liści są tylko partiami siatki od dzieci, korzeń powinien zawierać wszystkie płytki partie w jedną siatkę. Usunięcie jednego kafelka wymaga aktualizacji węzłów (ponowne zbieranie siatki) do katalogu głównego. Ale na każdym poziomie drzewa jest tylko jedna czwarta przebudowanej siatki, która nie powinna być aż tak wielka, 4 * łączenie siatki_wysokość?

Aha, a jeśli użyjesz tego drzewa w algorytmie przycinania, nie zawsze renderujesz węzeł główny, ale niektóre z jego elementów potomnych, więc nie musisz nawet aktualizować / ponownie ładować wszystkich węzłów do katalogu głównego, ale do węzła (bez liści) jesteś renderowanie w tej chwili.

Tylko moje myśli, bez kodu, może to nonsens.


0

@arrival ma rację. Problemem jest kod losowania. Tworzysz tablicę 4 * 3000 + poleceń rysowania quad (24000+ poleceń rysowania wielokąta ) na ramkę. Następnie te polecenia są przetwarzane i przesyłane do GPU. To jest raczej złe.

Istnieje kilka rozwiązań.

  • Renderuj duże bloki (na przykład rozmiar ekranu) płytek na statyczną teksturę i narysuj je w jednym wywołaniu.
  • Użyj shaderów, aby narysować kafelki bez wysyłania geometrii do GPU każdej klatki (tj. Zapisz mapę kafelków na GPU).

0

To, co musisz zrobić, to podzielić świat na regiony. Generacja terenu hałasowego Perlin może wykorzystywać wspólne ziarno, dzięki czemu nawet jeśli świat nie jest wstępnie wygenerowany, ziarno będzie stanowić część algo hałasu, który ładnie łączy nowy teren z istniejącymi częściami. W ten sposób nie musisz obliczać więcej niż małego bufora przed widokiem graczy na raz (kilka ekranów wokół bieżącego).

Jeśli chodzi o obsługę rzeczy, takich jak rośliny rosnące w obszarach daleko od bieżącego ekranu odtwarzacza, możesz na przykład mieć liczniki czasu. Timery te powtarzałyby się przez powiedzmy pliki przechowujące informacje o roślinach, ich położeniu itp. Wystarczy po prostu odczytać / zaktualizować / zapisać pliki w timerach. Gdy odtwarzacz ponownie dotrze do tych części świata, silnik wczyta się w pliki jak zwykle i wyświetli na ekranie nowe dane zakładu.

Użyłem tej techniki w podobnej grze, którą stworzyłem w zeszłym roku, do zbiorów i hodowli. Gracz mógł chodzić daleko od pól, a po powrocie przedmioty zostały zaktualizowane.


-2

Zastanawiałem się, jak poradzić sobie z tyloma miliardami bloków, a jedyne, co przychodzi mi do głowy, to wzór Flyweight Design. Jeśli nie wiesz, głęboko sugeruję przeczytać o tym: może bardzo pomóc, jeśli chodzi o oszczędzanie pamięci i przetwarzanie: http://en.wikipedia.org/wiki/Flyweight_pattern


3
-1 Ta odpowiedź jest zbyt ogólna, aby była przydatna, a podany link nie rozwiązuje bezpośrednio tego konkretnego problemu. Wzorzec Flyweight jest jednym z wielu sposobów efektywnego zarządzania dużymi zestawami danych; czy mógłbyś wyjaśnić, w jaki sposób zastosowałbyś ten wzór w konkretnym kontekście przechowywania płytek w grze podobnej do Terraria?
postgoodism
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.