# UDP Pakete prüfen, sortieren



## Dit_ (5. Jun 2011)

Hallo,

ich empfange Pakete von einem Server auf diese Weise:


```
//...
StringBuilder sb = new StringBuilder("");
        
        byte[] in = convertToBytes(cmd);
        
        /*
         * Erstellt ReplyPacket
         */
        DatagramPacket reply = createReplyPacket(COMMAND_BUFFER_SIZE);
        
        try {
            // SENDEN
            socket.send(new DatagramPacket(in, in.length, _server.getSocketAddress()));
            
            // EMPFANGEN
            while (true) {
                try {
                    socket.receive(reply);
                } catch (IOException e) {
                    break;
                }
                sb.append(encodeReply(reply));
            }
            
        } catch (IOException e) {
            throw new FailedConnectionException(_server.toString(), e.getMessage());
        } finally {
            socket.close();
        }
/...
```
Leider kommt es manchmal vor, dass die Pakete in der falschen Reihnfolge empfangen werden, so dass ich (BEISPIEL) statt A B C D E F G H, A B D C E F G H empfange...
gibt es eine möglichkeit zu prüfen ob ein Paket fehlerhaft ist oder nicht UND was wichtiger ist, wie kann ich die richtige Reihenfolge wiederherstellen?


Danke schon mal!


----------



## Empire Phoenix (5. Jun 2011)

Also wenn du beides willst kannst auch gleich tcp nehmen.

Udp hat ne fehlerüberprüfung drinnen, packte wo die chksum falsch ist werden einfach gedroppt.


----------



## Dit_ (5. Jun 2011)

ok schade, leider muss ich UDP verwenden TCP kommt nicht in Frage :/

kann ich wenigstens merken dass ein packet verworfen wurde?

danke


----------



## Tobias (5. Jun 2011)

wikipedia.org hat gesagt.:
			
		

> UDP stellt einen verbindungslosen, nicht-zuverlässigen Übertragungsdienst bereit. Das bedeutet, es gibt keine Garantie, dass ein einmal gesendetes Paket auch ankommt, dass Pakete in der gleichen Reihenfolge ankommen, in der sie gesendet wurden, oder dass ein Paket nur einmal beim Empfänger eintrifft. Eine Anwendung, die UDP nutzt, muss daher gegenüber verlorengegangenen und unsortierten Paketen unempfindlich sein oder selbst entsprechende Korrekturmaßnahmen beinhalten.



Soll heißen: Wer UDP nutzt, ist selbst dafür verantwortlich sicherzustellen, dass der Empfänger verlorene oder vertauschte Pakete erkennt und ggf korrigiert.


----------



## Dit_ (5. Jun 2011)

Tobias hat gesagt.:


> Soll heißen: Wer UDP nutzt, ist selbst dafür verantwortlich sicherzustellen, dass der Empfänger verlorene oder vertauschte Pakete erkennt und ggf korrigiert.





Das ist der Grung warum ich den Thread aufgemacht habe, um zu wissen wie man das am besten macht.


----------



## tagedieb (5. Jun 2011)

Dafuer gibt es TCP! :autsch:



			
				Dit_ hat gesagt.:
			
		

> ok schade, leider muss ich UDP verwenden TCP kommt nicht in Frage :/



Kannst du da ein bischen genauer sein? Wieso willst/kannst du TCP nicht verwenden.
Da du ja genau diese Loesung suchst, aber sie nicht verwenden willst waere diese Information sicher hilfreich.

Du wirst sicher einsehen, dass wir uns fragen wieso du lieber dein eigenes Fehlerprotokol implementieren wills anstatt eine bestehende Loesung zu verwenden.


----------



## Empire Phoenix (5. Jun 2011)

Also wennd er SErver vorgegben ist und keinerlei system zur fhlerkorrektur , nummerierung der apckete hast findeste das nie raus.
Der Server muss midnestes ne forlaufende nummerrierung amchen, so das du feststellst wenn einzelne nummern fehlen, und dann ein system definiert haben wie du diese neuanfragen kannst. 

