Hallo zusammen,

ich modelliere/plane gerade etwas Client/Server Funktionalität für meine Projekte.
Genauer gesagt: (wie sollte es anders sein? für ein Spiel)
Habe mir schon einige Tutorials und Papers diesbezüglich durchgelesen.

Auf ein ungefähres Format bzw. Handling habe ich mich schon eingeschossen. Hier einige Punkte:
Möglichst sicher soll es sein. Nicht unbedingt sicher was verschlüsselung etc angeht. Eher Cheatsicher.
Der Server hat die Kontrolle über alles was passiert. Also keine wichtige Logik auf dem Client.
Der Client wird nur sagen was er macht oder machen will und der Server sagt: Ja, das geht. Und zwar so...!

Jetzt muss ich natürlich die Objekte irgendwie identifizieren. Da hat man ein paar Möglichkeiten (evtl unvollständig):
- Eine integer ID vergeben, und die dann einfach inkrementieren.
- Das Objekt per Namen identifizieren. Strings sind aber nicht sonderlich schnell.
- einen Unique Identifier. Was mir eigentlich am besten gefällt.

Da ich in Java programmiere, gefiel mir auch die mitgelieferte Klasse UUID, welche einen pseudo zufälligen 128-bit Hash erzeugt. Das ist aber wahrscheinlich etwas viel an Daten. Wenn ich schon 16 Byte nur für die ID verballere und meist gerade mal 40 Byte an Rohdaten (Position, Geschwindigkeit, Orientierung) mitbringe.


Lange Rede, kurzer Sinn:
Kennt wer ne sparsamere Hashfunktion?
Hat jemand Erfahrung, welche Datenmengen in solchen Fällen gesendet werden?
Oder vielleicht bin ich auch völlig auf dem Holzweg und jemand hat ne bessere Idee?

Gruß
damadmax

_________________
Es werde Licht.
glEnable(GL_LIGHTING);
Und es ward Licht.

Zitat aus einem Java Buch: "C makes it easy to shoot yourself in the foot; C++ makes it harder, but when you do it blows your whole leg off"

on error goto next

Selbst eine UUID ist übers Netzwerk nicht zwangsläufig eindeutig. Gut es ist vermutlich wahrscheinlicher 5mal hintereinander vom Blitz getroffen zu werden, aber es kann passieren das zwei UUID gleich sind. Wenn du ein paar hundert tausend IDs verwendest besteht dann schon langsam eine realistische Chance das da was passiert, insbesondere weil du ja meist nur Pseudozufallszahlen als Quelle verwendest und nicht eine echte Zufallsquelle. (Die ganzen Wahrscheinlichkeitsanalysen gehen immer von echten Zufallszahlen aus...)

Eine sichere Lösung ist, dass einfach eine zentrale Stelle die IDs vergibt. In deinem Fall wäre das der Server. Hier kannst du dann einfach einen 32bit Unsigned Integer nehmen und inkrementieren. Für den Fall das ein Teil der IDs nur lokal benötigt wird kannst du bei diesen z.B. ein ein "lokal"-Bit (z.B. Vorzeichen-Bit) setzen und so lokal IDs erzeugen die nicht mit den Server-IDs kollidieren.

Eine weitere Möglichkeit die mir gerade ein fällt sind Namespaces. Je nach dem was du genau machen willst ist die Anzahl der Spieler ja recht klein. Du könntest also jedem Spieler (und auch dem Server) eine 8bit ID verpassen. 0 ist einfach der Server, 1 ist Spieler 1 usw. Der Server verteilt am Anfang diese IDs.
Jeder Client inkrementiert dann lokal einen 24bit Integer um neue IDs zu erzeugen. Beide IDs packst du zusammen in einen normalen 32bit Integer.
Das funktioniert natürlich nur wenn die Anzahl der Spieler klein ist und auch nicht ständig neue Spieler joinen bzw. das Spiel verlassen können, sonst würden dir schnell die IDs ausgehen. In dem Fall kannst du entweder mehr Bits für die Spieler-ID spendieren oder ggf. Spieler-IDs recyceln.

_________________
Yeah!

Ich hatte hier schonmal so eine ähnliche Frage gestellt. Es geht zwar ums Speichern in Dateien, aber auch um Referenzierung von Objekten übers Netzwerk.

