Wie man mit einer großen Anzahl von Pickups in einem MMO-Spiel umgeht

26

Wie gehen Spiele wie Minecraft oder wirklich alle MMO-Spiele mit Tonabnehmern damit um?

Sagen wir, das Terrain bringt jedes Mal, wenn Sie das Terrain graben, 3 Tropfen "Dreck" hervor. Angenommen, jedes Objekt verfügt über eine Rotationsanimation, die für jedes Bild berechnet wird. Wenn die Anzahl der Abholungen auf der Welt sehr hoch ist, wäre dies ein unnützer, massiver Aufwand bei der Rahmenberechnung für einen Client auf einem bestimmten Server, da wahrscheinlich viele dieser Abholungen Lichtjahre von Ihnen entfernt sind.

Was ich dachte, ist, dass Sie nur mit den Tonabnehmern "Sachen machen" müssen, die sich in der Nähe des lokalen Spielers befinden. Dennoch würde dies bedeuten, dass ich in jedem Frame überprüfen muss, ob ein anderes Tonabnehmerelement nah genug ist, um mit der Animation zu beginnen.

Meine eigentliche Frage lautet: Wie haben andere MMOs dieses Problem gelöst?

Alakanu
quelle
9
Darüber hinaus ersetzt der Server im Kontext von Minecraft nach einer bestimmten Anzahl von Elementen, die nahe genug beieinander liegen (3+ des gleichen Elements im gleichen Blockbereich), die 3 Instanzen durch eine gruppierte Instanz, die den Blocktyp enthält ( minecraft:dirt) und eine Zählung (30), sodass der Spieler, wenn er nahe genug ist, um sie aufzunehmen, so viel wie möglich in sein Inventar aufnimmt. Wenn der Spieler nur Platz für 6 Gegenstände hat und ein Stapel von 30 auf dem Boden liegt, nimmt der Spieler die 6 und der Stapel auf dem Boden wird auf 24 reduziert.
Zymus
6
@Zymus Es ist erwähnenswert, dass die Tick-Leistung bei einer moderaten Anzahl fallengelassener Objekte tatsächlich abnimmt, da alle ständig nach Objekten in der Nähe suchen.
user253751

Antworten:

48

Laden Sie einfach nur die Teile der Welt in den Speicher, die sich in der Nähe des Players befinden. Alles andere ist an die Festplatte gebunden. Wenn sich ein winziger Gegenstand in einer Entfernung von etwa zwei Kilometern befindet, kann der Spieler ihn nicht sehen und nicht damit interagieren. Es gibt also keinen Grund, es zu aktualisieren oder zum Rendern an die GPU zu senden. Je kleiner das Objekt und sein Interaktionsbereich sind, desto geringer ist der Bereich um den Player, in dem Sie es laden müssen.

Um herauszufinden, was in der Nähe des Spielers ist: Das läuft hauptsächlich darauf hinaus, die Welt in einer Datenstruktur zu speichern, die für die räumliche Suche optimiert ist. Gute Kandidaten dafür sind räumliches Hashing und mehrdimensionale Bäume .

