Jak to zrobili: Miliony płytek w Terraria

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);

            }
        }
    }
...

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).

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.

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ą.

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ść. :)

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.

@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).

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.

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