Aufwandsanalyse für Kollisionserkennung

[Nikolas]

Hallo

Bei meinem aktuellen Projekt, einem 2D WeltraumShooter (der in ein paar Tagen hier vorgestellt wird), baue ich gerade die Kollisionserkennung ein.

Mein aktueller Plan sieht so aus:

Ich unterteile den Bildschirm in Kacheln und merke mir in jedem Objekt die passende Kachel. In einem Frame suche ich dann nach Kollisionen:

Für jedes Objekt untersuche ich, ob es mit einem Objekt in den umliegenden 9 Kacheln innerhalb des nächsten Frames kollidieren würde und merke mir diese Paare (Objekt1, Objekt2, Zeitpunkt im Frame) und lege mir für jede Kachel eine zeitlich sortierte Liste für alle Kollisionen an. Wenn ich O Objekte in jeder Kachel habe, (und T Kacheln) werde ich dafür wohl etwa 9/2*T*O^2 Kollisionstests brauchen. (für jedes der T*O Objekt 9*0 Vergleiche, da ich aber nicht zwei Raumschiffe zweimal miteinander testen muss, nur 4,5*K*0^2 Tests)

Jetzt nehme ich die erste Kollision und setzte die beteiligten Objekte an den Kollisionsort und berechne deren neue Geschwindigkeiten (eines der Objekte wird diese Kollision fast immer nicht überleben, da es sich um einen Schuss handelt, der irgendwo einschlägt). Jetzt gehe ich die Liste der betroffenen Kachel durch und berechne alle Kollisionen, bei denen eines der gerade bewegten Objekte teilnimmt neu. Ausserdem berechne ich noch mal für das kollidierte Objekt die Kollisionen mit allen Objekten in den umliegenden Kacheln.
Damit habe ich dann sichergestellt, dass Kollisionen nicht stattfinden, wenn eines der Objekte vorher durch eine andere Kollision zerstört wurde, andererseits finde ich auch Kollisionen die stattfinden, weil z.B. ein Schuss von einem Schutzschild abgelenkt wurde und ein anderes Raumschiff trifft.

Das mache ich dann so lange, bis ich keine Kollision mehr finde.

Wenn ich in einem Frame K Kollisionen auf meinem Bildschirm habe, habe ich dadurch nochmal zusätzlich 9*K*O Kollisionsvergleiche.

So viel zum Plan. Jetzt kommt die wichtige Frage nach der Machbarkeit.

Für T=50, O=30, K=50 (2500Kollisionen pro Sekunde) 4,5*T*O^2+9*K*O = 200.000 + 13.500 Kollisionen, was deutlich zu viel ist. Wenn ich aber meine Kachelgröße senke, wird auch der testbereich eines Objekts kleiner, was zu Problemem mit schnellen Schüssen führen wird.

Meine Frage ist jetzt, ob die Werte sinnvoll sind. Ich bin mal von etwa 50 Kacheln ausgegangen mit durchschnittlich einer Kollision. Vielleicht ist das zu wenig, vielleicht sind 1500 Objekte übertrieben.

Habt ihr sowas schon mal geschrieben und vielleicht eine schnellere Lösung (vll auch nur eine gute Heuristik?)

Oder habt ihr Erfahrung mit den Werten für so ein Ballerspiel, also wie viele Objekte etwa auf dem Bildschirm sind und wie oft diese kollidieren?

Nikolas