spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hallo,

ich versuche gerade effizient eine Kollisionserkennung mit vielen Objekten durchzuführen. Das Problem ist allerdings die Komplexität dahinter, dass bedeutet, dass es durchaus zu lange dauern kann eine Kollision im 3D-Raum zu erkennen.

Erst einmal zu meinem Szenario: Ich habe ein paar hundert Objekte, die alle eine Bounding Box besitzen. Ich besitze selbst eine steuerbare Spielerfigur, die ebenfalls eine Bounding Box besitzt. Die Frage ist jetzt, wie ich nun effizient nach Kollisionen suche, so dass sich die Spielfigur auf anderen Objekten bewegt und beispielsweise eine Kollision vor der Figur erkannt wird und die Figur somit stoppt?

Der einfachste Ansatz wäre, alle Objekte der Welt abzufragen ob diese mit meiner sich bewegenden Spielfigur kollidieren (Brute-Force). Der Ansatz ist im nachhinein allerdings ineffizient, da es ja nicht heißt, dass meine Figur die einzige Figur ist, die sich in der Welt bewegt. Mal abgesehen davon, dass die Abfrage der Kollisionen stetig steigt, je mehr Objekte in der Welt "aufkreuzen" (das lässt sich natürlich mit der Sichtreichweite begrenzen).

Ich habe etwas gegoogelt und dort wurden einige Ideen vorgeschlagen. Unter anderen "Sweep and Prune " oder das "Grid". Wobei letzteres wohl am besten geeignet ist, allerdings müsste das auch bedeuten, dass alle Objekte die gleiche Größe besitzen. Zumindest, wenn man von dem Standardalgorithmus ausgeht. Ersteres klingt nicht schlecht, allerdings muss hier jedes der Objekte vorerst sortiert werden, was ich etwas unschön finde. Mal abgesehen davon, dass ich nicht weiß, ob sich diese Methoden im 3D Raum überhaupt behaupten und ob es da nicht andere effizientere Methoden gibt.

Jetzt stellt sich für mich natürlich die Frage, wie ihr das umsetzen würdet?
Vielleicht habt ihr ja noch Ideen, Ressourcen und Vorschläge zu diesem Thema?

Beste Grüße und vielen Dank,
Manic.

Hallöchen zusammen,

ich muss mich erst einmal entschuldigen. Ich hatte in der letzten Zeit leider etwas viel mit meiner Masterabeit zu tun, weswegen eine längere Abstinenz hier zustande kam. Jetzt möchte ich dennoch erst einmal antworten!

Ich muss schon sagen, dass eure Beiträge wirklich (größtenteils) Hilfreich sind.
Die Geschichte, was einen Quadtree angeht, finde ich sehr interessant. Auch AABB Tree's die sich generell schon anbieten würden, da jedes Objekt schon eine Bounding Box besitzt. Was ich nun genau verwende weiß ich jetzt noch nicht genau, dass wird sich dann aber später zeigen.

Diese 3D-Gitter-Sache meinte ich in meiner ersten Nachricht. Ein konkretes Konzept dafür hatte ich bisher noch nicht gefunden, würde danach aber nochmal gezielt suchen. Das 3D-Gitter würde sich hier auch ziemlich gut anbieten, da es sich eigentlich auch um simple Objekte handelt, die wahrscheinlich sowieso nur immer eine feste maximale Größe haben und die Kollisionserkennung nicht allzu komplex sein muss.

Interessant finde ich auch die erste Antwort auf meine Nachricht. Von derartigen Techniken für "Culling" und "Occlusion" hatte ich bisher noch nicht gehört. Vielleicht würde mir das schon fast genügen. Mal schauen was sich dazu finden lässt!

Eine Physik Engine einzubinden finde ich auch recht interessant, allerdings geht es mir hier nicht direkt um ein komplettes Spiel, welches ich programmieren möchte, sondern eher um die Mechaniken, die dahinterstehen. Diese möchte ich kennen lernen und verstehen. (-:

Ich finde das Buch "Real-Time Collision Detection" von Christer Ericson in diesem Bezug ziemlich hilfreich, da dort -wie der Name schon sagt- konkret auf ("Echtzeit-") Kollisionserkennung eingegangen wird. Das kann ich in diesem Zusammenhang nur empfehlen.

// EDIT: Schleifen sind in diesem Zusammenhang mehr als nur unpassend.