Synchronisation von Bewegungen

[Teppich]

Ich arbeite zurzeit an einem 2D MMORPG in welchem man bisher nur herumlaufen kann.
Der Server sendet im Moment jedem Spieler auf der selben Map die Positionen der anderen Spieler, die in der Nähe sind.
Der Client sendet Pakete mit einem einzelnen Byte um seine Bewegungsrichtung dem Server mitzuteilen (8 Richtungen).

Nun bin ich gerade dabei mir eine Lösung zu überlegen um dem Spieler ein flüssiges Spielerlebnis zu ermöglichen, ohne dass es möglich ist mit Hacks seine Position zu verändern.
Im moment habe ich dies umgesetzt:

1. Interpolation zur eigenen Position mithilfe der Serverpositionen.

• Position ist immer exakt
• Position ist um RTT / 2 verzögert
• Hoher Ping verhindert "flüssiges" Spielgefühl

2. Simulation der Bewegung durch Client

• Flüssiges Spielgefühl unabhängig vom Ping
• Position muss gelegentlich angepasst werden was zu einem kurzen Ruckler führt

Zweiteres klingt besser, jedoch scheiterts momentan an der Umsetzung, da die Ruckler zu oft auftreten und ich nicht genau weiß, wie ich die Position während der Bewegung richtig anpasse.
Ich habe versucht beim Client eine Historie der vorherigen Positionen + Zeit anzulegen um die Position vom Server mit der am naheliegendsten Position in der Historie zu vergleichen.

Das sieht in etwa so aus:
Positionshistorie:

• Position[x1, y1, time1]
• Position[x2, y3, time2]
• Position[x3, y3, time3]
• ...

Serverposition:
ServerPosition[x, y, currentTime - ping/2]

Nun wird verglichen welche Position in der Historie der Serverposition am nähsten kommt und eine Differenz berechnet. Meist liegt diese bei etwa 3-4 ms. Die Toleranz berechne ich aus der Differenz der Zeit und wenn die Position nicht in etwa übereinstimmt muss angepasst werden. Während der Bewegung ist es jedoch nicht einfach die richtige Position zu ermitteln. Anscheinend klappt das ganze bei mir noch nicht richtig und es kommt zu oft zu Rucklern.

Da die Zeiten nicht genau übereinstimmen und immer eine Differenz von etwa 0-15 ms (Ich speichere Positionen etwa alle 15 ms) vorhanden ist, muss ich irgendwie die eine Differenz der falschen und richtigen Position ermitteln um die momentanige Position zu verschieben damit die Client- und Serverposition wieder im Einklang ist.

Daran scheiterts im Moment. Eventuell gehe ich das ganze auch total falsch an. Ich weiß nicht.
Für Hilfe wäre ich dankbar.

Oliver

 

[Kr0e]

Ich glaube nicht, dass du das falsch angehst! Kurze Frage: TCP oder UDP ? Für solche Modelle wäre TCP denkbar ungeeignet! Verlorene Packete werden nachgesendet, was bei Games mit periodisch eintrudelnden Packeten keinen Sinn macht und ohnehin schon Lags verursacht.

Ich kann nur grob zusammenfassen, was ich von den meisten Spieleengines aka Source und Konsorten weiß:

Per UDP kommen permanente Updates rein ca. alle 33 ms. Das reicht natürlich nicht für flüssiges Spielen. Der Client darf also interpolieren und muss dies auch tun, damti das gut aussieht. Außerdem solltest du INPUT vom Client sowohl Clientseitig als auch Serverseitig auswerten. Sprich der CLient darf und sollte selbst auf Input reagieren, damit sich alles "instant" anfühlt. Die ca 60 ms später ankommenden Packete müssen dann ausgewertet werden und wenn es Probleme gab und dein CLient zu "vorschnell" war, dann muss nachträglich korrigiert werden.

-> Source Engine: Du denkst du wärst schon lange von einer Ecke weg und stirbst dennoch... -> Der Server hat berechnet, dass ein andere rSpieler relativ zu seinem Zeit-Kontext dich doch gesehen hat und sagt dann deinem CLienten "Du bist Tod!". Wobei Source ein Paradebeispiel ist für diese Art, wüsste kaum Spiel, dass so viel Technik und Tricks benutzt um zig von Spielern ein faires Spielerlebnis zu geben!


