Kurzfassung

Diese Arbeit beschäftigt sich mit den zu erwartenden Problemen von Mehrbenutzer-Echtzeitspielen, im Speziellen First Person Shooter, in zukünftigen mobilen Ad-Hoc Netzen und deren Lösungen. Dazu werden zunächst aktuell im Einsatz befindliche und desweiteren experimentelle Netzwerk-Architektur-Modelle hinsichtlich ihrer Eignung für mobile Ad-Hoc Netze überprüft. Als nächstes werden die Ursachen und Arten von Netzwerk-Verzögerungen, der kritischste Punkt beim Spielen über einen Kommunikationskanal, durchleuchtet. Anknüpfend werden die Techniken aktueller Internet-Echtzeitspiele zur Bekämpfung dieses und weiterer Probleme vorgestellt. Zur Veranschaulichung wird danach auf einige konkrete Realisierungen aus populären First Person Shooter Spielen eingegangen. Im Anschluss werden die auftretenden Probleme in mobilen Ad-Hoc Netzen erläutert. Es werden Methoden zu ihrer Bekämpfung vorgestellt und untersucht, in wie weit sich herkömmliche Lösungsmethoden auch in Spielen für mobile Ad-Hoc Netze anwenden lassen.

Inhaltsverzeichnis

ABBILDUNGSVERZEICHNIS   VII

EINLEITUNG   1

1.1  DANKSAGUNG  1

1.2  EINFÜHRUNG.  1

1.3  AUFBAU DER ARBEIT  2

NETZWERKARCHITEKTUR  -MODELLE 2.  3

2.1  PEER-TO-PEER-NETZWERKMODELLE  3

2.1.1  Unicasting-Systeme  3

2.1.2  Broadcasting/Multicasting-Systeme  4

2.2  CLIENT/SERVER-NETZWERKMODELLE  5

2.2.1  Arten von Client/Server-Modellen  5

2.3  ANWENDUNG IN MOBILEN AD-HOC NETZWERKEN.  6

2.4  ZUSAMMENFASSUNG.  9

ANFORDERUNGEN  AN EIN NETZWERKPROTOKOLL 3.  10

3.1  URSACHEN VON LATENZ IN ECHTZEITSPIELEN.  10

3.2  INFORMATIONSABHÄNGIGE WAHL DES NETZWERKPROTOKOLLS.  11

3.3  ZUSAMMENFASSUNG.  12

PROBLEML  ÖSUNGEN FÜR MEHRBENUTZERSPIELE 4.  14

4.1  TECHNIKEN DER SERVER-APPLIKATION  14

4.1.1  Unterteilung des virtuellen Raums  14

4.1.2  Filterung relevanter Informationen  17

4.1.2.1  Rasterbasierte Filterung  17

4.1.2.2  Objektbasierte Filterung.  17

4.1.3  Schutz vor Cheatern und Hackern  18

4.1.3.1  Paket Replay  18

4.1.3.2  Reverse Engineering.  20

4.1.3.3  Verschlüsselter Datenverkehr  20

4.1.4  Ephemeral Channels  21

4.2  TECHNIKEN DER CLIENT-APPLIKATION.  22

4.2.1  Methoden der Interpolation und Extraplolation.  22

4.2.2  Reversible Simulationen  23

4.2.3  Dead-Reckoning-Algorithmen  24

4.2.4  Ansätze der Vorhersage-Techniken  26

4.2.5  Event-Locking.  26

IMPLEMENTIERUNGEN  IN ECHTZEITSPIELEN 5  28

5.1  UNREAL TOURNAMENT - EPIC MEGAGAMES  28

5.1.1  Reduktion der Bandbreitenanforderung  28

5.1.1.1  Relevante Aktoren  28

5.1.1.2  Aktoren verschiedener Priorität.  28

5.1.1.3  Einschränkung des Wertebereichs.  29

5.1.1.4  Abschätzung von Spielerpositionen  29

5.1.2  Konsistenzerhaltung durch Replikation  30

5.1.2.1  Unzuverlässige/Zuverlässige Replikation  31

5.2  QUAKE - ID SOFTWARE.  32

5.2.1  Filterung relevanter Informationen  32

