W jakim jest najbardziej wydajny pojemnik do przechowywania dynamicznych obiektów gry? [Zamknięte]

Tworzę strzelanki z perspektywy pierwszej osoby i wiem o wielu różnych typach kontenerów, ale chciałbym znaleźć pojemnik, który jest najbardziej wydajny do przechowywania dynamicznych obiektów, które będą często dodawane i usuwane z gry. Kule EX.

Myślę, że w takim przypadku byłaby to lista, aby pamięć nie była ciągła i nigdy nie było żadnych zmian wielkości. Ale zastanawiam się również nad użyciem mapy lub zestawu. Jeśli ktoś ma jakieś pomocne informacje, byłbym wdzięczny.

Nawiasem mówiąc, piszę to w c ++.

Wymyśliłem również rozwiązanie, które moim zdaniem zadziała.

Na początek przydzielę wektor dużego rozmiaru ... powiedzmy 1000 obiektów. Mam zamiar śledzić ostatnio dodany indeks w tym wektorze, aby wiedzieć, gdzie jest koniec obiektów. Następnie utworzę kolejkę, w której będą przechowywane indeksy wszystkich obiektów „usuwanych” z wektora. (Faktyczne usunięcie nie zostanie wykonane, po prostu będę wiedział, że ten slot jest bezpłatny). Więc jeśli kolejka jest pusta, dodam do ostatnio dodanego indeksu w wektorze + 1, w przeciwnym razie dodam do indeksu wektora, który był na początku kolejki.

Odpowiedzią jest zawsze użycie tablicy lub std :: vector. Typy takie jak lista połączona lub mapa std :: map są zwykle absolutnie przerażające w grach, a to zdecydowanie obejmuje przypadki takie jak zbiory obiektów w grze.

Powinieneś przechowywać same obiekty (a nie wskaźniki do nich) w tablicy / wektorze.

ty chcesz pamięci ciągłej. Naprawdę naprawdę tego chcesz. Iteracja nad dowolnymi danymi w nieciągłej pamięci narzuca na ogół wiele braków w pamięci podręcznej i eliminuje zdolność kompilatora i procesora do efektywnego pobierania z pamięci podręcznej. To samo może zabić wydajność.

Chcesz także uniknąć przydziałów i zwolnień pamięci. Są bardzo wolne, nawet z szybkim alokatorem pamięci. Widziałem, że gry dostają 10-krotny wzrost liczby klatek na sekundę po prostu usuwając kilkaset przydziałów pamięci w każdej klatce. Nie wydaje się, żeby było tak źle, ale może być.

Wreszcie, większość struktur danych, którymi zależy ci na zarządzaniu obiektami gry, może być znacznie bardziej efektywnie osadzona w tablicy lub wektorze niż w drzewie lub liście.

Na przykład do usuwania obiektów gry można użyć funkcji zamiany i popu. Łatwo wdrożony za pomocą czegoś takiego:

std::swap(objects[index], objects.back());
objects.pop_back();

Możesz także oznaczyć obiekty jako usunięte i umieścić ich indeks na bezpłatnej liście, aby następnym razem trzeba było utworzyć nowy obiekt, ale lepiej jest zamieniać i popować. Umożliwia wykonanie prostej pętli dla wszystkich obiektów na żywo, bez rozgałęzień poza samą pętlą. W przypadku integracji fizyki pocisków i tym podobnych może to znacznie zwiększyć wydajność.

Co ważniejsze, możesz znaleźć obiekty z prostą parą przeglądów tabel ze stabilnej unikalnej, korzystającej ze struktury mapy miejsc.

Twoje obiekty gry mają indeks w głównej tablicy. Można je bardzo skutecznie wyszukać przy pomocy tego indeksu (znacznie szybciej niż mapa czy nawet tablica skrótów). Jednak indeks nie jest stabilny z powodu zamiany i popu podczas usuwania obiektów.

Mapa miejsc wymaga dwóch warstw pośrednich, ale obie są prostymi przeglądami tablic ze stałymi indeksami. Oni są szybkie . Naprawdę szybko.

Podstawową ideą jest to, że masz trzy tablice: główną listę obiektów, listę pośrednią i bezpłatną listę dla listy pośredniej. Twoja główna lista obiektów zawiera rzeczywiste obiekty, przy czym każdy obiekt zna swój unikalny identyfikator. Unikalny identyfikator składa się z indeksu i tagu wersji. Lista pośrednia to po prostu tablica wskaźników do głównej listy obiektów. Darmowa lista to stos indeksów do listy pośredniej.

