Jak najlepiej usunąć byt z pętli gry, gdy jest martwy?

Ok, więc mam dużą listę wszystkich moich bytów, które przeglądam i aktualizuję. W AS3 mogę przechowywać to jako tablicę (długość dynamiczna, bez typu), wektor (wpisany) lub listę połączoną (nie rodzimą). W tej chwili korzystam z Array, ale planuję zmienić na Vector lub połączoną listę, jeśli jest szybsza.

W każdym razie, moje pytanie, kiedy Encja zostanie zniszczona, jak powinienem usunąć ją z listy? Mógłbym zerować jego pozycję, podzielić go lub po prostu ustawić na nim flagę, aby powiedzieć „pomiń mnie, jestem martwy”. Gromadzę moje byty, więc Istota, która nie żyje, prawdopodobnie w pewnym momencie znów będzie żyła. Jaka jest moja najlepsza strategia dla każdego rodzaju kolekcji i która kombinacja typu kolekcji i metody usuwania będzie działać najlepiej?

Chciałbym przechowywać wszystkie dodawania / usuwania na osobnych listach i wykonywać te operacje po iteracji przez pętlę aktualizacji.

Struktura Flixel używa flagi martwej (w rzeczywistości kilka flag, które określają, czy należy ją narysować, zaktualizować itd.). Powiedziałbym, że jeśli zamierzasz ożywić byty, a jeśli wydajność stanowi problem, używasz martwej flagi. Z mojego doświadczenia wynika, że ​​tworzenie instancji nowych jednostek jest najdroższą operacją w opisywanym przypadku użycia, a splatanie lub zerowanie elementów może prowadzić do wzdęcia pamięci, biorąc pod uwagę czasami śmieciarskie zbieranie Flasha.

Podczas gdy niektóre techniki są z natury bardziej wydajne niż inne, będzie to miało znaczenie tylko wtedy, gdy zabraknie Ci cykli na platformie docelowej. Użyj dowolnej techniki, która pozwoli ci szybciej wykonać grę. W międzyczasie staraj się nie polegać na konkretnej implementacji struktur danych kontenera, a jeśli zajdzie taka potrzeba, pomoże Ci to później zoptymalizować.

Aby rozwiązać niektóre techniki omówione już przez innych tutaj. Jeśli kolejność elementów jest ważna, to martwa flaga może pozwolić na połączenie podczas pętli aktualizacji na następnej ramce. na przykład. bardzo prosty pseudokod:

void updateGame()
{
  // updateEntities()
  Entity* pSrcEntity = &mEntities[0];
  Entity* pDstEntity = &mEntities[0];
  newNumEntities = 0;
  for (int i = 0; i < numEntities; i++)
  {
    if (!pSrcEntity->isDead)
    {
       // could be inline but whatever.
       updateEntity(pDstEntity, pSrcEntity);
       // if entity just died, don't update the pDstEntity pointer, 
       // and just let the next entity updated overwrite it.
       if (!pDstEntity->isDead)
       {
          pDstEntity++;
          newNumEntities++;
       }
    }
    pSrcEntity++;
  }
}
numEntities = newNumEntities;

Oto cechy tego programu:

• naturalna zwartość jednostek (aczkolwiek z możliwym opóźnieniem 1 klatki, zanim szczelina jednostki może zostać odzyskana).
• bez przypadkowych problemów z ponownym zamawianiem.
• podczas gdy podwójnie Listy połączone mają wstawianie / usuwanie O (1), ale bardzo trudno jest je wstępnie pobrać dla optymalnego ukrywania opóźnienia pamięci podręcznej. Utrzymywanie ich w zwartej tablicy pozwala na dobre działanie technik pobierania bloków.
• W przypadku zniszczenia wielu obiektów nie trzeba wykonywać zbędnych kopii shift, aby zachować porządek i zwartość (wszystko odbywa się raz podczas aktualizacji)
• Skorzystasz z dotykania danych, które będą musiały znajdować się w pamięci podręcznej już podczas aktualizacji.
• Działa dobrze, jeśli elementy źródłowe i docelowe encji mają rozdzielać tablice. Następnie możesz dwukrotnie buforować tablice jednostek, aby skorzystać z wielordzeniowych / np. jeden wątek aktualizuje / zapisuje elementy dla ramki N, podczas gdy inny wątek renderuje elementy poprzedniej ramki dla ramki N-1.
• Kompaktowość oznacza, że ​​łatwiej jest przesłać DMA do heterogenicznego procesora, aby jeszcze bardziej odciążyć procesor, np. SPU lub GPU.

Mówiąc w kategoriach mojego ogólnego doświadczenia w programowaniu, splicowanie jest zwykle powolną operacją, polegającą na przesunięciu wszystkich istniejących elementów w górę o jeden. Wydaje mi się, że najlepszym rozwiązaniem byłoby ustawienie wartości zerowej ; martwa flaga działałaby, ale musisz uważać, aby nie spowodować bałaganu w kodzie.

