Mehrbenutzer-Echtzeitspiele erfreuen sich immer größerer Beliebtheit. Ein Grund dafür ist die in letzter Zeit steigende Anzahl an möglichen Mitspielern bzw. das daraus resultierende Spielerlebnis. Die Proxy-Architektur wurde unter diesem Gesichtspunkt entworfen und soll die heutigen Probleme, wie Skalierbarkeit, Serverengpässe und Fairnessunterstützung, etablierter Netzwerkarchitekturen lösen. Aus diesem Grund sind in der Proxy-Netzwerkarchitektur die an einer Partie teilnehmenden Clients jeweils mit einem von mehreren Proxyservern verbunden, welche zusammen einen virtuellen Server darstellen. Der Spielzustand liegt dabei als lokale Kopie auf den Proxies vor und wird über Benachrichtigungen zwischen ihnen synchronisiert. Diese Arbeit beschäftigt sich mit der Portierung einer Modifikation (QFusion) des quelloffenen Mehrbenutzer-Echtzeitspiels Quake II auf die Proxy-Architektur. Mit Hilfe dieses Engineports sollen die Erwartungen an die Skalierbarkeit der Proxy-Architektur evaluiert werden. In der Arbeit werden zunächst einige Grundlagen des originalen Enginecodes, wie das eingesetzte Netzwerkprotokoll, die Mainloops der Client- und Serverapplikation und die zu replizierenden Spielzustandselemente, erläutert. Im Anschluss wird ein Überblick über die verwendete Proxy-Architektur vermittelt. Darauf folgt eine Beschreibung der Implementierung des Framework-API’s der Proxy-Architektur. Anschließend werden die notwendigen Schritte zur Synchronisation des Spielzustandes veranschaulicht und für jede Aktionsart wird die Implementierung des Synchronisationskonzeptes (Eventual Consistency) vorgestellt. Die Evaluierung der Portierung umfasst drei Testläufe. Einerseits ein direkter Vergleich der Client/Server-Version mit der portierten Version der Engine. Dabei stellte sich heraus, dass die Proxy-Architektur unter Verwendung von zwei Proxyservern bis zu 40% mehr teilnehmende Clients erlaubt. Andererseits ein Internet- und ein Skalierungstest, aus deren Messergebnissen eine Unterstützung von fast 50 Spielern auf 4 Proxyservern ermittelt wurde.

Abstract

Multi-user real-time games enjoy of ever larger popularity. The lately rising number of possible players and respectively the play experience resulting from it are reasons for this. The proxy architecture was sketched under this criterion and solves the today's problems of established network architectures, like poor scalability, server bottlenecks and small fair play support. The participating clients of a session are each connected with one of several proxy servers, which together displays as one virtual server. The game state exists as a local copy on the proxies and is synchronized by notifications between the proxies. This work describes the porting from a modification (QFusion) of the open source multi-user real-time game Quake II to the proxy architecture. Expectations to the scalability of the proxy architecture should be evaluated with the help of this engine. In the work some basics of the original engine code are described first, like the assigned network protocol, client and server application main loops and the game state elements which must be replicated. Then an overview of the used proxy architecture is given, followed by implementation details, which describe the framework API’s of the proxy architecture. Subsequently, the necessary steps for the synchronisation of the game state are illustrated and the implementations of the synchronisation concept (eventual consistency) for each action type were introduced. The evaluation of the work covers three test runs. On the one hand a direct comparison of the client/server version with the ported version of the engine. It turned out that the proxy architecture allows up to 40% more participating clients using two proxy servers. On the other hand an internet test and a scalability test, from whose results a support by nearly 50 players on four proxies were determined.

III

Inhaltsverzeichnis

1  EINLEITUNG  1

1.1  DIE WAHL DER ENGINE  2

1.2  DIE QFUSION-ENGINE  3

1.3  VERWANDTE ARBEITEN.  3

2  DIE QFUSION-ENGINE UND DIE PROXY-ARCHITEKTUR  5

2.1  DIE QFUSION-ENGINE  5

2.1.1  Netzwerkarchitektur  5

2.1.2  Netzwerkprotokoll  6

2.1.2.1  Nachrichtentypen  7

2.1.2.2  Deltakomprimierung  7

2.1.2.3  Checksummen  8

2.1.3  Server-Mainloop  8

2.1.4  Client-Mainloop  9

2.1.5  Ausschnitt des Server-Datenmodells  10

2.2  DIE PROXY-ARCHITEKTUR  11

2.2.1  Aufbau der Netzwerkarchitektur  11

2.2.2  Möglichkeiten der Kommunikation.  12

2.2.3  Abstraktion der Adressierung.  12

2.2.4  Synchronisation des Spielzustandes.  12

2.2.5  Fairnessunterstützung.  13

3  IMPLEMENTIERUNG DES FRAMEWORK-API.  14

3.1  ÜBERBLICK UND NOTATION  14

3.2  DAS NETZWERKPROTOKOLL.  14

3.2.1  Client-Proxy-Kommunikation.  15

3.2.2  Inter-Proxy-Kommunikation  15

3.2.3  Netzwerkprotokoll-Header.  16

3.3  DIE SERVERKLASSE QPA SERVER  17

IV

3.4  SCHEDULING DER EINGEHENDEN PAKETE  19

3.5  DIE KLASSE EINGEHENDER PAKETE QPA MESSAGE  19

3.6  DIE CLIENTKLASSE QPA CLIENT.  19

3.7  CLIENT/SERVER-DATENFLUSS  20

3.8  INTER-PROXY-DATENFLUSS.  21

3.9  REMOTECLIENT-KONZEPT.  22

3.10  ZUSAMMENFASSUNG  23

4  SYNCHRONISATION DES SPIELZUSTANDES  24

4.1  MANAGEN DES REPLIZIERTEN ZUSTANDES.  24

4.2  MOVEMENT-SYNCHRONISATION.  25

4.2.1  Ableitung des Zustandsupdates für einen Remoteclient.  25

