Advertisement
  1. Game Development
  2. Game Engine Development

Was ist datenorientiertes Game-Engine-Design?

by
Read Time:12 minsLanguages:

German (Deutsch) translation by Federicco Ancie (you can also view the original English article)

Sie haben vielleicht schon von datenorientiertem Game-Engine-Design gehört, einem relativ neuen Konzept, das eine andere Denkweise als das traditionellere objektorientierte Design vorschlägt. In diesem Artikel erkläre ich, worum es bei DOD geht und warum einige Game-Engine-Entwickler glauben, dass es die Eintrittskarte für spektakuläre Leistungssteigerungen sein könnte.

Ein bisschen Geschichte

In den frühen Jahren der Spieleentwicklung wurden Spiele und ihre Engines in Old-School-Sprachen wie C. Sie waren ein Nischenprodukt, und es hatte damals höchste Priorität, jeden letzten Taktzyklus aus langsamer Hardware herauszuquetschen. In den meisten Fällen gab es nur eine bescheidene Anzahl von Leuten, die den Code eines einzelnen Titels hackten, und sie kannten die gesamte Codebasis auswendig. Die von ihnen verwendeten Tools hatten ihnen gute Dienste geleistet, und C bot die Leistungsvorteile, die es ihnen ermöglichten, das Beste aus der CPU herauszuholen – und da diese Spiele immer noch weitgehend an die CPU gebunden waren und ihre eigenen Frame-Puffer nutzten, das war ein sehr wichtiger punkt.

Mit dem Aufkommen von GPUs, die die Zahlenverarbeitung für Dreiecke, Texel, Pixel usw. übernehmen, sind wir weniger von der CPU abhängig. Gleichzeitig ist die Gaming-Branche stetig gewachsen: Immer mehr Menschen wollen immer mehr Spiele spielen, was wiederum dazu geführt hat, dass immer mehr Teams zusammenkommen, um diese zu entwickeln.

Das Mooresche Gesetz zeigt, dass das Hardware-Wachstum exponentiell und nicht linear in Bezug auf die Zeit ist: Das bedeutet, dass sich die Anzahl der Transistoren, die wir auf einer einzelnen Platine unterbringen können, alle paar Jahre nicht um einen konstanten Betrag ändert – sie verdoppelt sich!

Größere Teams brauchten eine bessere Zusammenarbeit. Schon bald verlangten die Game-Engines mit ihren komplexen Level-, KI-, Culling- und Rendering-Logiken von den Programmierern mehr Disziplin, und ihre bevorzugte Waffe war objektorientiertes Design.

Wie Paul Graham einmal sagte:

In großen Unternehmen wird Software in der Regel von großen (und häufig wechselnden) Teams mittelmäßiger Programmierer geschrieben. Die objektorientierte Programmierung zwingt diesen Programmierern eine Disziplin auf, die verhindert, dass einer von ihnen zu viel Schaden anrichtet.

Ob es uns gefällt oder nicht, dies muss bis zu einem gewissen Grad stimmen – größere Unternehmen begannen, größere und bessere Spiele bereitzustellen, und mit der Standardisierung der Tools wurden die Hacker, die an Spielen arbeiteten, zu Teilen, die viel einfacher ausgetauscht werden konnten. Die Tugend eines bestimmten Hackers wurde immer weniger wichtig.

Probleme mit objektorientiertem Design

Während objektorientiertes Design ein nettes Konzept ist, das Entwicklern bei großen Projekten wie Spielen hilft, mehrere Abstraktionsebenen zu erstellen und alle an ihrer Zielebene arbeiten zu lassen, ohne sich um die Implementierungsdetails der darunter liegenden kümmern zu müssen, ist es verpflichtet bereitet uns einige Kopfschmerzen.