Właściwie to rozmawialiśmy o puli zasobów w pokoju rozmów. To bardzo dobra praktyka i dobrze słyszeć, że to robisz. :)

Osobiście użyłbym połączonej listy. Iterowanie po polubionej liście jest szybkie, podobnie jak dodawanie i usuwanie elementów. Użycie tablicy lub wektora byłoby dobrym wyborem, jeśli potrzebujesz bezpośredniego dostępu do elementów w strukturze (np. Dostępu do indeksu), ale nie brzmi to tak, jakbyś tego potrzebował.

Za każdym razem, gdy usuwasz element z połączonej listy, możesz dodać go do puli obiektów, które można następnie poddać recyklingowi, aby zaoszczędzić na alokacji pamięci.

Korzystałem z wielokątnych struktur danych w kilku projektach i byłem z nich bardzo zadowolony.

Edycja: Niestety, myślę, że odpowiedź nie była zbyt jasna w zakresie strategii usuwania: Sugerowałbym usunąć element z listy, gdy tylko będzie martwy i dodać go bezpośrednio do struktury puli (recykling). Ponieważ usunięcie elementu z listy połączonej jest bardzo wydajne, nie widzę w tym problemu.

„po prostu ustaw na nim flagę, która mówi„ przeskocz nade mną, nie żyję. ”Łączę moje byty, więc Istota, która nie żyje, prawdopodobnie w pewnym momencie znów będzie żyła”

Myślę, że odpowiedziałeś na własne pytanie dotyczące tej konkretnej aplikacji. Uciekłbym od tablic, jeśli kiedykolwiek planujesz pracować nad nimi innymi niż push i pop. Listy połączone byłyby mądrzejszym rozwiązaniem, jeśli planujesz wykonywać ciężkie operacje. Biorąc to wszystko pod uwagę, jeśli planujesz ponownie zintegrować ten sam byt z powrotem w grze, warto ustawić tylko zmienną boolowską i sprawdzać ją podczas pętli działania gry.

Jednym z czystych i ogólnych rozwiązań, które znalazłem na lib, którego użyłem, było użycie zamykanej mapy.

masz 2 operacje lock()i unlock()podczas iteracji nad mapą będziesz lock()odtąd każda operacja, która zmienia mapę, nie działa, po prostu zostaje wprowadzona w tryb CommandQueue, który uruchomi się, gdy zadzwonisz unlock().

Zatem usunięcie encji miałoby następujący pseudo-kod:

void lockableMap::remove(std::string id) {
   if(isLocked) {
       commandQueue.add(new RemoveCommand(id));
   } else {
       //remove element from map
   }

a kiedy ty unlock()

isLocked = false
commandQueue.execute(this);

Jedyną rzeczą, którą musisz wziąć pod uwagę, jest to, że usuniesz byt dopiero po pętli.

EDYCJA: jest to rozwiązanie zaproponowane przez Simona.

Oto odpowiedź, którą otrzymałem od Liosan :
/gamedev//a/46765/24633

Mam dwie metody.

Kiedy wywołujesz obiekt do usunięcia, tak naprawdę ustawia on dwie flagi:

1. Należy powiedzieć kontenerowi, że obiekt został usunięty

2. Należy powiedzieć kontenerowi, które obiekty zostały usunięte

void object::deleteObject()
{
    container->objectHasBeenDeleted = true;
    isToDelete = true;
}

Jeden Korzystanie z wektora obiektów

std::vector<object*> objects;

Następnie w funkcji aktualizacji sprawdź, czy obiekt został usunięty, a jeśli tak, iteruj wszystkie obiekty i usuń te, które mają flagę usuwania

void container::update()
{
    if (objectHasBeenDeleted)
    {
        std::vector<object*>::iterator ListIterator;
        for(ListIterator=objects.begin(); ListIterator!=objects.end();)
        {
            if( (*ListIterator)->isToDelete )
            {
                ListIterator = objects.erase(ListIterator);
                delete *ListIterator;
            }
            else {
                ++ListIterator;
            }
        }
    objectHasBeenDeleted = false;
    }
}

Dwa za pomocą wektora (wskaźnika do) obiektów.

std::vector<object*> *objects;

W funkcji aktualizacji, jeśli obiekt ma zostać usunięty, iteruj po obiektach i dodaj te, których nie należy usuwać, do nowego wektora. usuń wektor obiektów i ustaw wskaźnik na nowy wektor

void container::update()
{
    if (objectHasBeenDeleted)
    {
        std::vector<object*> *newVector;
        unsigned long i;
        for (i = 0; i < objects->size(); i++)
        {
            if (!objects->at(i)->isToDelete)
            {
                newVector->push_back(objects->at(i));
            }
        }
        delete objects;
        objects = newVector;
        objectHasBeenDeleted = false;
    }
}