Gibt es eine bessere Möglichkeit, ein Ereignissystem einzurichten?

9

Ereignissysteme sind erstaunlich, sie machen extrem unhandlichen Code zahm und ermöglichen wirklich die dynamische Erstellung von Spielen durch einfache Kommunikation von Objekten und der Spielschleife. Ich habe Schwierigkeiten mit der Effizienz meiner aktuellen Implementierung. Derzeit hat meine leichte Optimierung der Aufteilung der Objektlisten in die Ereignisse, auf die sie reagieren, Wunder bewirkt, aber ich sollte noch mehr tun können.

Derzeit habe ich zwei Methoden:

  1. Am einfachsten: Alle Objekte werden einem Vektor hinzugefügt, wenn ein Ereignis gesendet wird. Alle Objekte erhalten das Ereignis über die handle_event () -Methode

  2. Komplexer: Ich habe eine Map mit einem String als Schlüssel und einem Int als Wert. Wenn ein Ereignistyp hinzugefügt wird, wird er dieser Zuordnung hinzugefügt, wobei der int einfach inkrementiert wird (es muss einen besseren Weg geben),
    der Vektor der Vektoren von Objekten wird dann ein neuer Vektor zurückgeschoben, um diesen Ereignistyp zu behandeln.
    Wenn ein Ereignis aufgerufen wird, ruft es einfach das entsprechende int in der eventTypes-Zuordnung zum Typ innerhalb des Vektors von Vektoren von Objekten auf und sendet dieses Ereignis an jedes Objekt, das diesen Ereignistyp behandelt.

Diese erste Methode ist (offensichtlich) für viele Objekte ziemlich langsam, für sehr wenige Objekte jedoch ziemlich schnell. Während die zweite Methode bei großen Objekten, die unterschiedliche Ereignistypen verarbeiten möchten, recht schnell ist, jedoch langsamer als die erste Methode pro Objekt bei Objekten, die denselben Ereignistyp verarbeiten.

Gibt es einen schnelleren Weg (zur Laufzeit)? Gibt es eine schnellere Möglichkeit, ein int vom Zeichenfolgentyp nachzuschlagen? (Anfangs hatte ich eine Aufzählung, aber es waren keine benutzerdefinierten Typen zulässig, die aufgrund der gewünschten Dynamik erforderlich sind.)

Ultifinitus
quelle
1
Dies ist eine Art Zweck von Hash Maps (oder Hash Table). Die Zeichenfolge wird auf eine Hash-Nummer heruntergerechnet, die dann verwendet wird, um direkt in einem Array nachzuschlagen. en.wikipedia.org/wiki/Hash_table
Patrick Hughes
Eine gute Frage ist: Ist dies wirklich ein Leistungsengpass oder machen Sie sich nur vorzeitige Sorgen?
Jari Komppa
Es ist bereits implementiert und es gibt einen Engpass, wenn viele Objekte verwendet werden. Mein vorheriger Kommentar zum Fehlen eines Engpasses betraf nicht die Anwendung selbst, sondern den Geschwindigkeitsunterschied zwischen den beiden oben genannten Implementierungen, bei denen dieselbe Anzahl von Objekten tatsächlich verarbeitet wurde. Ich hatte auf andere Methoden zum Erstellen von Ereignissystemen gehofft ... Einige der Ideen in diesem Thread werden jedoch die Geschwindigkeit
erheblich
100.000 Objekte klingen nur für ein Spiel schrecklich hoch. Ist dies ein Server oder eine Endbenutzer-Client-Anwendung?
Patrick Hughes
Dies ist mein Motor, also strebe ich wirklich nach Flexibilität. Es wird in Serveranwendungen und Endbenutzeranwendungen verwendet (seltener die erste, Optimierung)
ultifinitus

Antworten:

5

Es hört sich so an, als würden Sie sagen, dass der große Leistungsengpass darin besteht, Ereignis-IDs (Ganzzahlen) anhand ihrer Zeichenfolgennamen nachzuschlagen. Sie können Ihre Spieldaten vorverarbeiten, um alle Ereignisnamen in Ganzzahlen umzuwandeln, bevor Sie das Spiel ausführen oder möglicherweise während Sie das Level laden. Dann müssten Sie während des Spiels keine Konvertierungen vornehmen.

Wenn Objekte häufig erstellt und zerstört werden, können die Vektoren von Objekten stark abwandern. In diesem Fall können Sie davon profitieren, wenn Sie verknüpfte Listen anstelle von Vektoren verwenden. Sie können schneller eingefügt und gelöscht werden.