Das Konzept, was sich letztenendes aufgetan hat, ist das folgende. Es gibt, wie Coolcat gesagt hat, eine zentrale ID-Vergabestelle. Die vergibt inkrementell IDs an Objekte, wenn welche angefordert werden. Die Objekte speichern diese ID auch in sich selber, um lokal immernoch mit den (schnelleren) Pointern arbeiten zu können. Beim Spiechern wird dann auf die Objekt-ID zurückgegriffen.
Hier noch ein paar Implementationsdetails. Ich habe das so gelöst, dass ich ein Array aus Speicherblöcken habe. Diese Blöcke fassen bei mir 2^12 ( = 4096) IDs. Wenn ein Block voll ist, wird ein neuer angefangen. Das Wiederverwenden von nicht mehr gebrauchten IDs habe ich über eine verkettete Liste von "Free Blocks" gelöst. Jedes Element der Liste stellt einen zusammenhängenden Block von freien IDs dar, kennt also eine Start-ID und die Anzahl der folgenden freien IDs. Wenn nun eine neue ID gebraucht wird, wird der erste "Free Block" genommen und draus wird eine ID entfernt. Will man das ganze optimieren, kann man auch dafür sorgen, dass beim freigeben einer ID zwei dann zusammenhängende Free Blocks zu einem gemergt werden. Aber das ist, denke ich, eher optional. Wird eine ID freigegeben, wird geschaut, ob es einen Free Block gibt, der direkt an die ID grenzt, sonst wird ein neuer eröffnet. So schießt der Speicherverbrauch nicht in die Höhe, wenn plötzlich sehr viele hintereinander liegende Objekte freigegeben werden.

//Edit: Was ich noch dazusagen sollte. Diese Methode ist recht schnell, weil man sehr schnellen Zugriff hat. Es muss anhand der ID nur aufgelöst werden, in welchem Block sie sich befindet (1x div, wegen Power-Of-Two konstanten Blockgrößen) und dann ein Direktzugriff auf die entsprechende Stelle durchgeführt werden (1x mod).

Ich hoffe, das hilft. Ansonsten kann ich auch MPL/LGPL-Code anbieten.

greetings

_________________
If you find any deadlinks, please send me a notification – Wenn du tote Links findest, sende mir eine Benachrichtigung.
current projects: ManiacLab; aioxmpp
zombofant network • my photostream
„Writing code is like writing poetry“ - source unknown

„Give a man a fish, and you feed him for a day. Teach a man to fish and you feed him for a lifetime. “ ~ A Chinese Proverb

Doofe Frage am Rande, was spricht gegen die bereits mitgelieferte "uniqueID" namens IP? Sie ist in jedem Paket bereits drin, verhindert zusätzlichen Overhead und ist relativ eindeutig bei einer zentralen Stelle dem Clienten zugeordnet. Eine aufgebaute Session (z.B. Anmeldung bei einem Spiel) ließe sich so leicht weiterverfolgen. Etwaige Kritik wie "IP muss nicht eindeutig sein" ... nun um eine funktionierende flüssige Kommunikation zu haben schon. Gleichzeitig kenne ich kein Heimnetz bei dem der gleiche Rechner abwechselnd über zwei NICs-Daten versendet und ich würde den Betreiber wirklich fragen, ob er weiß, was er da tut. IPs lassen sich leicht manipulieren? Richtig, wie jedes andere Datenpaket und ID auch, die übers Netzwerk wandelt. Wenn man Spielmanipulation vorbeugen will, muss man ganz andere Geschütze auffahren. Daher die Fragen: Warum nicht KISS? Zumal man meist ja ohnehin bereits eine Socket-Verbindung zwischen Client und Server hat

_________________
"Light travels faster than sound. This is why some people appear bright, before you can hear them speak..."

Nun, es geht hier augenscheinlich nicht nur um Spieler (dafür ist die IP-Identifikation echt gut), sondern auch um die einzelnen Objekte. Also non-player Objekte. Zumindest, wenn ich das richtig verstanden habe.

greetings

_________________
If you find any deadlinks, please send me a notification – Wenn du tote Links findest, sende mir eine Benachrichtigung.
current projects: ManiacLab; aioxmpp
zombofant network • my photostream
„Writing code is like writing poetry“ - source unknown

„Give a man a fish, and you feed him for a day. Teach a man to fish and you feed him for a lifetime. “ ~ A Chinese Proverb

