Verweise auf andere Entities

[Nexus]

Hallo zusammen,

Bei vielen Spielen gibt es verschiedene Einheiten, welche untereinander Verweise haben. Beispiele sind Angriffsziele, Gruppenmitglieder, etc. Wie werden solche Indirektionen programmiertechnisch realisiert, sodass auch die Zerstörung einzelner Einheiten nicht zu Fehlern führt? Mir fallen folgende Ansätze ein:

• Rohe Zeiger und Notify-Funktionen. Letztere entfernen Verweise bei Zerstörung automatisch. Kann aber bei vielen Verweisen viel Speicher und Rechenzeit beanspruchen, zudem ist manuelle Buchführung notwendig.
• Shared und Weak Pointers. std::weak_ptr lässt sich bei einem zerstörten Objekt nicht mehr zu std::shared_ptr umwandeln. Hat aber ebenfalls recht viel Overhead, zumal der Besitz gar nicht wirklich geteilt wird.
• IDs in (Hash-)Maps. Jede Einheit entspricht einer eindeutigen ID (z.B. fortlaufende Integers), die in einer Map auf die entsprechende Einheit abgebildet wird. Verweise werden nur als IDs gespeichert, bei Zugriff muss jeweils die zentrale Map abgefragt werden. Stelle ich mir recht effizient vor, jedoch ist jeder Zugriff etwas langsamer, obwohl Verweis-Invalidierungen nur selten auftreten.

[cooky451]

Hübsche Frage. Was schöneres als IDs hab ich aber nicht anzubieten. Bin gespannt.

[dot]

Mir ist nicht ganz klar, wieso du rohe Zeiger und Notify Funktionen für weniger effizient hältst als eine riesige Map!?

[cooky451]

dot schrieb:

Mir ist nicht ganz klar, wieso du rohe Zeiger und Notify Funktionen für weniger effizient hältst als eine riesige Map!?

Weil man bei Notify Funktionen nen lineares Wachstum hat? Jedes Mal 5000 Objekte informieren zu müssen stelle ich mir nicht so toll vor.

[Ein ehemaliger Benutzer]

Observer Pattern? Alle Entities, die irgendwie Verweise auf andere Entities brauchen sind Observer, und die Entities die beobachtet werden sind Observables. Wenn du eine Entity kaputt machst, sagst du den anderen Entities bescheid und die räumen dann entsprechend auf.

Falls das allerdings das ist, was du mit "Notify-Funktionen" meinst, dann weiss ich nicht, was du mit manueller Buchführung meinst.

cooky451 schrieb:

dot schrieb:

Mir ist nicht ganz klar, wieso du rohe Zeiger und Notify Funktionen für weniger effizient hältst als eine riesige Map!?

Weil man bei Notify Funktionen nen lineares Wachstum hat? Jedes Mal 5000 Objekte informieren zu müssen stelle ich mir nicht so toll vor.

In welchen Fällen hat man schonmal 5000 Objekte, die man benachrichtigen muss? Ich denke, in allen realistischen Beispielen bleiben die Zahlen da so klein, dass das kaum einen Unterschied ausmacht. Auch 5000 Objekte zu notifizieren, wenn eins kaputt geht, sollte keinen großen prozentualen Leistungsverlust zum Rest deines Codes darstellen.

[Nexus]

TravisG schrieb:

Falls das allerdings das ist, was du mit "Notify-Funktionen" meinst, dann weiss ich nicht, was du mit manueller Buchführung meinst.

Ja, das meine ich.

Ich will damit sagen, dass sich ein Observer jedes Mal selbst beim Observable eintragen und wieder austragen muss, sobald ein Verweis geändert wird. Im Weiteren kann eine Einheit Observer und Observable sein, ebenso können sich verschiedene Einheiten gegenseitig referenzieren. Dadurch muss man zusätzlich vorsichtig sein, dass man Referenzen "gleichzeitig" entfernt, um keine ungültigen Zugriffe zu haben.

Alles in allem recht viel Logik, die man mit IDs nicht hat (d.h. auch grössere Fehleranfälligkeit). Dafür sind die Verweise stets aktuell, man muss also vor keinem Zugriff erst prüfen, ob ein Verweis noch gültig ist oder nicht. Ausserdem kann man Notify() generell für Status-Updates und nicht nur Löschungen verwenden.

