Asteroids - EIST Projekt
Ergebnisse
- Asteroids mit Arena Integration und Echtzeit Netzwerk
Unterstützung
(Source Code bei mir nur auf Anfrage per Email und nach Absprache mit meinen Teammitgliedern erhältlich)
Team: Philip Lorenz, Philip Daubmeier, Ferdinand Mayet, Franziskus Karsunke (damals alle 2. Semester)
Realisierung
Unsere Implementierung basiert auf dem UDP Netzwerk Protokoll. Zuerst haben wir uns Gedanken über die Kommunikation zwischen den Clients gemacht. Da uns Echtzeit Netzwerk Spiele zu implementieren neu war mussten wir erst einmal im Internet Ideen sammeln.
Die Quake Engine basiert darauf, dass der Server die virtuelle Welt abbildet, Bewegungsdaten von den Clients empfängt, berechnet und den berechneten Unterschied (Delta zum letzten Empfangenen Status des Spielers) zurückschickt. Die Darstellung der Welt und seinem jetzt aktualisiertem Zustand erfolgt dann wieder auf der CPU/Grafikkarte des Clients.
Diese Methode hat den Vorteil dass der Server bestimmte Arten von Betrug unterbinden kann: Spieler dürfen sich in einer bestimmten Zeitspanne nicht weiter bewegt haben als es die Geschwindigkeit der Figur zulässt (Speedhack). Weiterhin kann der Server entscheiden welche Daten er an den Client sendet und welche nicht. So muss er beispielsweise einen hinter der Wand befindlichen und für Client X nicht sichtbaren gegnerischen Spieler nicht an Client X senden. Dadurch bleibt der Einsatz von Wallhacks erfolglos.
Der Server besitzt also eine überwachende Rolle und garantiert es ein für jeden Spieler faires Spiel anzubieten. Jedoch erfordert diese Methode einen Server auf dem das Spiel ebenfalls komplett läuft und auf dem rechenintensive Berechnungen durchgeführt werden müssen. Als weiterer Nachteil für die Implementierung ist zu nennen dass bei dieser Methode die zeitliche Synchronisierung auf dem Server stattfindet und Spieler mit einer schlechten Verbindung/langen Latenzzeiten nicht im selben Umfang reagieren können wie Spieler mit kurz verzögernden Verbindungen. Besonders bemerkbar macht sich dieser Umstand bei Spielen bei denen Reaktionen im Millisekunden Bereich gefragt sind (Was durchaus bei vielen Spielen die auf der Quake Engine basieren der Fall ist).
Auf einen für unser Projekt weitaus brauchbareren Ansatz stießen wir bei Ensemble Studios, dem Hersteller von Age of Empires. Dort übernimmt der Server nur eine verteilende Rolle, das Spiel läuft einfach ausgedrückt Peer to Peer.
Diese Idee haben wir für unsere Implementierung verwendet. Zur Umsetzung dieser Strategie sind wir wie folgt vorgegangen: Jeder Client besitzt eine Network Controller Klasse die die Kommunikation mit dem Server übernimmt. Der Server wiederum leitet alle eingehenden Pakete zu allen übrigen Clients weiter.
Bei einem Netzwerkspiel im lokalen Netzwerk leitet üblicherweise ein Client das Spiel ein, die anderen Clients finden diesen dann über einen Netzwerk Broadcast im eigenen Subnet und treten dort bei. Bei einem Internet Spiel werden alle Clients über dedizierte Server miteinander verbunden. Dies fällt bei unserer Implementation weg, da sich die Spieler über das Arena System anmelden und über dieses die IP Adresse des Servers beziehen.
Der Ablauf eines Spiels vom Einleiten bis zum Ende des Spiels ist in folgendem Sequenz Diagramm dargestellt:
Die verschiedenen Paketklassen erben alle von einer Überklasse die die Grundlegenden Funktionen wie verpacken und dekodieren/parsen implementiert. Jeder Spieler meldet sich beim Server mit einem Hello Paket an und bekommt als Antwort ein Welcome Paket zurück. Somit weiß der Server welche Spieler teilnehmen. Wenn die gewünschte Anzahl an Spielern beigetreten ist generiert der Server ein Initialisation Paket welches die Startpositionen der Spieler und der Asteroiden enthält, um einen synchronen Start des Spiels zu gewährleisten. Danach findet über die Update Pakete das Spiel statt bis alle Spieler tot oder alle Asteroiden abgeschossen wurden. Diese Abbruchbedingung prüfen die einzelnen Clients und senden in diesem Fall ein GameFinished Paket an den Server, der die erzielten Punkte prüft, aufbereitet und den Endstand des Spiels an die Clients sendet.
In diesem Sequenz Diagramm ist der Ablauf innerhalb eines Frames des Spieles zwischen zwei Spielern und dem Server dargestellt. Jeder Client wartet auf Tasteneingaben (Beschleunigen, Bremsen, Links, Rechts, Schießen), und speichert diese bis zum Ende des Frames. Dies ist wichtig für die Synchronität: asynchrone Eingaben werden erst berechnet wenn der Frame zu Ende ist. Diese Informationen über den neuen Standort des Schuttles oder abgefeuerter Schüsse wird nun an den Server geschickt der diese an die anderen Clients verteilt. Wenn nun jeder Client die Informationen der anderen Spieler empfangen hat kann der Frame gerendert und am Bildschirm ausgegeben werden.
Unsere Implementierung ist Framesynchron, das heißt es werden die Frames mitgezählt und ein Frame erst berechnet wenn die Information von alle anderen Clients empfangen wurden. Der Vorteil ist totale zeitliche und lokale Synchronität, jedoch im schlechtesten Fall auf Kosten der Performance: das Spiel ist höchstens so schnell wie der langsamste Rechner im Spiel plus Netzwerk Verzögerung. Im Besten Fall und auch in den von uns getesteten durchschnittlichen Fällen ist jedoch die Verzögerung im Netzwerk unfühlbar klein und das Spiel so schnell wie der Zeitgeber (Tick) im Spiel. Dieser Zeitgeber ist notwendig da die Geschwindigkeitsberechnung auf einer Tick-Zeiteinheit basiert und nicht auf realer Zeit. Da das Spiel nicht sehr rechenintensiv ist wäre das Spiel ohne diese künstliche Bremse auf einem schnellen Rechner innerhalb einer Sekunde zu Ende, da sich alle Asteroiden in Zeitraffer bewegen und alle Spieler zerstören würden.
Dieses Diagramm illustriert die Abläufe im Spiel in Abhängigkeit der Zeit. Man sieht hier wie unterschiedliche Laufzeiten (durch unterschiedliche Leitungsdämpfungen und unterschiedlich viele Hops beim Routing) der Pakete im Netzwerk, besonders im Internet, berücksichtigt werden müssen um nicht asynchron zu laufen.
Wir stellten jedoch fest das spätere Pakete teilweise vor früheren Paketen bei den Clients eintrafen und dadurch einen Freeze im Spiel auslösten. Wir stellten nämlich die Bedingung, dass ein Client so lange mit dem Rendern eines Frames zu warten hat bis alle Informationen über diesen Frame von den anderen Clients eintreffen. Wenn aber nun immer nur das erste Paket aus der Netzwerk Queue geladen wird kann dies Probleme wie das oben genannte geben. Wir mussten also eine Sortierung der eingehenden Pakete mit Hilfe einer Hashlist implementieren (eine Priority Queue wäre unter Umständen effizienter gewesen, jedoch rechtfertigt es den Aufwand nicht).
Damit war es aber nicht getan: Tests im Internet und auch im lokalen Netzwerk mit WLAN haben gezeigt dass teilweise erhebliche Paketverluste eintreten, bzw. dass Pakete unbrauchbar werden, da sich Bits verändert haben und die Prüfsumme nicht mehr passt, und deswegen verworfen werden mussten.
Aus diesem Grund führten wir ein Acknowledge System ein das in folgendem Diagramm dargestellt ist:
Jeder Sender eines Pakets (dies kann sowohl ein Client oder der Server sein) speichert das Paket so lange bis er vom Empfänger ein Acknowledge Paket mit der korrespondierenden Paket ID zurück bekommt. Kommt dieses in einer festgelegten Zeitspanne nicht zurück, so muss der Sender davon ausgehen dass sein Paket verloren ging, und sendet es erneut. Nun wartet er erneut auf das Acknowledge Paket, und bekommt es üblicherweise spätestens beim zweiten Versuch auch. Er weiß nun dass das Paket angekommen ist und löscht es aus seiner Liste der zu sendenden Pakete. Die Anzahl der Versuche ist auf eine festgelegte Zahl begrenzt. Wird diese überschritten muss der Sender davon ausgehen dass die Verbindung zum Empfänger abgerissen ist, der Spieler wird dann vom Server aus dem Spiel entfernt.
Was passiert wenn ein Paket seinen Empfänger nicht erreicht ist hier dargestellt:
Ähnliches passiert wenn das Acknowledge Paket verloren geht:
Hier geht der Sender (diesmal irrtümlich) davon aus dass sein Paket nicht angekommen ist und sendet es erneut. Der Empfänger weiß allerdings anhand der Paket ID dass er dieses Paket bereits empfangen hat und geht davon aus dass nun das Acknowledge Paket verloren gegangen sein muss und sendet dieses erneut und verwirft das doppelte Paket.
Dieses System hält jedem instabilen Netzwerk stand und funktioniert sogar bei zeitweise auftretenden längeren Lags (Verbindungsstörungen). In solch einem Fall werden vom Sender mehrere Pakete abgeschickt bevor sie beim Empfänger ankommen. Dieser schickt mehrere Acknowledge Pakete und verwirft alle doppelten Pakete. Der Sender wiederum empfängt das erste Acknowledge Paket, weiß damit dass es angekommen ist und verwirft alle kommenden Acknowledge Pakete die zu diesem ursprünglichen Paket gehören. So treten keine Informationsverluste oder mehrfach vorkommende Informationen auf.
(Alle Illustrationen und Diagramme © 2007 Philip Daubmeier, erstellt mit Microsoft® Visio® 2007)