@Lord Horazont: Das wäre dann meine zweite Methode: die ID besteht aus zwei IDs...einmal IP, einmal lokale ID.

_________________
Yeah!

Verstehe nicht ganz, wozu die Lokale ID dienen sollte, wenn der Server eh alles managen soll. Die Lokale ID wäre für den Server komplett "irrational", oder übersehe ich da was?

greetings

_________________
If you find any deadlinks, please send me a notification – Wenn du tote Links findest, sende mir eine Benachrichtigung.
current projects: ManiacLab; aioxmpp
zombofant network • my photostream
„Writing code is like writing poetry“ - source unknown

„Give a man a fish, and you feed him for a day. Teach a man to fish and you feed him for a lifetime. “ ~ A Chinese Proverb

Das sind zwei verschiedene Ansätze, nicht durcheinander bringen

_________________
Yeah!

Die IP-Adressen haben allein schon den Nachteil, dass, wenn sich denn mal ein Client oder mehrere(?!) aus dem selben Haushalt über ein öffentliches Netzwerk an deinem Server anmelden, du in jedem Fall mit Problemen einer doppelten Vergabe rechnen musst. Besonders, da man ja mittlerweile voraussetzen kann das so gut wie niemand mehr eine Wählverbindung direkt von seinem PC aus herstellt, sondern einen Router für diese Aufgabe besitzt. NAT wird dir die Identifizierung eines Client anhand der IP-Adressen allein ziemlich schnell vermiesen.
Ich schreibe gerade an einer Implementation von RTP/RTCP und das Verfahren zur Identifizierung der einzelnen Teilnehmer ist wirklich interessant, besonders was das Auflösen von Kollisionen betrifft. Das ist auf jeden Fall ein Ansatz der sich meiner Meinung nach als Basislayer zur Kommunikation in Spielen eignet, bzw. wo man einige Ideen abschauen kann

Im RFC 3550(RTP) auf Seite 38 stehen ein paar Dinge zu Identifiern die man unter Umständen im Hinterkopf behalten sollte. Seite 39 ganz unten (letzter Absatz) merkt nochmal die IP-Adressen Problematik an.


Die ID-Vergabe für die Objekte im Spiel per Server ist doch eine super Idee. Besonders wenn der Server sowieso die gesamte bzw. wenigstens das meiste der Spiellogik vollstrecken soll. Besonders der Gedanke zur Gruppierung der IDs, was Coolcat erwähnt hat, ist Klasse. Falls ein Spieler Objekte im Inventar hat oder generell Objekte besitzt die im Grunde nichts mit den anderen Spielern zu tun hat, kann der Server anhand dessen prüfen ob irgendein Cheat auf diese angewendet wurde (ich hab da gerade das Dupen der Gegenstände in Diablo2 im Hinterkopf - wenn der Server alle IDs erzeugt würde ja im Grunde eine Prüfung ausreichen ob IDs doppelt verwendet werden oder dem Server überhaupt nicht bekannt sind)

MD5 ist ein 128Bit Hashwert der sich doch sicherlich für deine Zwecke zur ID-Vergabe verwursten lässt. Zum Beispiel frühere Packete der einzelnen Clients sollten als "Zufallswerte" doch sicherlich ausreichen. XOR der 4 32Bit Chunks des Hashwerts et voila: ein 32Bit-Wert
(Auch hier der Hinweis: Die ietf-Leute sind super Vordenker )

_________________
--->ladida<---

Erstmal danke für die Antworten.


Dann aber auch bitte mindestens 1mal beim Sch******
Ich meine mich daran erinnern zu können, dass bei Second Life auch mit UUIDs gearbeitet wird. Und die haben wirklich viele Objekte. Aber wie du schon sagtest: Wenn es eine zentrale Stelle gibt sollte das ja kein Problem sein.
Und die gibt es ja bei mir.


Da gehört ja auch noch der Port dazu.


Hehe. Ich auch^^

Ich glaube die die Sache mit der Inkrementierung ist dafür am besten geeignet. Bei 32-bit ints ist es recht sparsam und gut indizierbar. Evtl schau ich mir auch mal das mit den Blöcken an. Für den Anfang wird aber erstmal ein schnödes Array herhalten müssen.

Da bau ich mir ne schöne Singleton-Klasse, die die IDs vergibt.
Jedes Objekt bekommt ein "Gib-mir-deine-wichtigen-Infos-für-die-Clients"-Interface.

