1	World Simulation Level of Detail AI Michael Haar
2	Was vorher zu sagen ist: Nur wenig praktische Erfahrungen und Anwendungen existieren. Trotzdem interessante Ideen! Grundlagenforschung von: Stephen Chenney (Simulation Level of Detail) David O' Brien, Susan Fisher und Ming C. Lin (Simplification of Particle System Dynamics)
3	Worum geht es überhaupt? Spielumgebungen wachsen immer mehr simulierte Spielobjekte CPU und Speicher können nicht mit der Entwicklung der Grafik Schritt halten speziell auf Konsolen Trotzdem: Ansprechende Welten überzeugend zum Leben erwecken
4	Ein Beispiel: Landschaft Überzeugende Landschaft könnte bieten: Pflanzen soviele die Grafiktechnologie erlaubt Tiere die in der Landschaft leben Menschen die Tiere jagen Aliens die die Menschen jagen
5	Landschaft – das Problem Kleiner Ausschnitt kein Problem schon in vielen Spielen mehr oder weniger erfolgreich versucht viele kleine Level Nicht einfach lösbar: realistische Wegstrecken große Spieldauer in derselben Welt Auswirkungen entfernter Ereignisse
6	Erste Idee Nur sichtbare Grafik wird angezeigt – Großteil der Welt braucht nicht simuliert werden! Diese Lösung haben Spiele schon immer benutzt.
7	Beispiel: Midtown Madness Simulation Bubble: Grenze an der Objekte gelöscht werden oder abprallen Grenze bewegt sich immer mit dem Spieler Funktioniert nicht! auffällig, wenn zu klein zuviel Rechenzeit, wenn größer Entwicklungen der nicht sichtbaren Welt können keinen Einfluss auf das Spiel haben
8	Bessere Idee Lösung aus der Grafik: Level of Detail Welche Ereignisse beeinflussen das Spielerlebnis wirklich? Angenäherte Simulation: Details können zusammengefasst werden Nur direkt im Sichtnahbereich des Spielers wird wirklich korrekt simuliert
9	Simulations Level of Detail Beispiele: keine Interaktion von Objekten, wo nicht nötig Ereignisse nur statistisch korrekt Lineare Bewegungen in der Entfernung Reicht für einen überzeugenden Eindruck für den Spieler aus: Erinnerungen an exakte Details hat kein Spieler
10	Problem! Kein unwichtiges Objekt soll berechnet werden - wie findet man dann heraus, ob ein Objekt inzwischen wichtig für den Spieler geworden ist?
11	Betrachtung wichtiger Events Keine Simulation, aber wichtige Events für Objekte betrachten - dann bei Eintritt genauer simulieren: Bewegtes Objekt übertritt eine Grenze und wird wichtig für den Spieler Umschaltung der Simulationsgenauigkeit Events speichern und bearbeiten für alle wichtigen Objekte im Spiel.
12	Beispiele Schmetterlinge in einer Landschaft Fahrzeug aus gegnerischer Stadt
13	Vereinfachte Simulation (Proxy) Events werden vorhergesagt Kein gültiger Status mehr für Objekte zwischen Events! Queue zum Speichern der Events sortiert nach Eintrittszeit Nur erster Eintrag der Queue wird jeweils bearbeitet.
14	Genauigkeit? Alle wichtigen Events erkannt? Dann gutes Ergebnis auch ohne Simulation: Schwierigkeit für jedes Spiel neu zu lösen! Lösungen nur für einfache Systeme (Partikel) Richtige Dinge sollen zur richtigen Zeit am richtigen Ort passieren. WAS ist für den Eindruck des Spielers entscheidend? Reisezeiten, Zustände, Dichtenentwicklung
15	Vorhersagen Lineare Bewegungen: trivial Interaktion von Objekten: Vorhersage des frühestmöglichen Eintritts und Neueintragung nach Betrachtung der Umstände. Ausserdem eine statistische Korrektheit: durchschnittliche Geschwindigkeit modifiziert mit Objektdichte im aktuellen Gebiet Einberechnung der Umstände (Terrain Reasoning) Pfade im vorraus berechnen und als Verzögerung einfliessen lassen
16	Sichtbarkeitsbestimmung Objekte hängen an Zellen Einteilung der Spielwelt in Quadrate, Tree, … Sichtbarkeit der Zelle bestimmt Sichtbarkeit des Objektes Eintritts- und Austritts-Events: stellen Zuordnung nicht simulierter Objekte zu korrekten Zellen sicher
17	Bewegte Punkte Event Zellenwechsel Vorhersage nächster Zellenwechsels Bearbeitung des Events Zellenwechsel und neue Vorhersage Abfrage des nächsten Events Prüfung auf Eintritt, Rückgabe und Löschen aus der Queue
18	Implementierung Init() { for(all objects) { event.object = cur_object event.time = PredictNextEvent(cur_object) InsertQueue(event) } } OnIdle { event = GetQueueNextEvent() if(event) ProcessEvent(event) }
19	Implementierung ProcessEvent(event) { cell = HasEntered(event.object) if(cell) { event.time = PredictNextEvent(event.object) InsertQueue(event) } else { InsertToCell(cell, event.object) event.time = PredictNextEvent(event.object) InsertQueue(event) } }
20	Zustände Objekte die wieder in das Sichtfeld kommen sollten im erwarteten Zustand sein! Komplett neue Objekte (nicht einmal mehr mit Proxy simuliert) müssen mit funktionierenden Zuständen in das System eintreten! Wichtig: Neuer Zustand muss nicht korrekt sein, sondern nur so wirken!
21	Zufällige Generierung Mit Random Seed nach Position der Simulationszelle: nur für unwichtige Details geeignet z.B. kleine Pflanzen, Insekten
22	Auslagern/Abspeichern letzter bekannter Zustand wurde (komprimiert) gespeichert und wird wiederbelebt Zeitdifferenz wird nachsimuliert: nur bei einfacher Nachsimulation durch zufällige Verschiebung oder leichte Veränderungen der Zustände
23	Nutzung von Ähnlichkeiten Vorhandene, ähnliche Objekte benutzen und kombinieren Extremfall: Kopie einer kompletten Zelle Vorhandene Objekte müssen schnell auffind- und abfragbar sein!
24	Zusammenfassung: Schritte zur Proxy-Simulation Welche Verhaltensweisen sollen auch im Proxy beibehalten werden? Wie müssen die Bereichswechselevents gewählt sein so dass 1. funktioniert? Welche Statusvariablen benötigen die Objekte im Proxy? Wie wird der Status von Objekten die sichtbar werden wieder hergestellt? Testen, Ändern, Testen
25	Verbesserungsansätze Immer noch zuviel Aufwand bei vielen Objekten in einer Zelle! Beispiel: Partikelähnliche Verhalten Objekte nötig um Inkonsistenzen zu vermeiden
26	Ähnlichkeiten nutzen Lösung für Objekte mit ähnlichem Verhalten (Partikel) existiert: Ähnliche Objekte in räumlicher Nähe werden zu Clustern zusammengefasst und wie ein Objekt simuliert. Je nach Entfernung vom Spieler oder seinem Blickzentrum werden verschiedene Clustergrößen erzeugt. Performance steigt um ein Vielfaches
27	SLOD-Tree Sortierung der Objekte in kd-Tree: angelegt nach Physik- oder Simulationseigenschaften Blatt "simulation level of detail" (SLOD): resultiert aus einsortierten Objekten wirkt gleich auf alle
28	Einbindung in Proxy Zellen ergänzt durch kd-Tree wo nötig Speicherung verschiedener Objektarten: mehrere Trees pro Zelle. Änderungen am Tree nur bei Zellenwechseln kompletter Cluster wechselt in benachbarte Zelle wird eventuell neu gesplittet
29	Regions of Interest Wichtigkeit von Bereichen: Über Zellen und SLOD-Tree liegen ROIs: Wichtigkeit aller Objekte im Cluster für die Simulation Angabe von maximaler Clustergröße (Raum und Dichte) Fassen nach Vorgaben möglichst passend Objekte zu Clustern zusammen
30	ROIs Können schnell auf Veränderungen angepasst werden Cluster sortieren sich in folgenden Simulationsschritten automatisch neu Beispiele: Kamera-ROI bei Bewegungen des Spielers Spielevent-ROI bei wichtigen Ereignissen Hintergrund ROI hat niedrigste Priorität
31	Drei ROIs
32	Updates Neue Objekte vom ROI aus einfügen Beachtung der ROI-Prioritäten top-down in Zellen und Trees einsortieren Clusterwechsel beim Parent bottom-up eventuell ROI-Wechsel
33	Berechnung Pro Cluster eine Standardsimulation: mittlere Position mittlere Geschwindigkeit Je nach Objektart Gewichtung z.B. nach: Masse Ausdehung Ergebnis gilt für alle Objekte des Clusters
34	Zusammenfassung Grundidee: Nur was für den Spieler wichtig ist, braucht berechnet zu werden! Erreichte Ziele: Vorhersage und angenäherte Berechnung ermöglichen weit größere Spielwelten Besonders für die Dynamik von Partikelsystemen existiert eine Level of Detail Lösung mit großen Performancegewinnen.
35	Probleme Auch diese Lösung verschiebt das Problem nur ein Stück weiter. Bisher keine generelle Lösung gefunden - für jedes Spiel müss alle wichtigen Events selber gefunden werden.
36	Weitere Anwendung: Netzwerk Netzwerkspiele in großen Umgebungen können mit den hier beschriebenen Methoden unnötigen Traffic vermeiden. Daten müssen nur noch bei neuen Events und bei Objekten im Sichtbereich (bzw. voll simulierten Bereich) übertragen werden.
37	Weiterführende Quellen Joe Adzima, "Using AI to bring Open City Racing to Life", Game Developer Magazine, Dec 2000, pp 26-31 Stephen Chenney, "Simulation Level of Detail", GDC 2001 Proceedings, pp 177-191 http://www.cs.wisc.edu/~schenney David O' Brien, Susan Fisher, Ming C. Lin, "Automatic Simplification of Particle System Dynamics", http://www.cs.unc.edu/~geom/SLOD
38	Vielen Dank! Demo auf Playstation 2