Wir sehen eine Explosion der parallelen Programmierung – Coder ernten alle verfügbaren Prozessorkerne, um atemberaubende Rechengeschwindigkeiten zu erzielen – aber gleichzeitig wird die Spiellandschaft immer komplexer, und wenn wir mit diesem Trend Schritt halten und trotzdem die Frames liefern wollen -pro Sekunde, die unsere Spieler erwarten, müssen wir es auch tun. Durch die Ausnutzung aller uns zur Verfügung stehenden Geschwindigkeit können wir Türen für ganz neue Möglichkeiten öffnen: Die CPU-Zeit zum Beispiel zu nutzen, um die Anzahl der an die GPU gesendeten Daten insgesamt zu reduzieren.

Bei der objektorientierten Programmierung behalten Sie den Zustand innerhalb eines Objekts bei, was erfordert, dass Sie Konzepte wie Synchronisationsprimitive einführen, wenn Sie von mehreren Threads aus daran arbeiten möchten. Sie haben für jeden virtuellen Funktionsaufruf, den Sie durchführen, eine neue Indirektionsebene. Und die Speicherzugriffsmuster, die durch objektorientiert geschriebenen Code erzeugt werden, können schrecklich sein – tatsächlich hat Mike Acton (Insomniac Games, ex-Rockstar Games) eine großartige Reihe von Folien, die beiläufig ein Beispiel erklären.

Ähnlich formulierte es Robert Harper, Professor an der Carnegie Mellon University:

Objektorientierte Programmierung ist von Natur aus [...] sowohl antimodular als auch antiparallel und daher für einen modernen CS-Lehrplan ungeeignet.

Es ist schwierig, so über OOP zu sprechen, da OOP ein riesiges Spektrum von Eigenschaften umfasst und nicht alle sind sich einig, was OOP bedeutet. In diesem Sinne spreche ich hauptsächlich von OOP, wie es von C++ implementiert wird, da dies derzeit die Sprache ist, die die Welt der Spiele-Engines dominiert.

Wir wissen also, dass Spiele parallel werden müssen, da die CPU immer mehr Arbeit leisten kann (aber nicht muss) und Zyklen darauf warten, dass die GPU die Verarbeitung beendet, ist einfach Verschwendung. Wir wissen auch, dass gängige OO-Design-Ansätze erfordern, dass wir teure Sperrkonflikte einführen und gleichzeitig die Cache-Lokalität verletzen oder unter den unerwartetsten Umständen unnötige Verzweigungen verursachen können (die kostspielig sein können!).

Wenn wir nicht mehrere Kerne nutzen, verbrauchen wir weiterhin die gleiche Menge an CPU-Ressourcen, auch wenn die Hardware beliebig besser wird (mehr Kerne hat). Gleichzeitig können wir die GPU an ihre Grenzen bringen, da sie von Natur aus parallel ist und jede Menge Arbeit gleichzeitig übernehmen kann. Dies kann unsere Mission beeinträchtigen, Spielern die beste Erfahrung auf ihrer Hardware zu bieten, da wir sie eindeutig nicht voll ausschöpfen.

Dies wirft die Frage auf: Sollten wir unsere Paradigmen insgesamt überdenken?

Geben Sie ein: Datenorientiertes Design

Einige Befürworter dieser Methodik haben es datenorientiertes Design genannt, aber die Wahrheit ist, dass das allgemeine Konzept schon viel länger bekannt ist. Die grundlegende Prämisse ist einfach: Konstruieren Sie Ihren Code um die Datenstrukturen herum und beschreiben Sie, was Sie in Bezug auf die Manipulation dieser Strukturen erreichen möchten.

Wir haben diese Art von Gerede schon einmal gehört: Linus Torvalds, der Schöpfer von Linux und Git, sagte in einem Post auf der Git-Mailingliste, dass er ein großer Befürworter des "Entwerfens des Codes um die Daten herum und nicht umgekehrt" ist und nennt dies einen der Gründe für den Erfolg von Git. Er behauptet sogar, dass der Unterschied zwischen einer guten und einer schlechten Programmiererin darin besteht, ob sie sich um Datenstrukturen oder den Code selbst kümmert.