Dabei fällt mir noch ein: Macht es Sinn auf dem Server noch ein Culling zu betreiben? D.h. nur Daten für Objekte zu senden, die auch wirklich im Frustum des Clients liegen? Hängt wahrscheinlich von der Menge der Clients ab.

Ich hatte auch mal angedacht, wirklich alles vom Server zu holen. Auch Modelle und Texturen. Also einen richtig dummen Client zu bauen. Aber das wird wohl je nach Verbindung nicht allzu gut laufen.

_________________
Es werde Licht.
glEnable(GL_LIGHTING);
Und es ward Licht.

Zitat aus einem Java Buch: "C makes it easy to shoot yourself in the foot; C++ makes it harder, but when you do it blows your whole leg off"

on error goto next

Genau. Es kommt ja auch noch ein Port hinzu, der eben als Socket eine recht eindeutige Identifikation auch aus einem NAT heraus erlauben sollte. Sollte dies zu Duplikaten führen, haben wir im Netz ganz andere Probleme. Gerade da man auf der Anwendungsebene üblicherweise sowieso alles als Sockets betrachtet, wird das der einfachste Weg sein. Natürlich hat ein solches Konzept seine Nachteile, sollte aber in den meisten Fällen ausreichend sein. Einige der Probleme lassen sich heilen in dem die Session gefresht wird, z.B. in dem bei einer Anmeldung ein Key ausgetauscht wird, der beim Neuaufbau der Session (z.B. Disconnect) genutzt wird, um den Nutzer wieder zuzuordnen. Zumindest halte ich dies sinnvoller als eine ID jedes Mal zu verschicken. Dies sollte wenn überhaupt so gering wie möglich sein (8 bit max. für <= 256 Clients), da es eben doch ne Menge Overhead ist. Einen Vorteil sehe ich darin jedoch kaum, da es z.B. in Bezug auf die Sicherheit sogar fahrlässig wäre sich nur auf diese zu verlassen. (Gibt ja sogar bei der DGL-Webseite einige alte negativ-beispiele... *sg).

Stumpfe Clients kann man durchaus machen. Ich meine man sollte nicht vergessen, dass man die Daten wie Modelle und Texturen mitunter auch lokal Cachen kann und ggf. beim Start via Hash leicht prüfen kann, ob eine neue Anforderung nötig ist. Beim Entwicklern der Anwendung sollte man nie aus den Augen lassen: Der Client hat 0-Rechte. Der Spieler feuert und teilt dem Server mit "ich habe geschossen", dieser entscheidet dann, ob dies wirklich der Fall war. Der Server teilt also nur Ergebnisse mit und niemals anders herum. Alleine die Kommunikation in beide Richtungen macht eine Menge der Performance aus. Der Client darf ggf. z.B. beim Ausfall von Paketen nur "interpolieren", wie es vermutlich weiter geht. Auch wenn es weh tut... gerade auch UDP sollte man sich in dem Kontext wirklich einmal sehr genau ansehen. Gerade dann, wenn es auch irgendwie um "Geschwindigkeit" geht und verlorene Pakete ggf. bei einem späteren Eintreffen keinen Informationswert mehr haben.

Objekte sollten im Zweifel wirklich eine uniqueId haben. Allerdings sollte man wirklich sehr abwägen, ob das Objekt wirklich "unique" sein muss oder es dem Client evtl. ausreicht einfach nur den Typus des Objektes zu kennen. Im Zweifel ist ein "Objekt vom Typ 132" besser zu übertragen als "Das Haus der Basisklasse Objekt in der Farbe rot mit Texture Stein, die Dir aber fehlt und gleich auch noch verschickt wird." Mit einem kleinen Augenzwinkern an meine ersten Versuche...

_________________
"Light travels faster than sound. This is why some people appear bright, before you can hear them speak..."

Wobei es auch den Ansatz gibt, den Client möglichst deterministisch zu machen und dann indem man den Seed des Zufallsgenerators der Clients und des Servers in einem bestimmten Frame vergleicht festzustellen, wenn etwas nicht so gelaufen ist, wie es (laut Server) laufen sollte. Das ist gerade bei aufwändigen Simulationen recht hilfreich (vgl. Spring Engine). Selbst wenn der Client dann Sachen tut, die er eigentlich nicht könnte, fliegt das früher oder später im Seed auf (eher früher… Hatte jemand z.B. nen Widget, was stark an Cheat grenzte, er desyncte dann…).