5.2.2  Das Netzwerkprotokoll von Quake I.  33

5.2.3  Positions- und Input-Updates in Quake II  34

5.2.4  Verteilung der Paketgrößen einer Spielsession  35

5.2.4.1  Client-to-Server  35

5.2.4.2  Server-to-Client  36

5.2.4.3  Bandbreitenanforderungen.  36

5.3  HALF-LIFE - VALVE SOFTWARE  37

5.3.1  Abschätzung von Spielerpositionen.  37

5.4  ZUSAMMENFASSUNG.  37

MOBILE  AD-HOC NETZE 6  39

6.1  ZUKÜNFTIGE PROBLEME VON ECHTZEITSPIELEN  39

6.1.1  Mobilität der Endgeräte  39

6.1.2  Limitierte Bandbreiten  40

6.1.3  Synchronisation des verteilten Spielzustands  41

6.1.3.1  Trailing-State-Synchronisation  42

6.1.4  Automatisches Finden von Mitspielern.  44

6.1.5  Sicherheitsrelevante Aspekte  45

6.2  PORTIERUNG EINES FPS AUF MOBILE AD-HOC NETZE  45

6.3  ZUSAMMENFASSUNG.  46

ZUSAMMENFASSUNG  UND AUSBLICK 7  47

7.1  ZUSAMMENFASSUNG.  47

7.2  AUSBLICK.  48

LITERATURVERZEICHNIS   XIV

Abbildungsverzeichnis

I Das Titelblatt zeigt eine Momentanaufnahme (screenshot) des FPS-Spiels Counter-Strike, Quelle: [Mann01].

2.1 Client/Server und Mirrored-Server Bandbreitenanforderungen einer modifizierten Quake-Version, Quelle: [CFK01].

4.1 Beispiel eines Seamless-Server aus Asheron’s Call 2: Fallen Kings, Quelle: [Thor03].

4.2 Server-Randbereiche sind schraffiert dargestellt und von Obj. 5 müssen z.B. 2 Proxy’s auf A, B erstellt werden, Quelle: Veränderte Reproduktion in Anlehnung an [Thor03].

4.2 Ein zu klein dimensionierter Server-Randbereich, Quelle: [Thor03].

4.4 Überblendung der divergierten Client-Sicht in die der Server-Simulation durch Interpolation, Quelle: Veränderte Reproduktion in Anlehnung an [Thor03].

4.5 Catmull-Rom-Spline Interpolation für kontinuierlich springende Objekte, Quelle: Veränderte Reproduktion in Anlehnung an [Thor03].

4.6 Auf Positions-Updates basierende Version des Dead-Reckoning-Algorithmus, Quelle: Veränderte Reproduktion in Anlehnung an [Watt01].

4.7 Bestimmung des Grads der verwendeten Tracking-Kurve, Quelle: [Watt01].

4.8 Momentaufnahmen alle 200ms, einer vom Client Nr. 1 initiierten Bewegung eines Panzers, Quelle: [Thor03].

5.1 a) Numerierung der einzelnen Oktanten des Octrees b) Einige Beispielobjekte

innerhalb des virtuellen Raumes c) Octree-Darstellung entsprechend der Numerierungsregeln, dabei bedeutet ein schw.-Blatt das der zugehörige Raum komplett von einem Objekt(-teil) ausgefüllt wird, Quelle: [Fellner92].

5.2 Verteilung der Paketgrößen während einer Spielsession, von den Clients zum Server, Quelle: [Armit00].

5.3 Verteilung der Paketgrößen während einer Spielsession, vom Server zu den Clients, Quelle: [Armit00].

6.1 Beispiel einer Trailing-State-Synchronisation anhand zweier Kommandos, Quelle: Veränderte Reproduktion in Anlehnung an [CFK01].

6.2 Beispielhafte Behebung einer Inkonsistenz anhand des Kommandos B mit Hilfe der Trailing-State-Synchronisation, Quelle: Veränderte Reproduktion in Anlehnung an [CFK01].

Internet-Echtzeitspiele für mobile Netzwerke Seite 1

Einleitung 1

1.1 Danksagung