Außerdem läuft jeder Client für den Server quasi in der Vergangenheit, damit überhaupt interpoliert werden kann! Außerdem könntest du dir Grenzwerte überlegen ab denen korrigiert wird. Sprich wenn dein Client nur um 2% - 4% abweicht könntest du ihn einfach dabei belassen. Dann werden schon mini Änderungen abgeändert.

AU?ERDEM: Du brauchst ein konsistentes Timingkonzept, damit du deterministisch auf deinem Client sinnvoll "vor"-rechnen kannst.

Ich beschöftige mich mit Gameserverprogrammierung schon ne gaaaanze Weile und ich könnte dir vieeel Soruce zeigen, aber ob das was bringt, vorallem weil jeder sein Problem ja minimal anders angeht

Viele Grüße,

Chris

 

[Teppich]

Danke schonmal für deinen Beitrag, Chris.

Momentan benutze ich noch TCP. Ich werde aber in nächster Zeit nochmal alles auf UDP umprogrammieren.
Ich habe mich vor diesem Projekt noch kaum mit Netzwerkprogrammierung beschäftigt gehabt und habe deshalb einfach mit normalen Sockets und Streams gearbeitet...
Wie genau ich es dann umsetze, dass wichtige Pakete immer ankommen, muss ich mir noch überlegen.

Im Moment sende ich etwa 20 Positionspakete pro Sekunde an die Spieler. Ich habe schon darüber nachgedacht das ein wenig zu reduzieren, da es bei einem MMORPG mit vielen Spielern den Server überlasten könnte?
Ich könnte eventuell auch je nach Auslastung die Anzahl der Pakete pro Sekunde anpassen.

Zum Punkt Timingkonzept:
Der Server berechnet alle 15 ms die Position der Spieler.
(Bewegung * (15 / 1000))
Der Client berechnet je nach FPS seine eigene Bewegung indem er die Zeit zwischen Ticks nimmt und diese zur Berechnung der Position nimmt.
(Bewegung * (Zeit zwischen Ticks / 1000))

Das dürfte soweit funktionieren, oder?


Wie berechne ich am besten wie weit der Client von der tatsächlichen Position abweicht, während er in Bewegung ist und die Zeit des Positionspakets und der Zeit der naheliegendsten Position nicht exakt übereinstimmen (Im Moment 0-15 ms Differenz)?

Oliver

 

[Kr0e]

Also ich muss zu aller erst sagen, dass das ganze bei MMORGs nicht ganz so wichtig ist, wie bei Egoshootern.

Außerdem zum Thema "Wichtige Packete": Wieso nicht beides nehmen ? So machen es es die meisten Spiele. TCP für wirklich wichtige Nachrichten und UDP für die RAW Bewegungsdaten. So nutzt du von beidem das Beste und musst nicht TCP neuerfinden mit UDP.

Dein Timingkonzept ist doch ansich shcon ganz verlässlich. Ich würde die Diff. einfach so berechnen:
Aufgrund der Daten weißt du ja "wo er sein sollte" und die momentane Position ziehst du davon einfach ab und vergleichst den Wert mit einem Grenzwert.

Du kannst auch noch so Tricks benutzen wie z.b. dass der Player "langsam" zu gewünschten Position gepushed wird wie einer art Kraft die auf ihn wirkt, das wirkt schon um einiges flüssiger als ein knallhartes setzen der Position.

Wie gesagt, bei MMORGs ist das alles nicht so ganz krass wie bei Egoshootern. Bei krass vielen Usern darf es da ruhig mal laggen.

Alles in allem wirst du wohl viel testen müssen um ersten Erfharung in diesem Beriech zu sammlen um selbst entscheiden zu können welche Technik für dein Vorhaben passt. UDP ist generell zu bevorzugen wenn es um Daten geht, die ruhig mal inkonsistent sein können. TCP wenn es um tot-ernste Daten geht . TCP kannst du auch ruhig für "halbwichtige" Daten verwenden. Entscheident ist, dass die GESAMTE Bandbreite nicht durch TCP's Acks geblockt wird. Also Sachen wie Runden-Ende, Tod von Spielern, vlt. sogar der Chat kann alles über TCP laufen. Aber die Bewegungsdaten über UDP unbedingt!

