OjektIDs im Netzwerk

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.