4.2.2  Das Remoteclientupdate  26

4.2.3  Zusammenfassung  27

4.3  SYNCHRONISATION DER INTERAKTIONEN  27

4.3.1  Synchronisation geführter Waffen  27

4.3.2  Interaktionen zwischen Spielern  28

4.3.2.1  Interaktionen mit Remoteclients.  28

4.3.2.2  Interaktionen von Remoteclients  28

4.3.3  Interaktionen mit der Umgebung  29

4.3.4  Userinfo-Synchronisation  30

4.3.5  Zusammenfassung  30

4.4  SYNCHRONISATIONSINTERVALLE  31

4.5  PROBLEM UNGÜLTIGER SPIELERZUSTÄNDE  34

4.6  ACTION REORDERING.  34

4.7  SYNCHRONISATIONEN DURCH DEN MASTERSERVER  36

4.7.1  Synchronisierung der Hostuhren.  36

4.7.1.1  Slaveproxyserverzeit  36

4.7.1.2  Clientzeit  37

4.7.2  Synchronisierung der Spawnpoints  37

4.7.3  Spielsitzungsverwaltung.  38

4.8  PROXYSERVER-MAINLOOP.  38

4.9  MANIPULATION DER TICKRATE  40

V

5  INSTALLATION UND BENUTZUNG  41

5.1  INSTALLIEREN DER 3D-ENGINE  41

5.2  STARTEN DES SPIELS.  41

5.2.1  Initialisierung der Server.  41

5.2.2  Starten mit Hilfe der Batchdateien  41

5.3  DIE ENGINE-KONSOLE  42

5.3.1  Konsolenvariablen - CVAR’s  42

5.3.2  Konsolenbefehle  44

5.4  KONFIGURATION DER PROXY-ARCHITEKTUR.  45

5.4.1  Server-Konfiguration  45

5.4.2  Client-Konfiguration.  47

5.4.3  Ändern der Voreinstellungen  47

5.5  KOMPILIEREN DER ENGINE  47

5.5.1  Compiler-Einstellungen  48

5.5.2  Aktuelle GPA-Versionen linken.  48

5.6  DIE BENUTZUNG UND EINSTELLUNG DES SPIELES  48

5.6.1  Einstellungen des Spielermodells  49

5.6.2  Deathmatch Scoreboard  49

6  EVALUATION DER PORTIERUNG  51

6.1  ANALYTISCHE SKALIERBARKEITSMODELLE  51

6.1.1  Client/Server-Skalierungsmodell  52

6.1.2  Proxyserver-Skalierungsmodell  53

6.2  VERGLEICH DER CLIENT/SERVER- UND PROXY-VERSION.  54

6.2.1  Testbedingungen und Methodik  54

6.2.2  Erfassen von Messwerten.  55

6.2.3  Auswertung des Versuches  55

6.2.3.1  Berechnungszeiten für einen Tick  55

6.2.3.2  Bandbreitenanforderungen pro Tick  57

6.2.3.3  Zusammenfassung.  58

6.3  EVALUATION ÜBER DAS INTERNET.  59

6.3.1  Testauswertung anhand der benötigten Rechenzyklen  60

6.3.2  Testauswertung anhand der benötigten Bandbreiten  61

VI

6.4  SKALIERUNGSTEST.  61

6.5  AUFWAND DER PORTIERUNG.  63

6.6  ZUSAMMENFASSUNG  63

7  BEWERTUNG UND AUSBLICK  64

7.1  BEWERTUNG.  64

7.2  AUSBLICK  64

LITERATURVERZEICHNIS   66

A  VERZEICHNISSTRUKTUR.  69

B  DEFINITION REFERENZIERTER STRUKTUREN.  70

NETZKANALSTRUKTUR  NETCHAN T  70

NETZADRESS  -STRUKTUREN NETADRTYPE T, NETSRC T, NETADR T  70

BUFFER  -STRUKTUR SIZEBUF T.  71

USERINPUT  -STRUKTUR USERCMD T  71

CLIENTFRAME  -STRUKTUR CLIENT FRAME T  71

SPIELERZUSTANDS  -STRUKTUR PLAYER STATE T  72

SPIELERBEWEGUNGS  -STRUKTUR PMOVE STATE T  72

CLIENT  -STRUKTUR CLIENT T  73

C  FUNKTIONS-DEKLARATIONEN.  74

D  DIE KLASSE QPA SERVER  82

E  DIE KLASSE QPA CLIENT  88

F  QUELLCODELINKS  90

G  PROBLEMBEHANDLUNGEN  91

VII

Abbildungsverzeichnis   

Titelbild  Screenshot der Map Estatica aus der QFusion-Engine  

Abbildung  1 Weltkarte des MMORPG’s Ragnarok Online, Quelle 39  

Abbildung  2 Client/Server-Architektur  

Abbildung  3 Verbindungsorientierter Paketheader  

Abbildung  4 Nachrichtenorientierter Paketheader.  

Abbildung  5 Proxyserver-Architektur  

Abbildung  6 Kommunikationsarten und Protokolle des Engineports  

Abbildung  7 Verbindungsorientierter Paketheader der Client/Server-Kommunikation.  

Abbildung  8 Verbindungsorientierter Paketheader der Inter-Proxy-Kommunikation.  

Abbildung  9 Ausschnitt der Klassensstruktur des Servers  

Abbildung  10 Ausschnitt der Klassensstruktur des Clients  

Abbildung  11 Überblick des Client/Server-Datenflusses und der involvierten Funktionen.  

Abbildung  12 Überblick des Inter-Proxy-Datenflusses und der involvierten Funktionen  

Abbildung  13 Weiterleitung und Verarbeitung einer Benutzeraktion  

Abbildung  14 Paketstruktur des Zustandupdates eines Remoteclients.  

Abbildung  15 Beispiele auftretender Objekte der Spielwelt, Quelle: 33  

Abbildung  16 Beispiel eines Spielermodells (Xaero), Quelle: 33  

