Transcript
Algorithmen zur Unterstützung von Immersive Gaming Erzeugung von hochskalierbaren virtuellen Welten
Gliederung
Ansatzes des NICTA
Delaunay-Netze-basiertes Verfahren
Chord-Protokoll Quadtree Vorstellung des Verfahrens Diskussion
Delaunay-Triangulierung Dynamische Cluster-Bildung Bewertung
Fazit
5.November 2008 -
Sören Vinzelberg - Erzeugung von hochskalierbaren virtuellen Welten
2
Ansatz des NICTA Chord
Quadtree
Vorstellung
Diskussion
Protokoll zur effizienten Suche nach Knoten und Inhalten in einem Peer-to-Peer-Netz
Knoten in einem Ring angeordnet
Position durch Hash-Funktion bestimmt
Jeder Knoten kennt nur eine Teilmenge aller Knoten im Ring.
5.November 2008 -
Sören Vinzelberg - Erzeugung von hochskalierbaren virtuellen Welten
3
Interessenmanagement
Ein Objekt muss nur den Zustand einer Teilmenge aller Objekte in der virtuellen Welt kennen. Gebietsbasiert
Verbindung von Peers, deren Objekte sich in einem Gebiet befinden.
Nachbarschaftsbasiert
Verbindung von Peers, deren Objekte benachbart sind.
5.November 2008 -
Sören Vinzelberg - Erzeugung von hochskalierbaren virtuellen Welten
4
Ansatz des NICTA Chord
Quadtree
Vorstellung
Diskussion
Fingertabelle des Knotens N8
5.November 2008 -
N8 + 1 = N9
N14
N8 + 2 = N10
N14
N8 + 4 = N12
N14
N8 + 8 = N16
N21
N8 + 16 = N24
N32
N8 + 32 = N40
N42
Sören Vinzelberg - Erzeugung von hochskalierbaren virtuellen Welten
5
Ansatz des NICTA Chord Quadtree
Vorstellung
Diskussion
spezielle Baumstruktur
jeder Knoten hat höchstens vier Kinder
zweidimensionale Daten (z.B. Fläche einer virtuellen Welt) organisieren jeder Knoten repräsentiert einen Quadranten
5.November 2008 -
Sören Vinzelberg - Erzeugung von hochskalierbaren virtuellen Welten
6
Ansatz des NICTA Chord Quadtree
5.November 2008 -
Vorstellung
Diskussion
Sören Vinzelberg - Erzeugung von hochskalierbaren virtuellen Welten
7
Ansatz des NICTA Chord
Quadtree Vorstellung
Diskussion
trennt Regionsverwaltung und InteraktionsManagement gebietsbasiertes Verfahren
Die virtuelle Welt wird gemäß eines Quadtrees in Regionen unterteil. Wenn sich mehrere Objekte in einem Teil der virtuellen Welt aufhalten, findet erneut eine Teilung der Teilregion statt. Die Regionen werden den Peers im Netz zugeordnet. Diese verwalten die Objekte in dieser Region.
5.November 2008 -
Sören Vinzelberg - Erzeugung von hochskalierbaren virtuellen Welten
8
Ansatz des NICTA Quadtree Vorstellung
Chord
Diskussion
Objekte:
statische und dynamische
statische Objekte: Bilder, Häuser, Felsen dynamische Objekte: fliegende Raketen, fahrende Automobile
Jedes Objekt in der Virtuellen Welt hat einen Ereignisbereich.
5.November 2008 -
Sören Vinzelberg - Erzeugung von hochskalierbaren virtuellen Welten
9
Ansatz des NICTA Chord
Quadtree Vorstellung
Diskussion
Ereignisbereich:
Das Zentrum wird durch einen Knoten des Quadtrees indiziert. Ein Objekt kann sich innerhalb seines Bereiches bewegen. Objekte können interagieren, wenn sich ihre Ereignisbereiche überschneiden.
5.November 2008 -
Sören Vinzelberg - Erzeugung von hochskalierbaren virtuellen Welten
10
Ansatz des NICTA Chord
Quadtree Vorstellung
5.November 2008 -
Diskussion
Sören Vinzelberg - Erzeugung von hochskalierbaren virtuellen Welten
11
Ansatz des NICTA Quadtree Vorstellung
Chord
Diskussion
Peer-to-Peer-Verbindung
Zwei Voraussetzungen für eine Peer-to-PeerVerbindung müssen erfüllt sein:
Die Ereignisbereiche der Objekte überschneiden sich. Objekte werden von unterschiedlichen Peers verwaltet.
5.November 2008 -
Sören Vinzelberg - Erzeugung von hochskalierbaren virtuellen Welten
12
Ansatz des NICTA Chord
Quadtree
Vorstellung
Diskussion
Stärken:
Verwendung von vorhandenen Konstrukten (Baum, Chord)
Trennung von Raumverwaltung und Interaktion der Objekte Skalierbarkeit des Systems
5.November 2008 -
Sören Vinzelberg - Erzeugung von hochskalierbaren virtuellen Welten
13
Ansatz des NICTA Chord
Quadtree
Vorstellung
Diskussion
Schwächen:
Dynamik des Spiels statische Strukturen
Ballung von Objekten
Unterschiede der Nachbarschaftsbeziehungen
5.November 2008 -
Sören Vinzelberg - Erzeugung von hochskalierbaren virtuellen Welten
14
Ansatz des NICTA Chord
Quadtree
Diskussion
Vorstellung
Schwächen der Baumstruktur:
Objekte in der virtuellen Welt nicht gleichverteilt Baum ist nicht ausbalanciert Nachbarschaftsproblem Schlüsselverlust O
A
AA
5.November 2008 -
AB
B
AC
AD
C
CA
CB
D
CC
CD
Sören Vinzelberg - Erzeugung von hochskalierbaren virtuellen Welten
15
Ansatz des NICTA Chord
Quadtree
Vorstellung
Diskussion
Schwächen des Chord-Protokolls:
viele Peers => Schlüssellänge m groß
m groß => viele Einträge in den Fingertabellen
viele Einträge in den Fingertabellen => hoher Aufwand bei ausfallenden und hinzukommenden Peers (Knoten)
5.November 2008 -
Sören Vinzelberg - Erzeugung von hochskalierbaren virtuellen Welten
16
Delaunay-Netze-basiertes Verfahren Delaunay-Netze Dynamisches Clustern Bewertung
Festlegung der Topologie durch DelaunayTriangulierung
Der Umkreis eines beliebigen Dreiecks im Netz umschließt keinen anderen Knoten des Netzes.
5.November 2008 -
Sören Vinzelberg - Erzeugung von hochskalierbaren virtuellen Welten
17
Delaunay-Netze-basiertes Verfahren Delaunay-Netze Dynamisches Clustern Bewertung
Delaunay-Triangulierung
Kosten: Cm = Nn * Rb + k * Rf
Cm - Verwaltungskosten des Delaunay-Netzes Nn - Anzahl der direkten Nachbarn Rb - Häufigkeit des Nachrichtenaustausches an direkten Nachbarn k - Anzahl der versendeten Pakete für Wiederherstellung Rf - Häufigkeit der Wiederherstellung
5.November 2008 -
Sören Vinzelberg - Erzeugung von hochskalierbaren virtuellen Welten
18
Delaunay-Netze-basiertes Verfahren Delaunay-Netze Dynamisches Clustern Bewertung
Jeder Knoten kann Cluster-Bildung anregen. Verwaltung durch den Cluster-Head. Das Cluster-Zentrum ist ein virtueller Knoten. Die Delaunay-Triangulierung muss auch im Cluster beachtet werden. Cluster im Cluster ist möglich!
5.November 2008 -
Sören Vinzelberg - Erzeugung von hochskalierbaren virtuellen Welten
19
Delaunay-Netze-basiertes Verfahren Delaunay-Netze
Dynamisches Clustern Bewertung
Vorteile: Verwendung einer vorhandenen Struktur Veränderungen nur lokal nötig Ballung von Objekten durch Cluster-Bildung
Nachteile: Cluster im Cluster Triangulierung nicht eindeutig
5.November 2008 -
Sören Vinzelberg - Erzeugung von hochskalierbaren virtuellen Welten
20
Fazit
Peer-to-Peer ist als Netzmodell gut geeignet Ansätze haben Vor- und Nachteile
Größte Probleme sind:
Dynamik Ballung
5.November 2008 -
Sören Vinzelberg - Erzeugung von hochskalierbaren virtuellen Welten
21
