OjektIDs im Netzwerk

Noch eine Andere Sache:

Da ich sehr viele Einheiten und dazu noch einiges, was immer irgentetwas von einer Einheit will, passierte es häufig, dass z.B. ein Zielsuchgeschoss die Position seines Ziels anfragt, obwohl diese Einheit bereits gelöscht wurde, weil sie z.B. gestorben ist.

Eine "Schnelllösung" war eine Einheit erst nach z.B. 20 Sekunden gelöscht wird, und die Dauer eines Geschosses darf diese Zeit nicht überschreiten. Das ganze funktionierte Anfangs recht gut, jedoch musste ich für alle möglichen Dinge, die länger Zugriff auf Einheiten brauchten das Event-System des Spiels abfragen lassen, ob die Einheit, die grad gestorben ist, eine ist die ich z.B. noch im Target hab, sodass ich net in 30 Sekunden eine Einheit irgentwo hinschicken will, die garnicht mehr existiert. Das Endete dann in viel durcheinander wo ich schnell den überblick verloren habe.

Meine Zweite Lösung war eine Art Smartpointer zu verwenden: Wann immer eine Einheit länger als wie für eine "Frame" benutzt wird, wird ein Referenzzähler erhöht. Wird sie nicht mehr gebraucht, wird er eben wieder decrementiert. Wenn die Einheit nun stirbt, wird sie erst aus dem Speicher entfernt, wenn der Zähler auf 0 ist.

Ganz zufrieden bin ich mit der Lösung aber auch nicht. Ich dachte evtl. noch an das Observer Patter. Die Einheiten merken sich, wer grad zugriff auf sie hat (z.B. Zielsuchgeschosse) und informieren diese über wichtige Ereignisse, sprich sowas wie eine bidirektionale verbindung. Vorteil ist nun, dass sich so sehr einfach extra Effekte einbauen lassen, wie z.B. eine Fähigkeit, die alle anfliegemden Geschosse auf die Angreifer zurück fliegen usw...

Ich weiß nur nicht, ob diese Lösung nun ideal ist. Da das Problem im prinziep bei den meisten Spielen auftaucht, hoffe ich einfach, dass es auch hierfür eine einfache Standartlösung gibt?

TyRoXx

Little RTS schrieb:

Ich dachte evtl. noch an das Observer Patter.

Das ist die richtige Lösung.

rapso

dabei verwendet man normalerweise eine mischung aus recounter+id, in der art wie z.B.

struct UID
{
uint32_t m_ID:20;
uint32_t m_Counter:12;
IEntity* m_pEntity;
};

jedesmal wenn ein objekt angelegt wird im array, wird der counter erhoeht fuer diese ID, wenn eine rakete nun diese objekt referenziert, liest du die UID, stimmt die ID (ist ja derselbe slot), aber der counter nicht, wurde das objekt zerstoert. das verwendet z.b. Halo fuer alle objekte in der engine soweit ich weiss.
und ja, das kannst du dann zu einer linked list zusammenstecken, ganz ohne overhead. (ausser dem head der freelist).

Das gleiche prinziep nutze ich auch fürs Pathfinding und FogOfWar. Das man das Prinziep auch fürs Managment der Einheiten nutzen kann, daran hab ich ich nicht gedacht.

Es fehlt zwar die "bidirektionale" verbindung, aber dafür sieht es sehr einfach und robust aus! Ich werds mal ausprobieren, Danke!

hustbaer

TyRoXx schrieb:

Little RTS schrieb:

Ich dachte evtl. noch an das Observer Patter.

Das ist die richtige Lösung.

Das ist mit an Sicherheit grenzender Wahrscheinlichkeit für dieses Problem nicht die richtige Lösung.

TGGC

Eine einfache und effiziente Moeglichkeit ist Folgendes:
- ein Counter startet zu Spielbeginn bei 0, immer wenn ein Objekt erzeugt wird, erhöht man den Counter -> eindeutige ObjektID
- in einer Map wird jeder ID ein Pointer zugeordnet (in der Map ist Einfügen, Löschen und Suchen schneller als beim Array)
- wird eine Einheit ungültig wird sie aus der Map entfernt -> Problem "tote Einheit" geloest
- sollte man eine Riesenanzahl Einheiten benötigen kann man den Counter auch resetten und alle IDs neu vergeben, aber soweit kommst du wahrscheinlich nie...

DarkShadow44

TGGC schrieb:

snip

Genau so würde ich es auch machen. Spätestens bei einem 64bit Integer hast du genug IDs um das Spiel Jahrhunderte laufen zu lassen, mit 1Mio neuen Einheiten pro Sekunde.
Ergo keine Kollisionen. Und warum eine komplexe Lösung wenns einfach auch geht ?

DarkShadow44 schrieb:

TGGC schrieb:

snip