Abbildung  17 Differenz der Bandbreitenanforderungen zweier Synchronisations-Intervalle.  

Abbildung  18 Bandbreitenanforderungen der verschiedenen Synchronisations-Intervalle.  

Abbildung  19 Bsp. einer erfolgreichen Anwendung des Action Reordering, Quelle: 25  

Abbildung  20 Ausschnitt aus dem Kontrollfluss der Paketverarbeitung  

Abbildung  21 Zeitlicher Ablauf der verschiedenen Synchronisationsschritte.  

Abbildung  22 Benutzerinterface mit Konsolenfenster  

Abbildung  23 Graphisches Benutzerinterface der Applikation  

Abbildung  24 Einstellungsmenü des Spielermodells  

Abbildung  25 Verschiedene Hierarchien der Ergebnisanzeige  

Abbildung  26 Koeffizienten der Berechnungszeiten der C/S- und Proxyversionen.  

Abbildung  27 Berechnungszeiten der C/S- und Proxyversionen für einen Tick  

Abbildung  28 Bandbreitenanforderungen der C/S- und Proxyversionen für einen Tick.  

Abbildung  29 Bandbreitenanforderungen der C/S- und Proxyversionen in kbps.  

Abbildung  30 Vergleich der Berechnungszeiten der Server in Münster und Lübeck.  

Abbildung  31 -Kennlinien  

T  se n ( m , )  

VIII

Abbildung  32 Bandbreiten der ein- und ausgehenden Kommunikation.  61

Abbildung  33 Ermittelte Spieleranzahlen des Skalierungstestes  62

IX

Tabellenverzeichnis   

Tabelle 1  CLC MOVE-Nachricht.  7

Tabelle 2  Deltakomprimierte SVC PLAYERINFO  8

Tabelle 3  Ausschnitt aus dem Spielzustand eines Clients auf dem Server  11

Tabelle 4  Implementierung des Remoteclientflag.  23

Tabelle 5  Zusammenfassung der vorgestellten Synchronisationsintervalle.  33

Tabelle 6  Besonders relevante Konsolenvariablen  44

Tabelle 7  Voreinstellungen der Server-Konfiguration  46

Tabelle 8  Voreinstellungen der Client-Konfiguration.  47

Tabelle 9  Maximale Werte der Bandbreitenkoeffizienten  57

Tabelle 10  Lastverteilung des Experimentes  62

Danksagung

Bedanken möchte ich mich zunächst bei Prof. Fischer für das etwas außergewöhnliche Thema dieser Arbeit, welches in besonderer Weise meine Interessen im IT-Bereich widerspiegelt. Außerdem bei Christian Werner von der Universität Lübeck für seine Hilfe bei der Evaluierung über das Internet. Insbesondere möchte ich mich bei Jens Müller von der Universität Münster, für seine stets schnellen Hilfestellungen zu Fragen seiner Diplomarbeit und sein langfristiges Engagement, bedanken.

Mein größter Dank gilt meinen Eltern für ihr spezielles längerfristiges Engagement in Bezug auf meine Ausbildung. Danke.

Einleitung

Seit einiger Zeit zeichnet sich der Trend ab, dass im Genre der Mehrbenutzer-Echtzeitspiele (Multiplayer Games) bzw. speziell im Bereich der First-Person-Shooter (FPS) versucht wird, die Anzahl von Teilnehmern pro Spielpartie zu erhöhen. In einigen der bereits erschienenen Spiele, wie Joint Operations und Söldner - Secret Wars [23, 24], als auch bei dem noch in der Entwicklung befindlichen Battlefield 2 [22], wird bereits die Marke der 100 Mitspieler überschritten. Dieser Wunsch nach erhöhter Skalierbarkeit unterliegt jedoch im Moment, neben den Bandbreitenlimitationen, den Restriktionen der verwendeten Netzwerk-Architekturen (Client/Server, Peer-to-Peer) im kommerziellen Bereich [1].

Die dieser Arbeit zugrunde liegende Proxy-Plattform wurde entwickelt, um die Probleme der heutigen Mehrbenutzer-Echtzeitspiele, wie Skalierung der Teilnehmerzahlen, Serverengpässe und Fairnessunterstützung, zu lösen. In der Proxy-Netzwerkarchitektur sind die an einer Partie teilnehmenden Clients jeweils mit einem von mehreren, einen virtuellen Server bildenden, Proxyservern verbunden. Der Spielzustand liegt dabei als lokale Kopie auf den Proxies vor und wird über Benachrichtigungen zwischen ihnen synchronisiert. Ein spezieller Masterserver übernimmt besondere Aufgaben, z.B. das Aufbauen und Verwalten einer Spielsitzung. Für die Unterstützung des Spielens über das Internet werden die Proxyserver kommunikationsnah zu den Clients betrieben. Auf diese Weise soll die Latenz der Client/Proxy-Kommunikation möglichst gering bleiben. Ein Szenario für einen derartigen Aufbau ist beispielsweise die Betreibung der Proxyserver bei Internet Service Providern.

In dieser Arbeit werden nun anhand der Portierung eines Mehrbenutzer-Echtzeitspiels, im Speziellen eines FPS, die Vorteile des Einsatzes der Proxy-Architektur für ein solches Spiel evaluiert. Die für die Portierung eingesetzte 3D-Engine ist die QFusion-Engine [10]. Diese kommt zum Einsatz, weil entscheidende Kriterien wie Aktualität, Serverskalierbarkeit sowie Wartung und Pflege durch den Support einer aktiven Internet-Community erfüllt werden. Die quelloffene QFusion-Engine emuliert das erfolgreiche Mehrbenutzer-Echtzeitspiel Quake III [11] und stellt damit einen allgemeinen und weit verbreiteten Vertreter des FPS-Genres dar. Mit einer Engine wird das Grundgerüst eines Computerspiels bezeichnet, welches unter anderem die Abbildung einer dreidimensionalen virtuellen Welt zum Inhalt hat. Eine solche Engine besteht im Wesentlichen aus Bibliotheken von Funktionen mit deren Hilfe Spielinhalte verschiedener Art wie Grafik, Sound oder bspw. Physik realisiert werden können und die Interaktion verteilter Teilnehmer ermöglicht. Durch die Portierung der Engine auf die Proxy-Architektur können somit auch zukünftige Projekte umgesetzt werden, die über die Emulation des Spiels Quake III hinausgehen.

