Explodierende Sichtbereichsberechnung (AOI, N²) Area-of-interest explosion

Ursachen-ID sp-aoi · Hauptzuständig Server-Entwicklung (Entwicklungsteam)

In der interaktiven Fassung mit Grafiken und Experimenten öffnen →

Wird für alle Spieler paarweise geprüft, wer wen sehen kann, wächst der Rechenaufwand bei 10-mal so vielen Spielern auf das 100-Fache.

Warum Abstände werden zwischen allen Charakteren verglichen, oder trotz Aufteilung in ein Raster (Grid) drängen sich Hunderte um eine Zelle → Folge Bei 100 Spielern etwa 10.000 Vergleiche, bei 1.000 Spielern etwa 1 Million → Auf dem Bildschirm An vollen Orten wie beim Weltboss oder bei Belagerungen schießt die Tick-Zeit hoch: Zeitlupe und Ruckeln

Symptome: Zeitlupe, Ruckeln
Faktoren: Stillstand
Wer ist betroffen: Bestimmter Ort oder Kanal, Ganzer Server
Wann: Bei großem Andrang
Zuständigkeit: Hauptzuständig Server-Entwicklung (Entwicklungsteam)
Aufgaben Entwicklungsteam: In Raster oder Bereiche aufteilen und nur die Umgebung vergleichen, weit entfernte Objekte seltener aktualisieren, Zahl der Spieler begrenzen, die eine Person sieht.
Größenordnungen: Setzt man für Abstandsvergleich und Aktualisierung der Sichtbarkeitslisten zusammen 0,1 µs (eine Zehnmillionstelsekunde) pro Spielerpaar an, ergibt das bei 1.000 Spielern (etwa 1 Million Paare) 100 ms pro Tick. Das ist doppelt so viel wie das Budget bei 20 Ticks pro Sekunde (50 ms).
Im Graphen: Steigt mit Spielerzahl und Last · Server-Tick-Zeit, Spieler an einem Ort
Wo nachsehen: Spielerzahl pro Zone und Kanal und Tick-Zeit im selben Graphen darstellen, dazu die separat gemessene Zeit der Sichtbereichsberechnung innerhalb des Ticks. Ohne separate Messung mit perf top -p den CPU-Anteil pro Funktion im Spielprozess prüfen
Spricht dafür: Verdoppelt sich die Spielerzahl an einem Ort, steigt die Tick-Zeit fast auf das 4-Fache, und Funktionen für Sichtbereich und Abstand belegen den Großteil der CPU-Zeit
Spricht dagegen: Tick-Zeit wächst proportional zur Spielerzahl, oder Sende- und Serialisierungsfunktionen haben einen großen Anteil: eher explodierende Broadcast-Last oder Kosten für Serialisierung und Kompression
Prüfmittel: Logs oder Metriken aus Spielserver bzw. Client nötig

Quellen

Comparing Interest Management Algorithms for Massively Multiplayer Games ACM
Paper von NetGames 2006 (Autorenfassung). Abstandsmessung zwischen allen Paaren skaliert nicht mit wachsender Spielerzahl, bei Aufteilung in ein quadratisches Raster werden nur die 9 Zellen der Umgebung geprüft
Replication Graph in Unreal Engine Epic Games
Das Standardverfahren, das für jeden Actor alle Verbindungen prüft, wird bei vielen Spielern und Actors zum CPU-Engpass des Servers, MMORPGs u. a. teilen die Welt in ein Raster und verwenden Listen pro Zelle wieder
perf-top(1) — Linux manual page perf
Zeigt den CPU-Anteil eines laufenden Prozesses (-p) oder Threads (-t) pro Funktion (Symbol) in Echtzeit

Explodierende Sichtbereichsberechnung (AOI, N²) Area-of-interest explosion

Quellen

Verwandte Ursachen

Gleiche Schicht: L9 Spielprozess auf dem Server

Ursachen aus anderen Schichten mit demselben Symptom (Zeitlupe)