ACHJA!! Lass dem Server etwas nmehr Luft! Alle 15 ms ist zu viel, alle 40 ms reicht ach ncoht, solle ndie Clienten halt interpolieren, das merkt man optisch nicht und es entlastet den Server massivst!

Gruß,

Chris

 

[Teppich]

ACHJA!! Lass dem Server etwas nmehr Luft! Alle 15 ms ist zu viel, alle 40 ms reicht ach ncoht, solle ndie Clienten halt interpolieren, das merkt man optisch nicht und es entlastet den Server massivst!

Ich schicke 20 Pakete pro Sekunde. Das ist 1 Paket alle 50 ms. Nur die Berechnungen für die Bewegung der Spieler wird alle 15 ms berechnet.

Außerdem zum Thema "Wichtige Packete": Wieso nicht beides nehmen ?

Ich habe gelesen, dass das gleichzeitige Benutzen von TCP und UDP nicht empfohlen wird und man einfach die nötigen Teile aus TCP selber in sein UDP Protokoll implementieren soll:

The temptation then is to use UDP for player input and state, and TCP for the reliable ordered data. If you’re sharp you’ve probably even worked out that you may have multiple “streams” of reliable ordered commands, maybe one about level loading, and another about AI. Perhaps you think to yourself, “Well, I’d really not want AI commands to stall out if a packet is lost containing a level loading command – they are completely unrelated!”. You are right, so you may be tempted to create one TCP socket for each stream of commands.

On the surface, this seems like a great idea. The problem is that since TCP and UDP are both built on top of IP, the underlying packets sent by each protocol will affect each other. Exactly how they affect each other is quite complicated and relates to how TCP performs reliability and flow control, but fundamentally you should remember that TCP tends to induce packet loss in UDP packets. For more information, read this paper on the subject.

Quelle: UDP vs. TCP

Oliver

 

[Kr0e]

Machen aber die meisten Spiele ala CSS und Konsorten so... Also sofern ich mich jetzt nicht totoal täusche... Ich denke mal, dass wenn du ne Datei überträgt mit 100% Auslastung über TCP, dann werde nvermutlcih UDP Packete gedroppt TEILWEISE, sprich es kommt dann nicht mehr nichts an, keine Sorge..

TCP nachzubauen und das auch noch performant erfordert tiefgehendes Wissen über Netzwerktechnik und heute noch wird geforscht an der Handhabung des Flowcontrol, um den immer besser zu machen. TCP nachzubauen mit UDP halte ich für Unfug und gehört verboten. Es gibt eben verschiedene Protokolle mit verschiedenen Zielen, also sollte man jedes nutzen je nach Anforderung.

DAvon abgesehen ist das Verhalten, dass der Artikel beschreibt MASSIVST Hardware und Software-abhängig.

UDP PAckete werden halt bei ÜBERLAST ganz gerne mal gedroppt, aber das ist auch nur vereinzelt und genau das stört den Spieler ja nicht, da ja 33ms später sowieso das nächste ankommt...

AUßERDEM: Du kannst doch auch Skype benutzt und nebenbei zocken... Skype ist UDP und das SPiel ein Mix aus Beidem. Da beeinflusst sich nichts und selbst wenn, dann nur minimal. Es kommt halt auf die benutze Bandbreite an, wenn die kritisch wird, nagut dann gibts natürlüich Probleme, aber das wäre mit TCP nicht anders..

Lass doch also nicht von solchen theoretisch-orientierten Artikeln beängstigen, die sind praktisch meist nicht relevant.

 

[Teppich]

In Ordnung, danke. Dann werde ich erstmal versuchen beides zu benutzen um meine eigenen Erfahrungen damit zu sammeln.

Ich benutze zurzeit 2 verschachtelte ConcurrentHashMaps um die Spieler zu speichern:
private static ConcurrentHashMap<Integer, ConcurrentHashMap<Integer, Client>> clients;
Somit sind die Spieler per Map (Id) aufgeteilt und jeder Spieler hat eine eigene Id.
Ich bin mir jedoch nicht sicher ob es hier eventuell eine bessere lösung gäbe, da ich später auch gerne mal mehr Spieler drauf hätte.

Meine Anforderungen: Ich muss oft darüber iterieren und regelmäßig Spieler hinzufügen oder löschen. Wäre da eine ArrayList vielleicht angebrachter, da die iterationszeiten besser sind?
Wenn es jedoch mal viele Spieler werden, muss jedes mal ein riesiges Array kopiert werden um den Spieler zur ArrayList hinzuzufügen?