Im weiteren Verlauf des 1. Kapitels werden die Hintergründe für die Wahl der QFusion-Engine erörtert. Kapitel 2 der Arbeit beschäftigt sich zunächst mit den für die Portierung relevanten Grundlagen der Ausgangsversion der QFusion-Engine. Es wird die verwendete Client/Server-Netzwerkarchitektur zusammen mit dem dabei eingesetzten Netzwerkprotokoll vorgestellt. Anschließend werden die Hauptprogrammschleifen (Mainloops) der beiden Applikationstypen Client und Server beschrieben. Dadurch wird eine Vorstellung über die inneren Abläufe zur Generierung des jeweils nächsten Spielzustands vermittelt. Des Weiteren werden die Spielzustandselemente identifiziert die letztlich auf die Proxyserver repliziert werden müssen. Im zweiten Teil des Kapitels wird ein Überblick über den Aufbau, den Fairnesssupport und die Kommunikationsmöglichkeiten der einzusetzenden Proxy-Architektur gegeben. Es wird ebenfalls auf das Konzept für die Synchronisation des Spielzustands: Die Eventual Consistency

Einleitung

eingegangen. In Kapitel 3 wird die Implementierung des Framework-API’s der Proxy-Architektur in den Netzwerkcode der QFusion-Engine erläutert. Begonnen wird mit der Vorstellung der eingesetzten Kommunikationsarten der Client- und Inter-Proxy-Kommunikation sowie der dafür benutzten Protokollheader. Die Implementierungen des Client- und Serverobjektes, welche die Schnittstellen der Proxy-Architektur zur Engine darstellen, werden im Anschluss daran aufgezeigt. Ein Überblick über die in den Client- und Inter-Proxy-Datenfluss involvierten Funktionen sowie die Erläuterung des Remoteclient-Konzeptes schließen das Kapitel ab. Diese Ausführungen sollten ein Verständnis der erfolgten Implementierung vermitteln und zukünftige Arbeiten ermöglichen. Mit der Synchronisation des verteilten Spielzustandes beschäftigt sich das Kapitel 4. Zu Beginn des Kapitels werden beispielhaft die notwendigen Schritte zur Synchronisation des Spielzustandes nach einer neuen Clientinteraktion veranschaulicht. Darauf aufbauend werden die verschiedenen auftretenden Interaktionen kategorisiert. Für jede identifizierte Aktionsart wird anschließend die Implementierung des Synchronisationskonzeptes vorgestellt. Des Weiteren werden mögliche Zeitpunkte innerhalb eines Ticks ¹ für die Initiierung der Zustandssynchronisationen diskutiert. Das implementierte Verfahren (Action Reordering) zur Verbesserung der Fairness zwischen qualitativ unterschiedlich angebundenen Clients wird anschließend ebenso, wie die spezifischen Synchronisationsaufgaben des Masterservers beschrieben. Aus der letztlich angeführten Hauptprogrammschleife des Proxyservers ist die verwendete zeitliche Abfolge der unterschiedlichen Synchronisationsschritte zu ersehen. Kapitel 5 beschäftigt sich mit der Installation und Benutzung der portierten 3D-Engine. Hierbei wird auf das Starten der verschiedenen Applikationen ebenso, wie auf die Benutzung der Konsole eingegangen. Anschließend werden die voreingestellten Konfigurationen präsentiert und es wird auf eventuell notwendige Änderungen eingegangen. Das Kapitel endet mit einigen Anmerkungen über die Benutzung des Spiels und die Einstellungen des Spielermodells. Kapitel 6 stellt die Ergebnisse der Evaluation der Portierung vor. Dazu werden zunächst zwei Skalierbarkeitsmodelle eingeführt mit deren Hilfe die in der Engine gemessenen Werte beschrieben werden. Anschließen folgen die Auswertungen zweier Evaluationstests. Einerseits wird die Client/Server-Version der Engine mit der portierten Version innerhalb eines lokalen Netzes verglichen. Andererseits wird ein auf mehrere Standorte verteilter Test der Engine ausgewertet. In Kapitel 7 erfolgt eine Zusammenfassung der Arbeit und es wird ein Ausblick auf zukünftige weitergehende Themenbereiche gegeben.

1.1 Die Wahl der Engine

Bei der Wahl der zu portierenden Engine wurde neben dem offen zugänglichen Quellcode insbesondere darauf geachtet, dass die anschließenden Kriterien erfüllt werden. Aktualität. Idealerweise sollte die Engine so gut wie möglich den Stand der aktuellen kommerziellen Produkte (Quake III, Unreal Tournament 2003…) repräsentieren [11, 12]. Dadurch würde die Leistungsfähigkeit der Proxy-Architektur anhand aktueller Spieltechnologien gemessen und somit eine hohe Glaubwürdigkeit erreicht.

Server-Skalierbarkeit. Das Spiel muss eine typische Client/Server-Architektur besitzen (2.1.1), in welcher der Server den gültigen Spielzustand berechnet und damit die Hauptrechenlast trägt. Demgemäß ist folglich durch eine Verteilung der Last auf mehrere Server eine Skalierung der Spielerzahlen möglich.

Mapgenerierung. Es sollte möglich sein, weitläufige Karten (Maps) für große Spielerzahlen zu erzeugen und auf eine Vielzahl von bereits existierenden Maps zuzugreifen. Weiterentwicklung, Wartung und Pflege. Ein fortgeführter Support der Engine, über die Version auf der die Arbeit basiert hinaus, wäre wünschenswert.

¹ eine Abarbeitung des Server-Mainloops

Einleitung

