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

[Phantom1]

Ich arbeite im moment auch an einem 2D-Weltraumshooter ^^

Ich hab mir jetzt deine Collisionsberechnung nicht so genau angeschaut, denn ich hab das anders gemacht, so sieht der ablauf bei mir aus:
1. alle Objekte werden gegenseitig geprüft
2. in jedem Objekt ist definiert mit welchen Objekten es kollidieren darf
3. ein einfacher Vergleich ob sich zwei Objekte überschneiden (RectInRect)
4. Pixelcollision (nur schwarz/weiß)

Du kannst dir gerne meinen Code anschauen, hab das komplette Projekt angehangen.

Momentan hab ich folgende Sachen implementiert:
- DirectDraw (1024x768 in 16bit Fullscreen)
- alles komplett selbst geschrieben (NonVCL, OOP), hab auf jegliche komponenten/fremdcode verzichtet (ausnahme Directdraw.pas).
- eigenes Grafikformat für die animierten grafiken
- Timebased Movement
- Pixelcollision
- Alpha-Transparenz (8bit)
- Animationen
- die Grafiken wurden auch von jemanden extra für dieses Spiel gezeichnet

Spielen kann man allerdings noch nicht richtig, denn ich habe noch keine Levels gebaut, dh die gegner kommen bis jetzt nur zufällig. Man selbst kann auch nicht sterben ^^

mfg

[OregonGhost]

Ich habe jetzt zugegeben nicht versucht, deinen Algorithmus bis ins letzte Detail zu verstehen. Aber folgendes als Denkanregung:
Du kannst die Anzahl der benötigten Vergleiche reduzieren, indem du eine Achsensortierung vornimmst. Für die Kollisionsprüfung gehst du all deine Objekte also nicht in einer beliebigen Reihenfolge durch, sondern von links nach rechts und von oben nach unten (oder so in der Art). Ehrlich gesagt krieg ich den Algorithmus aus dem Kopf derzeit nicht auf die Reihe und finde ihn auch nicht (er war glaub ich in einem Buch zu finden, aber ich ziehe demnächst um und die Bücher sind in irgendwelchen Kartons ), aber sinngemäß kann man dadurch schnell ableiten, für welche Objekte eine Kollisionsprüfung überhaupt nicht erforderlich ist. Also wenn zum Beispiel auf der X-Achse Objekt 1 und 2 sich nicht überschneiden, kann sich Objekt 3 auch unmöglich mit Objekt 1 überschneiden.

Edit: Dir ging es eventuell weniger um die Kollisionen an sich als mehr um die Konsequenzen von Kollisionen auf spätere Kollisionen, richtig? Eventuell ist es dann möglich, innerhalb eines Frames die Kollisionen zeitlich nacheinander zu betrachten. Ein Frame-Skipping-Algorithmus kann dir helfen, die Granularität der Prüfung genau genug zu machen, damit du innerhalb eines Frames keine zwei aufeinanderfolgenden Kollisionen hast (schnelle Schüsse stellen da ein Problem da, wie von dir bereits erkannt). Ich sitze natürlich gerade auf der Arbeit und habe nicht genug Zeit, mir abschließend dazu genug Gedanken zu machen, aber ich denk bei Gelegenheit nochmal drüber nach

Dein Spiel wird bestimmt cool