[Mechanics]

Ich denke, so einfach kann man die Frage nicht beantworten. Es kommt sehr stark drauf an, wie man das ganze modelliert, und man kann das auf unterschiedliche Arten modellieren. Ich könnte mir z.B. vorstellen, dass die KI zentral implementiert ist und alle Einheiten steuert (und nicht jede Einheit eine eigene KI hat). Die KI könnte vielleicht intern auf das Blackboard Pattern setzen und eine Komponente müsste über Events benachrichtigt werden. Hier würde sich schon ein Observer anbieten. Oder wenn jede Einheit selbständig ihre Strategie neuberechnen muss (oder einen Teil der Strategie), holt sie sich Informationen aus einem globalen Objekt. Das neuberechnen wird ebenfalls zentral angestoßen und es muss nicht jede Einheit einzeln benachrichtigt werden.

[GHKR]

Du könntest einen globalen Array aller Entitys erstellen. Jeder Entity könntest du dann beim erstellene eine Zufallszahl zuordnen. Wenn eine Entity entfernt wird setzt du die Zufallszahl auf null und Speicherst den entsprechenden Arrayindex in einer Liste freier Plätze für neue Entitys.

Wenn du jetzt auf einen Entity verweisen willst nimmst du als "Pointer" sowohl den Index als auch die Zufallszahl.

Wenn du auf eine Entity zugreifen willst schaust du im Array unter dem Index nach ob deine und die Zufallszahl der Entity gleich sind. Wenn sie gleich sind kannst du die Entity nehmen und damit was auch immer tun. Wenn sie Ungleich sind, weiß du das die Entity nicht mehr existiert.

Das einzige Wichtige ist, dass deine Zufallszahlen groß genug sind um 2 Entitys mit der gleichen Zufallszahl zu vermeiden. Sollte allerdings mit einen komplett zufälligen uin64_t kein Problem sein.

Alternativ könnte man auch statt einer Zufallszahl jeweils beim erstellen und vernichten eine dem Platz zugeordnete Zahl inkrementieren und diese vergleich.

Hier würde jede Operation in konstanter Zeit verlaufen und kein zusätztliches dynamisches Speichermanagement pro Frame brauchen.

Falls nicht sinnvoll eine Obergrenze für die Anzahl deiner Entitys festlegene kannst (das solltest du können!), kannst du die größe des globelen Arrays auch verdoppeln wenn er voll ist.

[Mechanics]

GHKR schrieb:

Du könntest einen globalen Array aller Entitys erstellen. Jeder Entity könntest du dann beim erstellene eine Zufallszahl zuordnen. Wenn eine Entity entfernt wird setzt du die Zufallszahl auf null und Speicherst den entsprechenden Arrayindex in einer Liste freier Plätze für neue Entitys.

Wenn du jetzt auf einen Entity verweisen willst nimmst du als "Pointer" sowohl den Index als auch die Zufallszahl.

Wenn du auf eine Entity zugreifen willst schaust du im Array unter dem Index nach ob deine und die Zufallszahl der Entity gleich sind. Wenn sie gleich sind kannst du die Entity nehmen und damit was auch immer tun. Wenn sie Ungleich sind, weiß du das die Entity nicht mehr existiert.

Das einzige Wichtige ist, dass deine Zufallszahlen groß genug sind um 2 Entitys mit der gleichen Zufallszahl zu vermeiden. Sollte allerdings mit einen komplett zufälligen uin64_t kein Problem sein.

Alternativ könnte man auch statt einer Zufallszahl jeweils beim erstellen und vernichten eine dem Platz zugeordnete Zahl inkrementieren und diese vergleich.

Hier würde jede Operation in konstanter Zeit verlaufen und kein zusätztliches dynamisches Speichermanagement pro Frame brauchen.

Falls nicht sinnvoll eine Obergrenze für die Anzahl deiner Entitys festlegene kannst (das solltest du können!), kannst du die größe des globelen Arrays auch verdoppeln wenn er voll ist.

Was hat das alles für einen Sinn? Zufallszahlen sollte man ganz sicher nicht brauchen und auch nicht verwenden.