Zu Beginn der Arbeit wurden unter diesen Gesichtspunkten diverse Open-Source-Projekte untersucht, unter anderem:

• BZFlag

• Cube-Engine

• Quake I und Quake II

Der Hauptanteil der existierenden Projekte sind Erweiterungen der veröffentlichten Quake I und II Quellcodes und damit in den meisten Aspekten ähnlich. Die untersuchten Projekte waren alle mehr oder weniger gut geeignet. Es stellte sich allerdings heraus, dass die gewählte QFusion-Engine die oben genannten Gesichtspunkte mit Abstand am Besten erfüllte.

1.2 Die QFusion-Engine

Die QFusion-Engine wurde entwickelt, um eine Open Source Engine zu erschaffen, welche die Fähigkeit besitzt, Kontexte (Maps, Waffen, ect.) des Spiels Quake III Arena anzuzeigen. Die Engine ist eine Erweiterung und Veränderung des unter der GPL-Lizenz veröffentlichten Quake II Quellcodes [7]. Eine vollständige Liste der Features findet man in [4]. Die Engine erfüllt dementsprechend die Kriterien Aktualität und Server-Skalierbarkeit [6]. Für die Portierung wurde die QFusion-Engine Version 6.0 und die Modifikation SplitMod Version 2.0 als Basis verwendet [19]. Durch diese Modifikation können auch die Quake III Arena Spielermodelle eingesetzt werden. Es existiert eine Fülle von Karten für Quake III und damit auch für die QFusion-Engine [30]. Weiterhin können Karten über diverse Editoren und Tools (Q3Radiant, Q3map2…) generiert werden [20, 21], womit das Kriterium der Kartengenerierung erfüllt wird. An der Engine arbeitet ständig eine Handvoll Entwickler, die mit der Weiterentwicklung und Pflege beschäftigt sind, so dass in regelmäßigen Abständen neue Versionen erscheinen. Bei Fragen, beispielsweise zur Quellcodeanalyse, kann man sich an das Entwicklerforum wenden [13]. Aus diesen Gründen ist ersichtlich, dass sich die Engine hervorragend als Basis für diese Arbeit eignete.

1.3 Verwandte Arbeiten

In letzter Zeit wurden diverse Anstrengungen im Bereich der IT-Forschung unternommen deren Ziel es war, die Skalierbarkeit von Mehrbenutzerspielen zu erhöhen. Bevor mit den Ausführungen über die Portierung des First Person Shooters QFusion auf die Proxy-Architektur begonnen wird, sollen noch einige weitere erforschte Ansätze kurz vorgestellt und bewertet werden. In [38] wird eine skalierbare Client/Server-Architektur vorgestellt. Die dort erreichte erhöhte Skalierbarkeit resultiert aus einer Partitionierung der Spielwelt und der daraus folgenden Lastverteilung der Partitionen auf die eingesetzten Server. Ein Client hingegen wird innerhalb einer Session, entsprechend des Aufenthaltsortes seiner Spielfigur (Avatar) in der virtuellen Welt bzw. innerhalb einer Zone, verschiedenen Servern zugewiesen. Diese Partitionierung der Spielwelt findet auch bereits im kommerziellen Bereich des Genres der MMORPG’s ² statt und ermöglicht tausenden von Spielern eine Koexistenz in der jeweiligen Spielwelt. Abbildung 1 zeigt beispielhaft die Aufteilung der Spielwelt des japanischen MMORPG’s Ragnarok Online. Die Spielwelt hat

² Massively Multiplayer Online Role-Playing Games

Einleitung

eine Vielzahl weitgehend unabhängiger Zonen,

die jeweils von einem einzelnen Server verwaltet werden können. Unter Ausschluss der Möglichkeit, dass alle Spieler versuchen in eine einzige Zone und damit auf einen Server zu gelangen, erreicht man auf diesem Wege nahezu

Architekturen. Dieser Ansatz hat allerdings mehrere Nachteile für einen Einsatz im Bereich der FPS. Der Übergang von einem Server zum Anderen ist zeitaufwendig und erzeugt Spielflussunterbrechungen. Die Spielwelten bzw. Maps von First Person Shootern sind deutlich kleiner als die von MMORPG’s. Würde man diese partitionieren, sind

Zonenwechsel und damit Unterbrechungen des Spielflusses die Regel. In dem Fall, dass Interaktionen nahe den Serverübergängen

erlaubt sind, müssen diese speziell behandelt werden und sind ebenfalls kritisch [38, 6]. Des Weiteren kann man nicht ausschließen, dass sich zeitweise der Großteil der Spieler in einem Bereich befindet. Besonders nicht bei den durch das Spiel Battlefield eingeführten speziellen Spielmodi (Eroberung, Verteidigung, ect.) [22]. In diesem Anwendungsszenario stellt das Vorgehen der Proxy-Architektur, die Autorität über die Spieler zu partitionieren, einen deutlich besser skalierenden Ansatz dar.

