Seminar Game Development Distributed Applications

Seminar
Game Development
Distributed Applications
Christian Strebe
1005575
19. Juni 2007
Aufgabensteller:
Prof. Dr. Uwe M. Borghoff
Betreuer:
Dipl.-Inform. Daniel Volk
Institut für Softwaretechnologie
Fakultät für Informatik
Universität der Bundeswehr München
Christian Strebe
Distributed Applications
Inhaltsverzeichnis
1 Einleitung
3
2 Netzwerkarchitekturen
2.1 Client-Server . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 Vorteile der Client-Server Netzwerkarchitektur .
2.1.2 Probleme der Client-Server Netzwerkarchitektur .
2.2 Peer-to-Peer . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Vorteile der Peer-to-Peer Netzwerkarchitektur . .
2.2.2 Probleme der Peer-to-Peer Netzwerkarchitektur .
2.3 Hybride . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1 Verteilte Proxyserver . . . . . . . . . . . . . . . .
3 Client-Problematik
3.1 Interpolation/Extrapolation .
3.2 Reversible Simulation . . . .
3.3 Dead-Reckoning-Algorithmen
3.4 Event-Locking . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5
5
6
6
6
6
6
7
7
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
9
9
10
10
11
4 Skalierbarkeit
4.1 Shards . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Zoning . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Seamless Server . . . . . . . . . . . . . . . . . . .
4.3.1 Feste Zellen . . . . . . . . . . . . . . . . .
4.3.2 Dynamische Zellen . . . . . . . . . . . . .
4.3.3 Vorteile und Nachteile der Seamless Server
4.4 Trennung der Physik und KI-Simulation . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
12
12
13
13
15
15
16
16
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5 Ausblick
17
5.1 Zukünftige MMOGs . . . . . . . . . . . . . . . . . . . . . . . 17
5.2 Probleme der Mobilität . . . . . . . . . . . . . . . . . . . . . 17
5.3 Hybrid-Reality-Games . . . . . . . . . . . . . . . . . . . . . . 18
A Grafiken
19
2
Christian Strebe
Distributed Applications
Kapitel 1
Einleitung
In diesem Seminar, sind bisher die Probleme bei der Entwicklung einer
Singleplayer Game-Engine aufgezeigt und Lösungsmöglichkeiten dazu entwickelt worden. Mit der Entwicklung von Netzwerken sind jedoch neben den
’Verteilten Anwendungen’ auch Multiplayer-Games (MG) enstanden. Dies
sind Spiele, die es erlauben, dass mehrere Spieler im Netzwerk gegen oder
miteinander spielen können. Um die bisher gezeigten Konzepte so zu erweitern, dass eine Multiplayer-Engine entsteht, müssen neue Probleme gelöst
werden. Dies ist Thema dieser Arbeit. Schauen wir zunächst auf ’einfache’
MGs der Vergangenheit, wie zum Beispiel Quake2, Half-Life oder DeathRally. Diese Spiele verwendeten einfache Netzwerkarchitekturen, auf die in
Kapitel 2 näher eingegangen wird. Jedoch mussten gerade diese Spiele auf
Grund der verhältnismäßig leistungsschwachen Netzwerktechnik ihrer Zeit
mit den Problemen der Verteiltheit umgehen können, um einen realistischen
Spielfluss bei allen Teilnehmern zu ermöglichen. Diese Problematik wird im
Kapitel 3 näher betrachtet. Mittlerweile gibt es allerdings Massively Multiplayer Online Games (MMOG). Diese Spiele zeichnen sich, wie der Name schon sagt, dadurch aus, dass sehr viele Spieler gleichzeitig das Spiel
spielen können. Damit sind einzelne Server, wie noch bei den Vorgängern
üblich, nicht mehr ausreichend. Um eine Spielwelt der gewünschten Größe
zu verwalten, sind mehrere Server nötig. Dabei entstehen, dann zum Beispiel Konsistenzprobleme. Diese Problematik der Skalierbarkeit ist Thema
des Kapitels 4.
Eine Gemeinsamkeit der MG und der wesentliche Unterschied zu den Singleplayer Games ist die zur Game-Engine hinzugefügte ’Netzwerkkomponente’.
Sie ist verantwortlich für den Informationsaustausch über das Netzwerk zwischen den Teilnehmern. Wie in Abbildung 1.1 zu sehen, wird der aus dem
Bereich der Singleplayer-Game-Engines schon bekannte Begriff ’Middleware’
im Bereich der Multiplayer-Engines für diese Schicht verwendet. Ziel dieser
Komponente ist es, in möglichst kurzer Zeit mit möglichst geringer Netzwerklast den Informationsaustausch sicherzustellen sowie eine für den Pro-
3
Christian Strebe
Distributed Applications
Abbildung 1.1: Die Komponenten der Client/Server-Architektur.
Abbildung 1.2: Das ISO/OSI- und TCP/IP-Schichtenmodell.
grammierer transparente Schnittstelle zu schaffen. Eine Einordnung in das
ISO/OSI-Modell kann nur in Abhängigkeit von den Verantworlichkeiten bzw.
Fähigkeiten dieser Komponente getroffen werden. Im Allgemeinen ist sie, wie
in Abbildung 1.2 der Application-Schicht im TCP/IP-Schichtenmodell und
damit den Schichten fünf bis sieben im ISO/OSI-Modell zuzuordnen. Möglich ist jedoch auch, dass diese Komponente bereits auf der Transportschicht
ein eigenes Protokoll benutzt. Dann ist die Zuordnung entsprechend tiefer
vorzunehmen.
4
Christian Strebe
Distributed Applications
Kapitel 2
Netzwerkarchitekturen
Schon bei den ersten einfachen Multiplayergames spielte die Wahl der Netzwerkarchitektur eine wesentliche Rolle. Mit dieser Wahl verbunden sind grundlegende Charakteristiken und Schwachstellen des Spiels. Im Folgenden wird
die Client-Server sowie Peer-to-Peer Architektur vorgestellt. Abschliessend
wird kurz auf hybride Architekturen, die in heutigen Multiplayergames teilweise Anwendung finden, eingegangen.
2.1
Client-Server
In der klassischen Client-Server Netzwerkarchitektur gibt es einen Server,
der einen Dienst zur Verfügung stellt. Dieser Dienst kann dann, wie in Abbildung 2.1a zu sehen ist, durch mehrere Clients in Anspruch genommen
werden. Mittlerweile sind auch mehrstufige Architekturen möglich. So kann
zum Beispiel ein Server die Aufgabe der Datenspeicherung, für einen Client vollig transparent, an einen Datenbankserver abgeben. Die grundlegende
Charakteristik dieser Architektur bleibt jedoch erhalten.
(a) Die Client-Server-Architektur
(b) Die Peer-to-Peer-Architektur
Abbildung 2.1: Client-Server und Peer-to-Peer im Vergleich
5
Christian Strebe
2.1.1
Distributed Applications
Vorteile der Client-Server Netzwerkarchitektur
Wie man in Abbildung 2.1a erkennen kann, ist die Anzahl der Verbindungen, die in dieser Architektur unterhalten werden müssen gleich der Anzahl
der Clients. Damit wächst die Verbindungsanzahl lediglich linear. Gegenüber
der Peer-to-Peer Architektur ist dies sehr vorteilhaft. Ein weiterer wesentlicher Vorteil zeigt sich in folgender Situation. Angenommen in einem Multiplayergame kann nicht jedem Teilnehmer vertraut werden, dann wird eine
unanbhängige Schiedsrichterinstanz benötigt. Diese Funktion kann in dieser
Architektur vom Server übernommen werden. Es ist logisch, dass eine solche
Instanz unter Verwendung der Peer-to-Peer Netzwerkarchitektur nur sehr
schwer zu implementieren ist.
2.1.2
Probleme der Client-Server Netzwerkarchitektur
Betrachtet man diese Architektur vom Standpunkt der Ausfallsicherheit aus,
so wird der wohl wesentlichste Nachteil offensichtlich. Die gesamte, für das
Spiel notwendige, Kommunikation kann nur mit Hilfe des Servers stattfinden
und der für das Spiel notwendige Dienst ist ebenfalls nur auf diesem vorhanden. Somit ist klar, dass der Ausfall des Servers das Weiterspielen unmöglich
macht. Selbst wenn Backupserver eingesetzt werden, ist das ununterbrochene
Weiterspielen im Allgemeinen nur sehr schwer möglich.
2.2
Peer-to-Peer
Wie in Abbildung 2.1b zu sehen ist, sind in einem Peer-to-Peer Netzwerk
alle Teilnehmer gleichberechtigt. Das heißt, dass ein Teilnehmer Dienste zur
Verfügung stellt und auch von anderen in Anspruch nimmt. Eine klare Rollenverteilung, wie in der Client-Server Netzwerkarchitektur existiert somit
nicht.
2.2.1
Vorteile der Peer-to-Peer Netzwerkarchitektur
Der offensichtlichste Vorteil dieses Modells ist, dass kein zusätzlicher Server
benötigt wird. Dies reduziert den Hardwareaufwand. Außerdem wirkt sich
der Ausfall eines Peers im Gegensatz zur Client-Server Netzwerkarchitektur
nicht so gravierend aus. Die nicht betroffenen Spieler können weiter spielen.
Ein Neustart einer Spielsession ist somit nicht nötig.
2.2.2
Probleme der Peer-to-Peer Netzwerkarchitektur
Die Anzahl der Unicast-Verbindungen1 v, die unter Verwendung der Peer-toPeer Netzwerkarchitektur bei n Clients unterhalten werden müssen, errechnet
1
Eine Verbindung zwischen genau zwei Teilnehmern.
2.2. PEER-TO-PEER
6
Christian Strebe
Distributed Applications
sich wie folgt:
(n − 1) ∗ n
n2 − n
=
(2.1)
2
2
Es ist leicht zu erkennen, dass mit steigender Peer-Anzahl der Verbindungsaufwand quadratisch wächst. Dies bewirkt, dass Peer-to-Peer Modelle mit
Unicast-Verbindungen nur begrenzt skalierbar sind. Bei Verwendung von
Broadcast2 /Multicast3 -Verbindungen ist die Anzahl der Verbindungen gleich
der Anzahl der Peers, jedoch muss dann jeder Peer alle Nachrichten verarbeiten, auch wenn sie für ihn nicht relevant sind. Daher ist dieses Modell
für eine große Teilnehmeranzahl ungeeignet. Da es keinen zentralen Server
gibt, müssen die Teilnehmer in diesem Modell sich selbst um das Finden im
Netzwerk, was im Internet aufgrund der Größe und der Struktur schwierig
werden kann, kümmern. Eine Initialisierung eines Spiels/Sitzung kann daher
schwierig sein. Außerdem muss allen Peers vertraut werden, da es keine unabhängige Entscheidungsinstanz geben kann. Ein Schutz vor Cheatern oder
Hackern ist somit nicht bzw. nur sehr schwer möglich.
v=
2.3
Hybride
In den vorangegangenen Abschnitten lässt sich bereits erkennen, dass in beiden Netzwerkarchitekturen in Hinblick auf die Skalierbarkeit eine Obergrenze
existiert. Um diese Grenze nach oben zu verschieben sowie die Vorteile beider
Architekturen zu verbinden, können die bereits vorgestellten Netzwerkarchitekturen verändert bzw. gemischt werden. Nun nachfolgend wird ein Beispiel
für eine Hybride Architektur vorgestellt. Prinzipiell gibt es noch viel mehr
Varianten. Die wesentlichen Aspekte jedoch werden aber bereits in diesem
Beispiel deutlich.
2.3.1
Verteilte Proxyserver
Wie in Abbildung A.1 zu sehen ist, verwenden in dieser Architektur, mehrere Proxyserver4 zur Kommunikation untereinander eine Peer-To-Peer Netzwerkarchitektur. Mehrere Clients kommunizieren mit je einem dieser Proxyserver über die Client-Server Netzwerkarchitektur. Damit wird die Anzahl
der Verbindungen im Gegensatz zur reinen Peer-to-Peer Netzwerkarchitektur gering gehalten. Außerdem muss nicht jeder Server die gesamte Kommunikation mit allen Clients sicherstellen, was zu einer wesentlichen Entlastung
des Servers, im Gegensatz zu der reinen Client-Server Netzwerkarchitektur,
beiträgt. Desweiteren können die Server auch geographisch verteilt werden,
so dass die Verbindungswege der Server zu den Clients kürzer werden, was
2
Nachrichten werden an alle Teilnehmer eines Netzwerks versandt.
Nachrichten werden an eine bestimmte Teilnehmergruppe versandt.
4
Dienstprogramm für Netzwerke, dass Anfragen bearbeitet oder weiter vermittelt.
3
2.3. HYBRIDE
7
Christian Strebe
Distributed Applications
die Kommunikation ebenso verbessern kann. Weiterhin ist vorteilhaft, dass
trotz eines Serverausfalls die betroffenen Clients unter Verwendung eines anderen Proxyservers einfach weiter spielen können. Versuche am Institut für
Informatik an der ’Westfälischen Wilhelms-Universität Münster’ haben gezeigt, dass unter Verwendung dieser Architektur die Anzahl der Spieler in
Quake II bei Einsatz von drei Servern verdoppelt werden konnte. Damit skaliert diese Architektur nicht linear und ist somit für ein MMOG noch nicht
ausreichend. Im Kapitel 4 wird daher auf weitere Techniken eingegangen,
mit denen die Teilnehmeranzahl deutlich erhöht werden kann.
2.3. HYBRIDE
8
Christian Strebe
Distributed Applications
Kapitel 3
Client-Problematik
Bei einem MG ist die Darstellung auf dem Client von der Simulation auf dem
Server getrennt. Die Konsistenzerhaltung zwischen Simulation und Darstellung erfolgt über ein Netzwerk. Da aus technischen Gründen stets nur eine
begrenzte Bandbreite im Netzwerk zur Verfügung steht, können auch nur
im begrenzten Umfang Nachrichten über Änderungen in der Spielsimulationswelt vom Server an die Clients oder umgekehrt verschickt werden. Auch
Datenkompression oder andere Verfahren haben ihre Grenzen. Dies führt unweigerlich dazu, dass die Anzahl der Änderungsmeldungen beschränkt werden muss. Eine absolut konsistente Simulationswelt bei allen Teilnehmern ist,
wie in den folgenden Abschnitten klar ersichtlich ist, nicht möglich. Jedoch
ist der Grad der Konsistenz häufig entscheidend für die Glaubhaftigkeit der
Simulationswelt. Damit eine trotzdem flüssige Spielsimulation durchgeführt
werden kann, sind insbesondere Techniken der Movement Prediction notwendig. Diese Techniken erlauben es dem Client für eine gewisse Zeit, auch ohne
Änderungsinformationen von Objekten der Umgebung, die Bewegung dieser
weiter zu berechnen und darzustellen.
3.1
Interpolation/Extrapolation
Interpolation und Extrapolation sind von großer Bedeutung bei der Movement Prediction. Mit Extrapolation wird die Bewegung eines Objekts für eine
gewisse Zeit auch ohne genaue Informationen weiter berechnet. Das Prinzip
der Extrapolation ist in Abbildung 3.1a dargestellt. Die schwarze Linie ist
die Serversicht auf die Bewegung eines Spielers. Ein Client berechnet diese
Position bei dem Fehlen der genauen Positionsangaben anhand der letzten
Position und der Bewegung in dieser Position, was die gerade, rote Linie
ergibt.
Mit Hilfe der Interpolation wird eine möglichst kontinuierliche Angleichung zwischen zwei Punkten bestimmt. In Abbildung 3.1b ist die Interpolation beispielhaft dargestellt. Der Client versucht die Differenz zwischen
9
Christian Strebe
(a) Server und Client Sichten bei Extrapolation.
Distributed Applications
(b) Server und Client Sichten bei Interpolation.
Abbildung 3.1: Extrapolation und Interpolation im Vergleich.
der mittels Extrapolation berechneten und der tatsächlichen Position für den
Spieler unmerklich wieder auszugleichen. Jedoch wird in vielen Spielen diese
Problematik durch zum Beispiel springende Spieler zusätzlich erschwert. Damit dabei keine durch die Spielwelt schwebenden Spieler auftreten, kann die
Extrapolation auch mittels einer Kurve durchgeführt werden, die dann der
Sicht des Servers wesentlich näher kommt und dem Spieler eine realistischere
Spielwelt vermittelt.
3.2
Reversible Simulation
Da gerade bei First Person Shootern in dieser offensichtlich doch leicht inkonsistenten Spielwelt die Frage, ob der durchgeführte Schuss ein Treffer
war oder nicht, dies nicht sofort entschieden und dem Client nicht vertraut
werden kann, muss der Server über eine Möglichkeit verfügen, dies herauszufinden. Der Server muss also über eine Technik verfügen, die es ihm erlaubt
gemäß dem Prinzip "Never trust the client"die Korrektheit eines Treffers zu
überprüfen. Diese Technik heißt Reversible Simulation. Der Client übermittelt dem Server den Zeitpunkt sowie den Ort des möglichen Treffers. Der
Server ermittelt die letzte Änderungsnachricht, die er an diesen Client vor
dem Zeitpunkt des möglichen Treffers versandt hat. Ausgehend von dieser
Nachricht berechnet der Server dann den Ort, an dem sich das mögliche Opfer
zum Zeitpunkt des Treffers auf dem Client befunden haben muss. Stimmen
die beiden Orte überein, so ist der Treffer gültig.
3.3
Dead-Reckoning-Algorithmen
Viele Spiele verschicken mit einer konstanten Rate ihre Zustand-Updates.
Dies kann in einigen Fällen sehr ungünstig sein. Besonders bei Spielen, in
denen es relativ wenige Richtungswechsel gibt und so die Vorhersagbarkeit einer zukünftigen Position aus bereits bekannten Positionen durchaus möglich
ist, kann unter Verwendung der Dead-Reckoning-Algorithmen ein anderer
3.2. REVERSIBLE SIMULATION
10
Christian Strebe
Distributed Applications
Weg bestritten werden. Alle Clients berechnen die Positionen und Bewegungen der nicht von ihnen kontrollierten Objekte mittels der Extrapolation
und Interpolation. Bei den von ihnen kontrollierten Objekten berechnen die
Clients stets die Differenz der realen zur extrapolierten Position sowie Bewegung. Übersteigt diese Differenz einen Schwellwert, so wird ein Update
geschickt. Damit werden Updates nur nach Bedarf geschickt, was Bandbreite sparen kann. Wie schon erwähnt, sind diese Algorithmen nur für Spiele mit
relativ wenigen Richtungswechseln geeignet. Bei Spielen mit sehr häufigen
Wechseln kann das Reduzieren der Updatenachrichten auf Positionsangaben
sowie das Extrapolieren, mittels einer so genannten Tracking-Kurve durch
die letzten drei bekannten Positionen ebenfalls zu guten Ergebnissen führen.
Vorgestellt wurde diese Methode von Singhal und Cheriton (SC95).
3.4
Event-Locking
Gerade bei Spielen, bei denen ein Teilnehmer sehr wenige Eingaben durchführt, wie zum Beispiel bei Strategiespielen, kann die Anzahl der Änderungsnachrichten ebenfalls erheblich gesenkt werden. Da diese Spiele meist über
ausgereifte und auch deterministische Algorithmen für die Pfadsuche verfügen und alle Clients die aktuelle Position der Objekte kennen, genügt die
Angabe der Ankunftszeit eines Objekts an seinem Zielort. Mit diesen beiden
Informationen können dann alle anderen Clients und insbesondere der Server den Pfad des Objekts, die aktuelle Position entlang des Pfades sowie die
Bewegungsgeschwindigkeit berechnen. Es ist klar, dass es so möglich ist, die
Geschwindigkeit, mit der sich ein Objekt auf dem jeweiligen Client bewegt,
so anzupassen, dass dieses auf allen Clients gleichzeitig sein Ziel erreicht.
3.4. EVENT-LOCKING
11
Christian Strebe
Distributed Applications
Kapitel 4
Skalierbarkeit
Alle in den vorangegangenen Kapiteln beschriebenen Problematiken finden
sich ebenso bei MMOGs wieder. Jedoch besteht gerade bei diesen Spielen
das Problem, dass eine Spielwelt existieren muss, die genügend Platz für alle
Teilnehmer bietet. Man bedenke, dass bei einigen Vertretern dieser Spiele bereits mehr als 30.000 Teilnehmer gleichzeitig online waren. Dies führt
dazu, dass zunächst die Spielwelt auf verschiedene Server verteilt werden
muss. Dies kann bei MMOGs, wie man es von MGs schon seit langem kennt,
mit Hilfe von Shards aber auch durch Zoning oder Seamless Servern geschehen. Damit kann eine ausreichend große Spielwelt realisiert werden, jedoch
bringen gerade die Spieler eine gewisse Dynamik und damit auch ungleiche
Lastverteilung auf den Servern mit sich. Um dies abzufangen, können bei
Seamless Servern dynamische Zellen eingesetzt werden. Dies ist in Unterabschnitt 4.3.2 beschrieben.
4.1
Shards
In MGs ist es schon seit langem üblich, dass ein Server eine Spielwelt mit
begrenzter Teilnehmerzahl verwaltet. Möchte man erreichen, dass mehr Teilnehmer gleichzeitig spielen können, so genügte es, einen weiteren Server zu
starten. Die Spielwelt existiert noch einmal. Offensichtlich ist, dass die Spielwelten der beiden Server in diesem Fall nicht zusammenhängen. Spieler des
einen Servers können nicht mit Spielern des anderen Servers interagieren.
Diese Spielwelten nennt man dann Shards. Dies ist bei MMOGs teilweise
auch nötig. Ist zum Beispiel ein Kartenabschnitt so interessant gestaltet und
kann auf grund des Spieldesigns kein zweites mal erschaffen werden, so kann
mit Hilfe eines Shards dieser Abschnitt repliziert und die Spieler auf den
Replikaten verteilt werden. Dies ist jedoch nur eine ’Notlösung’.
12
Christian Strebe
4.2
Distributed Applications
Zoning
Um eine möglichst große Anzahl von Spielern gleichzeitig an dem Spiel teilnehmen zu lassen, muss die Spielwelt so aufgeteilt werden, dass die zur Verfügung stehende Serverkapazität ausreicht. Durch Unterteilen der Spielwelt
in gleich große Zonen kann dies erreicht werden. Der Übergang von einer
Zone zur Anderen wird so gestaltet, dass eine Interaktion über diese Grenze hinweg nicht möglich ist. Dies erlaubt es dann beliebig viele Zonen zu
gestalten. Für jede Zone wird dann ein Server eingerichtet, der die nötigen
Berechnungen innerhalb dieser Zone übernimmt. Dieses Prinzip wird Zoning
genannt. Vorteilhaft daran ist, dass es softwaretechnisch relativ leicht umzusetzen ist, da besonders schwierige Interaktionen zwischen den Servern nicht
existieren. Weiterhin kann eine so kreierte Welt durch Hinzufügen von Zonen
beliebig erweitert werden. Jedoch dürfen die bereits genannten Einschränkungen dieses Prinzips nicht vergessen werden. Interaktionen über Zonengrenzen hinaus dürfen nicht möglich sein. Die Möglichkeiten der Designer
einer Spielwelt werden dadurch sehr stark eingeschränkt. Als Gestaltungsmöglichkeiten bleiben ihnen zum Beispiel Teleporter, weit entfernte Inseln
oder ähnliche Dinge. Außerdem kann eine Zone selbst nicht besonders gross
sein, da sie von lediglich einem einzigen Server verwaltet werden muss. Zudem ist der angesprochene Aspekt der Dynamik ein großes Problem dieses
Konzepts. Wenn zum Beispiel eine Zone so interessant gestaltet ist, dass sich
sehr viele Teilnehmer in ihr aufhalten, so steigt die Anzahl der Clients, die
der zonen-verantwortliche Server bedienen muss, so dass dieser überlastet
werden kann und schliesslich ausfällt. Zwar können die Server anderer Zonen weiter laufen, aber für die betroffenen Spieler ist ein Weiterspielen nicht
möglich. Damit kann dieses Konzept als einfach zu Implementieren bewertet
werden, birgt aber auf Grund der Einschränkungen, die es den Spielweltdesignern auferlegt und der immer noch deutlich bestehenden Gefahr eines
Serverausfalls für MMOGs erhebliche Nachteile.
4.3
Seamless Server
Einen anderen Ansatz verfolgt das Prinzip der Seamless Server. Die Spielwelt
wird dabei fortlaufend gestaltet. Klar erkennbare Grenzen wie beim Zoning
gibt es nicht. Danach wird die Welt entlang sinnvoller Grenzen schachbrettartig aufgeteilt. Jedes dieser Felder wird in Verantworlichkeit eines Servers
gegeben. Den Spielern wird explizit gestattet, sich über die Grenzen hinweg,
zu bewegen beziehungsweise zu agieren. Damit ist klar, dass den Abläufen
in diesem Grenzbereich besondere Aufmerksamkeit gewidmet werden muss.
Zunächst der Fall, dass ein Spieler vor einer Grenze steht und hinüber schaut.
Logischerweise möchte dieser Spieler alle Objekte und auch andere Spieler
4.2. ZONING
13
Christian Strebe
Distributed Applications
in seinem Awareness-Bereich1 sehen. Dies führt dazu, dass der Server auf
dem er sich gerade befindet den Nachbarserver kennen und in einem ausreichend großen Abstand Objekte des anderen Servers ebenso anzeigen muss.
Da er diese nicht selbst als aktive Objekte verwalten darf, müssen dies ProxyObjekte2 sein.
Diese Proxy-Objekte müssen den gleichen Zustand aufweisen, wie ihre
aktiven Objekte auf dem Nachbarserver. Dies führt dazu, dass sie durch
beide Server absolut konsistent gehalten werden müssen. Um dies möglichst
effizient zu gewährleisten, liegt der Schluss nahe diese Proxy-Objekte auf
das Wesentliche zu beschränken. Dabei gilt es Folgendes zu bedenken. Führt
dieser Spieler nun eine genügend große Vorwärtsbewegung aus, so wird er die
Grenze überschreiten und begibt sich dann in Verantwortlichkeit des anderen
Servers. Somit ist klar, dass ein geschickter und schneller Mechanismus der
Übergabe von Objekten von einem zum anderen Server nötig ist. Verfügen die
Proxy-Objekte über die selben Informationen wie ihre zugehörigen aktiven
Objekte, so kann dieser Wechsel sehr schnell und simpel vollzogen werden. Es
genügt aus dem Proxy-Objekt ein aktives Objekt zu machen und umgekehrt.
Damit muss eine gute Balance zwischen einfach synchron zu haltenden und
schnell zu übergebenden Proxy-Objekten gefunden werden. Zusätzlich gilt
es dabei noch zu überlegen, ob die Übergabe an einer konkreten Linie zu
erfolgen hat oder innerhalb eines gewissen Bereichs erfolgen soll. Es ist ja
möglich, dass ein Spieler sich entlang einer Grenzlinie bewegt und somit
ständige Wechsel zwischen den Servern und damit eine erhöhte Last auf
diesen verursacht. Weiterhin muss an den Grenzen auf Interaktionen geachtet
werden, die zwar auf einem Server beginnen, jedoch auf dem Nachbarserver
enden oder einen Bereich dort betreffen. Auch diese Interaktionen müssen
die gleiche Wirkung haben, als wenn sie innerhalb eines Servers durchgeführt
werden. Dies erhöht die Schwierigkeit der Konsistenzerhaltung zwischen den
Servern wesentlich.
Nun folgend werden weitere spezielle Problemfälle betrachtet. In Abbildung A.3b ist zu erkennen, dass sich Spieler P2 im Grenzbereich befindet und
daher auf Server1 dargestellt wird und für Spieler P1 sichtbar ist. Umgekehrt
ist jedoch festzustellen, dass Spieler P1 sich nicht in diesem Bereich befindet und auf Server2 nicht dargestellt wird. Daher kann Spieler P2 seinen
Mitspieler nicht sehen und auch nicht mit ihm agieren, obwohl es umgekehrt durchaus möglich ist. Damit wird klar, dass der Grenzbereich zu klein
gewählt wurde. Wird jedoch der Grenzbereich sehr groß gewählt, so müssen wesentlich mehr Objekte auf beiden Servern verwaltet werden, was zu
einer immensen Laststeigerung führt. Das Ergebnis dieser beiden Feststellungen ist, dass der Grenzbereich genauso groß gewählt werden muss, wie
1
Bereich eines Spielers, in dem er mit Objekten interagieren oder diese sehen kann.
Meist auch Interessensbereich genannt.
2
Ein Stellvertreter-Objekt für ein aktives Objekt auf einem anderen Server
4.3. SEAMLESS SERVER
14
Christian Strebe
Distributed Applications
der maximal mögliche Awarnesbereich eines Spielers ist. Da aber die Spielwelt schachbrettartig aufgeteilt ist, gibt es nicht nur Grenzbereiche zwischen
zwei Servern, sondern sogar zwischen drei und mehr. In Abbildung A.3c ist
ein Grenzgebiet gezeigt, an dem sich drei Server beteiligen. In solch einem
Fall ist die Last, die durch die Server-Server-Interaktionen entstehen recht
hoch. Betrachten wir noch einen anderen Problemfall. In Abbildung A.3d ist
ein Objekt dargestellt, welches auf einer Grenze liegt und zusätzlich größer
als der Grenzbereich ist. Eine Lösungsmöglichkeit ist das simple Ignorieren
eines solchen Falls nach der ’Vogel-Strauß-Methode’, das Verbieten oder das
wesentlich aufwändigere Betrachten dieses Falls. Der letztere Lösungsansatz
erhöht den Entwicklungsaufwand wesentlich jedoch ist er gerade für die im
Unterabschnitt 4.3.2 vorgestellten dynamischen Zellen von Bedeutung.
4.3.1
Feste Zellen
Durch die Festlegung von festen Grenzen, die so gestaltet werden, dass möglichst wenig Interaktionen über Zellen hinaus möglich sind, wie zum Beispiel durch Einsatz von Hügeln oder Tunneln im Spiel, werden den Designern der Spielwelt drastische Einschränkungen auferlegt. Jedoch können
die Grenzbereiche der Zellen dann deutlich kleiner gestaltet werden, was die
Last durch Proxy-Objekte wiederum verringert. Das bekannte Problem vom
Zoning bleibt jedoch. Verteilen sich die Spieler nicht gleichmäßig, sondern
konzentrieren sich auf ein Feld, so hat dies zur Folge, dass der entsprechende
Server überlastet werden kann.
4.3.2
Dynamische Zellen
Um das bekannte Problem der Überlastung eines Servers aus Zoning und den
festen Zellen, aufgrund zu vieler Spieler, zu umgehen, können die Zellengrenzen dynamisch gestaltet werden. Die Zellengröße einer solchen kann dann, in
Abhängigkeit von der Spieleranzahl in der Zelle, angepasst werden. Befinden
sich also zu viele Spieler in einer Zelle wird sie entsprechend verkleinert. Außerdem kann mit Hilfe von dynamischen Zellen eine weitere Zelle in einem
Bereich und somit auch ein weiterer Server in diesem Bereich hinzugefügt
werden. Eine gleichmäßige Lastverteilung der Server kann so wesentlich besser erreicht werden. Die Zellengrenzen können dabei zum Beispiel in kleinen
Schritten verschoben, durch Unterteilung des betreffenden Gebiets in zwei
bzw. vier neue Teilgebiete oder auf andere Art verändert werden. Unabhängig
von der Art und Weise der dynamischen Grenzverschiebung sind diese Vorgänge sehr komplex. Häufig müssen bei einer Verschiebung der Zellengrenze
viele Objekte von einer Zelle zur nächsten ohne merkliche Verzögerung übertragen werden. Überdies hinaus ist auch die Häufigkeit der Verschiebungen
entscheidend. Zu häufig erzeugt dies natürlich eine erhöhte Serverlast. Werden Grenzen zu selten verschoben, treten die selben Probleme wie bei festen
4.3. SEAMLESS SERVER
15
Christian Strebe
Distributed Applications
Zellengrenzen auf. Ebenso ist die Funktion, die die neuen Grenzen berechenet, sehr komplex. Dies liegt daran, dass diese für die nächste Periode
gelten sollen. Damit sind aufwändige Abschätzungen in Bezug auf die Serverbelastung, für diesen Zeitabschnitt nötig. Unter Umständen kann es bei
dynamischen Zellen ebenso wichtig sein,dass Grenzen durch größere Objekte hindurch verlaufen können. Dies erlaubt dann eine wesentlich flexiblere
Positionierungen von Grenzen.
4.3.3
Vorteile und Nachteile der Seamless Server
Sehr vorteilhaft ist, dass dieses Prinzip durchaus sehr gut skalieren kann. Es
ist möglich, eine riesige Welt zu erschaffen, die sehr vielen Spielern gleichzeitig das Spielen ermöglicht. Durch die Nutzung von dynamischen Zellen ist
dieses Prinzip sehr verlässlich, da zumindest keine Überlastungen von Servern aufgrund zu vieler Spieler möglich sind. Weiterhin ist sehr vorteilhaft,
dass die Clients nicht dauerhaft die gesamte Spielwelt geladen haben müssen.
Es genügt, wenn das entsprechende Kartenstück kurz vor Überschreiten einer
Grenze nachgeladen wird. Nachteilig ist die sehr große Komplexität, die sich
in der Entwicklung eines solchen Spiels auswirkt. Um jedoch ein MMOG zu
gestalten, das einer realen Welt sehr nahe kommt, führt an Seamless Servern
kaum ein Weg vorbei.
4.4
Trennung der Physik und KI-Simulation
Bisher ist in diesem Kapitel auf die Trennung und anschließende Verteilung
der dynamischen Daten der Spielwelt eingegangen worden. Man kann jedoch
auch Teile der Game-Engine, wie zum Beispiel die Physiksimulation oder
die künstliche Intelligenz, abtrennen. Dies ist in Abbildung A.2 durch den
gestrichelten Trennstrich B dargestellt. Diese Teile können dann auf eigenen
Servern laufen. Dabei ist es meist notwendig ein so genanntes Frontend für
die Clients einzuführen. Außerdem ist es weiterhin sinnvoll, in einer solchen
Situation einen Datenbankserver, wie in Abbildung A.4 zu sehen, einzusetzen, der die Daten der Spielwelt beinhaltet. Der eigentliche Spielserver wird
in einem solchen Fall dann nicht mehr so stark belastet und kann so mehr
Spieler sowie auch größere Zellen verwalten. Eine absolute Obergrenze in
Hinblick auf die maximale Anzahl der Spieler und die Größe der Zelle existiert jedoch weiter.
4.4. TRENNUNG DER PHYSIK UND KI-SIMULATION
16
Christian Strebe
Distributed Applications
Kapitel 5
Ausblick
Die Weiterentwicklung im Bereich der MMOGs bewegt sich scheinbar immer
mehr hin zu Spielen mit dynamsichen Welten. Desweiteren hat die Entwicklung von mobilen Geräten und Anwendungen für diese stark an Bedeutung
gewonnen. Dies ist insbesondere für MMOGs auf diesen Geräten bedeutsam. Daher abschließend noch ein kleiner Blick auf die damit verbundenen
Problematiken.
5.1
Zukünftige MMOGs
Mit ’Second Life’ hat sich bereits ein MMOG mit dynamischer Welt etabliert.
In diesem Spiel ist es den Spielern möglich die Welt selbst zu gestalten und
somit ihren eigenen Bedürfnissen anzupassen. Weiterhin existiert in Hinblick
auf die Größe der Spielwelt keine festgelegte Obergrenze. Damit kann nicht,
wie bei herkömlichen MMOGs, die gesamte Welt auf einem Client installiert
werden. Viel mehr muss ein Mechanismus bestehen, der es dem Client ermöglicht Spielweltinhalte nach Bedarf herunterzuladen. Dies kann zum Beispiel
mit Hilfe von Streams geschehen. Patches um Fehler in der Spielwelt zu beheben oder diese zu erweitern sind nicht mehr nötig. Weiterhin ist in diesem
Zusammenhang zu beobachten, dass der Client immer mehr zu einem so genannten Thin-Client reduziert wird. Die einzige Aufgabe dieser Thin-Clients
ist es, die dynamische Spielwelt anzuzeigen und Eingaben des Spielers an
den Server zu übermitteln.
5.2
Probleme der Mobilität
Mobile Geräte wie Mobiltelefone haben meist nur eine verhältnismäßig kleine Anzeige, eingeschränkte 3D-Funktionalitäten und begrenzte Eingabemöglichkeiten. Dies bewirkt, dass die Darstellung eines Spiels auf diese Geräten
speziell angepasst werden muss. Wenn die Anwendung bzw. das Spiel gleichzeitig von stationären PCs und Mobiltelfonen genutzt werden soll, dann
17
Christian Strebe
Distributed Applications
dürfen im Allgemeinen für die mobilen Teilnehmer keine Nachteile daraus
entstehen. Dies stellt dann als Konsequenz sehr hohe Anforderungen an das
Design des User-Interfaces. Auch ist die Rechenkapazität der mobilen Geräte stark eingeschränkt. Dies muss in der Anwendung ebenso berücksichtigt
werden. Trotz Universal Mobile Telecommunications System (UMTS / 3G)
ist die zur Verfügung stehende Bandbreite für eine Verbindung im Verhältnis
zu den Bandbreiten stationärer Rechner stark begrenzt. Desweiteren sind die
Latenzzeiten der drahtlosen Verbindungen auch meist höher. Betrachtet man
diese Probleme näher, so stellt man fest, dass diese nachteiligen Effekte sich
durch die bereits bekannten Mechanismen der Movement Prediction ausgleichen lassen. Ebenso kann mit Hilfe dieser Mechanismen unter Umständen
auch ein kurzer Zusammenbruch der Verbindung auf Grund von Abschattung überbrückt werden. Ist die Verbindung jedoch länger unterbrochen, so
muss ein geeigneter Mechanismus, der den betreffenden Teilnehmer aus der
Spielsession herausnimmt oder eine künstliche Intelligenz, die für den Spieler
dann übernimmt, existieren. Da diese Probleme offensichtlich lösbar sind, ist
den Spielen auf mobilen Geräten durchaus erhebliches Potenzial zuzutrauen.
Einige namhafte Hersteller haben in den vergangenen Jahren bereits Produkte aus diesem Bereich auf den Markt gebracht und waren damit sehr
erfolgreich. Eine Entwicklung eines MMOGs für ein mobiles Gerät ist durchaus denkbar.
5.3
Hybrid-Reality-Games
Eine Chance für neue Spiele bieten gerade in Hinblick auf die Entwicklung
von mobilen Geräten die Hybrid-Reality-Games. Mit Pacmanhatten, welches
in Abbildung A.5 dargestellt ist oder anderen noch technisch aufwändigeren
Spielen, wie sie derzeit am Frauenhofer Institut erprobt werden, kann zudem
ein gewisser sportlicher Aspekt, wie in Abbildung A.5 in die Spielwelt mit
aufgenommen werden. Es scheint so, dass die Verbindung der realen mit der
virtuellen Welt den Spielherstellern neue interessante Möglichkeiten eröffnet.
5.3. HYBRID-REALITY-GAMES
18
Christian Strebe
Distributed Applications
Anhang A
Grafiken
19
Christian Strebe
Distributed Applications
Abbildung A.1: Die Verteilten Proxyserver kommunizieren untereinander mit
Hilfe der Peer-to-Peer Architektur.
Abbildung A.2: Die Aufteilungsmöglichkeiten der Gameengine.
20
Christian Strebe
Distributed Applications
(a) Die Unterteilung der Spielwelt
(b) P1 ist für P2 unsichtbar.
(c) Drei Server sind beteiligt.
(d) Ein sehr grosses Objekt.
Abbildung A.3: Fallbeispiele bei Semless Servern.
21
Christian Strebe
Distributed Applications
Abbildung A.4: Die Unterteilung in Server mit Unterschiedlichen Aufgaben.
Abbildung A.5: Pacmanhatten.
22
Christian Strebe
Distributed Applications
Abbildungsverzeichnis
1.1
1.2
Die Komponenten der Client/Server-Architektur. . . . . . . .
Das ISO/OSI- und TCP/IP-Schichtenmodell. . . . . . . . . .
4
4
2.1
Client-Server und Peer-to-Peer im Vergleich . . . . . . . . . .
5
3.1
Extrapolation und Interpolation im Vergleich. . . . . . . . . .
10
A.1 Die Verteilten Proxyserver kommunizieren untereinander mit
Hilfe der Peer-to-Peer Architektur. . . . . . . . . . . . . . . .
A.2 Die Aufteilungsmöglichkeiten der Gameengine. . . . . . . . .
A.3 Fallbeispiele bei Semless Servern. . . . . . . . . . . . . . . . .
A.4 Die Unterteilung in Server mit Unterschiedlichen Aufgaben. .
A.5 Pacmanhatten. . . . . . . . . . . . . . . . . . . . . . . . . . .
20
20
21
22
22
23
Christian Strebe
Distributed Applications
Literaturverzeichnis
[Ale03a] Alexander, Thor: Building a Massively Multiplayer Game Simulation Framework, Part 1: Structural Modeling. In: Massively
Multiplayer Game Development. Charles River Media, 2003, Kapitel 2.1
[Ale03b] Alexander, Thor: Building a Massively Multiplayer Game Simulation Framework, Part 2: Behavioral Modeling. In: Massively
Multiplayer Game Development. Charles River Media, 2003, Kapitel 2.2
[AST07] Andrew S. Tannenbaum, Maarten Van S.: Distributed Systems.
Bd. Second Edition. Pearson - Prentice Hall, 2007. – ISBN 0–13–
239227–5
[Bea03] Bearsley, Jason: Seamless Servers: The Case For and Against.
In: Massively Multiplayer Game Development. Charles River Media, 2003, Kapitel 3.1
[Bro03] Brockington, Mark: Client-Side Movement. In: Massively Multiplayer Game Development. Charles River Media, 2003, Kapitel
4.1
[Dal03] Dalton, William: MMP Server Development. In: Massively Multiplayer Game Development. Charles River Media, 2003, Kapitel
3.3
[Fox03] Fox, David: Tapping into MMP Worlds via Wireless Devices. In:
Massively Multiplayer Game Development. Charles River Media,
2003, Kapitel 3.4
[Lee03] Lee, Jay: Considerations for Movement and Physics in MMP Games. In: Massively Multiplayer Game Development. Charles River
Media, 2003, Kapitel 3.6
[MA05] Marios Assiotis, Velin T.: A Distributed Architecture for Massive Multiplayer Online Role-Playing Games. 2005
24
Christian Strebe
Distributed Applications
[Ols03] Olsen, John M.: Server-Side Object Refresh Rates. In: Massively Multiplayer Game Development. Charles River Media, 2003,
Kapitel 3.2
[O’N03] O’Neil, Sean: Procedural Worlds: Avoiding The Data Explosion. In: Massively Multiplayer Game Development. Charles River
Media, 2003, Kapitel 3.5
[Ota03] Otaegui, Javier F.: Observer/Observable Design Patterns For
MMP Game Architectures. In: Massively Multiplayer Game Development. Charles River Media, 2003, Kapitel 2.8
[Pat03] Patterson, Jay: Keep It Smooth: Asynchronous Clients and Time Travel. In: Massively Multiplayer Game Development. Charles
River Media, 2003, Kapitel 3.5
[SC95] Singhal, S. ; Cheriton, D.: Exploiting Position History for
Efficient Remote Rendering in Networked Virtual Reality. In:
Presence 4 (1995), Nr. 2, 169–194. citeseer.ist.psu.edu/
singhal95exploiting.html
[Sch03] Schröter, Tobias: Internet-Echtzeitspiele für mobile Netzwerke.
2003
[Wal03a] Walker, Matthew: Creating A ’Safe Sandbox’ For Game Scripting. In: Massively Multiplayer Game Development. Charles River
Media, 2003, Kapitel 2.3
[Wal03b] Walker, Matthew: Precise Game Event Broadcasting with Python. In: Massively Multiplayer Game Development. Charles River
Media, 2003, Kapitel 3.5
[Zin05] Zinke, Michael Andraschek; Stephan Gensch; Matthias Schulz; J.:
Netzwerkstrukturen in MMORPGs - Semesterarbeit in Semantic
Media. 2005
LITERATURVERZEICHNIS
25