Wenner das net tut haste schlichtweg pech.


----------



## Massenhaft (6. Jun 2011)

Hi,
ich hab bei meinem Game Sequenzenummern verwendet. Dadurch konnte ich einen "ack"-Algo verwenden.
Die Sortierung habe ich erstmal über eine einfache TreeMap anhand der Sequenznummer gelöst.
Quellcode gibts hier:
slick-netty-network-game-example - An UDP 2d netwok game example - Google Project Hosting

Das ganze ist ein Protokoll-Mix aus Quake und Valve (HL2).

Gruß,
Andreas


----------



## Kr0e (6. Jun 2011)

EDIT: Total verlesen  Sorry...


----------



## ice-breaker (6. Jun 2011)

Sliding Window Protocol


----------



## schalentier (6. Jun 2011)

Massenhaft hat gesagt.:


> ich hab bei meinem Game Sequenzenummern verwendet. Dadurch konnte ich einen "ack"-Algo verwenden.



Hast du das mal verglichen mit einer Loesung mit TCP? Das waere mal interessant, denn ich koennte ja einfach mal die Theorie aufstellen, dass das Nachprogrammieren von TCP in Java deutlich langsamer ist, als TCP direkt zu verwenden. 



Massenhaft hat gesagt.:


> Das ganze ist ein Protokoll-Mix aus Quake und Valve (HL2).



Meines Wissens nach, verwendet Quake weder Sequenzen noch ACK Pakete, sondern jagt einfach so schnell es geht Welt Update Pakete an alle Clients raus.


----------



## Kr0e (6. Jun 2011)

Schalentier hat Recht... TPC nachzubasteln ist sinnfrei. Bei Games werden einfach Snapshots der Welt verschickt mit aufeinanderfolgenden Nummern. Hinterher werden dann nur Pakete verarbeitet, die größere Sequenznummern haben, als das letzte verarbeitete Paket. Dadurch bist du stehts up2date. Wichtige Dinge werden über einen 2ten Kanal versendet undzwar mit TCP! Sprich wenn neue Leute reinkommen zB. oder dein Character stirbt usw...

Und die Source-Network Engine ist nochmal ne ganz andere GEschichte... Da werden neben Interpolation noch ganz andere Tricks verwendet, um das Spielgefühl möglichst realistisch zu gestalten. Lustig wirds dann mit Usern, die unterschiedliche Netzwerkanbindungen haben....


----------



## Massenhaft (6. Jun 2011)

schalentier hat gesagt.:


> Hast du das mal verglichen mit einer Loesung mit TCP? Das waere mal interessant, denn ich koennte ja einfach mal die Theorie aufstellen, dass das Nachprogrammieren von TCP in Java deutlich langsamer ist, als TCP direkt zu verwenden.


Hab ich nicht. Allerdings funktioniert es auch etwas anders. Ich habe UDP-Nachrichten die "wichtig" sind. Diese
werden solange gesendet (bei mir immer wieder ins Delta gepackt), bis vom Client ein "ack" kommt (Bruteforce <->Quake like). Positionsdaten und der
gleichen werden einfach immer in einem "Delta - (eigentlich im Moment immer nur die letzte Position)" gesendet. Sollten diese Daten verloren gehen, so ist es nicht
schlimm, da auf dem Client interpoliert/extrapoliert wird (Valve). Der Client "spielt" grundsätzlich 100ms + ping/2 in der
Vergangenheit. Die Spieler Kommandos (z.B. Pfeiltasten) werden immer als Reliable mit Timestamp gesendet und
auf dem Server in der Vergangenheit ausgeführt, damit die Kollisionserkennung funktioniert.




schalentier hat gesagt.:


> Meines Wissens nach, verwendet Quake weder Sequenzen noch ACK Pakete, sondern jagt einfach so schnell es geht Welt Update Pakete an alle Clients raus.