Die Aufgabe mag zunächst kontraintuitiv erscheinen, da Sie Ihr mentales Modell auf den Kopf stellen müssen. Aber stellen Sie es sich so vor: Ein Spiel erfasst während des Laufens alle Eingaben des Benutzers, und alle leistungsintensiven Teile davon (die, bei denen es sinnvoll wäre, den Standard aufzugeben, ist alles eine Objektphilosophie) verlassen sich nicht auf außen Faktoren wie Netzwerk oder IPC. Soweit Sie wissen, verbraucht ein Spiel Benutzerereignisse (Maus bewegt, Joystick-Taste gedrückt usw.) und den aktuellen Spielstatus und wandelt diese in einen neuen Datensatz um – zum Beispiel Stapel, die an die GPU gesendet werden, PCM-Samples, die an die Audiokarte gesendet werden, und ein neuer Spielstatus.

Dieses „Data Churning“ lässt sich in sehr viel mehr Teilprozesse zerlegen. Ein Animationssystem nimmt die nächsten Keyframe-Daten und den aktuellen Zustand und erzeugt einen neuen Zustand. Ein Partikelsystem nimmt seinen aktuellen Zustand (Partikelpositionen, Geschwindigkeiten usw.) und einen zeitlichen Fortschritt an und erzeugt einen neuen Zustand. Ein Culling-Algorithmus nimmt einen Satz von Renderables-Kandidaten und erzeugt einen kleineren Satz von Renderables. Fast alles in einer Spiel-Engine kann man sich als Manipulation eines Datenblocks vorstellen, um einen weiteren Datenblock zu erzeugen.

Prozessoren lieben die Referenzlokalität und die Cache-Nutzung. Daher neigen wir beim datenorientierten Design dazu, wo immer möglich, alles in großen, homogenen Arrays zu organisieren und, wo immer möglich, gute, Cache-kohärente Brute-Force-Algorithmen anstelle eines potenziell ausgefalleneren (der eine bessere Big O-Kosten, berücksichtigt aber nicht die Architekturbeschränkungen der Hardware, auf der es funktioniert).

Wenn es pro Frame (oder mehrmals pro Frame) ausgeführt wird, bietet dies möglicherweise enorme Leistungsprämien. Zum Beispiel berichten die Leute von Scalyr, dass sie Protokolldateien mit 20 GB/s durchsucht haben, indem sie einen sorgfältig erstellten, aber naiv klingenden linearen Brute-Force-Scan verwenden.

Wenn wir Objekte verarbeiten, müssen wir sie uns als "Black Boxes" vorstellen und ihre Methoden aufrufen, die wiederum auf die Daten zugreifen und uns das bekommen, was wir wollen (oder die gewünschten Änderungen vornehmen). Dies ist großartig, um die Wartbarkeit zu gewährleisten, aber wenn Sie nicht wissen, wie unsere Daten angeordnet sind, kann dies die Leistung beeinträchtigen.

Beispiele

Beim datenorientierten Design denken wir alles über Daten nach, also lassen Sie uns auch etwas anderes machen, als wir es normalerweise tun. Betrachten Sie dieses Stück Code:

Obwohl stark vereinfacht, ist dieses allgemeine Muster das, was oft in objektorientierten Spiel-Engines zu sehen ist. Aber warten Sie – wenn viele Renderables nicht wirklich sichtbar sind, stoßen wir auf eine Menge falscher Verzweigungsvorhersagen, die dazu führen, dass der Prozessor einige ausgeführte Anweisungen verwirft, in der Hoffnung, dass ein bestimmter Zweig genommen wurde.