Bedanken möchte ich mich bei Oliver Wellnitz für die Idee zu dieser Arbeit. Es ist ein Lichtblick hinsichtlich der Einbeziehung des Bereichs der Computerspiele-Entwicklung in den universitären Lehrbereich.

1.2 Einführung

Mehrbenutzerspiele repräsentieren mittlerweile eine der populärsten Arten der Gruppenkommunikation im Internet. In den letzten Jahren wurden Computerspiele mit Mehrspieler-Option bzw. reine Online-Mehrbenutzerspiele immer beliebter und kommerziell erfolgreich. Letzt genannte sind eine der wenigen Internet-Service, deren Nutzer bereit sind, eine monatliche Gebühr zu entrichten [SIG03]. In beiden Bereichen kann man alle Spiele-Genre wieder finden. Hierzu zählen die First Person Shooter (Quake, Unreal Tournament, Counterstrike … ), die Realtime Strategy Games (Age of Empires, Command & Conquer…) und die Adventures (Ultima Online, Everquest, Diablo…). Man muß jedoch im Bereich der Onlinespiele, auf Basis der unterstützten Anzahl von Mitspielern pro Spielsession, zwischen denen mit weniger als 100 und den Massive-Multiplayer-Spielen (MMP) mit weit über 1000 Mitspielern, unterscheiden. Diese Arbeit befasst sich nun schwerpunktmäßig mit FPS-Spielen, die einen Online-Mehrspieler-Modus besitzen und bis zu 64 Spieler ¹ pro Session unterstützen.

Im Moment zeichnet sich der Trend ab, das durch die zunehmende Verfügbarkeit des Internets, vor allem durch mobile Geräte, die Zahl der Nutzer von Mehrbenutzerspielen einem schnellen Wachstum unterliegt und sich so ein zukünftiger Massenmarkt entwickelt. Eine diesen Trend unterstützende Entwicklung ist die der Mehrbenutzerspiele in mobilen Ad-hoc Netzen. Ad-hoc Netze sind drahtlose Netzwerke, deren Teilnehmer sich spontan, ohne Unterstützung von Infrastruktur, zusammenfinden und kommunizieren können. Die daraus folgende größte Schwierigkeit bei einer evtl. Portierung eines First Person Shooter, ist die

¹ aktuelle obere Grenze in FPS, gesetzt von Battlefield 1942

Einleitung Seite 2

Mobilität der kooperierenden ² Endgeräte. Leistungsfähigkeit und Laufzeit der Geräte sind obendrein in vielen Fällen noch nicht ausreichend, um als Plattformen für Echtzeitspiele zu fungieren. Das gilt teilweise leider auch für die zur Verfügung stehende Bandbreite. Es ist jedoch abzusehen, dass die technologischen Vorraussetzungen in der Zukunft geschaffen werden. Zumindest insofern, dass grafisch abgespeckte und veraltete Versionen aktueller First Person Shooter auf der Mehrheit der Geräte gespielt werden können. Die jeweils aktuellen Spiele werden aufgrund der enormen und stetig wachsenden Hardwareanforderung nur einigen wenigen Endgeräten ³ vorbehalten bleiben.

In dieser Arbeit werden die Problemlösungen heutiger Mehrbenutzerspiele in Hinblick auf ihre Anwendung in mobilen Ad-Hoc Netzwerken untersucht.

1.3 Aufbau der Arbeit

In Kapitel 2 werden zunächst einmal die verschiedenen Netzwerkarchitektur-Modelle, auf denen die aktuellen Mehrbenutzerspiele basieren, vorgestellt, analysiert und ihre Anwendung in mobilen Ad-Hoc Netzen untersucht. Kapitel 3 beschäftigt sich mit den Ursachen von während der Internet-Kommunikation auftretenden Verzögerungen. Im anschließenden Kapitel 4 werden Konzepte zur Lösung dieses und weiterer Probleme von Mehrbenutzerspielen durchleuchtet. Überdies werden einige Implementierungen der vorgestellten Konzepte, aus aktuellen Mehrbenutzer-Echtzeitspielen in Kapitel 5 aufgezeigt. Kapitel 6 beschäftigt sich letztlich, nach einem Überblick der Schwierigkeiten von Mehrbenutzerspielen in mobilen Ad-Hoc Netzen, mit der Anwendung der gewonnenen Erkenntnisse zu ihrer Bekämpfung. Das letzte Kapitel stellt eine Zusammenfassung der zuvor präsentierten Erkenntnisse dar und gibt einen Ausblick auf im Rahmen der Arbeit interessante Fragestellungen und zukünftige Untersuchungen.