[nwp3]

Zuerst würde ich Objekte nicht sofort löschen. Zwischen "Einheit stirbt" und "Einheit verschwindet" vergeht ja einige Zeit (Sterbeanimation). Die Einheiten können außerdem einen Referenzzähler bekommen. Jedes Objekt, dass ein anderes Objekt referenziert, erhöht den Referenzzähler dieses Objekts und verringert ihn wieder sobald die Referenz weggenommen wird. Das letzte Objekt, dass die Referenz löscht, löscht auch das Objekt (mit einem Weltobjekt, dass Referenzen auf alle nicht toten Objekte hat um ihre Löschung zu verhindern).

[Nexus]

Mechanics schrieb:

Die KI könnte vielleicht intern auf das Blackboard Pattern setzen und eine Komponente müsste über Events benachrichtigt werden. Hier würde sich schon ein Observer anbieten.

Ja, generell bietet einem Observer recht viele Möglichkeiten als Event-System. Vielleicht kann man die Löschung von Verweisen gerade als speziellen Event modellieren... Vorläufig werde ich wohl diesen Ansatz ausprobieren, eventuell melde ich mich wieder.

Mechanics schrieb:

Was hat das alles für einen Sinn? Zufallszahlen sollte man ganz sicher nicht brauchen und auch nicht verwenden.

Ich finde die Idee gar nicht so schlecht, allerdings könnte man fortlaufende Ganzzahlen statt Zufallszahlen verwenden, um Kollisionen zu vermeiden.

Und bitte verwendet nicht gleich Full-Quotes, besonders wenn der zitierte Beitrag gerade darüber steht

nwp3 schrieb:

Zuerst würde ich Objekte nicht sofort löschen. Zwischen "Einheit stirbt" und "Einheit verschwindet" vergeht ja einige Zeit (Sterbeanimation).

Ja, bisher hatte ich auch meist ein Flag gesetzt und in regelmässigen Abständen alle markierten Objekte entfernt. Eigentlich können die Verweise schon zum Todeszeitpunkt (vor dem Löschzeitpunkt) entfernt werden, falls keine Interaktion mit toten Objekten mehr stattfindet.

nwp3 schrieb:

Die Einheiten können außerdem einen Referenzzähler bekommen. Jedes Objekt, dass ein anderes Objekt referenziert, erhöht den Referenzzähler dieses Objekts und verringert ihn wieder sobald die Referenz weggenommen wird. Das letzte Objekt, dass die Referenz löscht, löscht auch das Objekt (mit einem Weltobjekt, dass Referenzen auf alle nicht toten Objekte hat um ihre Löschung zu verhindern).

Das wäre im Prinzip der std::shared_ptr -Ansatz, nur von Hand programmiert.

[hustbaer]

Nexus schrieb:

nwp3 schrieb:

Die Einheiten können außerdem einen Referenzzähler bekommen. (...)

Das wäre im Prinzip der std::shared_ptr -Ansatz, nur von Hand programmiert.

Das wäre der intrusive_ptr Ansatz. Und der hat u.A. den Vorteil dass man nicht für die Thread-Safety bezahlt (InterlockedIncrement) die man gar nicht braucht.

[Nexus]

Stimmt, an boost::intrusive_ptr habe ich gar nicht gedacht, danke für den Hinweis.

[hustbaer]

Wobei das (Ref-Counting/intrusive_ptr) mMn. den Nachteil hat, dass man u.U. Objekte am Leben erhält die eigentlich schon weg sein sollten.

[TyRoXx]

Ich habe bisher gute Erfahrungen mit boost::signal und dem Verzicht auf shared ownership gemacht. Signal ist die Implementation des Observation Pattern in C++ und es gibt keine guten Argumente dagegen. Den resultierenden, verständlichen Code bezahle ich gerne mit einem leicht höheren Ressourcenbedarf.

Shared ownership wie mit shared_ptr oder intrusive_ptr ist meistens ein Designfehler, der zu zyklischen Abhängigkeiten und seltsamen Bugs führt (man verliert leicht den Überblick über die gerade vorhandenen Zeiger).
weak_ptr sollte nicht missbraucht werden, um zerstörte Objekte irgendwann irgendwo auszutragen. Das ist ein unlogischer Hack.

