Wie entferne ich ein Objekt am besten aus meiner Spieleschleife, wenn es tot ist?

16

Ok, also habe ich eine große Liste aller meiner Entitäten, die ich durchschleife und aktualisiere. In AS3 kann ich dies als Array (dynamische Länge, untypisiert), als Vektor (typisiert) oder als verknüpfte Liste (nicht nativ) speichern. Im Moment verwende ich Array, aber ich plane, zu Vector oder Linked List zu wechseln, wenn es schneller ist.

Wie soll ich meine Frage, wenn eine Entität zerstört wird, von der Liste entfernen? Ich könnte seine Position aufheben, es herausspleißen oder einfach eine Flagge darauf setzen, um zu sagen: "Überspringe mich, ich bin tot." Ich fasse meine Entitäten zusammen, sodass eine Entität, die tot ist, wahrscheinlich irgendwann wieder am Leben ist. Was ist meine beste Strategie für jede Art von Sammlung und welche Kombination aus Sammlungstyp und Entfernungsmethode funktioniert am besten?

Iain
quelle
Die Länge eines Vektors ist nicht festgelegt, sie ist jedoch typisiert und daher dem Array überlegen. Der Nachteil ist, dass es keine schnelle Syntax gibt, um eine vorab gefüllte Liste zu definieren, aber das brauchst du meiner Meinung nach nicht.
Bart van Heukelom

Antworten:

13

Ich würde alle hinzugefügten / entfernten Elemente in separaten Listen speichern und diese Operationen ausführen, nachdem ich die Update-Schleife durchlaufen habe.

Simon
quelle
10

Das Flixel-Framework verwendet das Dead-Flag (tatsächlich mehrere Flags, die festlegen, ob es gezeichnet, aktualisiert usw. werden soll). Ich würde sagen, wenn Sie Entitäten wiederbeleben wollen und Leistung ein Problem darstellt, verwenden Sie die Dead-Flagge. Nach meiner Erfahrung ist das Instanziieren neuer Entitäten in dem von Ihnen beschriebenen Anwendungsfall die teuerste Operation, und das Herausspleißen oder Aufheben der Werte von Elementen kann bei Flashs mitunter sehr unruhiger Speicherbereinigung zu einer Aufblähung des Speichers führen.

Gregory Avery-Weir
quelle
1
+1 für flixel. Recycling deadhilft wirklich bei der Leistung.
Snow Blind
3

Während einige Techniken von Natur aus effizienter sind als andere, spielt es nur eine Rolle, wenn Ihnen auf Ihrer Zielplattform die Zyklen ausgehen. Verwenden Sie die Technik, mit der Sie Ihr Spiel schneller erledigen können. Versuchen Sie, sich in der Zwischenzeit nicht auf die spezifische Implementierung Ihrer Container-Datenstrukturen zu verlassen, und optimieren Sie diese anschließend, wenn Sie sie benötigen.

Nur um einige der Techniken anzusprechen, die bereits von anderen hier besprochen wurden. Wenn die Reihenfolge der Entitäten wichtig ist, können Sie mit einem Dead-Flag während der Aktualisierungsschleife den nächsten Frame verbinden. z.B. sehr einfacher Pseudocode:

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;