² d.h. jedes Gerät leitet Nachrichten für andere Geräte weiter (Forwarding im multi-hop Netzwerk)

³ z.B. Laptops mit hoher Performance oder zukünftig spez. entwickelte Spiel-Endgeräte

Internet-Echtzeitspiele für mobile Netzwerke Seite 3

Netzwerkarchitektur-Modelle 2

In diesem Kapitel werden die verschiedenen Netzwerkarchitektur-Modelle, auf denen die Kommunikation aktueller Mehrbenutzerspiele basiert, vorgestellt und analysiert. Es wird weiterhin untersucht, inwieweit sich diese Modelle in mobilen Ad-Hoc Netzwerken anwenden lassen.

2.1 Peer-to-Peer-Netzwerkmodelle

Die ersten Mehrbenutzerspiele (Doom, Descent, …) nutzten diese am leichtesten zu implementierende Art der Kommunikation. Wesentliches Merkmal dieser Modelle ist, dass jeder Teilnehmer mit allen anderen verbunden ist. Man unterscheidet je nach gebotener Funktionalität mehrere Arten:

2.1.1 Unicasting-Systeme

Ein Peer-to-Peer Unicasting-Modell ist die einfachste Art der verwendeten Systeme. Es besteht aus nur einer Applikation, die aus der Spiellogik und einem Modul das Nachrichten senden, empfangen, und bearbeiten kann, zusammengesetzt ist. Bei n Teilnehmern muss ein Zustandsupdate eines Spielers, zu n-1 Mitspielern gesendet werden. Die Folge ist eine hohe Anzahl von Nachrichten und evtl., je nach Art des verwendeten Protokolls (3.2), offenen Verbindungen. Das System skaliert somit quadratisch zu der Anzahl der Mitspieler und ist deshalb für große Teilnehmerzahlen ungeeignet. Nachteile ergeben sich auch bei der Skalierbarkeit der internen Bildwiederholrate (framerate). Diese wird durch die folgende Hauptprogrammschleife bestimmt: Zustands-Updates aller Spieler empfangen → Input des Spielers lesen → neuen Spielerzustand berechnen und versenden → Bild anzeigen ↑. Die Bildwiederholrate muss bei allen Mitspielern auf demselben Level ⁴ (frame-locking) basieren [Treg02], um die Simulationen konsistent zu halten, d.h. die Hauptprogrammschleife kann nicht unterschiedlich

⁴ es wird eine Zeitlang gewartet, bis alle Updates von allen Spielern eingetroffen sein müssen

Netzwerkarchitekturmodelle Seite 4

schnell durchlaufen werden. Dies macht es schwierig unterschiedliche Hardwarepotentiale ⁵ auszunutzen.

Nachteilig ist ebenfalls das sich die Spieler verabreden müssen, um das Spiel gemeinsam zu starten, wenn sie sich nicht im selben Ethernet-Segment befinden und somit Broadcasting (2.1.2) nicht zur Spielerfindung verfügbar ist. Neue Spieler können dann auch nicht im Verlauf des Spiels teilnehmen. Eine Lösung des Problems stellt der Einsatz eines bekannten ⁶ Slot-Servers dar. Dessen Aufgabe beschränkt sich auf die Initialisierung des Peer-to-Peer-Modus durch Übermittlung einer Teilnehmeradressliste. Jeder Server hat eine gewisse Anzahl von Slots zu vergeben, die der maximalen Spieleranzahl pro Session entspricht, so dass auch noch während des Spiels, solange noch Slots frei sind, Clients durch Anfrage an den Server dem Spiel beitreten können. Der Einsatz eines Slot-Servers markiert den Übergang zu einer Client/Server-Architektur (2.2) und beschreibt auf diese Weise ein hybrides System.