Außerdem trenne ich das inhaltliche Verschwinden eines Spielobjektes von der Zerstörung des C++-Objektes. Das gehört schließlich zum normalen Verhalten des Objektes und nicht zur Ressourcenverwaltung. RAII ist nicht das geeignete Mittel, um andere Objekte zu benachrichtigen. Was tun mit einer Ausnahme im Destruktor? Es gibt keine Möglichkeit, die weiterzureichen. Wie verhindern, dass sich das Programm beim Beenden unnötig mit Benachrichtigungen aufhält oder dass unerwünschte Seiteneffekte auftreten?

Wenn ein Objekt in der Spielwelt ungültig wird, ruft es ein Signal auf, bei dem sich zuvor alle Beobachter des Objektes eingetragen haben. Die können sofort angemessen reagieren. Ein Beobachter muss sich nur an die einfache Regel halten, dass das beobachtete Objekt nach dem abgeschlossenen Aufruf des Signals nicht mehr benutzt werden darf. Wer das beobachtete Objekt besitzt, kann dem Beobachter egal sein. Zwei Objekte können sich problemlos gegenseitig beobachten, das hat keinen Einfluss auf die Lebenszeiten.

Aus solchen einfachen Überlegungen ergibt sich fast von selbst das gesamte Design. Ganz ohne shared_ptr oder andere Hacks.

shared_ptr hat durchaus seine Anwendungen, siehe Completion Handler in Boost Asio. Da braucht man Wertsemantik und Thread-Sicherheit -> shared_ptr . Bei Beobachtern und Beobachteten hat der aber nichts zu suchen.

[hustbaer]

TyRoXx schrieb:

Ich habe bisher gute Erfahrungen mit boost::signal und dem Verzicht und shared ownership gemacht. Signal ist die Implementation des Observation Pattern in C++ und es gibt keine guten Argumente dagegen.

Doch, dass es nicht threadsafe ist. In diesem Fall egal, in anderen nicht.

Und genau da kommt auch schon der Fall daher wo man doch weak_ptr beim Observer-Pattern braucht: wenn die Löschung von Objekten gleichzeitig mit dem Feuern von Events in unterschiedlichen Threads passieren kann.
Dann muss man beim Auslösen des Events nämlich ca. sowas machen:

for (auto entry : blah)
    if (shared_ptr<Observer> o = entry.weakObserver.lock())
        o->Notify();

Wobei es natürlich vorteilhaft wäre den Fall (gleichzeitiges Löschen und Feuern von Events) ganz zu vermeiden. Was vermutlich in den meisten Fällen auch (sinnvoll) möglich ist.

[TyRoXx]

hustbaer schrieb:

Und genau da kommt auch schon der Fall daher wo man doch weak_ptr beim Observer-Pattern braucht: wenn die Löschung von Objekten gleichzeitig mit dem Feuern von Events in unterschiedlichen Threads passieren kann.
Dann muss man beim Auslösen des Events nämlich ca. sowas machen:

for (auto entry : blah)
    if (shared_ptr<Observer> o = entry.weakObserver.lock())
        o->Notify();

Boost.Signals2 sollte so etwas erlauben, wenn man es denn braucht.
Dass shared_ptr und weak_ptr bei der Implementation von Signal/2 nützlich sind, will ich gar nicht bestreiten. In der eigentlichen Anwendung haben sie aber selten eine Daseinsberechtigung.

[Nexus]

Boost.Signals2 ist auch ein gutes Stichwort. Ich habe nur vor langer Zeit einmal Signals1 verwendet, müsste mich wieder genau einlesen.

hustbaer, wurde Signals2 nicht vor allem mit der Motivation entwickelt, threadsicher zu sein?

[hustbaer]

Nexus schrieb:

Boost.Signals2 ist auch ein gutes Stichwort. Ich habe nur vor langer Zeit einmal Signals1 verwendet, müsste mich wieder genau einlesen.

hustbaer, wurde Signals2 nicht vor allem mit der Motivation entwickelt, threadsicher zu sein?

Soweit ich das in Erinnerung habe: ja.
Es was aber die Rede von "signals" (=signals1)