Dies sind die Merkmale dieses Schemas:

  • natürliche Kompaktheit von Entitäten (obwohl möglicherweise 1 Frame-Latenzzeit verstrichen ist, bevor ein Entitäts-Slot wiederhergestellt werden kann).
  • Keine zufälligen Nachbestellungsprobleme.
  • Doppelt verknüpfte Listen haben zwar das Einfügen / Löschen von O (1), sind jedoch nur sehr schwer vorab abzurufen, um eine optimale Cache-Latenz zu erzielen. Wenn Sie sie in einem kompakten Array halten, funktionieren die Block-Prefetch-Techniken einwandfrei.
  • Im Fall der Zerstörung mehrerer Objekte müssen Sie keine redundanten Schichtkopien erstellen, um Ordnung und Kompaktheit zu erhalten (alles wird während des Aktualisierungsdurchlaufs einmal ausgeführt).
  • Sie nutzen die Möglichkeit, Daten zu berühren, die sich bereits während der Aktualisierung im Cache befinden müssen.
  • Es funktioniert gut, wenn Ihre Quell- und Ziel-Entity-Poiter Arrays trennen sollen. Sie können dann Ihre Entity-Arrays doppelt puffern, um die Vorteile von Multicore / eg zu nutzen. Ein Thread aktualisiert / schreibt die Entitäten für Frame N, während ein anderer Thread die Entitäten des vorherigen Frames für Frame N-1 rendert.
  • Kompaktheit bedeutet, dass es für einen heterogenen Prozessor einfacher ist, die gesamte Menge zu DMA, um noch mehr CPU-Arbeit zu entlasten, z. SPUs oder GPUs.
jpaver
quelle
+1. Ich mag das. Obwohl ich kaum Updates innerhalb eines Pools bestellen muss, füge ich diese in die Sammlung der Dinge ein, an die ich mich erinnern muss, wenn ich auf die Situation
Kaj
2

In Bezug auf meine allgemeine Programmiererfahrung ist das Spleißen normalerweise ein langsamer Vorgang, bei dem alle vorhandenen Elemente um eins nach oben verschoben werden. Ich würde denken , es auf null zu setzen, wäre die beste Lösung hier ; Eine tote Flagge würde funktionieren, aber Sie müssten darauf achten, dass Ihr Code nicht durcheinander kommt.

Wir sprachen eigentlich nur über das Zusammenlegen von Ressourcen im Chatroom. Es ist eine sehr gute Übung, und es ist gut zu hören, dass Sie das tun. :)

Ricket
quelle
1
Wenn die Aktualisierungsreihenfolge nicht wichtig ist, sollte das Zusammenfügen so einfach wie das Verschieben der letzten Entität in den aktuellen Index und das Verringern der Poolanzahl und des Iteratorindex sein.
Kaj
Wow, sehr guter Punkt, Kaj! :)
Ricket
2

Persönlich würde ich eine verknüpfte Liste verwenden. Das Durchlaufen einer Favoritenliste ist schnell und das Hinzufügen und Entfernen von Elementen ist möglich. Die Verwendung eines Arrays oder Vektors ist eine gute Wahl, wenn Sie direkten Zugriff auf Elemente in der Struktur benötigen (z. B. Zugriff auf einen Index), dies hört sich jedoch nicht so an.

Wann immer Sie ein Element aus der verknüpften Liste entfernen, können Sie es einem Pool von Objekten hinzufügen, die dann wiederverwendet werden können, um Speicherzuweisung zu sparen.

Ich habe die polygonalen Datenstrukturen in mehreren Projekten verwendet und war sehr zufrieden mit ihnen.

Bearbeiten: Tut mir leid, ich denke die Antwort war in Bezug auf die Entfernungsstrategie nicht sehr klar: Ich würde vorschlagen, das Element aus der Liste zu entfernen, sobald es tot ist und es direkt zur Poolstruktur hinzuzufügen (recyceln). Da das Entfernen eines Elements aus einer verknüpften Liste sehr leistungsfähig ist, sehe ich darin kein Problem.