Also es gibt schon Reliable-Pakete die mit ACK-Pakete bestätigt werden. Die Sequenze-Daten finde ich jetzt aber auch gerade nicht mehr .
Gruß,
Andreas


----------



## Empire Phoenix (6. Jun 2011)

Das mit der timestamp geschichte ist aber auch nur begrenzt eine lösung (je anhdem was man bracht) speziell bei physic engines ist es nromalerweise fast unmöglich diese einige sekunden zurückzusetzen. Zumal konflikte auftreten können (Zwei user senden wiedersprüchliches, was jenachdem was zuerst ausgeführt wird was anders macht, da ist dann der user mit schlechterm i net im vorteil)


----------



## Massenhaft (6. Jun 2011)

Empire Phoenix hat gesagt.:


> Das mit der timestamp geschichte ist aber auch nur begrenzt eine lösung (je anhdem was man bracht) speziell bei physic engines ist es nromalerweise fast unmöglich diese einige sekunden zurückzusetzen. Zumal konflikte auftreten können (Zwei user senden wiedersprüchliches, was jenachdem was zuerst ausgeführt wird was anders macht, da ist dann der user mit schlechterm i net im vorteil)


Ja, physicengines... das wird sehr schwierig. Ich habe in meinem Spiel keine und werde so schnell auch keine benötigen. Daher ist der Ansatz für mich schon mal Ok. Wenn man eine Physicengine nur für "Effekte" einsetzt,
dann sollte es auch noch gehen . Im Java-Bereich sehe ich allerdings auch nicht viele andere Netzwerk-Protokoll-Varianten, da ein "Gameloop" mit slick schon fast 20ms benötigt und man nicht wie bei der Quake-Engine bei 2 bis 7ms
liegt. Zudem ist der Clocksync bzw. eine Clock an sich etwas frickelig..


----------



## Kr0e (6. Jun 2011)

Massenhaft hat gesagt.:


> Im Java-Bereich sehe ich allerdings auch nicht viele andere Netzwerk-Protokoll-Varianten, da ein "Gameloop" mit slick schon fast 20ms benötigt und man nicht wie bei der Quake-Engine bei 2 bis 7ms
> liegt. Zudem ist der Clocksync bzw. eine Clock an sich etwas frickelig..



Das liegt aber an deiner Programmierung und nicht an Slick.... Für maximale Performance brauchst du auch Sachen wie Vertex Buffer Objects oder Displaylisten. Das Slick Image ist auch nur begrenzt leistungsfähig, denn dort wird jedes Mal bind() aufgerufen, bevor das Image gezeichnet wird. Besser wäre eine einzige Textur und jeweils andere Texturkoordinaten...

Ich programmiere zur Zeit auch ein Spiel mit Slick (Isometrisch mit verdammt vielen Images) und habe keine Geschwindigkeitsprobleme...


Und bzg Physics-Engines:

CSS/HL2 Deathmatch benutzen abgespeckte Physik im Onlinemodus undzwar genau aus diesem Grund. Wenn man alle 33 ms die Position und Ausrichtung von jedem Objekt übermittelt, gerät man shcon bei 20 - 50 Objekten in einen Engpass. Ich rede garnicht mal von der programmiertechnischen Umsetzung, sondern schlicht von der Bandbreite.

Wenn man viele physikalische Objekte übers Netzwerk managen will, braucht man eine deterministische Engine wie z.B. Bullet. Dann können die Clients den ganzen Physikkram selbst berechnen. Vom Server werden dann nur die Spielerpositionen verschickt...


----------



## Empire Phoenix (6. Jun 2011)

Also geht, benutze jbullet und kann problemlos 500 objecte bei 50ticktime übertragen. (Der trick ist halt nicht den ganzen gamestate zu überragen sondern diffs, und clientseitig hart zu interpolieren)