Kiedy tworzysz obiekt na liście głównej, znajdujesz nieużywany wpis na liście pośredniej (używając bezpłatnej listy). Wpis na liście pośredniej wskazuje na nieużywany wpis na liście głównej. Inicjujesz swój obiekt w tej lokalizacji i ustawiasz jego unikalny identyfikator na indeks wybranej pozycji listy pośredniej i istniejący znacznik wersji w głównym elemencie listy plus jeden.

Kiedy niszczysz obiekt, normalnie zamieniasz i pop, ale również zwiększasz numer wersji. Następnie dodajesz również indeks listy pośredniej (część unikalnego identyfikatora obiektu) do wolnej listy. Przenosząc obiekt w ramach zamiany i popu, aktualizujesz również jego wpis na liście pośredniej do nowej lokalizacji.

Przykładowy pseudo-kod:

Object:
  int index
  int version
  other data

SlotMap:
  Object objects[]
  int slots[]
  int freelist[]
  int count

  Get(id):
    index = indirection[id.index]
    if objects[index].version = id.version:
      return &objects[index]
    else:
      return null

  CreateObject():
    index = freelist.pop()

    objects[count].index = id
    objects[count].version += 1

    indirection[index] = count

    Object* object = &objects[count].object
    object.initialize()

    count += 1

    return object

  Remove(id):
    index = indirection[id.index]
    if objects[index].version = id.version:
      objects[index].version += 1
      objects[count - 1].version += 1

      swap(objects[index].data, objects[count - 1].data)

Warstwa pośrednia pozwala mieć stabilny identyfikator (indeks do warstwy pośredniej, w której wpisy się nie przenoszą) dla zasobu, który może się poruszać podczas zagęszczania (główna lista obiektów).

Tag wersji umożliwia przechowywanie identyfikatora w obiekcie, który może zostać usunięty. Na przykład masz identyfikator (10,1). Obiekt o indeksie 10 jest usuwany (powiedzmy, że kula uderza w obiekt i jest niszczona). Obiekt w tej lokalizacji pamięci na głównej liście obiektów ma następnie podbity numer wersji, co daje mu (10,2). Jeśli spróbujesz ponownie wyszukać (10,1) na podstawie przestarzałego identyfikatora, wyszukiwanie zwróci ten obiekt poprzez indeks 10, ale zobaczy, że numer wersji się zmienił, więc identyfikator nie jest już prawidłowy.

Jest to absolutnie najszybsza struktura danych, jaką możesz mieć dzięki stabilnemu identyfikatorowi, który pozwala obiektom poruszać się w pamięci, co jest ważne dla lokalizacji danych i spójności pamięci podręcznej. Jest to szybsze niż jakakolwiek implementacja tabeli skrótów; tabela skrótów musi co najmniej obliczyć skrót (więcej instrukcji niż przegląd tabeli), a następnie musi podążać za łańcuchem skrótów (albo połączona lista w okropnym przypadku std :: unordered_map, albo otwarta lista adresowana w jakakolwiek głupia implementacja tabeli skrótów), a następnie musi dokonać porównania wartości na każdym kluczu (nie droższe, ale możliwe, że tańsze, niż sprawdzenie tagu wersji). Bardzo dobra tabela skrótów (nie ta w żadnej implementacji STL, ponieważ STL nakazuje tabelę skrótów, która optymalizuje dla różnych przypadków użycia niż gra dla listy obiektów gry) może zaoszczędzić na jednej pośredniej,

Istnieje wiele ulepszeń algorytmu podstawowego. Na przykład użycie czegoś takiego jak std :: deque dla głównej listy obiektów; dodatkowa warstwa pośrednia, ale umożliwia wstawianie obiektów do pełnej listy bez unieważniania jakichkolwiek tymczasowych wskaźników uzyskanych z mapy szczelin.

Możesz także uniknąć przechowywania indeksu wewnątrz obiektu, ponieważ indeks można obliczyć na podstawie adresu pamięci obiektu (to - obiekty), a nawet lepiej jest potrzebny tylko przy usuwaniu obiektu, w którym to przypadku masz już identyfikator obiektu (i stąd indeks) jako parametr.

Przepraszamy za napisanie; Nie wydaje mi się, żeby to był jak najbardziej przejrzysty opis. Jest późno i trudno jest to wytłumaczyć bez poświęcania więcej czasu niż na próbki kodu.

tablica o stałym rozmiarze (pamięć liniowa)
z wewnętrzną wolną listą (alokacja O (1) / wolna, stabilne wskazania)
ze słabymi kluczami referencyjnymi (ponowne użycie klucza unieważnia klucz)
zerowe dereferencje narzutu (jeśli znane - poprawne)

