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.