Btw kann cih mir schlecht vorstellen das slick so langsam ist, da ich mit jme3 deutlich schneller sein kann. (bringt nur wenig da dann die clients dos'd werden)


----------



## Kr0e (6. Jun 2011)

Was meinst du mit diffs ? Vlt irre ich mich ja, aber es müssen doch immer Position und Rotation eines Objektes übertragen werden. Sprich min. 6 floats pro Objekt, was 24 byte pro Objekt bedeutet (3D-Bereich). Auch wenn mir klar ist, dass noch weitere Daten übertragen werden müssten...


Also gut: 500 Objekte * 24 Byte = 12kb. Wenn du schreibst ticktime 50, meinst du dann 50x pro Sekunde, oder 20x pro Sekunde ?
Ich geh mal von 20x aus... Also 12 * 20 = 240kb. Nun reden wir mal von 4 Clienten... Das ergibt also gut und gerne 1mb pro Sekunde pro Client. Also muss der Server einen Upstream von min 4mb/s haben und die Clients brauchen ne DSL 16000 Leitung, damit das ganze spielbar ist... Wenn ich mich jetzt nicht total verrechnet habe, wäre das also schon ein unmögliches Szenario. Abgesehen davon, müssen ja noch weitere Daten übertragen werden, als die rohen Daten.


----------



## Empire Phoenix (6. Jun 2011)

dsl 16k hat ca. 2mbyte/s oder halt 16mbit, wir brachen aber nur 1 pro client, und der server ist eh nen root.

Dazu optimierungne objecte wenn sie zur ruhe kommen werden nicht mehr konstant übertragen sondern nur ein einziges mal die entgültige position. Solande sich die objecte nicht bewegen aknn ich also problemlos mehrere tausende haben(da wird dann eher der objectcount füre grafikkarte nen problem).

Dazu die berechnung von sichtbarkeiten, das nru sichbare objecte übertragen werden.(Sag nur als beispiel BSP wie die Source engine)


----------



## Massenhaft (7. Jun 2011)

Deterministische ist das Schlüsselwort .
In meinem nächsten Test möchte ich ganz gerne so eine Art Commander-KI haben die eine Reihe
von Einheiten steuert. Das heißt, ich sage der Commander-KI: "Greife ziel A an" und auf allen Clients
müssen sich z.B. 10 Einheiten identisch bewegen. Das hätte den Vorteil, dass ich nur sehr "hohe abstrakte"
Daten durchs Netz jagen muss. Ich weiß nur nicht ob das möglich ist, da auf allen Client sich die
Kommander-KI gleich verhalten muss und überall immer der identische Worldstate für entsprechende Entscheidungen
vorhanden sein muss... 

@Empire Phoenix
Sichbarkeiten, Komprimierung und richtige Deltas (z.B. hat sich nicht bewegt) spare ich mir im Moment noch.
Ich schätze, dass lässt sich später noch einbauen.

@Kr0e
Mit slick kann ich schon einiges malen . Die Entity-Engine (Artemis) schafft auf meinem Rechner ca. 6000 Sprites
(alte Geforce u. 2.6Ghz). Ich hoffe, dass reicht für meine zwecke .


----------



## Dit_ (7. Jun 2011)

tagedieb hat gesagt.:


> Dafuer gibt es TCP! :autsch:
> 
> 
> 
> ...



weil die Kommunikation mit dem Server nur UDP möglich ist. Es geht um ein Q3-Protokoll.

Normalerweise kommen die Pakete in richtiger Reihenfolge an. Ohne FireWall, Proxy, usw gibt es pro Stunde 1 bis 2 Fehlerhafte Pakete dabei wird die Iformation alle 2 Sekunden abgefragt. Damit kann man leben  

Sobald die Anwendung aber in einer Umgebung mit Proxy läuft, steigt die Feherquote. Die Pakete sind zwar nicht beschädigt die Reihenfolge stimmt aber nicht... Aber auch hier ist es für den User kaum merkbar... Sonst ist UDP sehr schnell und man muss sich nicht um den Proxyzugang kümmern


----------

