Multiplayer-Spiele wie „World of Warcraft“ sind bei der maximalen Anzahl an Spielern immer noch durch die Kapazität und Anzahl der vorhandenen Server beschränkt. Die Server übernehmen die Verwaltung, Steuerung und Koordination der Spieler. Eine prinzipielle beliebige Skalierbarkeit der Spieler kann damit nur schwer erreicht werden.

Einen möglichen Ausweg bieten „Peer-to-Peer Netzwerke“: Peer-to-Peer Netzwerke gehören zur Klasse der Overlay-Netzwerke, d.h. für die Kommunikation zwischen den Netzwerkteilnehmern (Peers) wird ein darunter liegendes, physikalisches Netzwerk (zumeist das Internet) verwendet. Eine besondere Eigenschaft ist die symmetrische Funktionalität der Peers, d.h. jeder Peer agiert sowohl als Server als auch als Client. Diese Eigenschaft bietet das Potenzial für sehr hohe Skalierbarkeit.

Ziel der Projektgruppe ist die Entwicklung eines Multiplayer-Echtzeit-Strategiespiels, das durch ein auf einem Peer-to-Peer-System basierten Netzwerk prinzipiell unbegrenzt viele Nutzer zur selben Zeit verwaltet. Am Ende der Projektgruppe soll ein frei skalierbares Multiplayer-Echtzeit-Strategiespiel entstehen, welches eine durchdachte Spielmechanik und eine dem Umfang entsprechende 3D-Grafik hat. Die 3D-Grafik stellt die virtuelle Welt dar, in der sich die Spieler bewegen und spielen. Die Größe der virtuellen Welt ist verteilt gespeichert und skaliert ebenfalls mit der Anzahl aktiver Spieler. Der besondere Anspruch an das Peer-to-Peer-System ist die durch das Spiel erforderliche Analyse der Positionen der Spieler in der Spielwelt, da nicht unbegrenzt viele Daten gleichzeitig von einem User verschickt/empfangen werden können. Es ist daher nicht möglich, dass ein Spieler die Positionen von allen anderen Spielern kennt.

Es stellen sich damit zwei methodische Herausforderungen:

• Wie hält ein Spieler das Wissen seiner lokalen Umgebung aufrecht, von der er alle Positionen seiner Mitspieler kennt?
• Wie wird die verteilte Szene gespeichert und den sich durch die Szene laufenden Spielern zugänglich gemacht?

Bereich

Modelle und Algorithmen (MuA)

Veranstalter und Betreuer

 Matthias Fischer,  Claudius Jähn,  Peter Mahlmann

Projektteam

Andre Diekwisch, Andreas Martens, Boris Wolf, Claudia Schumacher, Daniel Mex, David Maicher, Dominik Leibenger, Gennadij Liske, Jürgen Tessmann, Kathrin Bujna, Martin Wistuba, Matthias Strotmeier, Peter Wendorff, Philipp Brandes

Termine:

• Wöchentliches Treffen: Donnerstags 16:15 - 18:00 Uhr
• Vorlesung: KW 42-50, F1.110, Do. 16:15 - 18:00 Uhr
• Seminar: 17. - 18.12.09
• Abgabe schriftliche Ausarbeitung: 3.1.10
• Workshop: 6. - 7.1.10 voraussichtlich in Schloß Gehrden

Vorlesung

• Rendering: Einführung Walkthrough-Problem ( pdf / ppt )
• Datenstrukturen: Octrees/BSP ( pdf / ppt )
• Rendering: Hierarchischer Z-Buffer ( pdf / ppt )
• Rendering: Randomisierter Z-Buffer ( pdf / ppt )
• P2P-Netzwerke: Napster/Gnutella ( pdf / ppt )
• P2P-Netzwerke: CAN ( pdf / ppt )
• P2P-Netzwerke: Chord ( pdf / ppt )

Seminar

 Agenda und Themen

Literaturbeispiele:

• Knutsson, B.; Honghui Lu; Wei Xu; Hopkins, B.: Peer-to-peer support for massively multiplayer games; INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies, pp. 96-107, 2004
• Ashwin Bharambe, Jeffrey Pang and Srinivasan Seshan: Colyseus: A Distributed Architecture for Multiplayer Games, ACM/USENIX NSDI 2006.
• Gauthier Dickey, Chris and Zappala, Daniel and Lo, Virginia: A fully distributed architecture for massively multiplayer online games, NetGames '04: Proceedings of 3rd ACM SIGCOMM workshop on Network and system support for games, p. 171, Poster Session, 2004.
  Full Paper: A Distributed Architecture for Massively Multiplayer Online Games ilab.cs.byu.edu/zappala/publications.html