Für kleine Szenen ist dies offensichtlich kein Problem. Aber wie oft machen Sie diese spezielle Sache, nicht nur beim Einreihen von Renderables, sondern auch beim Durchlaufen von Szenenlichtern, Shadow-Map-Splits, Zonen oder ähnlichem? Wie wäre es mit KI- oder Animations-Updates? Multiplizieren Sie alles, was Sie in der Szene tun, sehen Sie, wie viele Taktzyklen Sie ausstoßen, berechnen Sie, wie viel Zeit Ihr Prozessor zur Verfügung hat, um alle GPU-Batches für einen konstanten 120-FPS-Rhythmus bereitzustellen, und Sie sehen, dass diese Dinge auf eine beträchtliche Menge skalieren können.

Es wäre lustig, wenn zum Beispiel ein Hacker, der an einer Web-App arbeitet, auch nur über solch winzige Mikrooptimierungen nachdenken würde, aber wir wissen, dass Spiele Echtzeitsysteme sind, bei denen die Ressourcenbeschränkungen unglaublich knapp sind, daher ist diese Überlegung für uns nicht fehl am Platze.

Um dies zu vermeiden, denken wir anders darüber nach: Was wäre, wenn wir die Liste der sichtbaren Renderables in der Engine behalten würden? Sicher, wir würden die saubere Syntax von myRenerable->hide() opfern und gegen einige OOP-Prinzipien verstoßen, aber wir könnten dann Folgendes tun:

Hurra! Keine falschen Verzweigungsvorhersagen, und vorausgesetzt, mVisibleRenderables ist ein netter std::vector (ein zusammenhängendes Array), hätten wir dies genauso gut als schnellen memcpy-Aufruf umschreiben können (mit einigen zusätzlichen Aktualisierungen unserer Datenstrukturen wahrscheinlich).

Nun, Sie können mich auf die schiere Kitschigkeit dieser Codebeispiele hinweisen und Sie haben völlig Recht: Dies ist stark vereinfacht. Aber um ehrlich zu sein, habe ich noch nicht einmal an der Oberfläche gekratzt. Das Nachdenken über Datenstrukturen und deren Beziehungen eröffnet uns eine Menge Möglichkeiten, über die wir vorher noch nicht nachgedacht haben. Schauen wir uns als nächstes einige davon an.

Parallelisierung und Vektorisierung

Wenn wir einfache, gut definierte Funktionen haben, die mit großen Datenblöcken als Basisbausteine für unsere Verarbeitung arbeiten, ist es einfach, vier, acht oder 16 Worker-Threads zu erzeugen und jedem von ihnen ein Stück Daten zu geben, um die gesamte CPU zu behalten Kerne beschäftigt. Keine Mutexes, Atomics oder Sperrenkonflikte, und sobald Sie die Daten benötigen, müssen Sie nur alle Threads beitreten und warten, bis sie fertig sind. Wenn Sie Daten parallel sortieren müssen (eine sehr häufige Aufgabe bei der Vorbereitung von Daten, die an die GPU gesendet werden), müssen Sie dies aus einer anderen Perspektive betrachten – diese Folien können hilfreich sein.

Als zusätzlichen Bonus können Sie innerhalb eines Threads SIMD-Vektoranweisungen (wie SSE/SSE2/SSE3) verwenden, um einen zusätzlichen Geschwindigkeitsschub zu erzielen. Manchmal können Sie dies nur erreichen, indem Sie Ihre Daten auf eine andere Art und Weise platzieren, z. B. indem Sie Vektorarrays in einer Struktur von Arrays(SoA) platzieren (wie XXX...YYY...ZZZ...) konventionelle Array-of-Strukturen (AoS; das wäre XYZXYZXYZ...). Ich kratze hier kaum an der Oberfläche; Weitere Informationen finden Sie im Abschnitt Weiterführende Literatur weiter unten.

Wenn unsere Algorithmen direkt mit den Daten umgehen, wird es trivial, sie zu parallelisieren, und wir können auch einige Geschwindigkeitsnachteile vermeiden.

Unit-Tests, von denen Sie nicht wussten, dass sie möglich sind

Einfache Funktionen ohne externe Effekte machen den Unit-Test einfach. Dies kann besonders gut in Form von Regressionstests für Algorithmen sein, die Sie einfach ein- und auswechseln möchten.

