Entwicklung einer performanten Network Engine für

Transcrição

Fachbereich 4: Informatik
Entwicklung einer performanten
Network Engine für zeitkritische
Video- und Computerspiele
Diplomarbeit
zur Erlangung des Grades eines Diplom-Informatikers
im Studiengang Computervisualistik
vorgelegt von
Thomas Schypior
Erstgutachter:
Prof. Dr.-Ing. Stefan Müller
Institut für Computervisualistik, AG Computergraphik
Zweitgutachter:
Dipl.-Inform. Martin Schumann
Institut für Computervisualistik, AG Computergraphik
Koblenz, im September 2012
Erklärung
Ich versichere, dass ich die vorliegende Arbeit selbständig verfasst und keine anderen als die angegebenen Quellen und Hilfsmittel benutzt habe.
Ja
Nein
Mit der Einstellung der Arbeit in die Bibliothek bin ich einverstanden.
Der Veröffentlichung dieser Arbeit im Internet stimme ich zu.
.................................................................................
(Ort, Datum)
(Unterschrift)
Inhaltsverzeichnis
1
2
3
4
Einleitung
1
1.1
Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Aufgabenstellung im Detail . . . . . . . . . . . . . . . . . . .
3
1.2.1
Network Engine . . . . . . . . . . . . . . . . . . . . .
3
1.2.2
Video- und Computerspiele . . . . . . . . . . . . . . .
4
1.2.3
Zeitkritischer Aspekt . . . . . . . . . . . . . . . . . . .
5
1.2.4
Performanz . . . . . . . . . . . . . . . . . . . . . . . .
6
Grundlagen: Rechnernetze und das Internet
7
2.1
Das Internet . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.2
Das LAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.3
Pakettransport . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2.4
Netzwerkprotokolle . . . . . . . . . . . . . . . . . . . . . . .
10
Technische Probleme vernetzten Spielens
17
3.1
Latenz und Latenzschwankungen . . . . . . . . . . . . . . .
17
3.2
Netzwerkarchitekturen . . . . . . . . . . . . . . . . . . . . . .
19
3.2.1
Peer-to-Peer-Modell . . . . . . . . . . . . . . . . . . .
19
3.2.2
Client-Server-Modell . . . . . . . . . . . . . . . . . . .
20
3.3
Unzuverlässigkeit der Datenübertragung . . . . . . . . . . .
22
3.4
Datenübertragungsrate . . . . . . . . . . . . . . . . . . . . . .
22
3.5
Prozessorlast . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
3.6
Cheating . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
Funktionalitätsanforderungen
27
4.1
Analyse typischer Spiele-Genres . . . . . . . . . . . . . . . .
27
4.1.1
First Person Shooter (FPS) . . . . . . . . . . . . . . . .
27
4.1.2
Real Time Strategy (RTS) . . . . . . . . . . . . . . . . .
28
4.1.3
Massively Multiplayer Online (MMO) . . . . . . . . .
30
4.1.4
Rennspiele . . . . . . . . . . . . . . . . . . . . . . . . .
30
Auswertung . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
4.2
5
Konzepte und Ansätze zur Performanzsteigerung
34
5.1
Einbeziehung psychologischer Faktoren . . . . . . . . . . . .
34
5.2
Control Data / Sampling Input . . . . . . . . . . . . . . . . .
38
5.3
Client-side simulation / Aufteilung von Rechenlast . . . . .
39
6
5.4
Absichtliche Eingabelatenz . . . . . . . . . . . . . . . . . . .
40
5.5
Dedizierte (dedicated) Server . . . . . . . . . . . . . . . . . .
42
5.6
Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
5.7
Relevanz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
5.8
Priorisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
Praktische Umsetzung
46
6.1
Programmiersprache und Bibliotheken . . . . . . . . . . . .
46
6.2
Aufbau der Software . . . . . . . . . . . . . . . . . . . . . . .
48
6.2.1
Header-Dateien . . . . . . . . . . . . . . . . . . . . . .
48
6.2.2
C-Strukturen . . . . . . . . . . . . . . . . . . . . . . .
48
6.2.3
C++-Klassen . . . . . . . . . . . . . . . . . . . . . . . .
51
Implementierte Verfahren und Funktionalität . . . . . . . . .
54
6.3.1
Einfache Simulation und Synchronisation . . . . . . .
54
6.3.2
Client-side simulation . . . . . . . . . . . . . . . . . .
55
6.3.3
Verbergung von Latenz und Latenzschwankungen .
56
Demo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
6.3
6.4
7
Fazit
64
7.1
Ergebnisse und Bewertung . . . . . . . . . . . . . . . . . . . .
64
7.2
Ausblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
66
1
Einleitung
1.1
Motivation
„Any sufficiently advanced technology is indistinguishable from magic.“
- A RTHUR C. C LARKE
Vor etwa 15 bis 20 Jahren fand man nur in wenigen Haushalten einen
Computer. Falls doch, dann aber höchstwahrscheinlich keinen, der über
Netzwerkfunktionalität verfügte. Für mich ist diese historische Tatsache
heute vor allem ein Stück Erinnerung: Gegen Ende der 90er Jahre war es
noch etwas besonderes, Zeit im Computerraum unserer Schule verbringen
zu können. Mein Grund dafür war meistens die Shareware-Version1 des
Computerspiels Descent, die ein Lehrer für uns auf der Festplatte eines
jeden Rechners installiert hatte.
Descent kann man sich folgendermaßen vorstellen: Aus dem
Cockpit seines kleinen Ein-MannRaumschiffs blickend, fliegt der
Spieler sein Vehikel durch ein Labyrinth unterirdischer Minentunnel und liefert sich dabei Feuergefechte mit zahlreichen gegnerischen Robotern (vgl. Abbildung 1).
Das Spielziel ist fast immer, erst
Abbildung 1: Szene des Spiels Descent
den Reaktor des Levels zu finden,
ihn zu zerstören und anschließend, vor Ablauf eines Zeitlimits, den Ausgang zu erreichen - zumindest, wenn man alleine spielt. Mich aber hat Descent vor allem gereizt, weil es die Möglichkeit bot, gemeinsam und gleichzeitig an bis zu acht verschiedenen Computern gespielt zu werden. Zu dieser Zeit stellte das Netzwerk unseres Computerraums die einzige verfügbare Infrastruktur dazu bereit.
Das vernetzte Spielen mit mehreren Mitspielern gleichzeitig war außergewöhnlich. Ich war es gewohnt, ein Spiel - wenn überhaupt gemeinsam
1
Bei einer Shareware-Version handelt es sich um Software, die in ihrer Funktionalität
eingeschränkt wurde, dafür aber kostenlos weitergegeben und benutzt werden darf.
1
1.1
Motivation
- höchstens zu zweit spielen zu können und dies lediglich unvernetzt, lokal, am gleichen Bildschirm. Es war also ein Novum, den Monitor ganz
für sich allein zu haben. Dass man außerdem mehr als nur einem Mitspieler begegnen konnte, ließ neue, unbekannte Dynamik und Spielsituationen entstehen. Oft beflügelte das Spielen im Netzwerk meine Phantasie,
was wohl die Zukunft bringen mochte. Diese Euphorie wurde zusätzlich
genährt durch damals aufkommenden Technologien wie hochauflösende,
beschleunigte 3D-Grafik und die rasche Zunahme der Taktfreqzenz neuer
Computerprozessoren. Wie komplex und prächtig mussten wohl die Spielwelten aussehen, in denen man schon in Kürze gemeinsam würde spielen
können?
Auf diese ersten Erfahrungen vom vernetzten Spielen am Computer
komme ich häufig zurück, vermutlich deshalb, weil mich diese Faszination
der ersten Stunde nie verlassen hat. Für mich haben sich mit der Zeit viele
Mysterien rund um Computertechnologie erschlossen, etwa wie ein Computer und seine Software grundsätzlich funktionieren oder Grafik am Bildschirm entsteht. Die technische Umsetzung des vernetzten Spielens und
das dabei notwendige Synchronisieren ganzer Spiele-Logiken hingegen haben ihre mysteriöse Ausstrahlung behalten. Vermutlich hat dies jedoch weniger mit dem bloßen Verständnis der Technik zu tun, die dabei am Werk
ist. Vielmehr könnte es an der Tatsache liegen, dass es immer wieder faszinierend ist, Spielfiguren zu sehen, deren Handlungen, scheinbar gleichzeitig, von Mitspielern andernorts gelenkt werden. Ich erinnere mich, dass
eine Lehrerin regelrecht erschlagen schien, als sie verfolgte, wie ihre im
Computerraum verteilten Schüler Descent spielten. Offenbar war es das
erste Mal, dass sie mit dieser technischen Möglichkeit Kontakt hatte. Damals konnte schon das vernetzte Spielen im selben Raum diese Fazination
schüren. Heutzutage jedoch müssen Mitspieler sich nicht einmal im selben
Gebäude befinden, oder in der gleichen Stadt, oder im gleichen Land, oder
sogar auf dem gleichen Kontinent. Oft scheint es, als wäre ein gemeinsames
gleichzeitiges Spielen global und problemlos möglich.
Aber ist dem tatsächlich so? Kann eine Gleichzeitigkeit bei der Datenübertragung im Netzwerk wirklich erreicht oder zumindest vorgetäuscht
werden? Einerseits ist es die Faszination für vernetztes Spielen, die mich
zu dieser Abschlussarbeit motiviert. Gleichzeitig ist es auch wissenschaft-
2
1.2
Aufgabenstellung im Detail
lich von Interesse, die technischen Probleme und Grenzen bei der Datenübertragung in Computernetzwerken zu untersuchen und Lösungsansätze
zusammenzutragen.
1.2
Im Rahmen dieser Arbeit soll ergründet werden, was für Möglichkeiten es
gibt, die Illusion des zeitgleichen Spielens zu erreichen und welche Probleme dazu gelöst werden müssen. Bereits existierende Lösungen, die teils
speziell für die Bedürfnisse bestimmter Spiele entwickelt wurden, stellen
dabei eine wertvolle Ressource dar, die es zu untersuchen gilt. Was genau
man sich unter dem Thema „Entwicklung einer performanten Network Engine für zeitkritische Video- und Computerspiele“ vorzustellen hat, sei im
Folgenden erklärt.
1.2.1
Network Engine
Als „Engine“ (Englisch für „Antrieb“ oder „Motor“) bezeichnet man in
der Software-Entwicklung üblicherweise eine Menge von Funktionen, die
einem bestimmten Ziel dient. Beispielsweise wird oft von „3D Engine“,
„Render Engine“ oder allgemein „Grafik Engine“ gesprochen, wenn jener
Teil der Software gemeint ist, der für die grafische Darstellung auf dem
Bildschirm verantwortlich zeichnet. Ebenso kann es sich bei einer Engine
beispielsweise auch um eine Physik Engine oder Audio Engine handeln.
Der Zusatz vor dem Wort „Engine“ gibt also an, wofür die Software entwickelt wurde. Im Rahmen dieser Diplomarbeit soll es um die Entwicklung
einer Network Engine gehen. Der Begriff „Network“ umfasst hier allgemein Computernetzwerke bzw. Rechnernetze, also auch lokale Netzwerke,
wie etwa das in der Einleitung erwähnte Netzwerk innerhalb eines Computerraums (vgl. Abschnitt 1.1). Insbesondere ist hier jedoch das Internet
gemeint.
Zunächst soll herausgefunden werden, welche Probleme sich bei der
Datenübertragung in Netzwerken und insbesondere im Internet ergeben.
Zusätzlich sollen die technischen Anforderungen verschiedener Spiele-
3
1.2
Genres untersucht werden. Aus beidem gemeinsam soll sich ableiten lassen, was eine Network Engine leisten sollte und wie die bei der Netzwerkkommunikation auftretenden Probleme gelöst werden können. Zwar handelt es sich hier beim Anwendungsbereich, auf den gezielt wird, um zeitkritische Video- und Computerspiele, aber dennoch ließe sich die zu entwickelnde Network Engine theoretisch für eine Vielzahl vernetzter Simulationen nutzen, die in Echtzeit ablaufen.
1.2.2
Video- und Computerspiele
Zunächst ist es hilfreich, die Begrifflichkeit „Video- und Computerspiele“
zu spezifizieren und zu vereinfachen: Die Begriffe „Videospiel“ und „Computerspiel“ sind, ähnlich wie etwa der „Film“, geprägt von physikalischen
Merkmalen des Mediums. Das soll heißen: Diese Begriffe beschreiben nicht
die möglichen Inhalte, die das Medium umfassen kann, sondern beschränken sich allein auf den technischen Charakter. Auch wecken die Begriffe „Videospiel“ und „Computerspiel“ unterschiedliche Assoziationen: Der
Begriff des Videospiels betont, dass ein Spieler mit der visuellen Komponente des Spiels, also den Bildern eines Ausgabegerätes, aktiv umzugehen
kann. Doch heute wird der Begriff am häufigsten für Spiele verwendet,
wenn sie auf Spielekonsolen ausgeführt werden, also Geräten, die man üblicherweise an Fernseher anschließt.
Der Begriff „Computerspiel“ hingegen wird eher benutzt, wenn ein
Spiel an einem „Personal Computer“, kurz „PC“, gespielt wird. Eine Trennung zwischen Video- und Computerspiel ist jedoch problematisch. Grundsätzlich sind beide Begriffe synonym zu verstehen und werden auch so
verwendet. Ein Videospiel wird immer von einem System ausgeführt, das
intern wie ein Computer arbeitet, ist also auch ein Computerspiel. Aus diesem Grund und zur Vereinfachung der Begrifflichkeiten wird im Folgenden ausschließlich der Begriff „Videospiel“ verwendet. Wann immer ich
von nun an von einem Videospiel spreche, sind damit Computerspiele im
weitesten Sinne gemeint.
4
1.2
1.2.3
Zeitkritischer Aspekt
In diesem Abschnitt soll erläutert werden, was unter der Bezeichnung „zeitkritisch“ zu verstehen ist. Videospiele sind besonders gut geeignet, um
Technologie erlebbar zu machen, um einen Bezug zur Technik herzustellen,
man könnte sagen: Um ein Gefühl zu bekommen dafür, was bloße Zahlen
tatsächlich bedeuten. Im Falle vom netzwerkfähigen Videospielen handelt
es sich bei diesen spürbaren Zahlen besonders um Verzögerungen im Millisekundenbereich, die bei der Datenübertragung in Netzwerken zwischen
Sender und Empfänger auftreten. Diese Verzögerungen werden auch „Latenzen“ genannt. Die Latenz ist eine technische Größe, mit der viele Spieler
vernetzter Videospiele irgendwann in Kontakt kommen. Sie taucht im Spiel
oft unter der Bezeichnung „Ping“ oder „Lag“ auf. Hier kommt die Anforderung der Rechtzeitigkeit zur Aufgabenstellung hinzu. „Zeitkritisch“
heißt, dass es für das Aufrechterhalten der Spielbarkeit und der Immersion,
des Abtauchens in eine Spielwelt, wichtig ist, möglichst verzögerungsfrei
Rückmeldungen vom Spiel zu erhalten. Gerade bei Videospielen ergeben
sich hier durch die Beschaffenheit der Datenübertragung in Netzwerken
und insbesondere im Internet Probleme. Im Feld der Echtzeitsysteme würde man hier von „weichen Echtzeitbedingungen sprechen“. Dies heißt: Es
kann nicht garantiert werden, dass nach einer bestimmten Zeitspanne immer die benötigten Daten vorliegen, es reicht jedoch, wenn das Ziel meistens erreicht werden kann.
Im Idealfall würde man sich eine schnelle, konstante und zuverlässige Datenübertragung wünschen. Im Internet ist dies jedoch nicht der Fall.
Dies führt beim vernetzten Spielen zu Problemen, für die verschiedene
Lösungsansätze existieren. Für die Erforderlichkeit und den Umfang solcher Lösungen ist entscheidend, mit welcher Art von Spiel man es zu tun
hat. Ein Spiel etwa, das abwechselnd gespielt wird, stellt keine besonderen Ansprüche an die Geschwindigkeit der Datenübertragung. Sobald es
jedoch um Gleichzeitigkeit geht, muss eine Lösung gefunden werden, mit
den stets anfallenden Latenzen zwischen allen Mitspielern umzugehen. Lösungsfindungen für eben dieses Problem sollen bei dieser Arbeit im Vordergrund stehen.
5
1.2
1.2.4
Performanz
Mit „Performanz“ (vom Englischen performance, zu Deutsch Leistung) ist in
der Software-Entwicklung die Effizienz einer Applikation gemeint. Üblicherweise bezieht sich dies auf die Schnelligkeit der Programmausführung.
Wenn also beispielsweise ein bestimmter Such-Algorithmus bei gleicher
Zuverlässigkeit deutlich schneller zum selben Ergebnis kommt, wie ein anderes Programm, würde man den schnelleren Algorithmus als performanter bezeichnen. Im Zusammenhang mit einer Network Engine für zeitkritische Videospiele kann man Performanz folgendermaßen verstehen: Hier
geht es darum, trotz aller Probleme bei der Datenübertragung in Rechnernetzen - und insbesondere im Internet - möglichst effizient den Eindruck
aufrecht zu erhalten, dass Spieler ohne Zeitversatz miteinander interagieren können. Wann immer ein Spieler ein Ereignis auslöst, das die Spielwelt beeinflusst, muss dies oft auch an alle Mitspieler übertragen werden.
Da die dazu nötige Information erst über das Netzwerk übertragen werden muss, hat man dabei stets mit einem gewissen Zeitversatz zu tun, bis
die Information bei einem Mitspieler ankommt. Eine echte Gleichzeitigkeit
kann also nie erreicht werden. Man kann jedoch versuchen, die entstehenden Latenzen geschickt zu verbergen.
Allerdings sind Spieler sehr empfindlich, wenn die Rückmeldung eines
zeitkritischen Spiels auf ihre Handlung zu lange dauert, oder die Schnelligkeit der Rückmeldung schwankt. Wenn es beispielsweise eine halbe Sekunde dauert, bis nach einem Knopfdruck die Spielfigur mit ihrer Bewegung
beginnt, dann wird ein präzises steuern stark erschwert. Ebenso verhält es
sich, wenn die Reaktionen der Spielfigur inkonsistent sind, also Schwankungen bei der Reaktionsgeschwindigkeit spürbar werden. Unter Performanz kann man nun ebenfalls verstehen, dass Lösungen gefunden werden,
die möglichst wenig der entstehenden Latenz an den Spieler weiterzugeben. Performanz heißt auch, mit den verfügbaren Hardware-Ressourcen
ökonomisch umzugehen. Dabei geht es immer auch um die Berücksichtigung der lokalen Leistungsfähigkeit eines Systems, also die effiziente Nutzung von Speicherplatz und Rechenkapazität. Insbesondere muss auch die
Geschwindigkeit der verfügbaren Netzwerkverbindung berücksichtigt werden.
6
2
Grundlagen: Rechnernetze und das Internet
In diesem Abschnitt sollen Begriffe und Konzepte erläutert werden, die im
Folgenden häufig Verwendung finden oder generell für das Verständnis
dieser Arbeit relevant sind. Insbesondere werden Grundlagen der Datenübertragung in Computernetzwerken erläutert. Dabei handelt es sich allerdings nicht um eine umfassende Einführung in das Themengebiet „Rechnernetze“. Stattdessen sollen vor allem folgende Fragen beantwortet werden:
• Was ist gemeint, wenn wir von Rechnernetzen oder Netzwerken sprechen?
• Welche Phänomene - oder potentiell auch Probleme - treten allgemein
bei der Datenübertragung in Netzwerken auf?
• Wie können verschiedene vernetzte Computer Nachrichten austauschen und korrekt verarbeiten?
2.1
Das Internet
Das Internet (vom Englischen: Interconnected Network), oft auch als
„WWW“ abekürzt (vom Englischen: World Wide Network) ist ein weltweites
Netzwerk aus Computern, in dem Daten ausgetauscht werden. Oft wird
vom Internet gesprochen als sei es ein bestimmter Ort. Tatsächlich jedoch
ist das Internet vielmehr ein Rechnernetz aus weiteren Rechnernetzen. Dies
legt auch die Bezeichnung „Interconnected Network“ (zu Deutsch etwa:
zusammengeschaltetes Netzwerk) nahe. Die Daten, die umgangssprachlich als
„aus dem Internet“ bezeichnet werden, existieren streng genommen nicht
im Internet, sondern stets auf einzelnen Computern, die an dieses Netz aus
Netzen angeschlossen sind. Rechner können entweder Daten von anderen
Rechnern anfordern oder selbst eigene Daten zum Abruf zur Verfügung
stellen. Der dabei im Internet aufkommende Datenverkehr ist enorm. Abbildung 2 zeigt die Dichte weltweiter Internetverbindungen.
7
2.2
Das LAN
Abbildung 2: Dichte weltweiter Internetverbindungen2
Für Spieler von Videospielen ist das Internet vor allem deshalb interessant, weil es gemeinsames Spielen global ermöglicht. Einerseits erhöht
dies die Anzahl der verfügbaren Mitspieler, andererseits ist es praktisch,
von seinem Computer daheim aus spielen zu können. Zum vernetzten
Spielen war es früher üblich und nötig, den eigenen Computer an einen gemeinsamen Ort zu bringen, um dort alle Geräte in einem lokalen Netzwerk
miteinander vernetzen zu können. Mehr dazu im folgenden Abschnitt.
2.2
Das LAN
Ein „LAN“ (vom Englischen: Local Area Network, zu Deutsch lokales Netzwerk ist ein lokales Netzwerk aus Computern. Wenn Rechner lokal miteinander vernetzt werden, spricht man von einem LAN. Ein privates Heimnetz aus mehreren Computern, wie es heutzutage üblich ist, wäre dafür
ein Beispiel. Zwar gibt es außer „Internet“ und „LAN“ noch weitere Bezeichnungen für die unterschiedlichen Dimensionen von Netzwerken, wie
etwa „PAN“ (vom Englischen: Personal Area Network) oder „WAN“ (vom
Englischen: Wide Area Network), jedoch handelt es sich bei „Internet“ und
„LAN“ um zwei häufig verwendete Sammelbegriffe zur Unterscheidung
der Netzwerkgröße und Reichweite. Wie gebräuchlich der Begriff „LAN“
ist, zeigt sich beispielsweise darin, dass es sogenannte „LAN-Parties“ gibt.
2
Quelle: http://chrisharrison.net/img/internetmapconnectionssplash.jpg - abgerufen
im August 2012
8
2.2
Das LAN
Diese Veranstaltungen heißen so, weil die Besucher ihre Computer zum
Veranstaltungsort transportieren und dort lokal vernetzen. Somit entsteht
dort ein eigenständiges lokales Netzwerk. Meistens werden LAN-Parties
zum gemeinsamen vernetzten Spielen abgehalten.
Die Computer in einem LAN können auf unterschiedliche Weise vernetzt sein. Man spricht hier von „Topologien“. Heutzutage weit verbreitet
ist die Stern-Topologie, bei der jeder Computer mit einem gemeinsamen
Verteiler verbunden ist. Dieser Verteiler ist meist ein spezialisiertes Gerät,
etwa ein sogenannter „Hub“ oder „Switch“, das für den Transport sorgt.
Die Abbildung 3 zeigt einen Überblick über übliche Topologien von lokalen Netzwerken. Außer der Stern-Topologie (Star) sind hier noch die Ring-,
Bus- und Baum-Topologien zu sehen. Bei der Baum-Topologie (Tree) handelt es sich um eine sternförmige Verbindung weiterer, sternförmiger Teilnetze. In der Ring-Topologie ist jedes Endgerät mit genau zwei anderen
verbunden. Ein besonderes Vermittlungsgerät entfällt hier. Bei der BusTopologie (auch Linien- oder Strangtopologie) sind alle Geräte mit einem
gemeinsamen Übertragungsmedium verbunden.
Abbildung 3: Topologien im LAN3
9
2.3
Pakettransport
2.3
Pakettransport
Wie kann man sich nun den Datenverkehr innerhalb von Rechnernetzen
wie dem Internet oder einem LAN vorstellen? Zunächst sei dieser Prozess
kurz umrissen: Auf unterster Ebene handelt es sich bei der Übertragung
von Netzwerkdaten um die Übertragung vieler einzelner „Bits“ (vom Englischen: binary digit). Bits sind binäre Daten, also Informationen aus nur
zwei möglichen Zuständen, welche man üblicherweise durch Null oder
Eins symbolisiert. Für die Netzwerkübertragung werden diese unterschiedlichen Zustände beispielsweise als elektrische Ladungen durch ein Kabel
geschickt oder als elektromagnetische Wellen in kabellosen Netzwerken
übertragen. Zur effektiven Nutzung der Übertragungswege werden mehrere Bits zu einer Dateneinheit, einem sogenannte „Netzwerkpaket“, zusammengefasst und als solches interpretiert. Auf Grund der physikalischen
Beschaffenheit von Netzwerken ist es jedoch möglich, dass Bits nicht immer korrekt übertragen werden. Auch kann ein Datenstrom aus Bits jederzeit unerwartet unterbrochen werden. Die Zuverlässigkeit einer Verbindung ist also auf unterster technischer Ebene nicht garantiert. Wie es
dennoch möglich ist, Daten im Netzwerk zuverlässig zu übertragen und
zu interpretieren, wird im nächsten Abschnitt erklärt.
2.4
Netzwerkprotokolle
Angesichts der bereits beschriebenen technischen Probleme stellt sich natürlich die Frage, wie ein zuverlässiger Auslese- und Interpretationsprozess von Netzwerkdaten möglich wird. Dies wird erreicht durch sogenannte „Netzwerkprotokolle“. Unterschiedliche Computer - oder vielmehr unterschiedliche Programme oder Prozesse - müssen das gleiche Netzwerkprotokoll verwenden, damit die Kommunikation unter ihnen im Netzwerk
funktioniert. Bei diesem Protokoll handelt es sich um eine Kommunikationsvereinbarungen zwischen Sender und Empfänger (oder allgemeiner:
zwischen zwei kommunizierenden Entitäten), mit deren Hilfe beide Parteien die gegenseitigen Nachrichten in Bitform verstehen können. Ein Protokoll kann seinen Zweck also nur erfüllen, wenn mindestens zwei Compu3
Quelle: http://images-mediawiki-sites.thefullwiki.org/10/3/6/2/
66429742193536172.gif - abgerufen im August 2012
10
2.4
Netzwerkprotokolle
ter (bzw. Programme oder Prozesse) miteinander kommunizieren sollen.
Es basiert auf einer minimalen Dialogsprache, bestehend aus:
1. Syntax
2. Semantik
3. und Zeitbeschränkungen (vom Englischen: time constraints)
Diese drei Komponenten eines Netzwerkprotokolls seien im Folgenden
kurz erläutert:
Syntax: In der Grammatik bezeichnet der Begriff „Syntax“ die Satzlehre,
legt also den zulässigen Satzbau fest. Der Ausdruck wird sowohl für
natürliche als auch formale Sprachen, wie beispielsweise Programmiersprachen, verwendet. Syntax bezeichnet hier also ein System aus
Regeln, das bestimmte Wort- und Satzkonstruktionen erlaubt. Wörter
können dabei aus einem Alphabet (einem Vorrat von Zeichen) gebildet werden.
Semantik: Als „Semantik“ wird allgemein die Bedeutungslehre bezeichnet. Während eine Syntax die erlaubten Wort- und Satzkonstruktionen festlegt, legt die Semantik fest, was diese Zeichen bedeuten. Im
Falle eines Netzwerkprotokolls heißt dies, es wird festgelegt, welche
Bedeutung und Auswirkung eine Netzwerknachricht für den Empfänger hat.
Zeitbeschränkungen: Wenn eine Nachricht nach einer bestimmten Zeit
nicht beim Empfänger angekommen ist, kann von einem Fehler ausgegangen werden. Oft heißt dies, dass die Nachricht auf dem Weg
durch das Netzwerk verloren gegangen ist. Die Zeitspanne, bis eine
Nachricht beim Empfänger angekommen sein muss, wird im Rahmen des Themengebiets Rechnernetze auch als „Timeout“ bezeichnet. Je nachdem, was ein Netzwerkprotokoll für diesen Fall vorsieht,
kann beispielsweise der Befehl gegeben werden, einen erneuten Zustellungsversuch der gleichen Nachricht zu starten.
11
2.4
Netzwerkprotokolle
Nun stellt die Umsetzung einer zuverlässigen Kommunikation im Netzwerk viele verschiedene Anforderungen. Daher ist oft ein Zusammenwirken unterschiedlicher Protokolle nötig, die alle unterschiedliche Funktionalitäten abzudecken. Damit die dabei auftretende Komplexität beherrschbar bleibt, ordnet man die verschiedenen Protokolle und ihre unterschiedlichen Aufgabenbereiche konzeptionell in unterschiedliche Schichten ein.
Protokolle höherer Schichten nutzen dabei jene aus darunterliegenden. Der
somit entstehende Protokollstapel ist angelehnt an das sogenannte
„ISO-OSI-Referenz-modell“, auch „OSI-Schichtenmodell“ genannt. In Abbildung 4 ist dieses Modell dargestellt.
Abbildung 4: ISO-OSI-Referenzmodell4
Beim Versand durchläuft ein Datenpaket sämtliche Schichten des ISOOSI-Referenzmodells von oben nach unten. Auf der Empfängerseite geschieht es nochmals, jedoch umgekehrt von unten nach oben. Im Folgenden sind die Aufgaben der sieben einzelnen Schichten des Modells kurz
zusammengefasst:
Anwendungsschicht: Dies ist die oberste Schicht des Modells. Sie umfasst
4
Quelle: http://www.internetworking-buch.de/wp-content/uploads/2012/07/
ISO_OSI_Referenzmodell.jpg - abgerufen im September 2012
12
2.4
Netzwerkprotokolle
Protokolle, die eine Schnittstelle zwischen dem Computer und den
darauf ausgeführten Anwendungen bereitstellen. Beispiele dafür wären Protokolle wie „pop3“ oder „smtp“, welche dem E-Mail-Empfang
und E-Mail-Versand dienen.
Darstellungsschicht: Die Darstellungsschicht bietet Möglichkeiten, Daten
syntaktisch korrekt zwischen unterschiedlichen Systemen auszutauschen. Die systemabhängige Darstellung von Daten wird dazu in eine
systemunabhängige Form gebracht. Durch diese Konventionen der
Übertragung ist gewährleistet, dass Daten von einem Protokoll dieser
Schicht ebenfalls auf einem anderen System gelesen werden können.
Zu dieser Schicht gehören Aufgabenbereiche wie die Datei-Eingabe
und Datei-Ausgabe, das Anzeigen von Anweisungen und Fehlermeldungen und die Festlegung der Bildschirmdarstellung.
Sitzungsschicht: Aufgabe der Sitzungsschicht ist es, Verbindungen aufrecht zu erhalten, also Zusammenbrüche zu verhindern. Durch sogenannte Wiederaufsetzpunkte bzw. Fixpunkte (vom Englischen: Check
Points) wird gewährleistet, dass eine Übertragung nicht wieder neu
beginnen muss, wenn sie unterbrochen wurde.
Transportschicht: Die Transportschicht ist verantwortlich für eine Aufteilung (Segmentierung) des Datenverkehrs. Ein Ziel der Segmentierung ist die Stauvermeidung (vom Englischen: congestion avoidance).
Diese soll verhindern, dass Pakete schneller eintreffen als sie verarbeitet oder weitergeleitet werden können.
Vermittlungsschicht: Die Vermittlungsschicht ist für die Wegsuche von
Paketen (vom Englischen: Routing) zuständig. Nur wenn Computer
direkt miteinander verbunden sind, etwa über ein sogenanntes „Crosskabel“ bzw. „Crossoverkabel“, ist eine direkte Kommunikation möglich. In der Regel ist dies jedoch nicht der Fall, insbesondere nicht
bei der Kommunikation über das Internet. Netzwerkpakete passieren hier auf ihrem Weg zum Empfänger viele Zweigstellen. RoutingAlgorithmen der Vermittlungsschicht versuchen dabei, Pakete über
verschiedene Zwischenstationen zum Ziel zu schicken und schnelle
Verbindungen zu finden. Auch die Bereitstellung netzwerkübergreifender Addressen, sowie die Weiterleitung zwischen unterschiedli13
2.4
Netzwerkprotokolle
chen Teilnetzen aus unterschiedlichen Übertragunsmedien zählt zu
den Aufgaben der Vermittlungsschicht.
Sicherungsschicht: Ziel der Sicherungsschicht ist es, eine fehlerfreie Datenübertragung sicherzustellen. Dazu wird der Datenstrom aus einzelnen Bits in Blöcke (im Englischen auch Frames genannt, zu Deutsch:
Rahmen) aufgeteilt und es werden sogenannte „Prüfsummen“ hinzugefügt und beim Empfänger ausgelesen. Anhand einer Prüfsumme
lässt sich vom Empfänger feststellen, ob Bit-Blöcke fehlerhaft übertragen wurden. In diesem Falle können diese Blöcke verworfen oder
auch korrigiert werden. Durch eine Datenflusskontrolle wird außerdem geregelt, wie schnell Blöcke gesendet werden dürfen.
Bitübertragungsschicht: Dies ist die unterste Schicht. Durch sie werden
die grundlegenden Hilfsmittel zur Datenübertragung bereitgestellt,
mit denen sich physische Verbindungen kontrollieren lassen. Es kann
sich hierbei etwa um elektromagnetische Wellen (WLAN oder allgemein drahtlose Netze), elektrische oder optische Signale handeln.
Für die Programmierung einer Network Engine, im Rahmen dieser Arbeit, werden wir hauptsächlich mit den Schichten drei und vier zu tun haben, genauer: mit den Netzwerkprotokollen „IP“, „TCP“ und „UDP“. Diese seien hier ebenfalls kurz vorgestellt.
IP-Protokoll: Das IP-Protokoll (vom Englischen: Internet Protocol) ist die
Grundlage des Internets. Im ISO-OSI-Referenzmodell entspricht es
der Vermittlungsschicht und damit der ersten Schicht, die vom Übertragungsmedium unabhängig ist. Es erfüllt die Aufgaben der Addressierung und der Wegsuche von Netzwerkpaketen. Mittels Schlüsselkombinationen aus Zeichen, sogenannter „IP-Adressen“ und
„Netzmasken“, lassen sich Computer adressieren und in Teilnetze
zusammenfassen. Somit wird es erst möglich, ihnen IP-Pakete zuzuschicken.
IP ist jedoch ein sogenanntes verbindungsloses Protokoll (vom Englischen: connectionless protocol), das heißt: Anders als bei sogenannten verbindungsorientierten Protokollen (vom Englischen: connection
14
2.4
Netzwerkprotokolle
oriented protocols) wird bei Beginn der Kommunikation kein besonderer Verbindungszustand definiert. Es wird somit nicht gewährleistet,
dass Pakete beim Empfänger eintreffen. Pakete werden vom Sender
sozusagen blind an die Adresse des Empfängers geschickt, ohne eine
Rückmeldung, was mit dem Paket nach seinem Versand geschehen
ist. Wenn eine sichere und zuverlässige Übertragung gewährleistet
werden soll, wird das TCP-Protokoll benutzt, welches auf dem IPProtokoll aufsetzt.
TCP-Protokoll: Das TCP-Protokoll (vom Englischen: Transmission Control
Protocol), auch Übertragungssteuerungsprotokoll genannt, sorgt für
eine sichere und zuverlässige Datenübertragung. Es ist im ISO-OSIReferenzmodell in der Transportschicht angesiedelt und baut auf dem
IP-Protokoll auf. Teils ist daher umgangssprachlich oft die Rede vom
„TCP/IP“-Protokoll. Das besondere Merkmal dieses Protokolls ist die
Zuverlässigkeit: Zwischen den beiden Endpunkten des Senders und
des Empfängers findet ein verlässlicher Verbindungsaufbau (vom Englischen: Handshake) statt. Datenverluste werden erkannt und behoben, indem verlorene Pakete erneut verschickt werden. Zudem ist
sichergestellt, dass Pakete in korrekter Reihenfolge beim Empfänger
eintreffen. Zusätzlich zur IP-Adresse wird beim TCP-Protokoll zur
exakten Adressierung eine weitere Zahlenkombination benutzt, ein
sogenannter Port. Mit Hilfe eines Ports wird es möglich, verschiedene Programme und Prozesse des selben Rechners zu adressieren. Metaphorisch kann man sich IP-Adressen Als Straßennamen und Ports
als Hausnummern vorstellen.
Durch seine Sicherheits- und Korrekturfunktionalität ist dieses Protokoll jedoch nur bedingt geeignet für den Einsatz bei zeitkritischen
Videospielen. Hier zählt in vielen Fällen nicht unbedingt eine fehlerfreie, sondern eine schnelle Übertragung. Zur Veranschaulichung,
warum für bestimmte Anwendungsfälle die Geschwindigkeit der Datenübertragung wichtiger sein kann als ihre Korrektheit, sei das Beispiel Sprachübertragung bzw. Internet-Telefonie genannt. Hier ist weniger wichtig, ob es zwischendurch zu kurzen Aussetzern kommt,
und vielmehr erwünscht, dass eine schnellstmögliche Übertragung
erfolgt. Ähnlich ist es oft bei zeitkritischen Videospielen: Werden bei15
2.4
Netzwerkprotokolle
spielsweise die Positions-Daten eines bewegten Objekts im Netzwerk
übertragen, ist oft nur der aktuellste Status des Objekts interessant.
TCP würde jedoch dafür sorgen, dass bei Verlust eines Datenpakets
das Paket nochmals verschickt wird - und alle neueren Pakete erst
später eintreffen. Das Objekt jedoch bewegt sich in dieser Zeit kontinuierlich weiter und seine frühere Position ist in den meisten Fällen
für die grafische Darstellung nicht mehr relevant. Für die Netzwerkfunktionalität von Videospielen wird daher häufig das UDPProtokoll verwendet.
UDP-Protokoll: Das UDP-Protokoll (vom Englischen: User Datagram Protocol) ist - anders als TCP - ein verbindungsloses Netzwerkprotokoll.
Ebenso wie das TCP-Protokoll entspricht es der Transportschicht im
ISO-OSI-Referenzmodell, setzt also ebenfalls auf dem IP-Protokoll auf.
Ähnlich wie beim TCP-Protokoll werden auch hier zusätzlich zur IPAdresse Ports verwendet, um den Exakten Bestimmungsort eines Pakets festzulegen. Eine Sicherung der Datenübertragung entfällt bei
UDP jedoch weitestgehend. Zwar können auch hier fehlerhafte Übertragungen anhand einer Prüfsumme erkannt werden, jedoch bietet
das Protokoll keine Garantie, dass ein Paket sein Ziel erreicht. Auch
können Pakete in falscher Reihenfolge beim Empfänger eintreffen.
Dennoch ist es auf Grund seiner Geschwindigkeit oft die beste Wahl
für netzwerkfähige Videospiele. Für Probleme, die durch die verbindungslose, unzuverlässige Übertragung via UDP aufkommen, lassen
sich zudem verschiedene Lösungen finden (vgl. Abschnitt 5).
16
3
Technische Probleme vernetzten Spielens
„We can’t network everything!“
- D AVID A LDRIDGE , L EAD N ETWORKING E NGINEER AT B UNGIE
Bei der vorangegangenen Erläuterung der Grundlagen etablierter Netzwerktechnik ist bereits die Komplexität von Netzwerkkommunikation sichtbar geworden. Auch wurde bereits das allgemeine technische Problem der
Unzuverlässigkeit bei der Übertragung von Netzwerknachrichten deutlich.
Was für Probleme sich daraus nun insbesondere für vernetztes Spielen ergeben, soll in diesem Abschnitt erläutert werden.
3.1
Latenz und Latenzschwankungen
Wir sind es auch im Alltag gewohnt, dass es stets eine Weile dauert, bis
eine Nachricht - ganz gleich welcher Art - ihren Empfänger erreicht. Auch
bei einem Live-Bericht im Fernsehen, bei welchem umgangssprachlich von
Gleichzeitigkeit gesprochen werden könnte, sind die Ereignisse am Bildschirm oft vor mehreren Sekunden geschehen. Selbst unser eigener Körper
braucht Zeit, bis auf Reize und Nervensignale Reaktionen folgen, obwohl
es sich hier nur um Sekundenbruchteile handelt. Aber ähnlich kann man
sich auch die Verzögerung der Datenübertragung in Rechnernetzen vorstellen: Verschickt ein Computer eine Netzwerknachricht, braucht sie eine
gewisse Zeit, bis sie beim Empfänger eintrifft. Neben der Existenz physikalischer Grenzen treten hierbei auch Bearbeitungszeiten an Zwischengeräten und Endgeräten auf. Eine Netzwerknachricht passiert in der Regel mehrere Zweigstellen, bevor sie bei ihrem Empfänger ankommt. Wie
schnell diese Zweigstellen Netzwerkpakete weiterleiten, entzieht sich dabei unserer Kontrolle.
Die Zeitspanne, die ein Netzwerkpaket vom Sender zum Empfänger
benötigt, wird als Latenz bezeichnet. Diese verzögerung beträgt üblicherweise mehrere Millisekunden, selbst bei schnellen Verbindungen. Eine weitere Größe ist die Antwortzeit oder Paketumlaufzeit (vom Englischen: response time oder Round Trip Time, kurz RTT). Unter dieser Größe versteht
man den Zeitraum, der zwischen dem Versenden einer Netzwerk-Nachricht
17
3.1
Latenz und Latenzschwankungen
und dem Empfang einer Antwort des Empfängers auf die versendete Nachricht vergeht, oder genauer: bis zum Empfang des ersten Zeichens der Antwort. Man kann also annehmen, dass die Antwortzeit mindestens das Doppelte des Latenzwertes ist, da ein Paket in beide Richtungen, hin und zurück, geschickt werden muss und zusätzlich Bearbeitungszeit auf beiden
Seiten anfällt. Allerdings kann es ebenso vorkommen, dass sich durch asymmetrisches Routing die Dauer des Pakettransports in beiden Richtungen
unterscheidet.
Um eine Vorstellung davon zu erhalten, in welchen Größenordnungen
sich die Verzögerung beim Datentransport bewegt, sei der Vergleich mit
der Bildwiederholrate eines Computerbildschirms herangezogen: Üblich
für Computermonitore ist eine Bildwiederholrate von etwa 60 Bildern in
der Sekunden. Das heißt, dass etwa alle 16 bis 17 Millisekunden ein neues
Bild ausgegeben wird (vgl. Gleichung 1).
1000ms/60 = 16.67ms
(1)
Wann immer ein Benutzer also die Maus bewegt, sieht er nach frühestens 16.67 Millisekunden die entsprechende Bewegung des Mauszeigers. In der Praxis wird die Verzögerung auf Grund weiterer Faktoren, wie
der Bearbeitungsdauer des Eingabe-Signals, höher liegen. Angenommen,
ein Computer ist leistungsfähig genug, ein Videospiel mit mindestens 60
Bildern in der Sekunde darzustellen, so kann man davon ausgehen, dass
ein Spieler gewohnt ist, bei Eingaben etwa ein Bild später - oder bedingt
durch Bild-Pufferung der Grafikkarte, sowie eventueller Ausgabeverzögerung des Monitors erst zwei bis drei Bilder später - eine visuelle Rückmeldung vom Spiel zu erhalten. Dies entspräche also etwa 17 bis 50 Millisekunden, bis ein Spieler eine Rückmeldung auf seine Eingaben erhält, wenn
er ein Spiel unvernetzt, lokal spielt. Paketumlaufzeiten im Internet sind üblicherweise wesentlich höher und können deutlich über 100 Millisekunden
betragen. Würde man nun dafür sorgen wollen, dass allen Spielern eines
vernetzten Spiels gleichzeitig die Ereignisse der Spielwelt dargestellt werden, müsste stets auf den Mitspieler mit der langsamsten Netzwerkverbindung gewartet werden, bevor der Spielstatus voranschreiten kann, also
eine Reaktion sichtbar wird. Das heißt: Zu den bereits vorhandenen Latenzfaktoren, wie einer verzögerten Ausgabe am Bildschirm, würde somit die
18
3.2
Netzwerkarchitekturen
volle Paketumlaufzeit der langsamsten Verbindung hinzu kommen, was
die Reaktionsgeschwindigkeit potentiell um ein vielfaches verlangsamen
kann.
Diese Verzögerungen beim Datentransport im Internet stellen beim vernetzten Spielen ein allgemeines Problem dar. Spieler sind es beispielsweise gewohnt, dass ein Spiel unmittelbar auf ihre Eingaben reagiert. Wenn
man dies jedoch bei einem vernetzten Spiel zulässt, wird die Synchronisation der Spielelogik zwischen Mitspielern aufwändig und potentiell problematisch. Zudem kann davon ausgegangen werden, dass jederzeit Latenzschwankungen auftreten können, sich also die Latenz und Paketumlaufzeit
kurzzeitig erhöhen kann. Diese Unregelmäßigkeit kann die Spielbarkeit eines Spiels zusätzlich negativ beeinflussen.
3.2
Schon die Wahl der Kommunikationsstruktur für die am Spiel teilnehmenden Systeme birgt unterschiedliche Probleme für die Synchronisation in
sich. Traditionell gibt es hier bei Videospielen zwei verschiedene Netzwerkarchitekturen: „Peer-to-Peer“ und „Client-Server“. Diese sollen hier
vorgestellt werden.
3.2.1
Peer-to-Peer-Modell
Bei frühen netzwerkfähgien Videospielen, wie beispielsweise dem Spiel
„Doom“, war es üblich, dass die Computer aller Spieler direkt miteinander kommunizierten. Im lokalen Netzwerk entspräche diese Struktur einer
Stern-Topologie, jedoch ohne ein Vermittlungsgerät (vgl. Abbildung 3). Auf
jedem Computer wurde dabei eine eigene Kopie des Spiels ausgeführt. Die
Grundidee war, das Spiel intern in eine Abfolge von Spielzügen zu unterteilen, zu deren Anfang die Eingaben eines jeden Spielers an alle Mitspieler
übertragen und verarbeitet wurden (vgl. [Fie], What every programmer needs
to know about game networking). Einerseits ergab sich das bereits beschriebene Problem, dass die Geschwindigkeit des Spielablaufs abhängig gemacht
wurde von der langsamsten Verbindung eines Mitspielers (vgl. Abschnitt
3.1): Arbeitete die Netzwerkkarte oder das Modem nur eines bestimmten
19
3.2
Systems mit einer geringen Datenübertragungsrate, so verschlechterte sich
automatisch auch die Spielbarkeit auf den Systemen aller Mitspieler, da das
Spiel stets auf die Eingaben aller Spieler warten musste.
Zudem wurden bei vielen Peer-to-Peer-Spielen ausschließlich die Eingaben von Spielern übertragen. Somit war es nötig, dass alle Spieler das
Spiel gemeinsam begannen. Einem laufenden Spiel konnte kein weiterer
Spieler beitreten, da jeder Spieler mit dem gleichen initialen Status der
Spielwelt beginnen musste. Zusätzlich erschwerte sich auch die Synchronisation zwischen den Systemen: Da auf jedem Computer auch das Spiel
ausgeführt wurde und außer den Eingaben keine Kontrolldaten übertragen
wurden, war es teils schwierig, die Determiniertheit der Simulation zu gewährleisten. Unter Umständen konnte der Fall auftreten, dass eine Reihe
von Ereignissen auf dem System eines einzelnen Spielers ein geringfügig
anderes Ergebnis erzeugte. So konnten sich Zustände der Spielwelt ergeben, die nicht miteinander vereinbar waren, etwa wenn ein Spieler auf einem System einer Explosion entkommen war, wohingegen er auf allen anderen System getroffen wurde. Die Folge dieser geringfügigen Unterschiede war schließlich ein irreversibler Synchronisationsverlust, der es nötig
machte, ein gemeinsames Spiel abzubrechen und neu zu beginnen.
Allgemein ist die Peer-to-Peer-Architektur somit problematisch für zeitkritische Videospiele. Vorteilhaft ist sie insbesondere dann, wenn die Menge der zu synchronisierenden Objekte hoch ist. Aus diesem Grund eignet sich die Peer-to-Peer-Architektur besonders bei vielen Echtzeitstrategiespielen (vgl. Abschnitt 4.1.2), da hier die zu übertragende Datenmenge
groß sein kann. Ein Konzept, welches jedoch allgemein häufiger verwendet wird und einige der hier beschriebenen Probleme löst, ist das „ClientServer-Modell“.
3.2.2
Client-Server-Modell
Bei einer Vernetzung im Peer-to-Peer Verfahren ist es üblich, auf jedem einzelnen System die gesamte Simulation auszuführen. Als bei der Entwicklung des Spiels „Quake“ erstmals der Weg zu einer Client/Server-Struktur
angetreten wurde, war der Ansatz ein anderer: Die Simulation wurde ausschließlich auf einem System ausgeführt werden, nämlich dem „Server“,
20
3.2
der die Daten an alle Mitspieler, die „Clients“, verteilen sollte. Alle ClientSysteme sollten lediglich die Funktion eines sogenannten Terminals5 einnehmen, also Eingaben des Benutzers an den Server weiterleiten und die
Rückmeldungen des Servers empfangen. Vorteilhaft ist diese Methode besonders, da sie sich durch Einfachheit auszeichnet: Ausschließlich der Server hat Authorität über die Simulation der Spielwelt. Somit kann es nicht
zur Desynchronisierung kommen, wie etwa bei einer klassischen Peer-toPeer-Architektur.
Ursprünglich waren die Systeme von Spielern somit einfache Rezipienten des Spielstatus, die Meldungen vom Server erhielten, Eingaben an
den Server weiterreichten und die Spielwelt darstellten. Die Spielelogik jedoch wurde ausschließlich auf dem Server ausgeführt. Zwar zeichnete sich
dieser Ansatz durch softwaretechnische Klarheit und Eleganz aus, genügte jedoch lediglich den Anforderungen des vernetzten Spielens in lokalen
Netzwerken mit hoher Übertragungsgeschwindigkeit und schnellen Antwortzeiten. Für das gemeinsame Spielen über das Internet hingegen war
dies jedoch untauglich: Da die Spielelogik, die Simulation, ausschließlich
auf dem Server ausgeführt wurde, sahen und spürten Spieler die Rückmeldung ihrer Eingaben erst nachdem sie eine Antwort vom Server erhalten hatten. Die dabei vorhandene Eingabeverzögerung entsprach der Paketumlaufzeit zwischen Server und Client. Vorteilhaft war allerdings, dass
die eigene Spielgeschwindigkeit nun nicht mehr durch den Spieler mit der
langsamsten Verbindung ausgebremst werden konnte. Trotz dieser Probleme wurde das Client-Server-Modell weitgehend von vielen Spielen adaptiert und um verschiedene Verfahren erweitert, um die anfallenden Latenzen vor Spielen zu verbergen (vgl. Abschnitt 5).
5
„Ein Terminal, auch Konsole eines Computers, ist ein Benutzerendgerät zur Eingabe und
Anzeige von Daten.“, Quelle: http://de.wikipedia.org/wiki/Terminal_(Computer) - abgerufen im August 2012
21
3.3
Unzuverlässigkeit der Datenübertragung
3.3
Unzuverlässigkeit der Datenübertragung
Die Zustellung von Datenpaketen im Netzwerk erfolgt nach einem „BestEffort-Verfahren“. Das heißt, es wird stets versucht, ein Paket an seinen
Empfänger zu verschicken, aber es kann nicht garantiert werden, dass ein
Paket seinen Empfänger erreicht. Es besteht stets die Möglichkeit, dass das
Paket auf seinem Weg durch das Netzwerk verloren geht. (vgl. Abschnitt
2.3). Zwar bietet das Netzwerkprotokoll TCP Sicherungsfunktionen an, die
eine Zustellung der Netzwerkpakete garantieren, aber wie bereits erläutert
ist dieses Protokoll keine gute Wahl für zeitkritische Videospiele (vgl. Abschnitt 2.4). Für vernetzte und zeitkritische Videospiele bleibt also grundsätzlich das Problem, wie man Paketverluste behandeln kann und inwiefern sich die Spielbarkeit erhalten lässt. Werden beispielsweise in einem
regelmäßigen Intervall neue Positionsdaten eine Objekts übertragen, dann
kann das ausbleiben von Paketen eine unregelmäßige Bewegung verursachen, sofern keine weiteren Verfahren zur Behandlung dieses Falls implementiert wurden (vgl. Abschnitt 6.3.2 und 5.6).
3.4
Datenübertragungsrate
Für vernetztes Spielen im Internet ist die verfügbare Datenübertragungsrate von entscheidender Bedeutung. Umgangssprachlich wird auch von
Bandbreite (vom englischen: Bandwidth) gesprochen. Die Datenübertragungsrate ist eine Bezeichnung für die digitale Datenmenge, die in einer bestimmten Zeit übertragen werden kann. Übliche Maßeinheiten sind
„Bits pro Sekunde“ (vom Englischen: Bits per second, kurz bps).
22
3.4
Häufiger als im lokalen Netzwerk kann es im Internet vorkommen,
dass die Verbindung von Mitspielern unterschiedliche Datenübertragungsraten aufweisen. Es sollte somit davon ausgegangen werden, dass die Übertragung großer Datenmengen ein Problem darstellt. Daher sollte die Datenmenge möglichst gering gehalten werden. Für einige Spiele stellt diese Beschränkung ein unüberwindbares Hindernis dar, etwa für das Playstation3-Spiel „Comet Crash“. Hier ist die Implementierung der Internetfunktionalität an der Komplexität des Spiels gescheitert. Auf der offiziellen Internetseite des Spiels gaben die Entwickler folgendes bekannt:
„We invested over two months of development time attempting to implement
online multiplayer for Comet Crash. With thousands of units to keep in sync, we
knew there would be no elegant solution and had planned to hack around the problem. Unfortunately, with so many hacks it would be impractical to maintain a
robust and consistent gaming experience. For that reason we have decided not to
implement online multiplayer support.“6
Hier ist davon auszugehen, dass die zu übertragende Datenmenge den
problematischen Faktor darstellt. In seinem Vortrag „Networking for Physics Programmers“ (vgl. [Fie10]) führt der Autor, Glenn Fiedler, umfangreiche Messungen der durchschnittlich verfügbaren Datenübertragungsrate durch. Nach 20 tägigen Stichproben, verteilt über die Amerika, Europa,
Japan und Korea, kommt er zu dem Ergebnis, dass man als Entwickler auf
eine maximale Datenübertragungsrate von etwa 64kbps (auch kbit/s, vom
Englischen: kilobit per second) zielen sollte, da dies in 99.1% aller Fälle erreicht werden konnte. Abbildung 5 zeigt eine Auswertung der Messungen.
6
Quelle: http://www.cometcrash.com/en/component/content/article/3 - abgerufen
im August 2012
23
3.4
Abbildung 5: Häufigkeit der praktisch erreichten Datenübertragungsrate von Internetverbindungen7
Der Autor weist jedoch darauf hin, dass für die Auswertung seiner
Messungen wesentlich mehr Stichproben aus den USA und Europa zur
Verfügung standen, was die abschließende Statistik beeinflusst haben könnte. Die Konsequenz ist jedoch in jedem Fall, dass Netzwerkpakete effizient
mit Speicherplatz umgehen müssen. Wenn beispielsweise eine Datenübertragungsrate von 64 kbps vorliegt, hieße dies, dass ein Paket gerade einmal
etwa 256 byte (2048 bit) groß sein darf, wenn es 30 mal in der Sekunde
verschickt wird (vgl. Gleichung 2):
2048bit ∗ 30 = 61.44kbit
7
(2)
Quelle: [Fie10]
24
3.5
Prozessorlast
3.5
Prozessorlast
Dies ist ein Problem, das nicht direkt den Grenzen der technischen Möglichkeiten von Rechnernetzen zuzuschreiben ist. Es spielt aber dennoch eine wichtige Rolle, was die Performanz betrifft. Teilweise ist der Flaschenhals beim Datenverkehr im Netzwerk nicht die begrenzte Bandbreite, sondern die Leistungsfähigkeit des Hauptprozessors (vom Englischen: Central
Processing Unit, kurz CPU) eines Computers. Ein Computer ist nur dann
in der Lage, ein Programm schnell genug auszuführen, wenn seine Prozessorauslastung unter 100% liegt. Andernfalls verlangt ein Programm eine höhere Leistung von einem Prozessor als dieser berechnen kann. Somit
kommt es zu einer verlangsamten Programmausführung. Dies ist insbesondere dann ein Faktor, wenn die Geschwindigkeit der Programmausführung auf dem System eines Spielers seine Mitspieler beeinflusst. Bei
einer Vernetzung im Peer-To-Peer-Verfahren wäre dies beispielsweise der
Fall (vgl. Abschnitt 3.2.1).
25
3.6
Cheating
3.6
Cheating
Mit „Cheating“ (zu Deutsch: Betrügen) ist gemeint, dass Mitspieler sich innerhalb eines Spiels Vorteile verschaffen können, wie etwa die eigene Spielfigur unbesiegbar zu machen oder sie durch Wände gehen lassen zu können. Beim gemeinsamen Spielen sind Vorteile wie diese unfair, also üblicherweise nicht erwünscht. Besonders beim vernetzten Spielen kann sich
Cheating als ein Problemfaktor herausstellen, da die Implementierung der
Netzwerkfunktionalität darüber entscheidet, wie anfällig ein Spiel für Manipulationen ist.
Insofern ist Cheating auch ein Faktor für die Performanz, da es den Aufbau der jeweiligen Software beeinflusst. Liegt die Authorität für das Auslösen bestimmter Ereignisse beim Client, so ist dies potentiell problematisch. Denn allgemein ist es schwierig, zu garantieren, dass die Eingaben,
die ein Client-System an den Server sendet, auf dem vom Spiel vorgesehenen Weg entstanden sind. Man kann beispielsweise nicht ausschließen,
dass zusätzliche Software auf dem Client dem Spieler assistiert und seine
Eingaben verbessert. Dadurch, dass man einen Großteil der Spielelogik auf
dem Server ausführt, lässt sich zumindest die Manipulation erschweren.
Dies ist jedoch je nach Spiel nicht immer möglich oder praktisch, daher
bleibt Cheating ein allgemeines Problem vernetzter Videospiele.
26
4
Funktionalitätsanforderungen
Videospiele können höchst unterschiedliche Formen annehmen. Es hat sich
etabliert, von Genres zu sprechen, auch wenn eine Abgrenzung oft schwer
fällt. Festzuhalten bleibt jedoch, dass unterschiedliche Spielabläufe mit ihren individuellen Spielmechaniken auch unterschiedliche Anforderungen
an Netzwerkfunktionalität stellen. Um also eine Network Engine zu entwerfen, die die Bedürfnisse möglichst vieler verschiedener Spiele hinreichend bedient, muss zunächst identifiziert werden, um welche Bedürfnisse
es sich hier handelt.
In diesem Abschnitt geht es darum, anhand der Spielmechaniken einiger Videospiele-Genres herauszufinden, welche besonderen Anforderungen diese und ähnliche Spiele stellen. Bei der Auswahl handelt es sich um
eine Stichprobe jener Genres zeitkritischer Videospiele, die häufig mit mehreren Spielern gespielt werden. Tatsächlich ließe sich diese Liste beliebig
erweitern. Jedoch wurde hier, bedingt durch die allgemeine Ähnlichkeit
der zu lösenden Probleme, davon ausgegangen, dass die aus den vertretenen Genres hervorgehenden Anforderungen repräsentativ sind für zeitkritische Videospiele allgemein. Nachdem die Anforderungen für eine zu
implementierende performante Network Engine identifiziert wurden, sollen im darauffolgenden Abschnitt Lösungsmöglichkeiten gefunden werden, wie diese Anforderungen anhand der technischen Probleme in Computernetzwerken umgesetzt werden können.
4.1
4.1.1
Analyse typischer Spiele-Genres
First Person Shooter (FPS)
Historisch betrachtet ist es insbesondere das Genre der sogenannten „First
Person Shooter“ (oft auch als Ego Shooter oder 3D Shooter bezeichnet), das
maßgeblich zu Optimierungen der Netzwerkfunktionalität für zeitkritische
Videospiele geführt hat. Als prägend für dieses Genre gilt besonders der Titel „Doom“, der 1993 von der Firma id Software für den PC veröffentlicht
wurde. Bei Doom bewegt sich der Spieler in der Ich-Perspektive (daher die
Bezeichnung First Person- oder Ego Shooter) durch eine dreidimensionale
Umgebung. Dabei kann er auf Gegner schießen, deren Angriffen auswei-
27
4.1
chen, oder mit der Umgebung interagieren, indem er Schalter betätigt, Türen öffnet oder herumliegende Gegenstände einsammelt.
In Doom finden sich bereits viele der Anforderungen moderner First
Person Shooter: Eine zunächst naheliegende Anforderung beim vernetzten
Spielen ist, dass jeder Mitspieler die aktuelle Position anderer Mitspieler
erfährt. Ebenso sind alle Handlungen von Mitspielern relevant, die direkte Auswirkungen auf die Spielwelt haben. Wenn beispielsweise ein Mitspieler einen Gegenstand einsammelt, einen Schalter betätigt, eine Tür öffnet, oder einen Schuss abgibt, dann müssen diese Ereignisse grundsätzlich
im Netzwerk übertragen werden. Wie bereits beschrieben (vgl. Abschnitt
3.2.1) wurde bei Doom für die Netzwerkfunktionalität die Peer-to-PeerArchitektur benutzt. Zudem wurden ausschließlich Eingaben von Spielern
übertragen und dann bei jedem Spieler auf das lokal ausgeführte Spiel angewandt. Da First Person Shooter heutzutage jedoch insbesondere über das
Internet gespielt werden und oft eine hohe Spielerzahl aufweisen, wie etwa die Spiele der Reihe „Battlefield“, eignet sich dieser Ansatz für moderne
Spiele dieser Art nicht mehr. Je nach Komplexität des Spiels und der Spielwelt kann auch die Menge der zu übertragenden Daten problematisch werden. Früher hatte man es hier lediglich mit statischen Spielwelten zu tun, so
dass die Datenmenge gering ausfiel. Spiele wie etwa Quake 3 Arena waren
daher so konzipiert, dass sie stets den Status aller relevanten Objekte der
Spielwelt übertragen konnten (vgl. [Ald11], Common Simplifying Approaches). Auch handelt es sich hier um ein Genre, bei dem Spieler häufig direkt gegeneinander antreten können. Somit kommt es auf Reaktionsschnelligkeit an. Diese Tatsache macht es wichtig, dass Spieler schnellstmöglich
eine Rückmeldung des Spiels auf ihre Eingaben erhalten.
4.1.2
Real Time Strategy (RTS)
Die Bezeichnung „Strategiespiel“ ist im Computerspiele-Bereich meist synonym zu verstehen mit taktischer Kriegsführung oder Wirtschaftssimulation.
Der Spieler blickt dabei oft aus der Vogelperspektive auf eine Kartenansicht, aus der einzelne Einheiten oder ganze Truppen befehligen kann. Dies
geschieht üblicherweise per Maussteuerung. Will man seine Einheiten eine Aktion ausführen lassen, so klickt man zunächt einzelne Einheiten an
oder zieht einen Rahmen um mehrere von ihnen, um sie zu selektieren.
28
4.1
Anschließend wird mit einem weiteren Mausklick ein Befehl erteilt. Klickt
man also auf einen Punkt in der Landschaft, dann bewegen sich die selektierten Einheiten zu ihm. Klickt man auf feindliche Einheiten, dann ist dies
üblicherweise der Befehl zum Angriff.
Falls das Spiel abwechselnd, in Runden aufgeteilt gespielt wird, spricht
man von einem rundenbasierten Strategiespiel (vom Englischen: turn-based
strategy game). Diese Spielvariante ist netzwerktechnisch betrachtet unproblematisch, da sie durch abwechselndes Spielen keine besonderen Anforderungen an die Geschwindigkeit der Datenübertragung stellt. Um die
Spielbarkeit zu gewährleisten würde es hier genügen, nach dem Ende eines
Spielzugs die Änderungen der Spielwelt an den nächsten Spieler weiterzugegeben.
Als „Echtzeitstrategiespiel“ (vom Englischen: real-time strategy game,
oder kurz RTS) wird ein Strategiespiel bezeichnet, wenn alle Parteien gleichzeitig agieren. Diese Variante hingegen stellt gleich mehrere Anforderungen an die Netzwerkfunktionalität. Es stellt sich zunächst das übliche Problem der Verzögerung durch Paketumlaufzeiten im Netzwerk: Wie schon
bei First Person Shootern wäre es im Idealfall erwünscht, unmittelbar eine Reaktion auf eigene Eingaben zu spüren, um schnellstmöglich Änderungen der Spielwelt zu erfahren. Strategiespiele verstecken die anfallende
Eingabeverzögerung oft dadurch, dass sie den Sound-Effekt eines erteilten Befehls unmittelbar ausgeben, so dass ein Spieler Rückmeldung auf
seine Eingabe erhält. Die Auswirkung seiner Eingabe wird jedoch erst später vom Spiel verarbeitet (vgl. [Fie], What every programmer needs to know
about game networking). Allgemein ist zu vermuten, dass beim Spielen von
Strategiespielen eine höhere Toleranz gegenüber Verzögerungen von Eingaben existiert, da man üblicherweise nicht direkt die Bewegungen einer
bestimmten Spielfigur steuert.
Jedoch hat man es potentiell mit vielen zu synchronisierenden Objekten zu tun. Damit wächst auch die zu übertragende Datenmenge, sofern
man nicht das Spiel auf dem Computer jedes Spielers ausführt und ausschließlich die Eingaben von Spielern überträgt (vgl. Abschnitt 3.2.1). Eine
Anforderung wäre hier, eine Möglichkeit zu finden, die anfallende Datenmenge effizient zu reduzieren.
29
4.1
4.1.3
Massively Multiplayer Online (MMO)
Das Genre der Massively-Multiplayer-Online-Spiele (kurz MMO) deutet
bereits mit seiner Bezeichnung an, dass es sich hier um Mehrspieler-Spiele
mit außergeöhnlich hoher Spielerzahl handelt. Die Bezeichnung „MMO“
ist oft auch verbunden mit dem Begriff „Rollenspiel“ (vom Englischen: Role Playing Game, kurz RPG). Der vermutlich bekannteste Vertreter dieses
Genres ist das Spiel „World of Warcraft“. Der Begriff Rollenspiel betont
hier, dass die Entwicklung der Attribute einer Spielfigur einen großen Teil
des Spiels darstellt. Durch das Bewältigen verschiedener Aufgaben, wie etwa dem Sammeln von Gegenständen oder dem Bekämpfen von Gegnern,
wächst die Spielfigur in ihren Fähigkeiten. Oft ermutigt diese Spielform die
Kooperation zwischen Spielern, die sich zu Verbünden zusammenschließen können, um schwierige Kämpfe zu überstehen und sich gegenseitig zu
ergänzen.
Auf Grund ihres oft relativ langsamen Spielablaufs liegt es nahe, dass
MMOs üblicherweise nicht die hohe Geschwindigkeit und Genauigkeit benötigen, wie sie beispielsweise bei First Person Shootern wichtig ist. Jedoch
ist die Menge der zu übertragenden Daten potentiell groß, bedingt durch
die hohe Anzahl von gleichzeitigen Spielern. Eine wichtige Anforderung
wäre hier also ebenfalls, Möglichkeiten der Datenreduktion zu finden.
Zusätzlich finden MMOs üblicherweise in einer persistenten Spielwelt
statt, das heißt dass sich die Spielwelt auch in Abwesenheit des Spielers
nachhaltig verändern kann. Wenn der Spieler also das nächste Mal dem
Spiel beitritt, muss er stets den aktuellen Stand der Spielwelt erhalten. Diese Möglichkeit des späteren erneuten Beitretens (vom Englischen: Late Join)
ist eine weitere Anforderung eines Massively-Multiplayer-Online-Spiels.
4.1.4
Rennspiele
In Rennspielen bzw. Rennsimulationen ist es üblich, dass der Spieler die
Kontrolle über ein bestimmtes Fahrzeug übernimmt und gleichzeitig gegen
andere Fahrer bzw. Spieler antritt. Je nach Spiel kann die Komplexität sehr
unterschiedlich ausfallen. Solange es sich beispielsweise um ein Spiel handelt, in dem die gesamte Welt statisch ist, sich also außer den Fahrzeugen
nichts verändert, brauchen auch nur die Daten der einzelnen Fahrzeuge
30
4.1
selbst übertragen zu werden. Oft besteht die hauptsächliche Interaktionsmöglichkeit mit anderen Spielern darin, dass Fahrzeuge miteinander kollidieren können. Bei einigen Rennspielen ist aber selbst dies nicht der Fall.
Beim Spiel Trackmania Nations Forever beispielsweise werden die Fahrzeuge von Mitspielern zwar angezeigt, es ist jedoch nicht möglich, mit ihnen zu kollidieren. Dieser Fall stellt geringe Ansprüche an die Netzwerkfunktionalität, da lediglich die Positionen und Ausrichtungen der Fahrzeuge übertragen werden müssen.
Kompliziert wird es bei Rennspielen, die komplexe Physiksimulationen
beinhalten, Kollisionen zulassen oder eine dynamische Spielwelt aufweisen. In diesem Falle wäre sowohl eine rasche Reaktion erwünscht, als auch
eine effiziente Reduzierung der Datenmenge. Ein vereinfachender Faktor
könnte allerdings sein, dass wir von Fahrzeugen eine gewisse Trägheit gewohnt sind: Wenn man das Lenkrad einschlägt, erwartet man üblicherweise nicht einen spontanen Richtungswechsel seines Fahrzeugs, sondern vielmehr eine fließende, beschleunigte Bewegung. Dies könnte, zumindest bei
realistischen Simulationen, ein gewisses Zeitfenster für Paketumlaufzeiten
ermöglichen. Allgemein lässt sich jedoch feststellen, dass die Anforderungen ähnliche sind wie bei First Person Shootern und Echtzeitstrategiespielen.
31
4.2
Auswertung
4.2
Auswertung
In unterschiedlichen, typischen Spiele-Genres zeitkritischer Spiele sind
durchaus ähnliche Probleme zu lösen. Eine besonders wichtige Rolle allgemein kommt sichtbaren Bewegungen zu: Wann immer Objekte in Bewegung geraten oder ihre Bewegung ändern, ist eine möglichst schnelle Reaktion des Gesamtsystems erwünscht. Dies ist insbesondere dann eine technische Herausforderung, wenn Objekte sich unregelmäßig bewegen können.
Problematisch wäre hier die Synchronisierung beschleunigender und zum
Stillstand kommender Objekte, wie etwa Spielfiguren oder Fahrzeugen.
Auch die Synchronisierung und Behandlung von Kollisionen mit anderen bewegten sowie statischen Objekten ist ein wiederkehrendes Problem: Beim First Person Shooter wären beispielsweise die Kollisionen von
Spielern mit Wänden (oder allgemein statischen Begrenzungen des Spielfeldes), Projektilen, Explosionen oder Gegnern und anderen Spielfiguren
zu synchronisieren. Im Falle des Strategiespiels wären es die Kollisionen
der zu befehligenden Einheiten mit dem Terrain oder Bauten und anderen
Einheiten. Bei Rennspielen wären es die Kollisionen mit anderen Fahrzeugen oder der Streckenbegrenzung und bei Massively-Multiplayer-OnlineSpielen wären es ebenfalls Kollisionen mit Spielfiguren, Gegnern oder Gegebenheiten des Terrains. Hier lassen sich also große Schnittmengen von
Anforderungen bei stark unterschiedlichen Spielen und Spielemechaniken
ausmachen.
32
4.2
Auswertung
Zusammenfassend lässt sich erkennen, dass selbst bei einer Stichprobe
aus nur vier verschiedenen Videospiele-Genres überwiegend ähnliche Probleme zu lösen sind. Teilweise kommt einem bestimmten Faktor eine außergewöhnlich hohe Bedeutung zu. Im Falle eines Massively-MultiplayerOnline-Spiels ist es beispielsweise unverzichtbar, den Status der Spielwelt
an beitretende Spieler zu übermitteln. Allgemein ergeben sich die folgenden Anforderungen an eine performante Network Engine für zeitkritische
Videospiele:
• Eingaben des Spielers müssen möglichst schnell spürbar (üblicherweise vor allem sichtbar oder hörbar) gemacht werden können.
• Die zu übertragende Datenmenge muss sich reduzieren lassen.
• Der Status der Spielwelt muss nachträglich an beitretende Spieler
übermittelt werden können.
33
5
Konzepte und Ansätze zur Performanzsteigerung
Unter Berücksichtigung der zuvor aufgestellten Anforderungen sollen in
diesem Abschnitt Lösungen gefunden werden, mit deren Hilfe sich die
technischen Probleme bei der Datenübertragung im Netzwerk lösen lassen.
5.1
Einbeziehung psychologischer Faktoren
Zunächst sollen bestimmte psychologische Faktoren erläutert werden, die
mit einer bestimmten Spielmechanik verknüpft sein können. Ein Beispiel
für solch einen Fall ist der Wurf einer Granate im Spiel Halo: Reach, wie
er in [Ald11] beschrieben wird. Hier führt das Drücken eines Knopfes zunächst zum Beginn einer Wurf-Animation. Erst nach Ablauf der Animation
wird die Granate geworfen.
Damit die Möglichkeit des Cheatings unterbunden werden kann (vgl.
Abschnitt 3.6) soll sichergestellt sein, dass ein Spieler nur dann eine Granate werfen kann, wenn der Server dies authorisiert. Aus diesem Grund muss
der Server um Erlaubnis gebeten werden, nachdem ein Spieler den Knopf
zum Werfen einer Granate gedrückt hat. Dies heißt wiederum, dass die Erlaubnis frühestens nach Ablauf der Pakteumlaufzeit beim Client eintreffen
kann. Die anfallende Verzögerung nach dem Drücken des Knopfes kann
man nun ab unterschiedlichen Zeitpunkten an den Spieler weitergeben.
Das Sequenzdiagramm in Abbildung 6 verdeutlicht eine dieser Möglichkeiten. Anders als im Standard von Sequenzdiagrammen festgelegt sind
die Pfeile zwischen den Akteuren „Client“ und „Host“ hier geneigt. Dies
soll die Verzögerung zwischen Client und Host deutlich machen.
34
5.1
Abbildung 6: Sequenzdiagramm des Wurfs einer Granate beim Abwarten einer
Server-Antwort8
Im Falle von Abbildung 6 wird nach dem Registrieren des Knopfdrucks
auf dem Client (im Diagramm gekennzeichnet durch „Button press“) zunächst auf eine Antwort des Servers gewartet. Der Spieler spürt in diesem
Fall die gesamte Latenz - im Diagramm mit „Here’s the lag!“ gekennzeichnet -, bevor er eine Reaktion auf seinen Knopfdruck sieht und die WurfAnimation beginnt (im Diagramm: „Throw animation starts“). Sind die
Antwortzeiten im Netzwerk gering, also in der Größenordnung einzelner
Millisekunden, so stellt dies kein Problem dar. Doch für das Spielen in Netzen, in denen hohe Antwortzeiten auftreten können - wie etwa beim Spielen über das Internet - ist dieser Ansatz problematisch:
„We have a problem here. We’re waiting our round trip time before we’re giving the client any feedback on his button press. Players hate this, players hate it
with a passion.“ ([Ald11], Throwing a Grenade)
Ein möglicher Lösungsansatz für dieses Problem ist nun, die Simulation, oder zumindest einen Teil davon, ebenfalls auf dem Client-System auszuführen, um eine unmittelbare (meist vor allem visuelle) Rückmeldung
auf Eingaben des Spielers liefern zu können. Dies ist für Spiele, in denen es
8
Quelle: [Ald11]
35
5.1
um Sekundenbruchteile geht, notwendig. Bei dieser Vorgehensweise entsteht jedoch ein Problem: Der Server kann von den Eingaben des Benutzers und möglichen, unmittelbaren Einwirkungen auf die Simulation erst
zu einem späteren Zeitpunkt erfahren. Man hat somit auf dem Client einen
vom Server abweichenden Simulationsstatus geschaffen bzw. eine „Latenzschuld“ (vom Englischen: latency debt) erzeugt, die man zu einem späteren
Zeitpunkt kompensieren muss. Abbildung 7 zeigt den Ablauf einer solchen
Implementierung.
Abbildung 7: Sequenzdiagramm des Wurfs einer Granate bei sofortiger Reaktion
des Client-Systems, ohne vorherige Authorisierung durch den Server9
9
Quelle: [Ald11]
36
5.1
Für Sonderfälle, wie den hier dargestellten Wurf einer Granate, lässt
sich jedoch eine elegante Lösung finden. Die Grundidee ist, die anfallende Latenz nicht direkt nach der Eingabe auftreten zu lassen. Dieser Ansatz
stimmt zudem mit den Anforderungen an eine performante Network Engine überein (vgl. Abschnitt 4.2). Abbildung 8 zeigt die tatsächliche Implementierung im Spiel Halo: Reach.
Abbildung 8: Sequenzdiagramm des Wurfs einer Granate, wie er im Spiel Halo:
Reach implementiert wurde10
Bei dieser letzten Variante wird direkt nach dem Drücken des Knopfes
die Wurfanimation gestartet, also unmittelbar eine Rückmeldung geliefert.
Erst nach Ablauf der Animation wird eine Anfrage an den Server geschickt,
ob der Spieler tatsächlich berechtigt ist, die Granate zu werfen. Ist dies nicht
der Fall, verschwindet die Granate nach Eintreffen der Server-Antwort aus
der Hand der Spielfigur.
10
Quelle: [Ald11]
37
5.2
Control Data / Sampling Input
Nun mag die Frage aufkommen, inwiefern dieser Ansatz besser ist, als
die in Abbildung 6 dargestellte Variante, denn auch hier wird die Latenz
letztendlich an den Spieler weitergegeben. Der entscheidende Faktor hierbei ist jedoch, dass die Verzögerung im letzten Fall (vgl. Abbildung 8) von
Spielern unbemerkt bleibt und somit die Spielbarkeit nicht beeinflusst:
„Players don’t notice. They literally don’t see this. This can get up to 100, even
150 milliseconds.“ ([Ald11], Throwing a Grenade)
Ein Sonderfall wie dieser, der durch eine besondere Spielmechanik begünstigt wird, ist potentiell schwierig in die Funktionalität einer allgemeinen performanten Network Engine zu integrieren. Er macht allerdings deutlich, wie wichtig es generell ist, Spielern unmittelbar nach einem Tastendruck eine Reaktion auf ihre Eingaben zu liefern und auch Spielmechaniken in eventuelle Lösungsansätze mit einzubeziehen.
5.2
Control Data / Sampling Input
Wie bereits im Abschnitt 3.2 erläutert, ist es ein üblicher Ansatz, die Eingaben von Spielern abzufragen (vom Englischen: Sampling Input) und sie über
das Netzwerk weiterzuleiten, damit sie anschließend vom Spiel verarbeitet
werden können. Einerseits können diese übertragenen Eingaben dazu genutzt werden, den Spielstatus direkt zu beeinflussen. Sie können aber auch
der zusätzlichen Kontrolle dienen. Dies ist mit „Control Data“ (zu Deutsch:
Kontrolldaten) gemeint: Beim Betätigen einer Taste auf der Tastatur handelt
es sich üblicherweise um eine sogenannte digitale Eingabe. Das heißt, ein
Knopf kann nur zwei Zustände einnehmen, gedrückt und ungedrückt. Der
nötige Speicherplatz, um diese Information in einem Netzwerkpaket unterzubringen ist somit - selbst in unkomprimierter Form - gering. Diese
Steuerdaten können also selbst dann häufig übertragen werden, wenn eine
Verbindung nur eine geringe Datenübertragungsrate zulässt. Durch eine
häufigere Aktualisierung als die des Simulationsstatus der Spielwelt, kann
somit die Vorhersage (vgl. Abschnitt 5.6) zukünftiger Ereignisse verbessert
werden. Beispielsweise könnte die Information eintreffen, dass ein Spieler
den Knopf, der seine Spielfigur vorwärtslaufen lässt, nicht mehr drückt.
In diesem Falle ließe sich früher voraussagen, wo und wann das bewegte Objekt (die Spielfigur) zum Stillstand kommen wird, noch bevor neue
38
5.3
Client-side simulation / Aufteilung von Rechenlast
Positionsdaten eingetroffen sind. Dies könnte also auch eine Erhöhung der
Reaktionsgeschwindikeit des Spiels bewirken.
5.3
Client-side simulation / Aufteilung von Rechenlast
Mit „client-side simulation“ (zu Deutsch: clientseitige Simulation) ist gemeint,
dass Teile der Simulation vom Server auf Clients verlagert werden. Wann
immer man Teile der Authorität vom Server nimmt und sie an Clients übergibt, eröffnet man jedoch Möglichkeiten zur Manipulation (vgl. Abschnitt
3.6). Es kann aber gleichzeitig den Server entlasten, falls die Berechnung
der Simulation komplex ist. Dies könnte beispielsweise der Fall sein bei
aufwändigen Physiksimulationen. Hier müssen oft viele eigenständige Objekte möglichst realistisch von physikalischen Gegebenheiten wie Gravitation oder Momentum beeinflusst werden. Statt das Verhalten jedes einzelnen Körpers allein vom Server berechnen zu lassen, kann die Rechenlast
auf verschiedene Systeme von Mitspielern im Netzwerk aufgeteilt werden.
Beispielsweise bietet sich dies an, wenn Ereignisse in der Nähe eines bestimmten Spielers nicht relevant sind für seine Mitspieler, womöglich deshalb, weil der Spieler nicht zu sehen ist und auch sonst keinen Einfluss nehmen kann auf den Simulationsstatus von Mitspielern. Hier würde es sich
anbieten, rechenaufwändige Prozeduren, die nur für diesen einen Spieler
Relevanz haben, auch nur auf dessen Computer lokal berechnen zu lassen,
den Server so zu entlasten und die Spielbarkeit für Mitspieler zu garantieren.
Für bewegte Objekte kann eine clientseitige Simulation zudem genutzt
werden, um eine flüssige Bewegung auch ohne den häufigen Empfang neuer Positionsdaten möglich zu machen: Wird die gleiche Simulation auf ein
bewegtes Objekt angewandt, wie dies sonst nur auf dem Server geschieht,
so erfolgt beim Eintreffen neuer Positionsdaten kein ruckartiger Sprung
von der vorherigen zur aktuellen Position. Dies kann optisch zu einer Verbesserung der Performanz beitragen. Ein ähnlicher Effekt lässt sich allerdings auch durch das Verfahren „Prediction“ erreichen (vgl. Abschnitt 5.6),
ohne dabei Authorität vom Server zu nehmen.
39
5.4
Absichtliche Eingabelatenz
5.4
Die Erzeugung absichtlicher Eingabelatenz mag kontraintuitiv erscheinen,
wenn es um das Verbergen von Latenz und Latenzschwankungen geht. Jedoch verbirgt sich hier - zumindest theoretisch - ein Verbesserungspotential
der Spielbarkeit.
Dieser Ansatz ist allerdings weniger technischer, sondern mehr psychologischer Natur. Natürlich wird es besonders angenehm von Spielern empfunden (wie übrigens allgemein von Benutzern grafischer Oberflächen),
wenn ein Knopfdruck unmittelbar eine spürbare Reaktion auslöst. Je nach
Spiel können dabei verzögerungsfreie Rückmeldungen unterschiedlicher
Art wichtig sein, wie etwa Vibrationen des Eingabegeräts. Üblicherweise handelt es sich bei spürbaren Reaktionen jedoch vor allem um grafische Veränderungen oder die Ausgabe von Sound-Effekten. Wenn man
beispielsweise eine Spielfigur per Knopfdruck springen lässt, möchte man
schnellstmöglich den Sprung sehen oder auch gleichzeitig einen Ton dazu
hören. Mittels clientseitiger Simulation könnte diese unmittelbar sichtbare
und hörbare Reaktion auf Benutzereingaben zwar erreicht werden, erzeugt
aber unter Umständen neue Probleme und Artefakte, wie etwa eine Latenzschuld, die man nachträglich abtragen muss (vgl. Abschnitt 5.1). Damit ein
Client unmittelbar reagieren kann, muss eine Aktion ausgeführt werden,
noch bevor der Server diese authorisiert oder davon Kenntnis erhalten hat.
Eine Authorisierung kann also nur nachträglich geschehen, indem der Server nach der Übermittlung eines Clients prüft, ob ein Spieler die Aktion
hätte ausführen dürfen. Ein solcher Ansatz wurde bereits in Abschnitt 5.1
anhand von Abbildung 7 erläutert, jedoch als problematisch eingestuft. Unter Umständen müsste eine auf dem Client unmittelbar ausgeführte Aktion
nachträglich zurückgenommen werden, wenn der Server festellt, dass der
Client diese Aktion nicht hätte durchführen dürfen. Ein Beispiel dafür wäre eine Kollision der Spielfigur mit einem Hindernis, über das der Client
zum Zeitpunkt der Ausführung einer Spielfigurbewegung nicht informiert
gewesen ist. Aus Sicht des Spielers würde sich seine Spielfigur zunächst
unmittelbar in die gewünschte Richtung bewegen, dabei in das Hinternis
eintreten und einen Sekundenbruchteil später wieder zu ihrer ursprünglichen Position zurückgesetzt werden, nachdem der Server die Kollision
festgestellt und den Client korrigiert hat.
40
5.4
Als weiteres Problem kommt nun hinzu, dass die Verzögerungszeit bei
der Datenübertragung im Netzwerk schwankt. Server-Antworten mit nachträglichen Korrekturen können also mit stark unterschiedlicher Verzögerung beim Clientsystem eintreffen. Dies hat zur Folge, dass ein Spieler den
Eindruck erhält, die Spielwelt reagiere unregelmäßig auf seine Eingaben.
Man spricht hier auch vom Phänomen des „Jitterings“ (zu Deutsch: Taktzittern) beim übertragen von digitalen Signalen. Dies ist besonders problematisch, da Menschen sich im Allgemeinen zwar recht gut auf ein gewisses
Maß konstanter Verzögerung zwischen ihren Eingaben und den Reaktion
darauf einstellen können, nicht jedoch, wenn die Verzögerung variiert.
Ein psychologisch motivierter Lösungsansatz könnte daher sein, absichtlich ein geringes Maß an Eingabe-Verzögerung (vom Englischen: Input
Lag) zu erzeugen. Dies könnte dazu dienen, die Spürbarkeit von ServerKorrekturen, wie die beschriebene Kollision, allgemein zu reduzieren und
gleichzeitig das Reaktionsverhalten der Spielwelt konstant zu halten: Nachdem also der Spieler eine Eingabe gemacht hat, reagiert die clientseitige
Simulation nicht unmittelbar, sondern verzögert absichtlich um Latenzschwankungen der Netzwerkübertragung möglichst häufig zu verbergen.
„Möglichst häufig“ deshalb, weil es sporadisch zu außergewöhnlich hohen Verzögerungen (vom Englischen: Latency spikes) kommen kann. Diese
könnten zwar theoretisch ebenfalls durch eine sehr hohe künstliche Eingabelatenz verborgen werden, nur wäre dies eine unelegante Lösung, wenn
die Eingabelatenz die meiste Zeit deutlich niedriger liegen könnte. Obendrein würde man hier bei einer künstlichen Verzögerungszeit, die nah an
der Paketumlaufzeit liegt, eine ähliche Performanz erhalten wie bei einem
Client, der eine reine Terminal-Funktion erfüllt (vgl. Abschnitt 3.2.2).
Die Höhe dieser künstlichen Latenz könnte automatisch und adaptiv
festgelegt werden. Zwar ist der Grundgedanke hier, dass der Spieler sich
auf ein bestimmtes, gleichbleibendes Maß an Verzögerung einstellen soll,
aber wenn eine Anpassung des Wertes langsam über einen längeren Zeitraum erfolgt, könnte sich diese Änderung als unproblematisch herausstellen. In jedem Falle müsste zunächst hinreichend viel Information über die
Charakteristik der jeweiligen Internetverbindung gesammelt werden, um
einen effektiven Wert für die Eingabelatenz zu wählen. Es müssten also
Umlaufzeiten mehrerer Pakete laufend analysiert werden. Ausgehend von
41
5.5
Dedizierte (dedicated) Server
der Annahme, dass diese Messungen repräsentativ sind, könnte man nun
aus diesen Daten Erkenntnisse über das allgemeine Latenzverhalten der
Netzwerkverbindung gewinnen. Diese könnten dann als Grundlage für die
Wahl der Höhe der Eingabeverzögerung dienen.
Je nach Spielegattung werden sich die Toleranzbereiche einer solchen
Verzögerung stark unterscheiden. Beispielsweise können in einem Strategiespiel (vgl. Abschnitt 4.1.2), in dem man per Mausklick seine Truppen
zu einem bestimmten Punkt auf der Landschaft bewegt, die Verzögerungswerte relativ hoch sein, ohne vom Spieler überhaupt bemerkt zu werden.
Handelt es sich jedoch um Spiele, in denen es auf schnelle Reaktionen ankommt, wie First Person Shooter (vgl. Abschnitt 4.1.1 ), so können schon
kleinste Verzögerungen empfindlich stören.
5.5
Dedizierte (dedicated) Server
Ein Server wird dann als „dediziert“ (vom Englischen: dedicated) bezeichnet, wenn er ausschließlich für das Erfüllen von Netzwerkdiensten vorgesehen ist und keine weiteren rechenintensiven Anwendungen ausführt. Somit kann sichergestellt werden, dass möglichst viel Rechenzeit zum erledigen der Servertätigkeit zur Verfügung steht. Bei Videospielen ist es üblich,
zwischen „Dedicated Server“ und „Listen Server“ zu unterscheiden. „Listen Server“ wird ein Server genannt, wenn er direkt von einem Mitspieler
gestartet und auch auf dessen Rechner ausgeführt wird. Zugleich nutzt der
Spieler den selben Rechner als einen Client für das laufende Spiel. Je nach
Komplexität des jeweiligen Spiels kann dies bereits zu einer starken Auslastung des Servers führen, weshalb ein Listen-Server problematisch sein
kann. Auch wird ein Listen-Server üblicherweise beendet, sobald der Spieler, der den Server gestartet hat, das Spiel verlässt. Ein dedizierter Server
löst dieses Problem und erlaubt es, verfügbare Ressourcen besser zu nutzen.
5.6
Prediction
Begrenzte Datenübertragungsraten machen es erforderlich, dass Server nur
relativ selten Daten verschicken. Wenn die maximal verfügbare Datenüber-
42
5.6
Prediction
tragungsrate beispielsweise bei 64kbps liegt, können gerade einmal 30 Netzwerkpakete mit einer Größe von ungefähr 256byte verschickt werden (vgl.
Abschnitt 3.4). Ein Spieler jedoch kann kontinuierlich Eingaben machen. Im
Idealfall, bei clientseitiger Simulation etwa, nimmt er die Reaktionen auf
seine Eingaben als fließende Veränderungen wahr. Die meiste Zeit jedoch
weicht das, was ihm das Client-System zeigt und wonach er sich richtet,
vom tatsächlichen Simulationsstatus des Servers ab.
Nun lassen sich jedoch durch
das Auswerten des letzten bekannten Simulations-Status Vorhersagen treffen für bereits laufende Vorgänge und Veränderungen. Zwar
kann für ein ruhendes Objekt in der
Regel nicht vorhergesagt werden,
wann oder ob es sich jemals bewegen wird, aber wenn es bereits in
Bewegung versetzt wurde und relevante Faktoren, wie etwa die aktuelle Geschwindigkeit des Objekts
Abbildung 9: Prediction11
oder statische Hindernisse in seinem Weg bekannt sind, kann man mit hoher Wahrscheinlichkeit voraussagen, wo sich das Objekt zu einem späteren Zeitpunkt befinden wird. Dieses Konzept wird trefflicherweise als „Prediction“ (zu Deutsch: Voraussage) bezeichnet und kann sowohl auf dem Client als auch auf dem Server
geschehen. Man spricht dabei entweder von „client-side prediction“ bzw.
„Server-side prediction“.
Abbildung 9 zeigt ein Beispiel: Die grünen Sterne symbolisieren die eingetroffenen Positionsdaten eines Objekts. Die Pfeile bzw. Vektoren zeigen
an, in welche Richtung und wie schnell es sich zu diesen Zeitpunkten bewegt hat. Anhand dieser Daten lässt sich vorhersagen, dass sich das Objekt
aktuell vermutlich an der Position des weißen Punkts befindet.
Dieses Verfahren kann also dazu genutzt werden, Informationen bis zur
nächsten Server-Antwort darzustellen. Sofern eine Vorhersage, die durch
11
Quelle: [Ald11]
43
5.7
Relevanz
dieses Verfahren gemacht wurde, zutrifft, fällt die nachträgliche Validierung bzw. Korrektur durch den Server dementsprechend unspürbar aus.
Wenn beispielsweise zwischen dem Eintreffen neuer Positionsdaten vorhergesagt wird, wohin ein Objekt sich bewegen wird (und dies zutrifft),
findet beim Setzen der neuen Position kein deutlicher Positionssprung auf
die neue Position statt. Selbst wenn eine Abweichung zur vorhergesagten
Position auftritt, sollte diese gering genug sein, dass ein Positionssprung
nur unauffällig ausfällt.
5.7
Relevanz
Hierbei handelt es sich um einen Beitrag zur Datenreduktion. Mit „Relevanz“ ist gemeint, dass unter Umständen bestimmte Ereignisse der Spielwelt nicht übertragen werden müssen, da sie bestimmte Spieler nicht betreffen. Denkbar wäre der Fall, dass Ereignisse in weiter Entfernung vom
Spieler stattfinden oder der Spieler bestimmte Ereignisse nicht sehen kann.
Ein Ansatz wäre also, vor dem Zusammenstellen eines Netzwerkpakets
zu überprüfen, welche Daten tatsächlich relevant sind für dieses ClientSystem.
44
5.8
Priorisierung
5.8
Priorisierung
Auch bei der Priorisierung handelt es sich um eine Möglichkeit zur Datenreduktion. Ähnlich wie beim Lösungsansatz der Relevanz will man hierbei
die Wichtigkeit bestimmter Objekte bewerten. Das Ziel von Priorisierung
ist jedoch, innerhalb bestimmter Grenzen für Paketgrößen zu bleiben: Sind
mehr relevante Daten zu übertragen, als in einem Netzwerkpaket einer bestimmten Größe unterzubringen sind, soll durch Priorisierung entschieden
werden, welche Daten am wichtigsten sind. Die Kriterien für die Bedeutung bestimmter Objekte können hierbei theoretisch frei gewählt werden.
Hierbei können auch psychologische Aspekte eine Rolle spielen, wenn etwa einige Objekte besondere Aufmerksamkeit verdienen. Beispielsweise
wird Granaten beim Spiel „Halo: Reach“ eine hohe Priorität beigemessen,
da die Entwickler die Erfahrung gemacht haben, dass Spieler ihre geworfenen Granaten sehr genau beobachten.
45
6
Praktische Umsetzung
Insgesamt sollen im Rahmen dieser Arbeit zwei Applikationen entstehen:
Zum einen die Network Engine selbst, zum anderen eine Demo, welche
die Funktionen der Engine verwendet und präsentiert. Die zu entwickelnde Network Engine wird auf den Namen „Humble Network Engine“ (zu
Deutsch etwa: bescheidene Network Engine), kurz „HNE“ getauft. Die DemoApplikation erhält den Titel „HNE-Demo“. In diesem Abschnitt soll der
Funktionsumfang beider Applikationen erläutert werden, die während des
Entwicklungsprozesses entstanden sind.
Zunächst wird unter Abschnitt 6.1 ein Überblick gegeben über die Werkzeuge und Bibliotheken, die bei der Entwicklung verwendet wurden. Im
Anschluss erläutert Abschnitt 6.2 die Unterteilung des Programmcodes, sowie die Entscheidungen, die beim Entwurf getroffen wurden. Auch werden
dabei bereits einige wichtige Funktionen des entstandenen Systems erklärt.
Eine ausführliche Erläuterung der Schlüsselfunktionen findet im darauffolgenden Abschnitt 6.3 statt. Dort werden die für die „Humble Network
Engine“ verfolgten Ansätze zur Steigerung der Performanz erläutert. Abschließend wird in Abschnitt 6.4 die Demo-Applikation vorgestellt.
6.1
Programmiersprache und Bibliotheken
C++ Die Entscheidung, welche Programmiersprache für die praktische
Umsetzung verwendet werden sollte, fiel auf C++. Diese Sprache ist besonders durch ihre hohe Verbreitung beliebt. Zudem bietet sie die problemlose
Anbindung von vielen zusätzlichen Bibliotheken wie etwa SDL oder AntTweakBar.
Winsock
Zur Implementierung der Netzwerkfunktionalität wurde die Bi-
bliothek „Windows Sockets 2“, kurz „Winsock“, gewählt. Dabei handelt es
sich um eine Funktionssammlung, die das Sockets-Paradigma von BSDUNIX (Berkeley Software Distribution) verwendet. Das heißt: Ähnlich als
schriebe man Daten in eine Datei, können Daten über das Netzwerk von
Socket zu Socket geschickt werden.
46
6.1
Programmiersprache und Bibliotheken
Somit wurde sich hier gegen die Verwendung einer bestehenden Lösung wie etwa der Network Engine „RakNET“ entschieden. Grund hierfür war, dass eine Anwendung entstehen sollte, an der eindeutig der Einfluss bestimmter Latenz-Faktoren wie Paketverlust oder Schwankungen
der Übertragungsrate zu erkennen ist. Es sollte also eine möglichst geringe
Software-Basis existieren, damit sichergestellt ist, dass beobachtete Phänomene nicht von den Funktionen weiterer Software beeinflusst werden. Dies
bringt zwar einen erhöhten Implementierungsaufwand mit sich, jedoch minimiert man somit die Möglichkeit fremder Einflussfaktoren.
SDL SDL (Simple DirectMedia Layer) ist eine freie Multimedia-Bibliothek,
die auf einer Vielzahl von Plattformen verfügbar ist. Sie dient als Schnittstelle zu Grafik-, Sound-, oder Eingabegeräten. Insbesondere eignet sie sich
für die Entwicklung von Videospielen. Da SDL viele Plattformen unterstütz, kann von einer hohen Portabilität der mit SDL entwickelten Software ausgegangen werden. Im Rahmen dieser Arbeit wurde SDL für die
HNE-Demo-Applikation verwendet, um zum Beispiel die Verwaltung des
Applikationsfensters zu übernehmen oder die Registrierung und Verarbeitung von Eingaben auf der Tastatur.
OpenGL
OpenGL (Open Graphics Library) ist eine weit verbreitete, quel-
loffene und plattformunabhängige Programmierschnittstelle zur Grafikprogrammierung. Für die Entwicklung der „Humble Network Engine“ wurde
OpenGL hier nicht genutzt, jedoch für die Ausgabe der Grafik des HNEDemo-Programms.
AntTweakBar Für die HNE-Demo sollte es möglich sein, zur Laufzeit interaktiv Server-Variablen der „Humble Network Engine“ zu ändern. Aus
diesem Grund wurde die Bibliothek AntTweakBar verwendet. AntTweakBar ist eine C/C++ Bibliothek, mit deren Hilfe sich eine grafische Liste mit
manipulierbaren Werten erstellen und im Programmfenster anzeigen lässt.
Die angezeigten Werte lassen sich dann zur Laufzeit durch Maus- und Tastatureingaben verändern. Somit ist diese Bibliothek attraktiv, um die Auswirkungen bestimmter Änderungen sichtbar zu machen.
47
6.2
Aufbau der Software
6.2
Aufbau der Software
In diesem Abschnitt soll ein Überblick gegeben werden über die Struktur
einzelner Programm-Komponenten der „Humble Network Engine“, sowie
der HNE-Demo.
6.2.1
Header-Dateien
HNE_Constants.h Für die Performanz der „Humble Network Engine“
spielen viele verschiedene Faktoren eine Rolle. Beispielsweise ist von entscheidender Bedeutung, wie häufig Netzwerkpakete verschickt und empfangen werden können, oder wie häufig die Simulation der Spielwelt auf
dem Server ausgeführt wird. Diese und ähnliche Faktoren sind im Programm durch Zahlenwerte zu beeinflussen, die beispielsweise ein
Ausführungs-Intervall in Millisekunden angeben. Es ist daher hilfreich,
möglichst viele dieser Werte in einer Datei zu vereinen. Deshalb dient die
Datei HNE_Constants.h als Sammlung initialer Werte, Makros und Variablen, die den Programmablauf der „Humble Network Engine“ und der
HNE-Demo beeinflussen.
HNE_Base.h Um die Inklusion wichtiger Header-Dateien zu vereinfachen, existiert die Datei HNE_Base.h. In ihr sind alle externen Bibliotheken
wie SDL oder Winsock eingebunden, sowie zusätzlich einige Strukturen
definiert. Jede Klasse der „Humble Network Engine“ inkludiert
„HNE_Base.h“ und muss anschließend ausschließlich HNE-interne HeaderDateien einbinden.
6.2.2
C-Strukturen
HNE_ClientInfo Diese Struktur wurde geschaffen, um die Daten eines
bestimmten Client-Systems, die für die Netzwerkübertragung relevant sind,
zu speichern. Anhand der darin enthaltenen und zufällig generierten
Integer-Variablen clientID lässt sich jeder Client innerhalb der „Humble
Network Engine“ eindeutig identifizieren, so dass Netzwerknachrichten an
seine IP-Adresse verschickt und von ihm empfangen werden können. Jede
48
6.2
Aufbau der Software
HNE_App besitzt eine HNE_ClientInfo-Struktur, da jede HNE_App als
Client gestartet werden kann.
HNE_UserInput Die HNE_UserInput-Struktur ist dem Gedanken
entsprungen, möglichst häufig die Eingaben übertragen zu können, die
ein Spieler zuletzt gemacht hat. Dies hätte beispielsweise das Potential, Ereignisse innerhalb der Spielwelt vorherzusagen, noch bevor Informationen
über die direkten Änderungen selbst eingetroffen sind (vgl. Abschnitt 5.2).
Damit diese Daten möglichst klein gehalten werden können, wurden hier
insgesamt nur sechs boolsche Variablen verwendet, um den Status sechs
verschiedener Tasten zu repräsentieren.
HNE_RTTsample und HNE_RTTsample_avg
Ein „HNE_RTTsample“
enthält eine Stichprobe (vom Englischen: Sample) der gemessenen Paketumlaufzeit (vom Englischen: Round Trip Time), sowie einen Zeitstempel
des Zeitpunkts der Messung. Beide Werte werden genutzt, um die durchschnittliche Verzögerung von Nachrichten zwischen einem bestimmten Client und dem Server zu berechnen. In der Datei „HNE_Constants.h“ sind
zudem die Initialwerte HNE_DEFAULT_RTT_MEASURE_INTERVAL
und HNE_DEFAULT_NUMBER_OF_RTT_SAMPLES definiert. Sie legen
fest, wie häufig die Paketumlaufzeit zu jedem verbundenen Client gemessen wird und welche Anzahl gemessener Paketumlaufzeiten maximal gespeichert bleibt. Aus den gespeicherten Werten wird anschließend ein Mittelwert (arithmetisches Mittel) berechnet. Dieser wird zusammen mit der
ID des zugehörigen Clients in der Struktur „HNE_RTTsample_avg“ abgelegt. Nach jeder neuen Messung eines Round-Trip-Time-Samples wird
auch eine neuer Mittelwert berechnet. Dieser dient als Grundlage für die
Berechnung der Verzögerung von Netzwerknachrichten zwischen Client
und Server (vgl. Abschnitt 6.3.3).
HNE_NetObjectsStateUpdate Mit den Daten dieser Struktur soll sich der
Status aller existierenden Objekte der Klasse „HNE_NetObject“ reproduzieren lassen. Dazu enthält sie ein Array „states“, welches Objekte der Klasse „HNE_State“ beinhaltet, sowie einen Integer „objectsCount“. Die Variable „objectsCount“ gibt hierbei an, wie viele HNE_State-Objekte sich in
49
6.2
Aufbau der Software
dem Array „states“ befinden. Sie ist einerseits für die schnelle Abfrage der
Array-Größe gedacht, als auch zur Kontrolle, ob die Anzahl der verschickten HNE_State-Objekte mit der beim Empfänger existierenden Anzahl der
HNE_NetObject-Objekte übereinstimmt.
HNE_NetUpdateData „HNE_NetUpdateData“ enthält alle wichtigen Informationen, die für die Übertragung neuer Positionsdaten relevant sind.
Insbesondere ist eine HNE_NetObjectsStateUpdate-Struktur namens „update“ enthalten, welche aktuelle Daten für HNE_NetObject-Objekte speichert. Darüber hinaus ist eine Struktur „HNE_UserInput userInput“ vorhanden, die zur weiteren Kontrolle der verschickten Daten vorgesehen ist
(vgl. Abschnitt 6.2.2), sowie eine Variable „timestampLastTickSV“, die per
Zeitstempel
festhält,
wann
der
Sender
die
Daten
in
„HNE_NetObjectsStateUpdate update“ erzeugt hat. Daran und mit Hilfe
der gemessenen Paketumlaufzeit kann ermittelt werden, wie alt diese Daten bereits sind, wenn sie beim Empfänger eintreffen (vgl. Abschnitt 6.3.3).
Zudem ist eine Variable „sequenceNumber“ enthalten, mit der kontrolliert
werden kann, ob es sich beim zuletzt empfangenen Netzwerkpaket tatsächlich um das erwartete nächste Paket handelt. Dies ist wichtig, da bei Verwendung des UDP-Protokolls Pakete verloren gehen oder auch in falscher
Reihenfolge beim Empfänger eintreffen können (vgl. Abschnitt 2.4).
HNE_MSG Die Struktur „HNE_MSG“ gibt den Aufbau für jedes
Netzwerk-Paket an, das innerhalb der „Humble Network Engine“
verschickt und empfangen wird: Anhand der Integer-Variablen „msgType“
lässt sich der Typ der Netzwerkpakets identifizieren und feststellen, welche
Daten darin enthalten sind und gelesen werden können. Zur einfachen Verwendung sind in der Datei „HNE_Constants.h“ Makros für die einzelnen
Nachrichtentypen definiert. Diese sind anhand des vorangestellten Zusatzes „HNE_MSG“ zu erkennen. Ein Beispiel dafür ist der Nachrichten-Typ
„HNE_MSG_SERVER_WANTS_TO_KNOW_RTT“. Der Server fordert damit eine Messung der Round Trip Time an. Auf diese Nachricht antwortet
der
Empfänger
beispielsweise
mit
einem
Paket
des
Typs
„HNE_MSG_CLIENT_RESPONDS_TO_RTT_REQUEST“.
50
6.2
Aufbau der Software
Dem Nachrichten-Typ „HNE_MSG_STATE_UPDATE“ kommt hier eine besondere Rolle zu. Im Falle dieser Nachricht enthält das Array
„HNE_NetUpdateData data“ neue Daten für den Status existierender
HNE_NetObject-Objekte. Die beiden Variablen „receiverId“ und „senderId“ werden benutzt, um intern festzustellen, welche HNE_App ein Paket
geschickt hat und an welche es geschickt werden soll. Die Variable „timestamp“ gibt an, wann das Paket vom Server zum Versand vorbereitet wurde. Damit lässt sich ermitteln, wie lange ein Paket gebraucht hat, um beim
Empfänger einzutreffen. Dies ist wichtig für die Ermittlung der Round Trip
Time (vgl. Abschnitt 3.1).
Falls nur die Änderung einer einzelnen, bestimmten Variablen übertragen werden soll, findet sich die entsprechende Änderung in den Variablen
„intChanged“, „floatChanged“ oder „boolChanged“, wenn jeweils die Änderung eines Integers, einer Fließkommazahl oder einer boolschen Variable
übertragen werden soll. Dieser Fall tritt etwa dann ein, wenn zur Laufzeit
der HNE-Demo-Applikation über die grafische AntTweakBar-Menüleiste
Änderungen vorgenommen werden, die jeden verbundenen Client betreffen. Ein Beispiel dafür wäre die Änderung der Geschwindigkeit (velocity)
aller HNE_NetObject-Objekte.
6.2.3
C++-Klassen
HNE_Vector3D Die Klasse „HNE_Vector3D“ dient zur Berechnung von
Richtungen und Positionen im dreidimensionalen Raum. Sie enthält nötige Funktionen zur Vektorberechnung, wie die Addition, Subtraktion und
Multiplikation mit Skalaren und Vektoren. Auch eine Funktion zur Berechnung des Kreuzprodukts ist vorhanden. Da bewegten Objekten beim vernetzten Spielen eine besondere Wichtigkeit zukommt (vgl. Abschnitt 4.2),
wird die Funktionalität dieser Klasse zum festen Teil der „Humble Network Engine“ gemacht. Als Basis für diese Klasse diente die „Vector3D“Klasse der AG Computergraphik an der Uni-Koblenz, von 2004.
HNE_Timer Da genaue Zeitmessungen für die „Humble Network Engine“ notwendig sind, um die Synchronisation zwischen Client und Server
51
6.2
Aufbau der Software
zu gewährleisten, sowie die exakte Dauer zwischen Operationen zu berechnen, wurde die Klasse „HNE_Timer“ implementiert. Zur Zeitmessung
verwendet diese Klasse die Windows-Funktion „QueryPerformanceCounter“. Die Entscheidung fiel auf QueryPerformanceCounter, da diese Funktion eine hohe Zeitauflösung garantiert, welche übliche Tick-Counter12 oft
nicht garantieren können. SDL stellt ebenfalls Funktionen zur Zeitmessung
zur Verfügung, wie etwa SDL_GetTicks. Auch nutzt die Windows-Version
von SDL ebenfalls QueryPerformanceCounter, jedoch ist in der hier verwendeten SDL-Version 1.2 durch ein Makro in der Header-Datei
„sdl_timer.h“ die Genauigkeit der Zeitmessung auf eine Auflösung von etwa 10 Millisekunden begrenzt. Dies ist für eine genaue Zeitmessung nicht
ausreichend, daher wurde QueryPerformanceCounter direkt verwendet.
Potentiell problematisch kann sich die Zuverlässigkeit dieser Funktion
allerdings dann herausstellen, wenn sie auf einer vielzahl verschiedener
Computer verwendet wird. Je nach System können Fehler im BIOS oder
der Hardwareabstraktionsschicht (vgl. [que]), sowie die Verwendung auf
Mehr-Prozessor-Systemen dazu führen, dass Zeitmessungen ungenau werden. QueryPerformanceCounter hat sich jedoch auf dem Entwicklungssystem der „Humble Network Engine“ als zuverlässig herausgestellt. Für eine Implementierung, die über einen Prototypen hinausgeht, wären jedoch
weitere Kontrollverfahren zur Zuverlässigkeit der Zeitmessung ratsam.
HNE_State Ein Objekt der Klasse „HNE_State“ umfasst sämtliche Daten,
die zur Reproduzierung des Status eines HNE_NetObject-Objekts auf einem anderen System notwendig sind. Allerdings ist keine Funktionalität
vorhanden, Variablen dynamisch zu einem HNE_State-Objekt hinzuzufügen. Bedingt durch den prototypischen Charakter der zu entwickelnden
Engine wurden im Rahmen dieser Arbeit Variablen für jedes HNE_StateObjekt festgelegt, wie etwa Daten zur Position oder Geschwindigkeit.
HNE_NetObject Ein „HNE_Netobject“ ist jedes Objekt, dessen Status
zwischen Client und Server synchronisiert werden soll. Das heißt, wann
12
Ein Tick ist: „in verschiedenen Computerbetriebssystemen (z.B. Windows, Mac
OS) eine von Software zählbare Einheit (1 Tick = 1 Chipberechnungsschritt)“, Quelle:
http://de.wikipedia.org/wiki/Tick - abgerufen im August 2012
52
6.2
Aufbau der Software
immer eine Applikation - wie etwa die HNE-Demo - Objekte erzeugen will,
deren Status über das Netzwerk übertragen werden soll, muss die Klasse
dieser Objekte von der Klasse „HNE_NetObject“ erben. Beispielsweise implementiert die HNE-Demo eine Klasse „HNE_BounceBall“, welche von
HNE_NetObject erbt. Jedes Objekt des Typs „HNE_BounceBall“ ist also ein
HNE_NetObject-Objekt.
Über
die
statische
Integer-Variable
„HNE_NetObject::numberOfNetObjects“ kann stets abgefragt werden, wie
viele
Objekte
dieser
Klasse
existieren.
Die
statische
Variable
„std::vector HNE_NetObject::allNetObjects“ enthält zudem Zeiger auf alle existierenden HNE_NetObject-Objekte.
HNE_App
Da bei der Aufgabenstellung auch auf Klarheit im Entwurf
geachtet werden sollte, wurde bei der Entwicklung der „Humble Network
Engine“ eine einfache Klassenstruktur umgesetzt: Zwischen den Funktionen der Demo und der Engine sollte eine Abstraktion stattfinden, daher
wurde eine Klasse „HNE_App“ geschrieben, welche die Funktionalität der
Engine beinhalten soll. Diese Klasse kann somit als das Herzstück der Engine bezeichnet werden. Jede Applikation, welche die Funktionalität der
„Humble Network Engine“ implementieren will, muss von dieser Klasse
erben. Auch die HNE-Demo-Applikation erbt von der Klasse „HNE_App“.
Demo_BounceBall Wie
bereits
erwähnt
handelt
es
sich
bei
„Demo_BounceBall“ um eine Klasse, die von der Klasse „HNE_NetObject“
erbt. Objekte der Klasse Demo_BounceBall sollen beispielhaft die speziellen, zu synchronisierenden Objekte der HNE-Demo-Applikation darstellen. Sie stehen stellvertretend für jedes Objekt, was sich in einem Videospiel
bewegen könnte, wie beispielsweise Spielfiguren, Projektile oder Fahrzeuge. Die Objekte der Klasse „Demo_BounceBall“ bewegen sich mit konstanter Geschwindigkeit innerhalb des Applikationsfensters und kehren ihre
Richtung um, wenn sie eine Bildkante berühren.
Demo Diese Klasse repräsentiert die HNE-Demo-Applikation, welche die
Funktionalität der „Humble Network Engine“ implementiert. Sie erbt ihre
Netzwerkfunktionalität von der Klasse HNE_App und fügt weitere, davon
53
6.3
Implementierte Verfahren und Funktionalität
unabhängige Funktionalität hinzu. Dazu zählen etwa OpenGL-Funktionen
zur grafischen Darstellung aller Objekte der Klasse Demo_BounceBall auf
dem Bildschirm, oder das Verarbeiten von Benutzer-Eingaben via Maus
und Tastatur. Auch stellt die Demo verschiedene AntTweakBar-Menüleisten
für Client und Server bereit. Im Applikationsfenster des Servers lassen sich
so Parameter der „Humble Network Engine“ zur Laufzeit ändern. Die
AntTweakBar-Leiste im Fenster eines Clients dient ausschließlich der Anzeige unterschiedlicher Werte, wie der zuletzt gemessenen Paketumlaufzeit oder der Anzahl verlorener Pakete (vgl. Abschnitt 6.4).
Demo_Camera Diese Klasse bietet verschiedene Funktionen zum Kontrollieren
der
OpenGL-Kamera.
Sie
dient
innerhalb
der
HNE-Demo-Applikation zum Setzen des Blickpunktes. Zwar enthält sie
noch weitere Kamera-Funktionen, diese werden jedoch nicht benutzt. Als
Basis für diese Klasse diente die „Camera“-Klasse der AG Computergraphik an der Uni-Koblenz, von 2004.
6.3
6.3.1
Einfache Simulation und Synchronisation
Für die Simulation der Spielwelt wurde bei der „Humble Network Engine“ ein festes Zeitschritt-Intervall (vom Englischen: fixed timestep) gewählt,
in dem die Simulation voranschreitet. Das Intervall zwischen einzelnen
Ticks ist als das Makro „HNE_SIM_UPDATE_INTERVAL“ in in der Datei „HNE_Constants.h“ angegeben. In der Grundeinstellung beträgt es 20
Millisekunden.
Der Vorteil eines festen Ausführungsintervalls liegt darin, dass man
leicht bestimmen kann, wie viele Ticks der Simulation sich in einem bestimmten Zeitraum auf dem Server ereignen, sofern das Programm dort
mit voller Geschwindigkeit ausgeführt werden kann. So lässt sich beispielsweise voraussagen, wie weit die Simulation in einer bestimmten Zeit voranschreiten wird, selbst dann, wenn ein Paketverlust auftritt.
Durch die Integer-Variable „HNE_App::hneNetUpdateInterval“ lässt
sich zudem das Intervall für die Häufigkeit des Versands von Positionsdaten regulieren. Die Grundeinstellung beträgt hier 50 Millisekunden und ist
54
6.3
durch das Makro „HNE_NET_UPDATE_INTERVAL_DEFAULT“ ebenfalls
in „HNE_Constants.h“ festgelegt. Diese Grundeinstellung kann jedoch zur
Laufzeit geändert werden. Auch in der HNE-Demo-Applikation ist dies
über den Menüpunkt „net update interval“ermöglicht. Der zulässige Wertebereich liegt hier zwischen 1 und 1000 Millisekunden. Somit wird es für
eine Anwendung möglich, die Häufigkeit der Positionsübertragungen je
nach Erforderlichkeit beliebig zu erhöhen oder zu verringern.
Die Paketversand-Strategie „HNE_SEND_STRAT_NAIVE“, die auch in
der Grundeinstellung verwendet wird, führt dazu, dass stets der Status aller HNE_NetObject-Objekte übertragen wird. Clients, die eine Verbindung
zur laufenden Simulation aufbauen, erhalten somit automatisch den aktuellen Status aller zu synchronisierenden Objekte.
6.3.2
Client-side simulation
Als ein erster Versuch, das Phänomen des ruckartigen Positionssprungs
bzw. des „Einrastens“ (vom Englischen: snapping) beim Eintreffen neuer
Positionsdaten zu reduzieren, wurde hier die Möglichkeit der clientseitigen Simulation implementiert. Dabei wird auf einem Client, auf Basis der
letzten bekannten Positionsdaten, die gleiche Simulation ausgeführt, wie
auf dem Server. Für Demo_BounceBall-Objekte heißt dies, dass die Berechnung aller Zwischenpositionen bis zum Eintreffen neuer Positionsdaten
ausschließlich auf dem Client stattfindet. Sobald neue Positionsdaten eintreffen, werden diese vom Client übernommen. Die Authorität für die Berechnung neuer Positionen liegt also zwischen dem Erhalten neuer Positionsdaten allein beim Client. Dieser Ansatz ist bereits als problematisch
charakterisiert worden (vgl. Abschnitt 5.3). Da er jedoch beim Szenario der
HNE-Demo-Applikation optisch eine deutliche Verbesserung bewirkt, ist
er Teil der „Humble Network Engine“ geblieben. Das Verfahren führt insbesondere dann zu einer deutlich flüssigeren Bewegung, wenn das Zeitintervall zwischen dem Erhalt neuer Positionsdaten groß ist. Ein Objekt
springt nicht mehr von der letzten zur neuen Position, sondern bewegt
sich auch im Zeitintervall zwischen dem Eintreffen neuer Positionsdaten
fließend weiter. Dieses Verfahren lässt sich insbesondere für Objektbewegungen und Ereignisse benutzen, deren Verlauf bekannt ist. Die konstante
55
6.3
Bewegung der HNE_BounceBall-Objekte begünstigt die Anwendung dieses Verfahrens.
6.3.3
Verbergung von Latenz und Latenzschwankungen
Diesem Punkt kam bei der Aufgabenstellung eine besondere Bedeutung
zu: Es sollte möglich sein, Latenzschwankungen zu verbergen. Um dies zu
ermöglichen wurden mehrere Funktionen implementiert, die im Folgenden erläutert werden sollen.
Zunächst lässt sich die aktuelle Paketumlaufzeit in regelmäßigen Intervallen messen. Aus diesen einzelnen Messungen lässt sich ableiten, wie
hoch der Zeitversatz zwischen Client und Server zum Zeitpunkt der Messung gewesen ist. Zwar gilt, dass die Latenz in beiden Richtungen unterschiedlich sein kann (vgl. Abschnitt 3.1), jedoch wurde hier angenommen,
dass zur Berechnung der Latenzhöhe die Hälfte der Paketumlaufzeit ausreicht.
Da die gemessene Latenzhöhe kurzfristigen Schwankungen bzw. „Latenzspitzen“ (vom Englischen: Latency Spikes) unterworfen sein kann, ist es
potentiell problematisch, den jeweils zuletzt gemessenen Latenzwert Berechnungen zu Grunde zu legen. In diesem Falle würden derartige plötzliche Latenzschwankungen zur Berechnung eines einzelnen, unerwarteten
Ergebnisses führen, welches stark von der Mehrzahl bisheriger Ergebnisse abweicht. Daher wurde allen Berechnungen, welche die Paketumlaufzeit mit einbeziehen, nicht der zuletzt gemessene Wert zu Grunde gelegt,
sondern ein Mittelwert (arithmetisches Mittel) aus einer Menge zuletzt gemessener Paketumlaufzeiten. Falls beispielsweise in Positionsberechnungen die durchschnittliche Paketumlaufzeit einbezogen wird, dann wird die
Berechnung der tatsächlichen aktuellen Position eines Objekts zwar ungenauer, jedoch soll gleichzeitig vermieden werden, dass sich durch plötzliche Latenzschwankungen Positionssprünge bei der Bewegung ereignen.
Zusätzlich existiert die Funktion „HNE_App::hnePredictPositions“. Sie
ist an das Prediction-Verfahren angelehnt (vgl. Abschnitt 5.6) und soll auf
einem Client anhand der letzten bekannten Position eines HNE_NetObjectObjekts, sowie seiner Richtung, Vorhersagen treffen, wohin das Objekt sich
bis zum Eintreffen neuer Positionsdaten bewegen wird. Zusätzlich bezieht
56
6.3
die Funktion noch die gemessenen Paketumlaufzeiten mit ein sowie die
Zeit, die seit dem letzten Server-Ticks vergangen ist. Somit soll sich auf einem Client-System vorhersagen lassen, wo ein Objekt sich zur gleichen Zeit
auf dem Server befindet. Zum Verständnis dieser Funktionalität sind die
relevanten Algorithmen für das hier implementierte Prediction-Verfahrens
im Folgenden zusammengefasst:
57
6.3
Speicherung des letzten Server-Tick-Zeitstempels Ttick
1. Speicherung eines Zeitstempels Ttick , wann immer der Server für die
Simulation den nächsten Zyklus ausgeführt hat. Dies geschieht in der
Grundeinstellung alle 20 Millisekunden.
2. Kopieren dieses Zeitstempels Ttick in jedes vom Server verschickte
Paket, das neue Positionsdaten über den aktuellen Status aller
HNE_NetObject-Objekte auf dem Server enthält.
3. Speicherung des mitgeschickten Zeitstempels Ttick auf dem empfangenden Client-System zur Verwendung durch die Funktion
„HNE_App::hnePredictPositions“.
Berechnung der durchschnittlichen Paketumlaufzeit RT Tavg
1. Messung der aktuellen Paketumlaufzeit RT Ti in regelmäßigen Abständen. In der Grundeinstellung geschieht dies alle 1000 Millisekunden bzw. jede Sekunde.
2. Speicherung der zuletzt gemessenen n Paketumlaufzeiten. In der
Grundeinstellung werden die letzten n = 10 Werte gespeichert.
3. Berechnung des Mittelwerts (des arithmetischen Mittels) RT Tavg aus
der Summe der n zuletzt gemessenen Umlaufzeiten RT Ti :
n
RT Tavg
1X
RT T1 + RT T2 + · · · + RT Tn
=
RT Ti =
n
n
(3)
i=1
4. Speicherung des zuletzt berechneten Mittelwerts auf dem Client.
58
6.3
Voraussage der aktuellen Objekt-Position VposP redicted
1. Festlegung des Latenzwerts Tlat auf die Hälfte des berechneten Mittelwerts RT Tavg :
Tlat =
RT Tavg
2
(4)
2. Berechnung des Zeitintervalls Tpassed , das seit dem letzten ServerTick Ttick vergangen ist. Anders ausgedrückt: Hier wird das Alter der
letzten Status-Änderung auf dem Server berechnet. Tpassed setzt sich
dabei zusammen aus dem Zeitintervall TpreSend , das zwischen dem
letzten Server-Tick und dem Versand des letzten Netzwerkpakets mit
neuen Positionsdaten vergangen ist, der Latenz Tlat und dem Zeitintervall TpastReceive , das seit dem Übernehmen der neuesten Positionsdaten auf dem Client vergangen ist.
Tpassed = TpreSend + Tlat + TpastReceive
(5)
3. Berechnung der Anzahl Server-Ticks Nticks , die im regelmäßigen Intervall TnetU pdate zwischen dem Eintreffen von Positionsdaten ausgeführt wird. Das Intervall Ttick gibt dabei das Tick-Intervall des Servers
an.
Nticks =
TnetU pdate
Ttick
(6)
4. Berechnung des Bewegungsvektors Vmove , der für ein existierendes
HNE_NetObject-Objekt angibt, wie weit es sich von seiner aktuellen Position VposLastT ick zu seiner Position VposN extT ick innerhalb eines Server-Ticks bewegen wird.
Vmove = VposN extT ick − VposLastT ick
(7)
59
6.4
Demo
5. Berechnung eines Interpolationsfaktors I aus dem Alter der zuletzt
erhaltenen Positionsdaten Tpassed dividiert durch das regelmäßige
Paketversand-Intervall TnetU pdate .
I=
Tpassed
TnetU pdate
(8)
6. Mit Hilfe des Faktors I lässt sich von der letzten bekannten Position
VposLastT ick eines HNE_NetObject-Objekts eine lineare Interpolation
entlang des Vektors Vmove vollziehen, welche die aktuelle Position
VposP redicted des Objekts auf dem Server voraussagt.
VposP redicted = VposLastT ick + (I ∗ (A ∗ Vmove ))
6.4
(9)
Demo
Um die Funktionen der „Humble Network Engine“ zu veranschaulichen,
wurde die HNE-Demo entwickelt. Diese Applikation soll hier vorgestellt
werden.
Nach dem Start der Software
kann ausgewählt werden, ob die
Applikation als Server oder Client gestartet werden soll. Beim
Drücken der Taste „1“ wir das Programm als Server gestartet. Das Betätigen der Taste „2“ lässt das Programm als Client starten. Wurde
das Programm als Server gestartet,
werden direkt nach dem Start mehrere Demo_BounceBall-Objekte erzeugt und ein Programmfenster geöffnet, welches zur grafischen Darstellung genutzt wird (vgl. Abbil-
Abbildung 10: HNE-Demo (Server)
ding 10). Die Größe dieses Fensters lässt sich durch die Variablen
60
6.4
Demo
„WIN_WIDTH“ und „WIN_HEIGHT“ in der Datei „HNE_Constants.h“
anpassen. Die Grundeinstellung ist hier 400 x 400 Pixel.
Innerhalb des Fensters werden einzelne Demo_BounceBall-Objekte als
rote Punkte gezeichnet, die sich mit konstanter Geschwindigkeit bewegen.
Für die Demo wurde eine Bewegung mit konstanter Geschwindigkeit gewählt, da dieser Fall deutlich die Einwirkungen von Latenzschwankungen sichtbar machen kann, beispielsweise durch den Verlust eines Pakets,
der zur ungleichmäßigen Bewegung aller Demo_BounceBall-Objekte führt.
Die hier gezeichneten Demo_BounceBall-Objekte werden durch mehrere
Eigenschaften beschrieben, welche in dem HNE_State-Objekt „objectState“
zusammengefasst sind (vgl. Abschnitt 6.2.3). Relevant für die Bewegung
eines Objekts sind insbesondere seine Position (Vector3D position), seine
Richtung (Vector3D direction) und sein Geschwindigkeitsfaktor (float velocity). Die Richtung eines Objekts ist durch einen grünen Vektor dargestellt,
der vom Mittelpunkt jedes roten Punktes ausgeht bzw. von der aktuellen
Position eines Objekts. Trifft ein Objekt auf eine Bildkante, prallt es von
dieser ab und ändert seine Richtung. Der Wert der Variablen „velocity“,
also die Geschwindigkeit aller Objekte, kann über den gleichnamigen Eintrag in der AntTweakBar-Menüleiste „Server settings“ verändert werden.
Möglich ist hier die Eingabe von Werten zwischen 1 und 20. Alle weiteren Einstellmöglichkeiten in der Leiste „Server settings“ sind relevant für
die Netzwerkübertragung zwischen Client und Server. So lässt sich unter
dem Menüpunkt „net update interval“ das Intervall einstellen, in dem aktuelle Positionsdaten aller Objekte vom Server übertragen werden. Mögliche Werte liegen zwischen 1 und 1000 Millisekunden. Beim Menüpunkt
„simulated packet loss“ kann der Verlust von Netzwerkpaketen simuliert
werden. Der Wert „0“ bedeutet hier, dass kein künstlich erzeugter Paketverlust stattfindet. Bei einem Wert von „1“ geht jedes einzelne Paket verloren, bei einem Wert von „2“ nur noch jedes zweite, bei einem Wert von „3“
jedes dritte Paket usw. Der Menüpunkt „client side simulation“ führt dazu, dass auch auf verbundenen Client-Systemen zwischen dem Eintreffen
neuer Positionsdaten die gleiche Simulation ausgeführt wird wie auf dem
Server (vgl. Abschnitt 6.3.2). Wird die Leertaste (Space) gedrückt, so hält
die Simulation an. Drückt man sie nochmals, wird die Simulation fortgeführt.
61
6.4
Demo
Wurde das Programm als Client gestartet, wird man zunächst aufgefordert, die IP-Adresse des Servers einzugeben. Eine Server-Port-Nummer
muss nicht angegeben werden, da diese bereits in der Datei
„HNE_Constants.h“ festgelegt ist. Nach dem Start des Clients wird versucht, unter der angegebenen IP-Adresse eine Verbindung zum Server aufzubauen. Gelingt dies, erhält der Client eine zufällig generierte ID-Nummer
(HNE_App::hneAppID), anhand der er eindeutig identifiziert werden kann.
Der Server erhält stets die ID-Nummer „0“, jeder Client erhält stets eine
ID-Nummer größer als 0. Diese ID wird zusammen mit der IP-Adresse des
Client-Systems auf dem Server in einer HNE_ClientInfo-Struktur abgespeichert.
Nachdem der Verbindungsvorgang abgeschlossen ist, erstellt der
Client ein Programmfenster für die
grafische Darstellung und beginnt,
Status-Änderungen vom Server zu
empfangen (vgl. Abbildung 11).
Auf dem Client existiert ebenfalls
eine AntTweakBar-Menüleiste. Diese nimmt allerdings keine Eingaben entgegen, sondern zeigt die
aktuellen Werte mehrerer Parameter an. Der Punkt „last RTT
sample“gibt die Höhe der zuletzt
gemessenen Paketumlaufzeit zwi-
Abbildung 11: HNE-Demo (Client)
schen dem Server und dem jeweiligen Client an. „average RTT“ gibt die
Höhe der durchschnittlichen Paketumlaufzeit an, die aus den zuletzt gemessenen Stichproben errechnet wurde. „age of last state update“ gibt an,
wie lange der letzte Server-Tick der Simulation zurück liegt. Es handelt
sich hierbei also um das Alter der zuletzt empfangenen Positionsdaten.
„packets lost“ zeigt die Anzahl aller bisher auf dem Weg zum jeweiligen
Client verlorenen Netzwerkpakete.
Im Fenster des Clients wird jedes Demo_BounceBall-Objekt doppelt gezeichnet, einmal in rot und einmal in blau. Die Darstellung in rot richtet
sich nach den letzten verfügbaren Positionsdaten. Dabei handelt es sich
62
6.4
Demo
grundsätzlich um die zuletzt vom Server empfangenen Positionsdaten.
Wird auf dem Server jedoch die clientseitige Simulation ermöglichst, dann
kann auch der Client selbst Änderungen an den Positionsdaten seiner
HNE_NetObject-Objekte vornehmen. Die zweite Darstellung eines jeden
Objekts in blau zeigt die Position, wie sie durch das Prediction-Verfahren
vorausgesagt wird (vgl. Abschnitt 6.3.3). Ziel dieses Verfahrens ist die Vorhersage, wo sich ein Objekt aktuell zur gleichen Zeit auf dem Server befindet. Je größer der Wert „net update interval“ auf dem Server gesetzt wird,
desto unverlässlicher wird auch die Positions-Vorhersage.
63
7
Fazit
In diesem Abschnitt wird analysiert, inwiefern die hier implementierten
Verfahren und Funktionen zur Lösung der Aufgabenstellung und insbesondere der beim Netzwerkverkehr auftretenden Latenzschwankungen geeignet sind. Abschließend folgt ein Ausblick, in dem mögliche weitere Ansätze zur Verbesserung der Performanz einer Network Engine für zeitkritische Videospiele diskutiert werden. Auch wird erläutert, welche Ansätze
im Rahmen dieser Arbeit nicht verfolgt wurden.
7.1
Ergebnisse und Bewertung
Abschließend ist zu erkennen, dass die Entwicklung einer performanten
Network Engine für zeitkritische Videospiele ein komplexes Unterfangen
darstellt. Es ist fraglich, ob eine allgemeine und zugleich effektive Softwarelösung für viele verschiedene Spiele-Genres gefunden werden kann.
Die Relevanz psychologischer Faktoren, die durchaus mit speziellen Spielmechaniken zusammenhängen können (vgl. Abschnitt 5.1), lässt vielmehr
darauf schließen, dass zumindest ein Teil der Funktionalität einer Network
Engine zum jeweiligen Spiel passen muss.
Der hier verfolgte Ansatz zum Verbergen von Latenzschwankungen allerdings hat sich als effektiv herausgestellt: Das Bilden eines Mittelwerts
aus gemessenen Paketumlaufzeiten ist hilfreich, wenn auf Basis dieses Wertes Berechnung durchgeführt werden sollen. Zur Laufzeit der HNE-Demo
konnte durch das Beobachten der angezeigten Werte festgestellt werden,
dass die zuletzt gemessene Paketumlaufzeit tatsächlich kurzzeitig um ein
Vielfaches ansteigen und wieder absinken kann. Beim berechneten Mittelwert der Paketumlaufzeiten geschah dies indes nicht. Die hier gewählte
Anzahl der für die Mittelwertberechnung genutzten einzelnen Paketumlaufzeiten (Samples) wurde mit n = 10 allerdings willkürlich festgelegt. je
nach Beschaffenheit einer Verbindung könnte eine höhere Anzahl Samples
nötig oder eine geringere Anzahl ausreichend sein, um Latenzschwankungen zu verbergen.
64
7.1
Ergebnisse und Bewertung
Das für die HNE-Demo-Applikation gewählte Szenario (Objektbewegungen mit konstanter Geschwindigkeit) ist einerseits beschränkt: Hier
bleibt zu bedenken, dass bei einem laufenden Videospiel weitere Fälle unregelmäßiger Bewegung auftreten können. Objekte verhalten sich hier oft
unvorhersehbar und beschleunigen, kommen plötzlich zum Stillstand oder
wechseln unerwartet ihre Richtung. Diese Fälle wurden hier nicht betrachtet.
Andererseits eignet sich dieses vereinfachte Szenario besonders dazu,
die Auswirkung von Latenzschwankungen bei der Datenübertragung deutlich zu machen, da es zu deutlich sichtbaren, ungleichmäßigen Bewegungen kommt. Anhand der verschiedenen zur Laufzeit einstellbaren Parameter der HNE-Demo lässt sich zudem die Auswirkung einzelner Faktoren
erkennen, wie etwa eines Paketverlustes oder eines hohen PaketversandIntervalls. Es konnte zudem beobachtet werden, dass die Häufigkeit des
Paketverlustes stark zunimmt, wenn das Paketversand-Intervall zu niedrig gewählt wird, etwa unter 10 Millisekunden. Daraus kann geschlossen
werden, dass Pakete häufiger vom Server verschickt wurden, als sie bei
einem Client verarbeitet werden konnten.
Da bewegten Objekten und deren Übertragung im Netzwerk eine große
Wichtigkeit zukommt, halte ich das Verfahren „Prediction“ generell für eine wirksame Methode, die Performanz einer Network Engine zu erhöhen.
Auch die häufige und erfolgreiche Verwendung dieses Verfahrens in modernen Videospielen wie etwa Halo: Reach (vgl. [Ald11]) spricht dafür. Bei
geringen Latenzen, hohen Senderaten von neuen Positionsdaten oder auch
bei langsamen Bewegungen eignet sich dieser Ansatz, um den Eindruck
einer flüssigen Bewegung zu erzeugen. Je höher jedoch die Latenz oder
die Abstände zwischen gesendeten Positionsdaten sind, desto problematischer wird auch dieser Ansatz, da Vorhersagen für längere Zeitintervalle getroffen werden müssen. Die Genauigkeit solcher Vorhersagen könnte
sich allerdings durch häufiges Senden von Kontrolldaten (vgl. Abschnitt
5.2) verbessern lassen.
Die Wahl eines festen Ausführungsintervalls (vgl. Abschnitt 6.3.1) kann
sich als problematisch erweisen. So kann es je nach System, auf dem das
Programm ausgeführt wird, zu Situationen kommen, in denen das
gewünschte Intervall nur höchst ungleichmäßig ausgeführt wird, etwa
65
7.2
Ausblick
wenn der Computer nicht leistungsfähig genug ist. Insbesondere können
die Grafikfunktionen der HNE-Demo dazu führen, dass das Programm zu
langsam ausgeführt wird. Dies ist insbesondere dann der Fall, wenn eine Synchronisierung mit der Bildwiederholrate des Monitors erfolgt. Gibt
der Monitor beispielsweise 60 Bilder in der Sekunde aus, so wird das Programm nach jedem Durchlauf solange angehalten, bis der Monitor das
nächste Bild darstellt und die Grafikkarte einen Pufferwechsel (vom Englischen: buffer swap) durchgeführt hat. Damit es nicht zu dieser Blockierung
kommt, wird im Programm explizit die Vertikale Synchronisation ausgestellt. Bei Wahl eines flexiblen Ausführungsintervalls wäre dieses Problem
generell nicht gegeben. Hier könnte beispielsweise die Simulation der Spielwelt so häufig wie möglich ausgeführt und anschließend die verstrichene
Zeit gemessen werden, statt auf den Ablauf eines festen Zeitintervalls zu
warten.
Die Verwendung von Winsock bewerte ich als eine gute Entscheidung.
Zwar hat sich der Implementierungsaufwand als hoch erwiesen, jedoch ist
somit die Wahrscheinlichkeit gesunken, dass zusätzliche Softwarefunktionalität in die Netzwerkübertragung eingreift. Es kann somit davon ausgegangen werden, dass die beobachteten Phänomene allein durch die technischen Probleme der Netzwerkkommunikation hervorgebracht werden
bzw. durch Funktionen der „Humble Networking Engine“ vermieden wurden.
7.2
Ausblick
Bei der Programmierung der „Humble Network Engine“ wurde ein Großteil der vorgestellten Konzepte und Ansätze zur Performanzsteigerung leider nicht umgesetzt. Auch ist die Abstraktion zwischen Engine und Demo
nicht vollständig erfolgt. Besondere Aufmerksamkeit ist hier dem Verbergen von Latenzschwankungen und der Implementierung des PredictionVerfahrens zugekommen.
Ein wichtiger nächster Schritt wäre, für eine Reduzierung der zu übertragenden Datenmenge zu sorgen. Dies findet innerhalb der „Humble Network Engine“ nicht statt. Durch die implementierte Paketversand-Strategie
„HNE_SEND_STRAT_NAIVE“ wird stets der Status aller Objekte übertragen, die synchronisiert werden sollen. Denkbar wäre hier das Hinzufügen
66
7.2
Ausblick
weiterer Paketversand-Strategien, mit denen sich anfallende Daten effektiv
komprimieren lassen und eine Priorisierung oder Analsyse ihrer Relevanz
durchgeführt wird (vgl. Abschnitt 5.8 und 5.7).
Auch wurden keine Lösungen verfolgt, um Spielern eine schnelle Reaktion auf ihre Eingaben zu liefern. Ein schnelles Reaktionsverhalten verbessert grundsätzlich die Spielbarkeit jedes Videospiels. Hier könnte ein
Verfahrens wie „Prediction“ dazu genutzt werden, Spielern unmittelbar
eine Reaktion zu zeigen. Dies birgt jedoch stets die Möglichkeit, dass eine Handlung auf einem Client, die durch „Prediction“ zunächst ausgeführt wurde, nachträglich zurückgenommen werden muss, wenn der Server feststellt, dass ein Spieler zur Ausführung nicht berechtigt gewesen ist.
Angesichts dieses Problems stellt die unmittelbare Rückmeldung eines vernetzten Spiels somit ein komplexes Unterfangen dar. Um den hier bei Korrekturen auftretenden Effekt des Einrastens (vom Englischen: Snapping) in
eine vom Server bestimmte, neue Objekt-Position zu entschärfen, könnten
zusätzlich Algorithmen zur „Glättung“ (vom Englischen: Smoothing) verwendet werden, die für ein weniger ruckartiges Gleiten zur tatsächlichen
Position sorgen.
Letztendlich lassen sich die technischen und auch physikalischen Beschränkungen, die mit dem Datenverkehr über das Internet einhergehen,
nur maskieren und kompensieren - wenn auch in manchen Fällen sehr geschickt. Steht aber nur eine langsame Verbindung zur Verfügung, wird dies
in kritischen Fällen, wie etwa der schnellen und exakten Positionsbestimmung, spürbar bleiben und die Spielbarkeit beeinflussen.
Wie in Abschnitt 5.1 erläutert bietet die Berücksichtigung spezieller
Spielmechaniken, wie etwa des Wurfs einer Granate, elegante Möglichkeiten, anfallende Latenzen vor Spielern zu verbergen. Sonderfälle wie dieser
machen allerdings deutlich, dass es trotz ähnlicher Anforderungen (vgl.
Abschnitt 4.2) problematisch ist, eine Software zu entwerfen, die für möglichst viele zeitkritische Spiele und Spiele-Genres geeignet ist. Zwar lassen
sich generelle Funktionen bereitstellen, die in einer Vielzahl von Spielen
nützlich sind, wie etwa die Verbesserung der Übertragung bewegter Objekte, aber um Netzwerkfunktionalität bestmöglich in besondere Spielmechaniken zu integrieren, sind spezielle Funktionen notwendig.
67
Literatur
[Ald11] David Aldridge. I Shot You First! - Gameplay Networking in
Halo: Reach.
http://downloads.bungie.net/presentations/David_
Aldridge_Programming_Gameplay_Networking_Halo_
final_pub.pptx, 2011.
[ant]
AntTweakBar.
http://www.antisphere.com/Wiki/tools:
anttweakbar, abgerufen im August 2012.
[Ber01] Yahn W. Bernier. Latency Compensating Methods in
Client/Server In-game Protocol Design and Optimization.
https://developer.valvesoftware.com/wiki/
Latency_Compensating_Methods_in_Client/Server_
In-game_Protocol_Design_and_Optimization, 2001.
[FG99] Mark Frohnmayer and Tim Gift. The tribes engine networking
model.
http://www710.univ-lyon1.fr/~jciehl/Public/educ/
GAMA/2008/tribes_networking_model.pdf, 1999.
[Fie]
Glenn Fiedler. Game Development Tutorials - Networking for
Game Programmers.
http://gafferongames.com/
networking-for-game-programmers/, abgerufen im
August 2012.
[Fie10] Glenn Fiedler. Networking for Physics Programmers.
http://gafferongames.com/2010/03/11/
gdc-2010-networked-physics-slides-demo/, 2010.
[gam]
GameDev.net - all your game development needs.
http://www.gamedev.net/, abgerufen im August 2012.
[ope]
OpenGL - The Industry Standard for High Performance
Graphics.
http://www.opengl.org/, abgerufen im August 2012.
[que]
QueryPerformanceCounter function - Microsoft msdn
Online-Hilfe.
http://msdn.microsoft.com/en-us/library/windows/
desktop/ms644904%28v=vs.85%29.aspx, abgerufen im
August 2012.
[rak]
RakNet - Multiplayer game network engine:.
http://www.jenkinssoftware.com/, abgerufen im August
2012.
[sdl]
Simple DirectMedia Layer.
http://www.libsdl.org/, abgerufen im August 2012.
[WS2]
Windows Sockets 2 - Microsoft msdn Online-Hilfe.
http://msdn.microsoft.com/en-us/library/windows/
desktop/ms740673%28v=vs.85%29.aspx, abgerufen im
August 2012.

Entwicklung einer performanten Network Engine für

Transcrição

Documentos relacionados

Herzlich willkommen

http://www.pspsource.de/news.php?item.722 Seite 1/1 Snes9x TYL

Webhosting - easyWEB4u

Tischtennis Game - Tischtennis

Architekturbüro "Architekturwert"

Inhaltsverzeichnis zum

ESWC LF8 Counter-Strike 1

Mona Hapke - Theater Ulm

Sophos Anti-Virus —Business

Tric-Trac - ziegelmueller.ch