• Jared Jardine and Daniel Zappala: A Hybrid Architecture for Massively Multiplayer Online Games, Proceedings of the 7th ACM SIGCOMM Workshop on Network and System Support for Games (NetGames), 2008.
• B. Hariri, S. Ratti, S. Shirmohammadi, M.R. Pakravan, "A Distributed Routing Architecture for Massively Multi-User Online Games", Proc. IEEE Workshop on Haptic Audio Visual Environments and Games, Ottawa, ON, Canada, October 2008
• Assiotis, Marios and Tzanov, Velin: A distributed architecture for MMORPG; Proceedings of 5th ACM SIGCOMM workshop on Network and system support for games, 2006
• Patric Kabus, Wesley Terpstra, Mariano Cilia, Alejandro Buchmann: Addressing Cheating in Distributed Massively Multiplayer Online Games; International Workshop on NetGames (NetGames'05), 2005.
• Projektgruppe MMOG: Massive Multiplayer Online Games, Universität Paderborn, WS 2005/06 steam.upb.de/mmog/

Elektronisches Format der Ausarbeitung

Die Ausarbeitung des Seminars wird in  LaTeX mit dem  svmult-Style (siehe Paket  Beitragswerke, Konferenzbände) des  Springer-Verlags erstellt. Es wird ein Gesamtband erstellt, ein Beispiel sehen Sie  hier. Die LaTeX-Sourcen UND ein fertiges pdf Ihrer Ausarbeitung schicken Sie als zip-Datei per E-Mail an Matthias Fischer ( mafi(at)upb.de). Bitte geben Sie in Ihrer Ausarbeitung keine Matrikelnummer an. Beachten Sie folgende LaTeX-Spielregeln:

• Das Dokument wird nur mit pdflatex kompiliert. Bilder werden dementsprechend direkt mit pdf, jpg oder png eingebunden. DVI-LaTeX wird nicht erzeugt.
• Es gibt nur eine .tex Datei für die gesamte Ausarbeitung. Starten Sie am besten mit der im svmult Paket angegebenen Datei "author.tex". Alle Bilder und die Tex-Datei liegen im selben Verzeichnis. Die oberste Gliederungsebene ist \section.
• Um alle selbst definierten Kommandos, Labels und Referenzen eindeutig zu definieren, bekommt jeder Autor eine eindeutige ID, mit der ein eindeutiges Präfix erzeugt wird (bspw. "ID3"). Kommandos, Labels und Referenzen bezeichnen wir dann so: \label{ID3meinLabel}. Der Name der LaTeX-Datei ist aus Nachname und ID aufgebaut: „FischerID3.tex“. Die Namen der Bilddateien ebenso plus einem individuellem Teil: „FischerID3meinbild.png“
• Nach \maketitle wird der Abstract in svmult mit \begin{abstract} \end{abstract} erfasst, ihm folgt das lokale Inhaltverzeichnis: \hrule \setcounter{minitocdepth}{2} \dominitoc
• Wir verwenden durchgängig die svmult theorem-Umgebungen. Die Option "nospthms" und das Paket "amsthm" findet keine Verwendung. Das Paket "amsthm" verträgt sich nicht mit "svmult".
• Wir verwenden kein BibTex, die Literatur wird so wie im svmult Template „referenc.tex“ angegeben, jedoch nicht in 2 Dateien, sondern zusammen mit dem Haupttext in einer Datei. Der Inhalt von "referenc.tex" sollte daher ans Ende der Autor-Datei kopiert werden. Die Referenzen werden, wie im svmult Template "referenc.tex" gezeigt, angegeben. Es ist einheitlich zur Formatierung der Einträge der in „reference.tex“ angegebene Stil (Autor, Jahr, Titel, ....) zu verwenden.
• Zur Formatierung der Pseudocode-Algorithmen verwenden wir "algorithmicx" inkl. der floating Umgebung "algorithm" aus "Algorithms". Empfehlenswert ist mit dem bereits vordefinierten Befehlen im Paket "algpseudocode" zu starten. Das Paket "algorithmic" aus "Algorithms" verwenden wir nicht. Alternativ zu "algorithmicx" können die Algorithmen auch mit "listings" oder "verbatim" erstellt werden. Wer Erfahrung mit dem Paket "algorithm2e" hat, melde sich bitte.
• Zusammen mit dem im svmult Beispiel "author.tex" angegebenen Header
  \documentclass[deutsch]{svmult} \usepackage{makeidx} \usepackage{graphicx} \usepackage{multicol} \usepackage[bottom]{footmisc} \makeindex
  können dann noch die folgenden Pakete verwendet werden; andere sind nicht erlaubt:
  \usepackage[latin1]{inputenc} \usepackage[ngerman]{babel} \usepackage[T1]{fontenc} \usepackage{amsmath, amssymb, amsfonts, amscd} \usepackage{algpseudocode} \usepackage{algorithm} \usepackage{listings} \usepackage{verbatim}
• Die in svmult effektiv beschreibbare Seitengröße ist für unsere Verwendung zu klein. Die angepasste Form erhalten Sie hier. Tauschen Sie ihre svmult.cls dagegen aus.