Philipp
quelle
Danke für die schnelle Antwort. Ich dachte darüber nach, Unity zu verwenden, da ich vermute, dass es eine Art räumliche Partitionierung verwendet, um Trigger-Collider zu überprüfen, sodass ich einen großen Kreis-Collider um meinen Charakter herum erstellen würde und jedes Element darin "animiert" wäre. Ist dies eine Möglichkeit, Ihre Antwort umzusetzen? Korrigiere mich, wenn ich falsch liege, Prost!
Alakanu
2
@Alakanu Kann verwendet werden, wenn Objekte über große Entfernungen sichtbar sein sollen, aber nur in der Nähe des Players bestimmte rechenintensive Verhaltensweisen ausgeführt werden sollen (und nur das Drehen von Objekten um die y-Achse sollte nicht sehr teuer sein). Die eigentliche Herausforderung bei der Implementierung eines Open-World-Spiels in Unity besteht jedoch darin, auf intelligente Weise Spielobjekte zu instanziieren und zu zerstören, während sich der Spieler durch die Welt bewegt (oder noch besser: Verwenden Sie Objekt-Pooling anstelle von Instanzen und Zerstören).
Philipp
Ja, Objekt-Pooling ist in dieser Situation obligatorisch :) Ok, vielen Dank!
Alakanu
3
@Alakanu Weitere Informationen dazu, wie diese Antwort auf dieses Spiel zutrifft, finden Sie in Minecrafts Konzept "Loaded Chunks".
T. Sar - Wiedereinsetzung von Monica
1
Dies gilt nicht nur für Pickups. JEDES Objekt, das zu weit vom Spieler entfernt ist, kann auf diese Weise behandelt werden. Manchmal auch Objekte, die sich in der Nähe des Players befinden. Stellen Sie sich ein Haus mit vollem Innenraum vor, aber Sie müssen erst rendern, wenn Sie das Haus betreten.
Zibelas
22

Sie müssen zwei sehr unterschiedliche Dinge verwalten:

  1. Der Server muss die gesamte Welt autoritär verwalten. Dazu ist eine Kommunikation mit N Clients (wobei N "massiv" ist) notwendig.

  2. Der Kunde könnte im Prinzip über die ganze Welt Bescheid wissen, muss es aber nicht . Für den Kunden ist es ausreichend zu wissen, was sich in der Nähe des Spielers befindet. Nehmen wir zum Beispiel eine grobe gitterartige Unterteilung an, müssten nur die Zelle des Spielers und die 26 Zellen um den Spieler herum bekannt sein (oder 8 Zellen, falls Sie ein 2D-Gitter haben). Ein etwas feineres Raster ist besser, aber Sie haben die Idee.

Nun, viele Pickups, was ist "viel"? Sie graben vielleicht 5 Dinge pro Sekunde, das sind vielleicht zwei Dutzend Zahlen, die auf dem Server aktualisiert werden müssen, und der Server muss diese möglicherweise an einen anderen Spieler übertragen, dessen Interessenbereich Ihre Zelle überlappt. Für einen Computer ist dies eine ziemlich lächerliche Datenmenge und ein vernachlässigbarer Rechenaufwand. Es kann zu einer Herausforderung werden, wenn sich Hunderttausende von Spielern in derselben Zelle befinden (dann ist Ihre Aufteilung zu grob).

Der Server muss die Rotation der Tonabnehmer oder solche Details nicht kennen und sich auch nicht darum kümmern. Warum sollte es?

Es ist dem Kunden eigentlich auch egal, da dies nur eine Augenweide ist, die der Kunde im laufenden Betrieb nachholen kann.

Aus Sicht des Servers ist es wichtig zu wissen, dass Sie in dem Knoten, in dem Sie sich befinden, nach (30, 40, 50) gegraben haben, und es entscheidet sich, dass dies z. B. drei Objekte vom Typ 5 oder ein Objekt vom Typ 7 mit sich bringt eine Zählung von 3. Das ist alles, was es interessiert, und es ist alles, was es Ihnen sagt. Diese Informationen werden auch in den Daten enthalten sein, die an jemanden gesendet werden, der sein Interessengebiet später über die Rasterzelle bewegt (vorausgesetzt, dass sie bis dahin noch vorhanden sind).

Dem Klienten werden drei Gegenstände mitgeteilt, die dort erschienen sind, bla bla. Egal, ob der Client eine ASCII-Art-Karte anzeigt, auf der jetzt ein 'D' angezeigt wird, oder ob ein rotierender Schmutzhaufen angezeigt wird, ist alles gleich. Es ist auch egal, ob die Stapel unterschiedliche Rotationen haben oder nur die, die sich in der Nähe Ihres Spielers befinden. Es sind nur Dinge, die auf Ihrem Monitor angezeigt werden und die niemanden betreffen.