Genau so würde ich es auch machen. Spätestens bei einem 64bit Integer hast du genug IDs um das Spiel Jahrhunderte laufen zu lassen, mit 1Mio neuen Einheiten pro Sekunde.
Ergo keine Kollisionen. Und warum eine komplexe Lösung wenns einfach auch geht ?

Das obere ist einfacher und schneller, die Suche auf std::map is O(log(n)), in relation zum Indizieren in einem Array O(1) ist unnötig. Die Freelist ist ebenfalls einfach zu machen und wenn std::list, std::queue oder sogar ein std::vector als stack genutzt wird.

Aber das ist sowieso der falsche Ansatz. Hunderte Einheiten wird niemand auf diese Weise per Netzwerk synchronisieren, Star Craft lief schon mit einem 14.4 Modem und ein Savegame ist winzig.

TGGC

Es gibt ja noch andere Maps, man brauch sich ja nur die aussuchen, die am besten auf den Anwendungsfall passt. Dein Array wird halt kompliziert, sobald du die zweite Anforderung auch erfüllen willst. Entweder muss es gross genug sein, um auch alle ehemaligen Objekte zu enthalten (sprich du brauchst einen riesigen zusammenhängenden Speicherblock und wenn noch ein paar mehr Objekte kommen, musst du den komplett umkopieren) oder du musst diese in einer weiteren Liste speichern und irgendwie rausfinden, dass sie jetzt ganz sicher nicht mehr benutzt werden. Oder du musst alles durchgehen was Referenzen hält und sie ungültig machen. Von daher alles unnötige Optimierung, die man auch noch später angehen kann, wenns an der Stelle wirklich haken sollte.

Der SC1 Vergleich ist witzlos. Die Groesse des Savegames oder der Netzwerknachrichten ist unabhaengig von der Struktur welche die IDs verwalten, denn diese zu speichern oder uebertragen ist voellig unnoetig. (Uebrigens sind die Systemanforderungen für SC1 eine 28.8 KBps Verbindung mit geringer Latenz...)

volkard

rapso schrieb:

dabei verwendet man normalerweise eine mischung aus recounter+id, in der art wie z.B.
struct UID
{
uint32_t m_ID:20;
uint32_t m_Counter:12;
IEntity* m_pEntity;
};
jedesmal wenn ein objekt angelegt wird im array, wird der counter erhoeht fuer diese ID, wenn eine rakete nun diese objekt referenziert, liest du die UID, stimmt die ID (ist ja derselbe slot), aber der counter nicht, wurde das objekt zerstoert. das verwendet z.b. Halo fuer alle objekte in der engine soweit ich weiss.
und ja, das kannst du dann zu einer linked list zusammenstecken, ganz ohne overhead. (ausser dem head der freelist).

Gefällt mir. So bleibt das Array ID->Pointer hübsch klein. Dann braucht man nicht mal mit einer Hastable anzurücken.

TGGC

Ehm volki, das ist ne Hashmap. Siehst du nicht die Hashfunktion? Dort steht sie. Hat nur den Nachteil das du vorher die Maximalzahl deiner Objekte bestimmen musst, denn eine Kollision aufloesen kann diese Hashmap nicht. Wird die Zahl überschritten gehen IEntity* Pointer verloren. Wenn wie gewünscht jedes Geschoss und auch jedes tote Objekt verwaltet werden soll, kann man so eine Grenze nur schwer bestimmen. Warum also die Funktion eines Sparse Arrays schlecht nachbauen, wenn es schon zig Implementierungen dafür gibt?

volkard

TGGC schrieb:

Ehm volki, das ist ne Hashmap.

Ist mir doch klar, daß Du ne Hashtable brauchst. Das ist das übliche Wort für Hashmap. Schau mal aufs Wort "Hashtable" in meinem Posting. Siehst Du es? Aber ich brauche keine, kleiner. Ich habe das auch geschrieben, oder?

TGGC schrieb:

Siehst du nicht die Hashfunktion? Dort steht sie.

Ich sehe Knuths phi hash, double hashing, als Größe eine Zweierpotenz, die IDs einigermaßen am Stück und man hat meiner Erfahrung nach praktisch keine Kollisionen hat, durchschnittliche Zugriffsanzahl pro Anfrage dicht bei 1 statt bei 2. Da würde ich gerne hinkommen. Wie die IDs einigermaßen am Stück lassen? Na, die Frei-Liste! Uih, jetzt aber mal genau nachgedacht, die Hashtable sollte nicht voller wie sagen wir mal 80% werden. Und wachsen und schrumpfen tut sie ungern. Bei wechselnden Objektanzahlen sollte man bei geringem Füllstand nicht panisch werden, sondern sie auch mal mit 10% fahren. Dann kann ich doch gleich ein Array nehmen! Genau ein Zugriff pro Anfrage. Mehr Speicherlokalität. Kann zu viel geringeren Kosten als eine schlichte Hashtable wachsen. Geht aber nur, wenn durch rapsos Trick tote IDs sofort wiederverwendet werden dürfen! Nu gib schon zu, daß da alles harmonisch zusammenpaßt.