struct DataArray<T>
{
  void Init(int count); // allocs items (max 64k), then Clear()
  void Dispose();       // frees items
  void Clear();         // resets data members, (runs destructors* on outstanding items, *optional)

  T &Alloc();           // alloc (memclear* and/or construct*, *optional) an item from freeList or items[maxUsed++], sets id to (nextKey++ << 16) | index
  void Free(T &);       // puts entry on free list (uses id to store next)

  int GetID(T &);       // accessor to the id part if Item

  T &Get(id)            // return item[id & 0xFFFF]; 
  T *TryToGet(id);      // validates id, then returns item, returns null if invalid.  for cases like AI references and others where 'the thing might have been deleted out from under me'

  bool Next(T *&);      // return next item where id & 0xFFFF0000 != 0 (ie items not on free list)

  struct Item {
    T item;
    int id;             // (key << 16 | index) for alloced entries, (0 | nextFreeIndex) for free list entries
  };

  Item *items;
  int maxSize;          // total size
  int maxUsed;          // highest index ever alloced
  int count;            // num alloced items
  int nextKey;          // [1..2^16] (don't let == 0)
  int freeHead;         // index of first free entry
};

Obsługuje wszystko, od kul, potworów, tekstur po cząstki itp. To najlepsza struktura danych dla gier wideo. Myślę, że przyszedł od Bungie (w czasach maratonu / mitów), dowiedziałem się o tym na Blizzardzie i myślę, że to było w grze programistycznej. Prawdopodobnie w tym momencie jest to w całej branży gier.

P: „Dlaczego nie użyć dynamicznej tablicy?” Odp .: Tablice dynamiczne powodują awarie. Prosty przykład:

foreach(Foo *foo in array)
  if (ShouldSpawnBaby(*foo))
    Foo &baby = array.Alloc();
    foo->numBabies++; // crash!

Możesz sobie wyobrazić przypadki bardziej skomplikowane (takie jak głębokie stosy połączeń). Dotyczy to wszystkich kontenerów podobnych do tablicy. Podczas tworzenia gier mamy wystarczającą wiedzę na temat naszego problemu, aby wymuszać na wszystkich rozmiarach i budżetach w zamian za wydajność.

I nie mogę powiedzieć wystarczająco: naprawdę, to najlepsza rzecz na świecie. (Jeśli się nie zgadzasz, opublikuj swoje lepsze rozwiązanie! Uwaga - należy rozwiązać problemy wymienione na górze tego postu: pamięć liniowa / iteracja, alokacja O / 1, wolne, stabilne indeksy, słabe referencje, zerowe koszty ogólne lub masz niesamowity powód, dla którego nie potrzebujesz jednego z nich;)

Nie ma na to właściwej odpowiedzi. Wszystko zależy od implementacji twoich algorytmów. Po prostu wybierz ten, który Twoim zdaniem jest najlepszy. Nie próbuj optymalizować na tym wczesnym etapie.

Jeśli często usuwasz obiekty i tworzysz je ponownie, sugeruję przyjrzeć się implementacji pul obiektów.

Edycja: Po co komplikować rzeczy za pomocą automatów, a co nie. Dlaczego nie po prostu użyć stosu, oderwać ostatni przedmiot i użyć go ponownie? Więc kiedy dodasz jeden, zrobisz ++, a kiedy go otworzysz - zrobisz to, by śledzić swój indeks końcowy.

To zależy od twojej gry. Kontenery różnią się tym, jak szybki jest dostęp do określonego elementu, jak szybko element jest usuwany i jak szybko element jest dodawany.

• std :: wektor - Szybki dostęp, usuwanie i dodawanie do końca jest szybkie. Usuwanie od początku i od środka jest powolne.
• std :: list - Iterowanie po liście nie jest dużo wolniejsze niż wektor, ale dostęp do określonego punktu listy jest powolny (ponieważ iteracja jest w zasadzie jedyną rzeczą, którą możesz zrobić z listą). Dodawanie i usuwanie elementów w dowolnym miejscu jest szybkie. Największy narzut pamięci. Nieprzerwany.
• std :: deque - Szybki dostęp i usuwanie / dodawanie do końca i początku jest szybkie, ale wolne w środku.

Zwykle chcesz użyć listy, jeśli chcesz, aby twoja lista obiektów była posortowana w inny sposób niż chronicznie, a zatem musisz wstawiać nowe obiekty zamiast dołączać, w przeciwnym razie. Deque zwiększył elastyczność w stosunku do wektora, ale tak naprawdę nie ma wiele wad.

Jeśli masz naprawdę dużo bytów, powinieneś przyjrzeć się Partycjonowaniu przestrzeni.