Auch in [41] wurde versucht die Skalierbarkeit von Massively Multiplayer Games (MMG’s), durch eine Partitionierung der auftretenden Rechenlast, zu steigern. Die Aufteilung der Last erfolgt darin allerdings anhand von Spielergruppen und nicht durch eine generelle Partitionierung der Spielwelt. Dies ist möglich, da sich in den meisten MMG’s insbesondere in MMORPG’s immer nur eine Gruppe von Spielern an einer Stelle der Spielwelt befindet und dort einer Aufgabe (Quest) nachgeht oder sich beispielsweise duelliert. Die Interaktionen der vielen anderen Spieler haben deshalb auch keinen Einfluss auf deren Teil des Spielzustands. Die Zugehörigkeit eines Spielers zu einer Gruppe bzw. die Gruppenbildung basiert jeweils auf einem spielspezifischen Interessenmanagement durch Sichtbarkeits- und Einflussbereiche. Updates über Änderungen des Zustandes werden in der Folge auch nur innerhalb dieser Gruppen propagiert. Leider ist auch genau aus diesem Grund dieser Ansatz nicht geeignet die Skalierbarkeit von First Person Shootern zu erhöhen. Schließlich sind auch die Bemühungen auf diesem Gebiet dahingehend gerichtet die Anzahl gleichzeitig miteinander interagierender Spieler anzuheben. Gerade in Kampfsimulationen wie Battlefield 2 liegen aufgrund der Vehikelsimulationen die meisten Spieler im Einflussbereich der Mitspieler und verschlechtern somit die Möglichkeit der Gruppenbildung [22]. Eine andere Herangehensweise, zur Erhöhung der Skalierbarkeit von Mehrbenutzerspielen, präsentiert die Arbeit aus [40]. Darin wurde die Serverapplikation des FPS-Spiels Quake auf eine Version mit multiplen Threads portiert und anschließend auf einem Mehrprozessor-Host evaluiert [7]. Im Rahmen der Realisierung der Parallelisierung von Quake, stellte sich die Synchronisation des, nun durch mehrere Threads verwalteten, Spielzustandes als äußerst schwierig und laufzeitkritisch heraus. Bei den Auswertungen der Evaluationstests ergaben sich, bedingt durch das Locking von Teilzuständen, Synchronisationswartezeiten, die bis zu 40% der Berechnungszeit betrugen. Folglich ergab auch die Evaluation der Portierung, auf einem Host mit 8 Prozessoren, lediglich 25% mehr unterstützter Clients im Vergleich zur sequentiellen Originalversion. Im Gegensatz dazu wird sich im Lauf dieser Arbeit zeigen, dass bereits mit nur zwei Proxyservern ein Skalierungsvorteil von bis zu 40% zusätzlicher Teilnehmer im Vergleich zur Orginalversion mit Hilfe der Proxy-Architektur erreicht werden konnte.

Die QFusion Engine

In diesem Kapitel werden die für diese Arbeit relevanten Technologien, der Portierung zu Grunde liegenden QFusion-Engine, beschrieben. Das Verständnis dieser Techniken ist für den weiteren Verlauf der Arbeit entscheidend, da die Portierung so nah wie möglich an den ursprünglichen Konzepten vorgenommen wurde. Dazu wird die verwendete Netzwerkarchitektur zusammen mit dem eingesetzten Netzwerkprotokoll vorgestellt. Anschließend werden die Hauptprogrammschleifen (Mainloops) der Client- und Serverapplikation beschrieben. Des Weiteren werden die Spielzustandselemente identifiziert die auf die Proxyserver repliziert werden. Abschließend wird ein Überblick über die Funktionsweise und den Aufbau der für die Portierung verwendeten Proxy-Netzwerkarchitektur. Das einzusetzende Synchronisationskonzept (Eventual Consistency) wird ebenfalls im zweiten Teil des Kapitels erläutert. Mit diesem Kapitel erhält der Leser einen Überblick über die Softwarekomponenten, welche die Interaktion und Synchronisation der verteilten Spielsimulation eines Mehrbenutzer-Echtzeitspiels realisieren.

2.1 Die QFusion-Engine

Zu Beginn dieses Abschnittes werden die Client/Server-Netzwerkarchitektur und das eingesetzte Protokoll der QFusion-Engine zusammen mit dessen Headern dargelegt. Dabei wird auch auf die wichtigsten Nachrichtentypen und die zur Verringerung des zu versendenden Datenvolumens verwendete Deltakomprimierung eingegangen. Ferner werden die Abläufe innerhalb der Mainloops der beiden Applikationstypen (Client, Server) vorgestellt, um eine Vorstellung über die inneren Abläufe zur Generierung des jeweils nächsten Spielzustands zu vermitteln. Im Anschluss wird auf den Ausschnitt des Server-Datenmodells eingegangen, der die synchronisationsrelevanten Elemente des Spielzustandes beinhaltet.

2.1.1 Netzwerkarchitektur

Die in der Engine eingesetzte Architektur ist die im Allgemeinen in Multiplayer-Spielen

verwendete Client/Server-Architektur [6]. In diesem Szenario sendet der Client die Aktionen seines Spielers an den Server (1). Der Server empfängt alle Aktionen der Clients und berechnet den daraus folgenden Spielzustand, siehe Abbildung 2. Darin inbegriffen sind die Legalitätsprüfung der Aktionen, die Berechnung der Auswirkungen der Clientinteraktionen Voranschreiten

kontrollierten Elemente der Spielumgebung (2). Im nächsten Schritt werden allen Clients die daraus Spielerzustände sowie Abbildung 2 Client/Server-Architektur Zustände der Objekte mitgeteilt (3). Diese zeigen daraufhin eine aktualisierte Sicht auf

Die QFusion Engine

die Spielwelt an. Im folgenden Abschnitt wird ein Überblick über das für die Kommunikation eingesetzte Protokoll und die im Zusammenhang stehenden Konzepte gegeben.

2.1.2 Netzwerkprotokoll

Die QFusion-Engine wie auch ihre Derivate (Quake I, II…) verwenden für die Versendung von Daten ausschließlich das UDP-Protokoll [7, 36]. Der Großteil des Kommunikationsaufwandes erfolgt dementsprechend auch unzuverlässig. Zur Kompensation der entstehenden Nachteile, wie Paketverluste, Duplikation und Vertauschung

Paketsequenznummern eingesetzt. Für die Realisierung und Verwaltung des Netzverkehrs existiert deshalb eine Art Netzkanal (Struktur netchan_t, Anhang B) zu jedem Client, in dem unter anderem die Sequenznummer des zuletzt empfangenen Paketes gespeichert wird. Nachfolgende Pakete mit kleineren Sequenznummern und Duplikate können infolgedessen verworfen werden. Einige wenige Performance unkritische Transmissionen, wie Initialisierungsphase bzw. Verbindungsaufbau, Veränderung

des Spielermodells und z.B. der Inhalt des Client-Inventars, werden auf UDP basierend zuverlässig übertragen. Dies geschieht, in dem die Sequenznummern dieser Pakete durch ein „Zuverlässigkeitsbit“