Sie können beispielsweise eine Testsuite für das Verhalten eines Culling-Algorithmus erstellen, eine orchestrierte Umgebung einrichten und die Leistung genau messen. Wenn Sie einen neuen Culling-Algorithmus entwickeln, führen Sie denselben Test ohne Änderungen erneut aus. Sie messen Leistung und Korrektheit, damit Sie die Bewertung jederzeit zur Hand haben.

Je mehr Sie sich mit datenorientierten Designansätzen beschäftigen, desto einfacher wird es, Aspekte Ihrer Spiel-Engine zu testen.

Kombinieren von Klassen und Objekten mit monolithischen Daten

Datenorientiertes Design steht der objektorientierten Programmierung keineswegs entgegen, nur einige ihrer Ideen. Infolgedessen können Sie Ideen aus dem datenorientierten Design ganz ordentlich verwenden und trotzdem die meisten Abstraktionen und mentalen Modelle erhalten, an die Sie gewöhnt sind.

Schauen Sie sich zum Beispiel die Arbeit an OGRE Version 2.0 an: Matias Goldberg, der Mastermind hinter diesem Unterfangen, hat sich dafür entschieden, Daten in großen, homogenen Arrays zu speichern und Funktionen zu haben, die über ganze Arrays iterieren, anstatt nur an einem Datum zu arbeiten , um Ogre zu beschleunigen. Laut Benchmark (was er zugibt, ist sehr unfair, aber der gemessene Leistungsvorteil kann nicht nur daran liegen) arbeitet es jetzt dreimal schneller. Darüber hinaus behielt er viele der alten, vertrauten Klassenabstraktionen bei, sodass die API bei weitem nicht komplett neu geschrieben wurde.

Ist es praktisch?

Es gibt viele Beweise dafür, dass Spiel-Engines auf diese Weise entwickelt werden können und werden.

Der Entwicklungsblog von Molecule Engine hat eine Reihe namens Adventures in Data-Oriented Design und enthält viele nützliche Ratschläge, wo DOD mit großartigen Ergebnissen eingesetzt wurde.

DICE scheint an datenorientiertem Design interessiert zu sein, da sie es im Culling-System der Frostbite Engine verwendet haben (und auch signifikante Geschwindigkeitssteigerungen erzielt haben!). Einige andere Folien von ihnen beinhalten auch den Einsatz von datenorientiertem Design im KI-Subsystem – auch einen Blick wert.

Abgesehen davon scheinen Entwickler wie der bereits erwähnte Mike Acton das Konzept zu übernehmen. Es gibt ein paar Benchmarks, die belegen, dass es viel an Leistung zulegt, aber ich habe seit einiger Zeit nicht mehr viel Aktivität an der datenorientierten Designfront gesehen. Es könnte natürlich nur eine Modeerscheinung sein, aber seine Hauptprämissen scheinen sehr logisch. Es gibt in diesem Geschäft (und in jedem anderen Softwareentwicklungsgeschäft) sicherlich eine Menge Trägheit, so dass dies eine groß angelegte Einführung einer solchen Philosophie behindern kann. Oder vielleicht ist es keine so gute Idee, wie es scheint. Was denkst du? Kommentare sind sehr willkommen!

Weiterführende Literatur

  1. Datenorientiertes Design (oder warum Sie sich mit OOP in den Fuß schießen könnten)
  2. Einführung in das datenorientierte Design [DICE]
  3. Eine ziemlich nette Diskussion auf Stack Overflow
  4. Ein Online-Buch von Richard Fabian, das viele Konzepte erklärt
  5. Ein Benchmark, der die andere Seite der Geschichte zeigt, ein scheinbar kontraintuitives Ergebnis
  6. Mike Actons Review von OgreNode.cpp, der einige häufige Fallstricke bei der Entwicklung von OOP-Spielengines aufdeckt
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.