Oliver

 

[Empire Phoenix]

Arraylist , Hashmap ect einfach mit der erwateten maximalgröße erstellen, dann müssen die nciht im normalbetreib wachsen. (wobei solange du unter ein paar hunder clients bist das ganze harmlos ist.)

Zu tcp + udp
Natürlich sollte man auf dem client eine erkennung haben wenn extrem viele udp packete voerloren gehen, so das der dass dann an den server melden kann(per tcp). Fals möglich kann der SErver dann versuchen den traffik zu reduzieren. zb nur noch für den betroffenen client all 66ms ein update schicken. Wenn der tcp datenstrom alleine schon die gesamte bandbreite frisst, und du wirklich nur wichtige sachen per tcp überträgst, ist der verlust der udp daten eh egal. Da der client schlicht ein zu langsamen internetanschluss besitzt. (Was sollst du in tcp reduzieren,wenn nur wichtige sgesendet wird? Hier ist es ja gerade wünschenswert das eher udp gedroppt wird als die wichtigen nachrichten, und wenn irgetwann gar kein udp mehr ankommt ist es eh vorbei.)

 

[Kr0e]

Sehe ich genauso wie Empire Phoenix!

 

[Teppich]

Das war nicht die Antwort auf meine Frage aber trotzdem danke. Nun sitze ich aber vor einem anderen Problem. Da ich jetzt TCP und UDP verwenden will muss ich ein Socket und ein DatagramSocket erstellen und bei beiden Pakete empfangen und senden. Momentan verwende ich 2 Threads, einen zum senden und einen zum empfangen. Wenn ich jetzt aber zusätzlich noch UDP verwende bräuchte ich nochmal zusätzliche Threads?! Ich möchte aber nicht zu viele Threads pro Client erstellen...

So löse ich das momentan (TCP):
1. Thread (Senden)
LinkedBlockingQueue welche mit Paketen gefüllt wird, die vom Thread gesendet werden um den Server nicht zu blocken
2. Thread (Empfangen)
Auf Pakete warten und diese in eine synchronized ArrayList schreiben, welche der Server in seinem Loop verarbeitet.

Wie implementier ich denn nun am besten UDP ohne zusätzliche Threads zu benötigen?

Oliver

 

[Empire Phoenix]

Ein thread zum udp empfangen, ein socket reicht für alle.
Dann selector angucken, ist zwar etwas unschön zu verwenden da recht lowlevel, aber dafür reicht ! thread zum senden und empfangen für unendlich viele clients aus. -> Socketchannel googlen

für udp zum empfangen brachste dann natürlich ncoh einen Thread, aber!!! normalerweise ist der wichtige Traffic ja server to client. Zumindestens benutzte ich udp ur vom server zum client hin, und der client sendet nur tcp zurück(mir ist klar das dadurch theoretische verzögerungen auftreten können, aber praktisch merkt man davon nichts!).

 

[Teppich]

Ein thread zum udp empfangen, ein socket reicht für alle.
Dann selector angucken, ist zwar etwas unschön zu verwenden da recht lowlevel, aber dafür reicht ! thread zum senden und empfangen für unendlich viele clients aus. -> Socketchannel googlen

für udp zum empfangen brachste dann natürlich ncoh einen Thread, aber!!! normalerweise ist der wichtige Traffic ja server to client. Zumindestens benutzte ich udp ur vom server zum client hin, und der client sendet nur tcp zurück(mir ist klar das dadurch theoretische verzögerungen auftreten können, aber praktisch merkt man davon nichts!).

Nach etwa 10 mal lesen hab ich bestimmt die häfte der Semantik deines Beitrags erfasst.

Das hast du geschrieben:
- "Ein thread zum udp empfangen, ein socket reicht für alle."
- "für udp zum empfangen brachste dann natürlich ncoh einen Thread"

Was genau hast du damit gemeint?! Sollte im zweiten Satz TCP statt UDP stehen?

Dann dies:
- "normalerweise ist der wichtige Traffic ja server to client."
- "Zumindestens benutzte ich udp ur vom server zum client hin, und der client sendet nur tcp zurück"

Das ist für mich ein widerspruch, da TCP die wichtigen Daten übertragen sollte...


Oliver