Nathan Reed
quelle
Der Engpass ist nicht groß (für 100.000 Objekte verliert er 0,0000076 ms / Objekt), aber ich denke, Ihre Idee ist eine großartige Idee! Ich denke, ich werde tatsächlich eine einmalige Suche der ID durchführen und die eventID als int anstatt als die ursprünglichen Zeichenfolgendaten speichern lassen. Und ich hatte eigentlich nicht an verknüpfte Listen gedacht, gute Idee.
Ultifinitus
1
+1 Zur Vorverarbeitung der IDs. Sie können dies auch träge tun, indem Sie einen EventType-Typ haben, den jedes Modul über so etwas erhalten kann EventType takeDamageEvent = EventSystem::CacheEventType("takeDamageEvent");. Machen Sie es zu einem statischen Mitglied von Klassen, und in jeder Klasse, die es benötigt, schwebt nur eine Kopie herum.
michael.bartnett
2
Beachten Sie, dass das Speichern von IDs anstelle von Zeichenfolgen das Debuggen etwas erschwert. Es ist immer nützlich, Text zu sehen, der angibt, woher ein Objekt stammt. Sie können den halben Weg gehen, indem Sie sowohl die ID als auch die Zeichenfolge speichern, die Sie zum Debuggen aufbewahren (möglicherweise wird sie sogar in Release-Builds entfernt).
Nicol Bolas
2

Nun, lassen Sie uns zuerst die einfachen Dinge aus dem Weg räumen. Sie haben dies mapzwischen Zeichenfolgen (vermutlich der Name des Ereignisses) und Ganzzahlen (dem Index der registrierten Ereignis-Listener).

Die Suchzeit in a mapbasiert auf zwei Faktoren: der Anzahl der Elemente in der Karte und der Zeit, die für den Vergleich zwischen zwei Schlüsseln benötigt wird (wobei Cache-Probleme ignoriert werden). Wenn die Suchzeit ein Problem darstellt, können Sie die Vergleichsfunktion durch Ändern des Zeichenfolgentyps ändern.

Nehmen wir an, Sie verwenden std::stringund operator<zum Vergleich. Dies ist sehr ineffizient; es führt einen byteweisen Vergleich durch. Sie interessieren sich nicht für die echte Zeichenfolge, die weniger als der Vergleich ist. Sie brauchen nur eine Art Vergleich, der eine streng schwache Reihenfolge ergibt (weil mapes sonst nicht funktioniert).

Daher sollten Sie stattdessen eine 32-Byte-Zeichenfolge mit fester Länge verwenden std::string. Ich benutze diese für Bezeichner. Vergleichstests für diese festen Zeichenfolgen führen keine byteweisen Vergleiche durch. Stattdessen führen sie 32-Bit- (oder 64-Bit-) Vergleiche durch. Es nimmt alle 4 Bytes eine vorzeichenlose Ganzzahl und vergleicht sie mit den entsprechenden 4 Bytes der anderen Zeichenfolge. Auf diese Weise dauert der Vergleich höchstens 8 Vergleiche. Es stellt eine streng schwache Reihenfolge sicher, obwohl die Reihenfolge nichts mit den Daten als Zeichen zu tun hat.

Das Speichern von Zeichenfolgen, die länger als 31 Byte sind (das Zeichen NULL ist erforderlich), schneidet die Zeichenfolge ab (jedoch eher von der Mitte als von den Enden. Ich finde, dass die Entropie am Anfang und am Ende am größten ist). Und Zeichenfolgen, die kürzer sind, füllen die verbleibenden Zeichen mit auf \0.

Jetzt könnten Sie das mapkomplett fallen lassen und eine Hash-Tabelle verwenden. Wenn Sie wirklich über 100.000 verschiedene Arten von Ereignistypen haben, könnte dies eine gute Idee sein. Aber ich kenne kein Spiel, bei dem das eine vernünftige Sache wäre.

Nicol Bolas
quelle
Daher sollten Sie anstelle von std :: string eine 32-Byte-Zeichenfolge mit fester Länge verwenden. Fantastisch! Ich hatte nicht daran gedacht, den String-Typ zu ändern.
Ultifinitus
0

Um die allgemeine Frage zu beantworten:

Besserer Weg, um ein Ereignissystem einzurichten

Da ist gar nichts. Alles, was Sie tun können, ist, die spezifischen Anforderungen zu identifizieren, die Sie an Ihre Ereignissysteme haben (es kann mehrere verschiedene geben), und dann das richtige Werkzeug für den richtigen Job zu verwenden.

Ich habe Tonnen von Ereignissystemen implementiert und versucht, sie zu verallgemeinern, und bin zu diesem Schluss gekommen. Weil Kompromisse wirklich unterschiedlich sind, wenn Sie es zur Kompilierungs- oder Laufzeit machen, wenn Sie Objekthierarchien oder Tafeln usw. verwenden.

Der beste Weg ist, die verschiedenen Arten von Ereignissystemen zu studieren, und dann haben Sie Hinweise darauf, welches in welchem ​​Fall verwendet werden soll.

Wenn Sie nun das wirklich flexibelste System wünschen, implementieren Sie ein Black-Board-System (Laufzeit) mit dynamischen Eigenschaften von Ereignissen, und Sie haben etwas sehr Flexibles, aber möglicherweise sehr Langsames.

Klaim
quelle