(0x800000000) gekennzeichnet werden. Trifft solch ein zuverlässig zu versendendes Paket bei seinem Empfänger ein, wird von diesem bei der nächsten Sendegelegenheit die Sequenznummer des Paketes, inklusive gesetztem Bit, zurück an den Paketsender übertragen. Transmissionen werden folglich solange wiederholt, bis die entsprechende Sequenznummer einer zuverlässigen Transmission in dem zweiten Fragment des Headers (Abbildung 3) eines empfangenen Paketes enthalten ist. Aufgrund des ständig beiderseitigen Sendens von Informationen (Aktionen und Zustandsupdates) können die nötigen Bestätigungen (Acknowledgements) eines erfolgreichen zuverlässigen Transports auf diese Weise im regulären Datenverkehr integriert werden. Die Versendung von zusätzlichen ACK-Paketen, wie im Fall von TCP, kann somit entfallen [35]. Einer der Paketheader der bidirektionalen Kommunikation ist in Abbildung 3 dargestellt, wobei die angegebenen Zahlen für die Bytegröße des jeweiligen Fragmentes stehen. Das dritte

³ Ist nur in Paketen enthalten, die vom Client zum Server übertragen werden

Die QFusion Engine

2.1.2.1 Nachrichtentypen

Die wichtigste Nachricht die vom Server zu einem Client versendet wird, ist die Nachricht SVC_FRAME. Sie beinhaltet all die Informationen die der Client benötigt, um eine aktualisierte Sicht, somit ein neues Bild (Frame) der Simulation, anzuzeigen. Inbegriffen sind die Frame- und Deltaframe-Nummer des Komprimierungs-Verfahrens (2.1.2.2), die Nachricht die den Spielerzustand aktualisiert SVC_PLAYERINFO und die Nachricht die den Zustand aller im Sichtfeld des Client liegenden Objekte aktualisiert SVC_PACKETENTITIES. Der Client sendet hauptsächlich Nachrichten des Typs CLC_MOVE. Darin enthalten sind die Benutzeraktionen die aus den Eingaben des Users resultieren. In einem Paket wird jeweils die aktuelle Aktion (Struktur usercmd_t, Anhang B) zusammen mit den letzten beiden Aktionen versendet. Dies dient dem Server für Voraussagen auf Basis der Geschwindigkeit und Beschleunigung des Clients [6] und der Kompensation von Paketverlusten. Tabelle 1 gibt einen kurzen Überblick über den Inhalt der CLC_MOVE-Nachricht.

Eine Auflistung aller verwendeten Nachrichtentypen findet man in [Codelink01] und [8]. In [28] werden des Weiteren einige näher erläutert.

Tabelle 1 CLC_MOVE-Nachricht

2.1.2.2 Deltakomprimierung

Die QFusion-Engine setzt zur Reduktion des Datenaufkommens an mehreren Stellen verschiedene Versionen einer Deltakomprimierung ein. Besonders relevant ist die Komprimierung der Clientupdates (SVC_FRAME) durch den Server. Diese wird ermöglicht, in dem beim Übertragen des Updates ein Deltaframe angegeben wird, d.h. die Nummer eines Updates, welches als Basis für die Bildung des neuen Frames dient. Versendet werden dann nur die Elemente eines neuen Updates, die sich zu dem Deltaframe unterscheiden. Auf beiden Seiten wird dafür eine gewisse Anzahl alter Zustände zur Referenzierung gespeichert. Damit der Server Kenntnis über das vom Client als letztes empfangene Update hat, übermittelt der Client mit jeder CLC_MOVE die entsprechende Framenummer (Tabelle 1). Auch die Nachricht CLC_MOVE ist innerhalb ihres Wiederholungsteils komprimiert. Das erste Benutzerkommando wird noch unkomprimiert in die Nachricht übernommen, bei dem zweiten und dritten Kommando werden dann mit Hilfe der Bitmaske die Felder markiert, die sich gegenüber dem Deltakommando geändert haben und nur noch diese werden versendet.

Die QFusion Engine

Beispiel anhand der SVC_PLAYERINFO

Verwendung des Verfahrens, da der hier auftretende Kommunikationsaufwand um 33-56% verringert werden konnte.

2.1.2.3 Checksummen

Zur Vorbeugung von Manipulationen und damit zum Schutz des Inhaltes einer Benutzerkommando-Nachricht (CLC_MOVE), wird über den Kontext dieser Nachricht eine Checksumme gebildet. Der zur Generierung der Signatur verwendete Algorithmus ist MD4 [9]. Von den erzeugten 128 Bit pro Signatur werden 8 Bit für eine Nachrichten-Checksumme verwendet. Nähere Informationen findet man in [6] und [Codelink04].

2.1.3 Server-Mainloop

In diesem Abschnitt soll der Mainloop der Serverapplikation der QFusion-Engine näher beschrieben werden. Der Server-Mainloop wird durch die Methode SV_Frame(_) ⁴ [Codelink05] repräsentiert. Das wiederholte Ausführen dieser Methode generiert jeweils einen neuen Spielzustand, ein so genanntes Serverframe. Dieser neue Spielzustand wird vom Server nach einer Zeitspanne von ca. 100ms, auch Länge eines Ticks genannt [1], mit Hilfe der Nachricht SVC_FRAME (2.1.2.1) an die Clients versendet. Im Wesentlichen werden die folgenden Schritte zur Generierung eines neuen Serverframes abgearbeitet:

1. Auslesen, verifizieren und verarbeiten aller vorhandener Clientpakete. Es wird jeweils das erste Paket das beim Server eintrifft, als aktuell zu verarbeitendes gewählt. Speziell die Clientkommandos der Nachricht CLC_MOVE (2.1.2.1) werden durch die Methode ClientThink(_) [Codelink06] zu einem neuen Spielzustand verarbeitet. 2. Als nächstes zieht der Server von der Ticklänge die Berechnungszeit des letzten Frames ab und schläft für die Dauer der Differenz. Bei einer stetigen Erhöhung der Spieleranzahl, bis hin zur maximal unterstützten Anzahl, konvergiert diese Differenz gegen Null. Ist ein Paket eingetroffen wird Schritt 1 erneut ausgeführt und anschließend ruht der Server für die noch verbleibende Zeit. Nach Ablauf dieser Zeit werden nun aufgrund des Voranschreitens der Simulationszeit die Zustände aller von dem Server kontrollierten Objekte (Waffen, Rüstungen…) aktualisiert. Zu diesem Zweck dient die Methode G_RunFrame() aus [Codelink07].

⁴ Auslassung der Parameter, siehe Notation 3.1

Die QFusion Engine

3. Das Ende eines Durchlaufs durch den Mainloop ist durch das Übermitteln des neuen Spielzustandes, mit Hilfe der Methode SV_SendClientMessages() [Codelink03], an die Clients gekennzeichnet. Dafür ist es nötig, dass der Server zur Generierung eines clientspezifischen Updates die relevanten Informationen aus dem Gesamtspielzustand filtert. Durch die Reduktion der Updateinformationen auf die Objekte des Sichtbarkeitsbereiches (Viewspace) des Clients, werden die Bandbreitenanforderungen gesenkt und Betrugsversuche (Cheating) verhindert.

Die benötigte Zeit für die Abarbeitung dieser Schritte hängt maßgeblich von der Anzahl der Clients ab und bildet zugleich eine obere Grenze für die Anzahl der unterstützten Clients pro Spielsitzung. Für ein akzeptables Gameplay muss der Server eine Rate von 10 Clientupdates pro Sekunde (Tickrate) einhalten. Durch zu viele Clients wird der Server überfordert und kann die Tickrate nicht mehr erfüllen, so dass das Spiel zunehmend ruckelt (lagged) und unspielbar wird.

2.1.4 Client-Mainloop

Die Clientapplikation bleibt zwar bei der Portierung bis auf wenige Ausnahmen unangetastet, ist jedoch für die Steuerung der Synchronisationsintervalle des Servers von Interesse (vgl. 4.4). Die Hauptprogrammschleife der Clientapplikation wird durch die Methode CL_Frame(_) [Codelink08] implementiert. Ähnlich zum Server erzeugt das wiederholte Durchlaufen dieser Methode ein neues Clientframe bzw. eine aktualisierte und dem Benutzer angezeigte Sicht auf die virtuelle Welt. Eine Ausführung des Client-Mainloops besteht im Wesentlichen aus den folgenden Schritten:

1. Auslesen und verarbeiten eventuell vorhandener Serverpakete. Auch hier wird jeweils das erste Paket das eintrifft, als aktuell zu verarbeitendes gewählt. Im Speziellen werden die Clientupdates des Servers (SVC_FRAME) durch die CL_ParseFrame() Methode aus [Codelink09] verarbeitet.

2. Als nächstes wird mit Hilfe der CL_SendCommand() [Codelink08] eine Nachricht generiert (CLC_MOVE), welche die aktuelle Benutzeraktion repräsentiert. Anschließend sendet der Client die Nachricht an den Server.

3. Im letzten Schritt wird durch die SCR_UpdateScreen() Methode in [Codelink12] das aktuelle Frame angezeigt.

Der Client durchläuft diese Schleife mit einer individuellen und variablen Bildwiederholrate (Framerate), die aus der Komplexität der darzustellenden Szene und der Leistungsfähigkeit des Hosts resultiert. Für ein flüssiges Spielerlebnis muss die Clientframerate wesentlich höher liegen als die Tickrate des Servers es ermöglicht. Aus diesem Grund lässt man die Clientapplikation mit Hilfe derselben Bewegungsroutinen die auch der Server verwendet die Spielerposition bestimmen und anzeigen (Movement Prediction) [10, 6]. Auch wenn dieser Zustand erst noch durch den Empfang eines Zustandsupdates vom Server (SVC_FRAME) bestätigt werden muss. Der Server empfängt demzufolge innerhalb eines Ticks mehrere Nachrichten des Typs CLC_MOVE pro Client. Diese repräsentieren die Aktionen zwischen den Updates und synchronisieren die Simulationen. Damit eine sehr hohe Framerate auf dem Client nicht die zur Verfügung stehende Bandbreite überlastet, bestimmt man eine obere Grenze für die maximal erlaubte Bildwiederholrate. Zu diesem Zweck wird die Konsolenvariable cl_maxfps (5.3.1) gesetzt.

Die QFusion Engine

2.1.5 Ausschnitt des Server-Datenmodells

Die von der Engine simulierte virtuelle Welt besteht aus den statischen Informationen (Geometriedaten, Texturen, …) der jeweils geladenen Kartendaten (pk3-Dateien) und den Objekten (Entities), wie beispielsweise Spielern, Monstern oder Waffen. Der Spielzustand ist innerhalb der Engine stark verteilt, weshalb im Folgenden nur der Teil des Server-Datenmodells beschrieben werden soll, der von der Game-DLL (5.5) kontrolliert wird und für die Arbeit besonders relevant ist. Die zuvor erwähnten Objekte sind Instanzen der Struktur edict_t [Codelink14] und über ein globales Array zugreifbar: #include "g_local.h" edict_t *ent = &game.edicts[0]; for (i=0; i

Handelt es sich bei einem solchen Objekt um einen Avatar ⁵ , enthält die Instanz der Struktur einen gültigen Zeiger auf eine gclient_t-Struktur. Diese und die übergeordnete edict_t beherbergen dann die Informationen über den Zustand eines Clients auf dem Server und sind somit von besonderem Interesse. In der folgenden Tabelle 3 werden aus diesem Grund die Attribute der Strukturen vorgestellt, die die wichtigsten Elemente des Spielzustandes eines Clients repräsentieren und im späteren Verlauf auf die Proxyserver repliziert werden.

⁵ vom Spieler gesteuerte Figur bzw. Spielermodell