In dem konkreten Fall, dass Sie nur in der Nähe befindliche Schmutzhaufen drehen möchten, können Sie einfach eine Reichweitenkontrolle aller Ihnen bekannten Objekte durchführen. Da die Datenmenge nicht groß ist, funktioniert sogar Brute Force auf alles .

Sie können (und sollten) je nach Partitionsgröße zu weit entfernte Rasterzellen trivial entfernen.

Natürlich können Sie Ihre Zelle auch weiter unterteilen und etwas Superintelligentes verwenden. Verwenden Sie einen kd-Tree, wenn Sie wollen, aber erwarten Sie keine großen Gewinne. Sie können Sachen mit Manhattan distace wegschneiden oder Ihre Sachen in einem eigenen kleinen Raster sortieren ... aber warum?

Eine Entfernungsüberprüfung (wirklich quadratische Entfernung, aber für Sie ist es das Gleiche) besteht nur aus zwei Multiplikationen und einer Addition (optimiert für MUL, MADD, also wirklich nur zwei Operationen), gefolgt von einer Verzweigung oder einer bedingten Bewegung. Das geht so schnell wie bei jeder anderen Operation, bei der nicht ganze Gitterzellen gleichzeitig entfernt werden. In der Tat, das ist etwas , dass Sie könnte auch auf der GPU tun ...

Wenn Sie sehen, wie Sie ein paar Hundert oder höchstens ein paar Tausend Entfernungsprüfungen an derselben Position durchführen (quadratische Entfernung funktioniert einwandfrei), haben Sie wirklich keine großen Schwierigkeiten, nur diese Berechnung durchzuführen, noch mehr, da es sich um einen eher cachespezifischen Vorgang handelt. freundliche Iteration über zusammenhängendes Gedächtnis und mit bedingten Bewegungen ist es spottbillig. So etwas wie (Pseudocode) rot = r[i] + 1; r[i] = ((dx*dx+dy*dy) < DIST_SQ) ? rot : r[i];. Das ist eine Iteration über ein Array von einigen hundert Werten pro Frame. Dem Computer ist das egal, es sind zusammenhängende Ladevorgänge und Speicher, eine einfache ALU, keine Verzweigungen und nur ein paar tausend Iterationen.

Dies (viele-zu-eins) ist nicht die gleiche Problemklasse (viele-zu-viele) wie auf dem Server. Wirklich, der Kunde ist nicht das Problem.

Damon
quelle
Es tut mir leid, ich dachte, es sei klar, dass ich über einen Kunden sprach, als ich anfing, über Framerate zu sprechen.
Alakanu
1
Aber der Kunde ist niemals das Problem. Der Client ist sehr nicht massiv und sehr lokal. Er muss viel weniger wissen als der Server. Im Idealfall kennt der Client den räumlichen Partitionierungsknoten (z. B. das Raster), in dem sich der Player befindet, und die unmittelbar umgebenden Knoten, und das war's. Aktualisierungen sind daher sehr bescheiden, es sei denn, tausend Spieler stehen nebeneinander. Normalerweise benötigen Sie nur Deltas für ein oder zwei Objekte und den Inhalt eines neuen Gitterknotens, nachdem Sie sich für mehr als die Hälfte der Knotenbreite in eine Richtung bewegt haben. Alles andere: Nicht dein Problem.
Damon
1
Der Punkt ist, dass zu klug zu sein eine sehr dumme Idee sein kann. Ihre Welt ist notwendigerweise bereits räumlich aufgeteilt, mit einer überschaubaren Anzahl von Objekten in jedem Knoten. Moderne CPUs (und noch mehr GPUs) können große Mengen von SoA-Daten nacheinander verarbeiten. Sie mögen keine inkohärenten Verzweigungen, und sie mögen inkohärenten Speicherzugriff noch weniger - was jedoch genau das ist , was "nur in der Nähe verarbeiten" tut. Für überschaubare Zahlen (einige Hundert, einige Tausend) ist "Alles verarbeiten" in einer Zelle vollkommen ausreichend und wahrscheinlich das Beste, was Sie tun können.
Damon
1
@Alakanu Dies sieht nach einer detaillierten und vollständigen Antwort auf Ihre Frage aus, für mich. Wenn Sie denken, dass es keine Antwort ist, haben Sie sie entweder falsch verstanden oder Ihre Frage ist so unklar, dass Damon, ich und alle, die diese Antwort positiv bewertet haben, sie falsch verstanden haben.
David Richerby
2
@Alakanu Du verbringst wirklich viel Zeit damit, dich über Leute zu beschweren, die versuchen, dir zu helfen. Viel Glück damit.
David Richerby
2