Blödmann
quelle
1
Ich gehe davon aus, dass Sie hier eine doppelt verknüpfte Liste vorschlagen? (vorwärts zurück)? Außerdem: Schlagen Sie eine Art Pool über den Link-Elementen vor oder ordnen Sie dynamisch jeden Zeigerhalter in der verknüpften Liste zu?
Simon
Ja, es müsste eine doppelt verknüpfte Liste sein, die für diese Aufgabe am besten geeignet ist. Vielen Dank für den Hinweis! Hinsichtlich der Wiederverwendung von Elementen: Ich habe über eine spezielle Poolklasse / Datenstruktur nachgedacht, die bei Bedarf neue Objekte erstellt oder vorhandene Instanzen verwendet, wenn sich einige im Pool befinden. Daher wäre es gut, tatsächlich "tote" Elemente aus der Liste zu entfernen und sie zur späteren Verwendung in den Pool aufzunehmen.
Mistzack
Eine einfach verknüpfte Liste reicht aus. Doppelt verknüpfte Listen bieten nur den Vorteil, in beide Richtungen zu iterieren. Um eine einzeln verknüpfte Liste mit der Option zum Entfernen des aktuellen Elements zu durchlaufen, müssen Sie den vorherigen Eintrag verfolgen.
deft_code
@caspin ja genau. Wenn Sie eine einfach verknüpfte Liste verwenden, müssen Sie die vorherigen Knoten verfolgen und ihren nextZeiger nach einem gelöschten Knoten mit dem Knoten verknüpfen . Wenn Sie dies nicht mühsam selbst erledigen möchten, ist eine doppelt verknüpfte Liste die DataStructure Ihrer Wahl.
Bummzack
1

"Setzen Sie einfach eine Flagge darauf und sagen Sie:" Überspringen Sie mich, ich bin tot. "Ich fasse meine Entitäten zusammen, so dass eine Entität, die tot ist, sehr wahrscheinlich irgendwann wieder am Leben ist."

Ich denke, Sie haben Ihre eigene Frage zu dieser speziellen Anwendung beantwortet. Ich würde Arrays meiden, wenn Sie jemals vorhaben, andere Arbeiten als Push-and-Pop auszuführen. Verknüpfte Listen sind eine intelligentere Methode, wenn Sie umfangreiche Operationen durchführen möchten. Wenn Sie jedoch vorhaben, dieselbe Entität wieder in das Spiel zu integrieren, ist es sinnvoll, nur eine boolesche Variable festzulegen und diese während der Spieloperationsschleifen zu überprüfen.

scape
quelle
0

Eine saubere und allgemeine Lösung, die ich in einer von mir verwendeten Bibliothek gefunden habe, war die Verwendung einer abschließbaren Karte.

Sie haben zwei Operationen lock()und unlock(), während Sie Iterierte über die Karte , werden Sie lock()nun von diesem Punkt jede Operation , die die Karte ändert nicht wirksam werden, wird es nur in eine geschoben , CommandQueuedie ausgeführt wird , wenn Sie anrufen unlock().

Das Entfernen einer Entität hätte also den folgenden Pseudocode:

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

und wenn du unlock()

isLocked = false
commandQueue.execute(this);

Sie müssen nur berücksichtigen, dass Sie die Entität erst nach der Schleife entfernen.

EDIT: Dies ist die von Simon vorgeschlagene Lösung.

GriffinHeart
quelle
0

Ich habe zwei Methoden.

Wenn Sie ein zu löschendes Objekt aufrufen, setzt es tatsächlich zwei Flags:

1. Sie müssen dem Container mitteilen, dass ein Objekt gelöscht wurde

2. Sie müssen dem Container mitteilen, welche Objekte gelöscht werden sollen

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

Eins Verwenden eines Objektvektors

std::vector<object*> objects;

Überprüfen Sie dann in der Aktualisierungsfunktion, ob ein Objekt gelöscht wurde, und durchlaufen Sie in diesem Fall alle Objekte und entfernen Sie die Objekte, die ein Löschkennzeichen aufweisen

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

Zwei Verwenden eines (Zeigers auf einen) Vektor von Objekten.

std::vector<object*> *objects;

Wenn in der Aktualisierungsfunktion ein Objekt gelöscht werden soll, iterieren Sie durch die Objekte und fügen Sie diejenigen, die nicht gelöscht werden sollen, zu einem neuen Vektor hinzu. Löschen Sie den Objektvektor und setzen Sie den Zeiger auf den neuen Vektor

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

quelle