TGGC schrieb:

Hat nur den Nachteil das du vorher die Maximalzahl deiner Objekte bestimmen musst, denn eine Kollision aufloesen kann diese Hashmap nicht.

Kein Zwang, eine defekte Hashtable zu verwenden.

TGGC schrieb:

Wird die Zahl überschritten gehen IEntity* Pointer verloren. Wenn wie gewünscht jedes Geschoss und auch jedes tote Objekt verwaltet werden soll, kann man so eine Grenze nur schwer bestimmen.

Muß doch keiner bestimmen, oder willst Du ein 80-er-Jahre-Game basteln, was immer abstürzt, wenn man mal mehr Elefanten hat als die Betatester? Das Array könnte wachsen (und die Hashtable zu hohen Kosten auch). Soll jedes tote Objekt verwaltet werden? Nee, ich glaube, diese Forderung hast Du Dir selber ausgedacht, weil Du uns nicht folgen konntest.

TGGC schrieb:

Warum also die Funktion eines Sparse Arrays schlecht nachbauen, wenn es schon zig Implementierungen dafür gibt?

Erst rausfinden, was man genau braucht. Wenn es diese Datenstruktur dann schon fertig gibt, kann man sie ja verwenden.

Kellerautomat

DarkShadow44 schrieb:

Spätestens bei einem 64bit Integer hast du genug IDs um das Spiel Jahrhunderte laufen zu lassen, mit 1Mio neuen Einheiten pro Sekunde.
Ergo keine Kollisionen. Und warum eine komplexe Lösung wenns einfach auch geht ?

+1

TGGC

volki, musst du halt mal lesen. Dann kannst du dir auch die falschen Aussagen sparen.

TGGC schrieb:

Es gibt ja noch andere Maps, man brauch sich ja nur die aussuchen, die am besten auf den Anwendungsfall passt.

Du hast also den Wink gemerkt, du hast dasselbe Verfahren mit einer anderen Datenstruktur beschrieben.

Dein Array wird halt kompliziert, sobald du die zweite Anforderung auch erfüllen willst. Entweder muss es gross genug sein, um auch alle ehemaligen Objekte zu enthalten (sprich du brauchst einen riesigen zusammenhängenden Speicherblock und wenn noch ein paar mehr Objekte kommen, musst du den komplett umkopieren) oder du musst diese in einer weiteren Liste speichern und irgendwie rausfinden, dass sie jetzt ganz sicher nicht mehr benutzt werden.

Das hat der Counter gemacht. Es ist ein 32bit Counter, ein Teil der Bits wird zum Indizieren benutzt, ein Teil ist das Alter, falls ein Eintrag noch in Benutzung ist, dann kannst du eins weiter rechnen und den Eintrag ausprobieren.
Im Normalfall hast du weitaus weniger Allokationen als Referenzierungen, damit ist das Verfahren effizienter wenn du O(1) Find statt O(1) Alloc hast.

Oder du musst alles durchgehen was Referenzen hält und sie ungültig machen.

Der Counter ist genau dafür da.

Von daher alles unnötige Optimierung, die man auch noch später angehen kann, wenns an der Stelle wirklich haken sollte.

Es ist unnötig jetzt schon dafür zu optimieren, dass nicht genug IDs für Objekte allokiert werden könnten.

Der SC1 Vergleich ist witzlos. Die Groesse des Savegames oder der Netzwerknachrichten ist unabhaengig von der Struktur welche die IDs verwalten

Das ist das Topic!
Der ganze Sinn der IDs ist Pointer über Netzwerk aufzulösen.
Das machen RTS nicht, hier zu debatieren wie es am besten zu machen ist, ist witzlos. Ein Buch oder Tutorial das aufzeigt wie es richtig gemacht wird ist 1000 mal mehr Wert.

(Uebrigens sind die Systemanforderungen für SC1 eine 28.8 KBps Verbindung mit geringer Latenz...)

Der eigentliche Punkt den du beim Besserwissen übersiehst ist, dass RTS niemals all die Daten übertragen die der Threadstarter übertragen will, du kannst dich gerne auf Warcarft berufen oder etwas davor, die Datenmenge ist nichtmal 1KB/s, das sind 256 IDs/s wenn sonst keine Daten vorhanden sind im packet.
Mit Header und Nutzdaten bist du bei vielleicht 50 Packeten/s. 50 Einhehtein/s, da brauch er keine Angst zu haben das Arraylimit zu erreichen.

rapso

bitte ab jetzt nur noch sachlich, keine herabwuerdigenden kosenamen, keine persoenlichen angriffe, etc.

so ein simpler thread sollte nicht so aus dem ruder laufen. helft dem thread starter und ignoriert notfalls provokationen.