© best_vector/Shutterstock.com
Teil 4: Grundlegende künstliche Intelligenz und Leveldesign

Kollisionserkennung auf der Xbox One


Die Entwicklung von 3-D-Spielen ist unter anderem deshalb so komplex, weil die Anzahl der Akteure schnell sehr groß wird und – insbesondere bei falscher Programmierung – enorme Ansprüche an die Hardware stellt.

Am Ende des letzten Teils dieser Serie hatten wir unsere Würfel in Bewegung versetzt: Leider waren wir noch nicht dazu in der Lage, Kollisionen zwischen den einzelnen Elementen zu erkennen. Kollisionserkennung ist eine jener Schwierigkeiten, die auf den ersten Blick primitiv erscheint, bei falscher Implementierung aber zu großen Problemen führt. Das liegt unter anderem an der Art des Wachstums: Wenn sich die Anzahl der Objekte verdoppelt, erhöht sich der Komplexitätsgrad der Kollisionserkennung mit dem Faktor n². Dies ist ansatzweise in Abbildung 1 dargestellt.

hanna_xbox_1.tif_fmt1.jpgAbb. 1: Dieses Wachstum überfordert über kurz oder lang jede Workstation

Alles Ansichtssache

Der erste Weg zur Kollisionserkennung besteht darin, jedes Objekt nacheinander abzuarbeiten und auf Kollisionen mit allen anderen Objekten zu überprüfen. Die Methode ist insofern nicht zielführend, als sich dabei Ineffizienzen ergeben: Wer das Objekt eins auf Kollisionen mit dem Objekt vier prüft, muss nachher keine Prüfung von vier und eins mehr durchführen. Die erste Optimierung setzt somit das Reduzieren der zu prüfenden Indizes voraus – Abbildung 2 zeigt das dahinter stehende Verfahren auf eine grafische Art und Weise.

hanna_xbox_2.tif_fmt1.jpgAbb. 2: Wer die Indizes der Iteration dynamisch anpasst, spart Rechenzeit

Das zweite – und wesentlich wichtigere – Verfahren zur Reduktion des Kollisionserkennungsaufwands ist die Einführung von Bounding Boxes und/oder Bounding Spheres. Es ist insofern wichtig, als komplexe Modelle schnell aus mehreren 100 Dreiecken bestehen: Wer jedes Dreieck mit allen anderen vergleicht, hat auch bei zwei oder drei Ikosaedern massive Probleme mit der Framerate. Zur Lösung dieses Problems bietet sich die Einführung einer Kontrollstruktur an, die das zu überprüfende Objekt als Ganzes einschließt und so den Vergleich vereinfacht. Wenn die beiden Rechtecke bzw. Kugeln sich nicht berühren, berühren sich auch die beiden Objekte nicht. Haben die beiden Elemente Kontakt, kann eine detailliertere Prüfung erfolgen – in vielen Fällen reicht es aber auch aus, von einer Kollision auszugehen (Kasten „Mehrstufige Hierarchien“).

Das manuelle Erzeugen einer Bounding Box ist nicht besonders komplex: Iterieren Sie einfach über alle im Modell enthaltenen Vertizes und notieren Sie die Koordinaten. Auf diese Art und Weise können Sie einen maximalen und einen minimalen Wert für jede Koordinate bestimmen, der dann die Eckpunkte der Bound­ing Box beschreibt. Erfreulicherweise ist dies im Fall des DirectX-Toolkits nicht notwendig: Das Framework kümmert sich im Rahmen der Modellerzeugung automatisch um das Anlegen einer Bounding Box für jeden Mesh. Als Entwickler müssen Sie diese Informationen nur noch entnehmen und in eine gemeinsame Bounding Box zusammenfassen, die für das Objekt als Ganzes Gültigkeit hat. Eine weitere Nettigkeit ist die von Microsoft im Rahmen des SimpleMath-Erweiterungsobjekts bereitgestellte BoundingBox-Klasse, die einen Gutteil der Verwaltungslogik der Bounding Box implementiert.

Damit stellt sich für uns eigentlich nur die Frage, wo die Bounding Box entstehen soll. Hierzu ist etwas Theorie notwendig: Erinnern Sie sich, dass Modelle im Rahmen der Darstellung skaliert, rotiert und verschoben werden. Das Modell selbst sitzt dabei im Modellkoordinatensystem, das normalerweise – je nach Implementierung – entweder im Bereich 0-1 oder im Bereich -1 bis +1 beheimatet ist. Daraus folgt, dass Sie die Bounding Box für das Modell idealerweise gleich nach dem Laden der Modellkoordinaten berechnen – sie verändert sich zur Laufzeit nicht mehr. Im Fall unserer Modellklasse erledigen wir diese Arbeit im Konstruktor:

SUSModel::SUSModel(ID3D11Device* _dev, std::string& resource) { . . . myModel = Model::CreateFromCMO(_dev, myPointer, *m_fxFactory); createRawBoundingBox(); . . .

createRawBoundingBox() ist nicht sonderlich komplex. Sie beschafft im ersten Schritt einen Generator, der alle im jeweiligen Modell vorliegenden MeshParts nacheinander abarbeitet. Der Korpus der Selektion prüft im ersten Schritt, ob das zurückgegebene Mesh-Objekt nicht null ist. Ist das der Fall, so werden seine Werte mit den schon in der Bounding Box vorhanden Informationen zusammengeführt (Listing 1).

Listing 1

void SUSModel::createRawBoundingBox(){ for (auto it = myModel->meshes.cbegin(); it != myModel->meshes.cend(); ++it) { auto mesh = it->get(); assert(mesh != 0); myRawBoundingBox.CreateMerged(myRawBoundingBox, myRawBoundingBox, mesh->boundingBox); } }

Auffällig an dieser Konstruktion ist, dass die Bound­ingBox-Klasse fast ausschließlich mit out-Parametern arbeitet. So ist die Funktion CreateMerged beispielsweise folgendermaßen deklariert:

static void CreateMerged( _Out_ BoundingBox& Out, _In_ const BoundingBox& b1, _In_ const BoundingBox& b2 );

Die nächste Aufgabe besteht darin, die berechnete Box an den gewünschten Ort zu transferieren. Eine Bound­ing Box ist im Grunde genommen genauso ein dreidimensionales Objekt wie e...

Neugierig geworden? Wir haben diese Angebote für dich:

Angebote für Gewinner-Teams

Wir bieten Lizenz-Lösungen für Teams jeder Größe: Finden Sie heraus, welche Lösung am besten zu Ihnen passt.

Das Library-Modell:
IP-Zugang

Das Company-Modell:
Domain-Zugang