Um back to topic zu kommen: Ich frage mich gerade, was überhaupt genau gewünscht ist. Geht es um riesige persistente Welten wo sich spieler laufend ein und aus klinken oder geht das mehr in richtung RTS, wo nach dem Spielstart keiner mehr dazukommt?

greetings

_________________
If you find any deadlinks, please send me a notification – Wenn du tote Links findest, sende mir eine Benachrichtigung.
current projects: ManiacLab; aioxmpp
zombofant network • my photostream
„Writing code is like writing poetry“ - source unknown

„Give a man a fish, and you feed him for a day. Teach a man to fish and you feed him for a lifetime. “ ~ A Chinese Proverb

War in etwa das was ich meine. Aber die Entscheidungsgewalt muss beim Server liegen. Och denke das hier beschriebene Phänomen sollten die meisten vom Ur-CounterStrike kennen. Wenn man auf dem Client gerade unter Feuer stand und sich hinter die Deckung verkroch, der Server aber (auf Grund von fehlenden Paketen), dazu entschließt festzustellen, dass der Client definitiv gerade im offenen Feld stand...

Aber ja... all diese Entscheidungen haben massiv damit zu tun wie zeitkritisch es ist und was für eine Welt abgebildet wird.

_________________
"Light travels faster than sound. This is why some people appear bright, before you can hear them speak..."

Genau sowas hatte ich mir gedacht. Das ganze aber generell eher optional.


Ich möchte Position, Orientierung und deren Geschwindigkeiten übertragen. Da der Server ja nicht ständig sendet. Also eine gewisse FPS berücksichtigen soll. Bei Quake werden sie z.b. Snapshots genannt. Wobei da ein gängiger Wert 20 snaps/sek ist. Dann kann der Client mit den letzten Daten interpolieren, bis was neues kommt.


Ich denke ein Health Item oder ein Gegner sollte ruhig eine Unique ID bekommen. Wohingegen ein Partikelsystem nicht für jeden Partikel eine ID auswerfen braucht. Wäre ein wenig Overkill. Da sollten ja sogar clientseitige Einstellungen die Performance betreffend berücksichtigt werden. Da ich ja in Java schreibe, wollte ich es dem Client ersparen ständig neue Objekte zu erzeugen bzw. freuzugeben. Sprich: Nur auf Befehl vom Server wird ein Objekt erzeugt, durch nachfolgende Infos neu orientiert oder animiert und irgendwann, z.b. wenn es zerstört wurde, entfernt. Evtl. wäre an der Stelle auch eine TTL angebracht. Falls ein "zerstöre-objekt"-Paket nicht angekommen ist.
Wobei mir da gerade auffällt... wenn der Client die "Erschaffe"-Botschaft verpasst, würde eine darauf folgende Positionsinfo ins leere laufen. Ich glaube einen Objekt-Typ zu übertragen ist da besser. Dann kann sich der Client ein entsprechendes Objekt aus einem Pool holen, der bereits erzeugte Objekte cached.


Ich denke so komplex wird es bei mir nicht werden.

Kleine Anekdote aus Anno: Wir spielten im Koop. In den meisten Fällen haben unsere stundenlangen Sessions locker durchgehalten. Wir hatte aber auch Runden in denen nach einiger Zeit wirklich nichts mehr parallel lief. Bei meinem Kumpel brannte die Stadt, bei mir aber nicht und er schnauzt mich an warum ich denn das Feuer nicht lösche. Das Spiel meckerte dann ein paar mal, dass wir Out-Off-Sync seien, aber nach einem langen Ladebalken änderte sich daran nichts.

_________________
Es werde Licht.
glEnable(GL_LIGHTING);
Und es ward Licht.

Zitat aus einem Java Buch: "C makes it easy to shoot yourself in the foot; C++ makes it harder, but when you do it blows your whole leg off"

on error goto next

So was sollte man gar nichts übers Netzwerk jagen. Partikel sind in der Regel unwichtig für das Spielgeschehen, der Client kann die einfach komplett eigenständig berechnen. Es sollte reichen etwa die Position des Objektes welches die Partikel erzeugt durch zu geben.

_________________
Yeah!