World Simulation
Level of Detail AI

Michael Haar

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)

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

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

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

Erste Idee

Nur sichtbare Grafik wird angezeigt – Großteil der Welt braucht nicht simuliert werden!

Diese Lösung haben Spiele schon immer benutzt.

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

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

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

Problem!

Kein unwichtiges Objekt soll berechnet werden - wie findet man dann heraus, ob ein Objekt inzwischen wichtig für den Spieler geworden ist?

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.

Beispiele

Schmetterlinge in einer Landschaft

Fahrzeug aus gegnerischer Stadt

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.

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

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

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

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

Implementierung

Init()

{

for(all objects)

{

event.object = cur_object

event.time = PredictNextEvent(cur_object)

InsertQueue(event)

}

}

OnIdle

{

event = GetQueueNextEvent()

if(event)

ProcessEvent(event)

}

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)

}

}

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!

Zufällige Generierung

Mit Random Seed nach Position der Simulationszelle:

nur für unwichtige Details geeignet

z.B. kleine Pflanzen, Insekten

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

Nutzung von Ähnlichkeiten

Vorhandene, ähnliche Objekte benutzen und kombinieren

Extremfall: Kopie einer kompletten Zelle

Vorhandene Objekte müssen schnell auffind- und abfragbar sein!

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

Verbesserungsansätze

Immer noch zuviel Aufwand bei vielen Objekten in einer Zelle!

Beispiel:

Partikelähnliche Verhalten

Objekte nötig um Inkonsistenzen zu vermeiden

Ä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

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

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

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

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

Drei ROIs

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

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

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.

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.

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.

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

Vielen Dank!

Demo auf Playstation 2


	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)


	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


	Ü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


	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


	Nur sichtbare Grafik wird angezeigt – Großteil der Welt braucht nicht simuliert werden!
	Diese Lösung haben Spiele schon immer benutzt.


	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


	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


	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


	Kein unwichtiges Objekt soll berechnet werden - wie findet man dann heraus, ob ein Objekt inzwischen wichtig für den Spieler geworden ist?


	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.


	Schmetterlinge in einer Landschaft
	Fahrzeug aus gegnerischer Stadt


	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.


	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


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


	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


	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


	Init()
	{
	for(all objects)
	{
	event.object = cur_object
	event.time = PredictNextEvent(cur_object)
	InsertQueue(event)
	}
	}
	OnIdle
	{
	event = GetQueueNextEvent()
	if(event)
	ProcessEvent(event)
	}


	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)
	}
	}


	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!



	Mit Random Seed nach Position der Simulationszelle:
		nur für unwichtige Details geeignet
		z.B. kleine Pflanzen, Insekten


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


	Vorhandene, ähnliche Objekte benutzen und kombinieren
		Extremfall: Kopie einer kompletten Zelle
	Vorhandene Objekte müssen schnell auffind- und abfragbar sein!


	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


	Immer noch zuviel Aufwand bei vielen Objekten in einer Zelle!
	Beispiel:
		Partikelähnliche Verhalten
		Objekte nötig um Inkonsistenzen zu vermeiden


	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


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


	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


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


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


	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