2.1.2 Broadcasting/Multicasting-Systeme

Einige der Probleme des oben vorgestellten Systems werden gelöst, wenn das zugrunde liegende Netzwerk das Versenden von Broadcast- oder Multicast-Nachrichten unterstützt. Mit Hilfe von Broadcasting kann man den Kommunikationsaufwand auf O(n) reduzieren. Dies bezieht sich auf den Grossteil der Nachrichten, die häufig und unzuverlässig ⁷ übertragenen Zustandsupdates. Für zuverlässige Übertragungen erhöht sich der Aufwand evtl. durch wiederholt gesendete Nachrichten (retransmits). Bei sehr hoch skalierten Systemen mit mehreren hundert Teilnehmern ist der Aufwand trotzdem zu groß, da jeder Client jede Zustandsänderung empfangen und bearbeiten muss, auch wenn die Änderung nicht seine nähere Umgebung beeinflusst und somit irrelevant für das nächste Bild ist. Genau hier setzen Multicasting-Systeme an. Durch eine dynamische Partitionierung des Virtuellen Raums (4.1.2) werden Multicast-Gruppen gebildet und somit die Anzahl der Update-Nachrichten reduziert.

⁵ höherwertige Hardware ermöglicht eine höhere Framerate und somit flüssige Simulationen höherer Qualität

⁶ feste IP-Adresse oder URL

⁷ Broadcasting/Multicasting-Übertragungen sind stets unzuverlässig

Netzwerkarchitekturmodelle Seite 5

2.2 Client/Server-Netzwerkmodelle

Wegbereiter für die Verwendung der Client/Server-Architektur in der Spielentwicklung war das Spiel Quake. Bei diesem Modell sind alle Spieler bzw. Clients nur noch mit einem Server und nicht mehr untereinander verbunden. Die Server-Applikation empfängt und bearbeitet alle Nachrichten bzw. Anfragen (bewege, erzeuge…) der Clients und versendet dann gültige Zustandsupdates. Die Bandbreite der Serveranbindung und die Rechenleistung des Servers bestimmen folglich die maximale Anzahl von Spielern pro Server. Dieses Problem des Server-Flaschenhalses tritt an die Stelle des Problems der Anzahl der Nachrichten und Verbindungen bei Peer-to-Peer-Architekturen.

Da die Server-Applikation die Zustandsupdates verteilt, kann sie mit Hilfe von Sichtbarkeits-Algorithmen oder anderen Kontext bezogenen Regeln entscheiden, für welche Clients die Updates relevant sind (4.1.2). So kann der Kommunikationsaufwand, ähnlich wie beim Peerto-Peer Multicasting, reduziert werden.

Der Server kann auch als vertrauenswürdige Instanz zum Schutz vor Cheatern und Hackern dienen (4.1.3).

Eine Client/Server-Architektur stellt letztlich die beste Lösung bei hoher Bandbreite und geringer Latenz dar. Deshalb wird sie auch von allen aktuellen FPS eingesetzt und im weiteren Verlauf der Arbeit favorisiert.

2.2.1 Arten von Client/Server-Modellen

Es gibt verschiedene Arten der Verwendung von Client/Server-Modellen, die durch die Funktionserfüllung (4.2) der Clients gekennzeichnet sind. Bei den ersten Mehrbenutzerspielen wie Quake, die Client/Server-Modelle verwendeten, spricht man von einer rigorosen (monolithischen) Anwendung. Die Clients waren reine Anzeige-Terminals, welche die Benutzereingaben an den Server sendeten und daraufhin eine Liste von anzuzeigenden Objekten empfingen. Mit der Entwicklung von Quake 2 wurde dann zunehmend Funktionalität bzw. Eigenverantwortung auf die Clients übertragen. Unreal führte schließlich ein generalisiertes Client/Server-Modell bei den Mehrbenutzerspielen ein. In diesem Modell bleibt der Server zwar die einzige, über die Evolution des Spielzustands entscheidende Instanz, jedoch spiegelt der Server einen Teil des Gesamtzustands auf jeden der Clients. Dadurch kann der Client, bei Anwendung derselben Spiellogik wie der Server, den