@ T.Sar schreibt in einem Kommentar, dass Sie sich Minecrafts "Loaded Chunk" -Konzept ansehen sollten, um weitere Informationen zu erhalten. Wenn Sie dies tun, beachten Sie, dass dies in Minecraft aufgrund der Leute, die Maschinen im Spiel bauen, ziemlich kompliziert ist.

Es folgt eine sehr vereinfachte Version:

Die Welt ist in quadratische Regionen (Chunks) unterteilt. In Minecraft gibt es auch eine Höhenunterteilung, aber die meisten mmos brauchen das nicht.

Der Spielclient kümmert sich nur um die Regionen in der Nähe des Spielers. Dies ist viel einfacher als das Zeichnen eines Kreises um den Spieler, aber vollkommen ausreichend.

In Minecraft sind die Regionen 16 x 16 Blöcke groß, und der Client kennt 9 x 9 Regionen, 4 Regionen in jeder Richtung. (4 Regionen Ost + Region Spieler ist in + 4 Regionen West = 9 Regionen insgesamt. Gleiche Nord / Süd)

Diese Zahlen haben nichts Magisches an sich. Verwenden Sie alles, was in Ihrem Spiel Sinn macht.

Der Client animiert nur Dinge in diesem Bereich. Der Server berechnet nur Dinge wie umherziehende Monster in Regionen, die sich in der Nähe eines Spielers befinden.

Wenn ein Spieler in einer Region herumläuft, passiert nichts Besonderes. Wenn er eine Regionsgrenze überschreitet, wird der "Rand der Animation" um eine Region verschoben. Der Client muss dann den Server nach den Regionen fragen, die er jetzt sieht.

Es ist nichts Falsches daran, mehrere verschachtelte Animationsgrenzen zu haben. ZB fällt ein animierter Gegenstand in ein 3x3-Gebiet, wandert in einem 5x5-Gebiet umher und zeigt die Landschaft einfach in einem 9x9-Gebiet.

Der Server behält eine "eingefrorene Version" von Regionen, die kein Spieler sieht. Wenn dies viel Speicher benötigt, möchten Sie diese möglicherweise nach einiger Zeit wieder entladen. Wenn ein Spieler das nächste Mal ankommt, wird die Region neu geladen, ohne dass der Gegenstand abfällt. Du musst das nächste Mal schneller sein, Spieler 1.

Stig Hemmer
quelle
Die Zeichenentfernung ist einstellbar, aber in diesem Fall sind 8 Blöcke 9 x 9 und es ist eine clientseitige Entscheidung, die den Server darüber informieren kann, die Dinge zu beschleunigen (der Server sendet also keine Daten, die der Client nicht rendert). Also ... haben Doom und Quake das Problem nicht gelöst, nur das zu rendern, was Sinn macht?
SparK
Über das Despawnen der abgeworfenen Gegenstände ... in Minecraft "altert" der Gegenstand nur, wenn sich ein Spieler in der Nähe befindet. So können Sie einen abgelegten Gegenstand in einem entladenen Block "speichern" und später abrufen.
SparK