Kollisionserkennung



  • Also ich arbeite zu Übungszwekcen an einem kleinem 2D-Arcade-Weltraumballerspiel. Jetzt überlege ich, wie ich die Kollisionserkennung umsetzen soll.

    Zunächst folgende Abschätzung:
    - Es werden sich maximal 20 Schiffe auf dem Bildschirm befinden.
    - Es werden sich maximal 40 Laser/Raketen auf dem Bildschirm befiden.

    Kollisionserkennung erfolgt für:
    - Schiffe untereinander.
    - Schiffe mit Lasern/Raketen.
    (- Kollisionserkennung bei Lasern/Raketen untereinander findet nicht statt.)

    Folgendes habe ich mir gedacht.
    - Als grobe Vorabschätzung verwende ich Bounding Spheres (bzw. bei mir Circles), und für die Kollisionserkennung zwischen Waffenfeuer (Laser/Raketen) und Schiffen auch ausschließlich diesen Test.
    - Für Schiffe untereinander, bei denen der Vorabtest positiv ausfällt, prüfe ich ob sich Linien von einem groben Polygonmodell des Schiffs (das die Form annähert) schneiden. (siehe z.B. http://director-online.com/howto/ud_articles/ud219/ud219d.jpg)

    Ist diese Vorgehen ok? Würdet ihr etwas anders machen, falls ja, wie?



  • Dass du vorher mit Bounding Spheres testen willst ist zwar nett, aber eine bessere Zeitkomplexität erreichst du damit nicht. Wenn du alle Schiffe mit allen anderen testest, beträgt der Aufwand O(n²).

    Vorher brauchst du noch eine vernünftige Raumunterteilung (im einfachsten Fall ein Grid), so dass du nur mit Objekten testest, auf die es ankommt.


  • Mod

    Evolver schrieb:

    Ist diese Vorgehen ok? Würdet ihr etwas anders machen, falls ja, wie?

    bei 1200 Tests duerfte das vollkommend ausreichend sein, falls du doch mal performance probs bekommen solltest, merk dir bei jedem objekt beim testen die entfernung zum naehersten anderen objekt. dann teile das durch 2. bei jeder bewegung der objekte musst du die zurueckgelegte strecke von dieser gemerkten entfernung abziehen, falls die entfernung dann <=0 prfuefst du das objekt gegen alle anderen die da sind.

    hat eine laufzeit von O(n)



  • rapso schrieb:

    hat eine laufzeit von O(n)

    Das glaub ich nicht. Wie willste verhindern, dass für mehr als konstant viele Objekte der Wert gleichzeitig unter 0 sinkt? Sobald das passierte haste mehr als Linearzeit.



  • Wegen der Geschwindigkeit egal, die kann man spaeter noch reparieren. Ich wuerde mir lieber sorgen darum machen, ob Schuesse durch Schiffe durchfliegen koennen, wenn sich z.b. innerhalb eines Frames durch das ganze Raumschiff bewegegen. Genauso ist dein Test ob sich die Linien schneiden, ja auch nicht ganz korrekt. Es koennen ja auch Dinge komplett ineinander sein. Das kann dann dazu fuehren, das sich irgendwas ineinander verkeilt. f'`8k

    Gruß, TGGC (\-/ has leading)



  • Dass du vorher mit Bounding Spheres testen willst ist zwar nett, aber eine bessere Zeitkomplexität erreichst du damit nicht. Wenn du alle Schiffe mit allen anderen testest, beträgt der Aufwand O(n²).

    Klar, ich muss nicht weniger Tests durchführen. Der Sinn ist ja, nicht bei jedem Test die aufwendige Schnittpunktberechnung durchführen zu müssen.

    Genauso ist dein Test ob sich die Linien schneiden, ja auch nicht ganz korrekt. Es koennen ja auch Dinge komplett ineinander sein. Das kann dann dazu fuehren, das sich irgendwas ineinander verkeilt.

    Ich habe von diesem Problem gelesen, da aber die Schiffe etwa gleiche Größen haben, sollte ich das außer Acht lassen können.

    Ich wuerde mir lieber sorgen darum machen, ob Schuesse durch Schiffe durchfliegen koennen, wenn sich z.b. innerhalb eines Frames durch das ganze Raumschiff bewegegen.

    Das hatte ich noch nicht bedacht. Wie würdest du das vermeiden?



  • Genaue Methode:
    Die Tests finden in 3D statt, mit t als dritte Dimension. Es gibt keine Kreise mehr, sondern (schiefe) Zylinder.

    Akzeptable Methode:
    Statt Kreisen werden "Kapseln" benutzt, langgezogene Kreise, die beim Kreis aus dem vorigen Schritt starten und beim naechsten Schritt enden, dazwischen liegt ein Rechteck mit Laenge des Bewegungsschrittes und Breite des Durchmesser der Kreise.

    Frickel Methode:
    Es ist eine maximale Bewegung von x Einheiten pro Schritt erlaubt, ist die Bewegung groesser, so wird sie in n Unterschritte zerlegt, so das jeder Unterschritt < x.

    Gruß, TGGC (\-/ has leading)[/quote]



  • Evolver schrieb:

    Dass du vorher mit Bounding Spheres testen willst ist zwar nett, aber eine bessere Zeitkomplexität erreichst du damit nicht. Wenn du alle Schiffe mit allen anderen testest, beträgt der Aufwand O(n²).

    Klar, ich muss nicht weniger Tests durchführen. Der Sinn ist ja, nicht bei jedem Test die aufwendige Schnittpunktberechnung durchführen zu müssen.

    Das nutzt dir aber bei 50+ Objekten nichts mehr. Wenn du 50² Tests durchführen musst, dann muss ein Test schon wirklich sehr schnell gehen, damit noch nicht alles scheiße ist. 🙂



  • Jester schrieb:

    rapso schrieb:

    hat eine laufzeit von O(n)

    Das glaub ich nicht. Wie willste verhindern, dass für mehr als konstant viele Objekte der Wert gleichzeitig unter 0 sinkt? Sobald das passierte haste mehr als Linearzeit.

    In dem einen Frame, ja. Wenn man das aber über alle Frames mittelt, dann könnte (ich weiß es nicht) schon sowas wie O(n) rauskommen. Wir haben das als Bankkonto-Prinzip kennengelernt. Du sagst ja auch nicht, dass std::vector O(n) für's adden hat, kann aber durchaus mal passieren.



  • Stell Dir 3 Objekte nebeneinander vor und das dazwischen wackelt immer rechts links hin und her. Dann unterschreitet dieses Objekt ständig seine Grenze und muß mit allen Objekten verglichen werden.

    Das gibt auch amortisiert nicht O(n):

    Von diesen dreier-Gruppen können wir nun eine n Stück hinstellen. Alle paar Frames unterschreitet 1/3 n der Objekte seine Schwelle und muss mit allen anderen Objekte verglichen werden.

    Wenn die Szene aber günstig ist, dann ist die Heuristik sicher nett und vor allem leicht zu implementieren.



  • soweit (ich weis und bemerkt habe) arbeiten 2D-Arcarde-Weltraumballerspiele mit einfachen Computerki's (Raumshiffe bewegen sich sinusartig dem gegner entgegen -> berechnen der entfernung und des sinus - somit weis man beim schuss schon das es zu (k)einer kollision kommt -> der rechen aufwand wird anschliesend "nur" noch die kollision sein ... wenn man(n und frau) es richtig hand habt.

    Sollte es aber einen ausweich-algoryhtmus geben sollte das nicht mehr funktionieren -.-


  • Mod

    Jester schrieb:

    rapso schrieb:

    hat eine laufzeit von O(n)

    Das glaub ich nicht. Wie willste verhindern, dass für mehr als konstant viele Objekte der Wert gleichzeitig unter 0 sinkt? Sobald das passierte haste mehr als Linearzeit.

    genauso wie du verhindern willst, dass ein binärbaum mit zwei elementen eine laufzeit von O(n) hat, statt der ueberall angegebenen O(log n)


  • Mod

    Evolver schrieb:

    Ich wuerde mir lieber sorgen darum machen, ob Schuesse durch Schiffe durchfliegen koennen, wenn sich z.b. innerhalb eines Frames durch das ganze Raumschiff bewegegen.

    Das hatte ich noch nicht bedacht. Wie würdest du das vermeiden?

    schuesse stellt man nicht als punkte dar (oder spheres), sondern als rays (anfangspunkt ist die position des letzten frames, endpunkt die des jetzigen). du musst also 20*50 tests von ray-sphere machen. falls du vorab sphere-sphere testen willst, nimmst du die mitte des rays und der radius ist die laenge ist die haelfte vom ray.

    das funktioniert problemlos, da bei deinem 2D spaceshooter vernutlich keine so grossen geschwindigkeiten auftauchen wie bei einem 3d spaceshooter



  • rapso schrieb:

    Jester schrieb:

    rapso schrieb:

    hat eine laufzeit von O(n)

    Das glaub ich nicht. Wie willste verhindern, dass für mehr als konstant viele Objekte der Wert gleichzeitig unter 0 sinkt? Sobald das passierte haste mehr als Linearzeit.

    genauso wie du verhindern willst, dass ein binärbaum mit zwei elementen eine laufzeit von O(n) hat, statt der ueberall angegebenen O(log n)

    ich hab doch ein beispiel angegeben, das quadratische Laufzeit hat. Ich glaub Dir ja, dass die Heuristik gut ist und in vielen Fällen auch schöne Ergebnisse liefert. Aber ich denke nicht, dass sie die Komplexität senkt. Dazu muss man schon sowas wie ne Lokalisierung bringen, wie Optimizer ja vorgeschlagen hatte.



  • Jester schrieb:

    rapso schrieb:

    Jester schrieb:

    rapso schrieb:

    hat eine laufzeit von O(n)

    Das glaub ich nicht. Wie willste verhindern, dass für mehr als konstant viele Objekte der Wert gleichzeitig unter 0 sinkt? Sobald das passierte haste mehr als Linearzeit.

    genauso wie du verhindern willst, dass ein binärbaum mit zwei elementen eine laufzeit von O(n) hat, statt der ueberall angegebenen O(log n)

    ich hab doch ein beispiel angegeben, das quadratische Laufzeit hat. Ich glaub Dir ja, dass die Heuristik gut ist und in vielen Fällen auch schöne Ergebnisse liefert. Aber ich denke nicht, dass sie die Komplexität senkt. Dazu muss man schon sowas wie ne Lokalisierung bringen, wie Optimizer ja vorgeschlagen hatte.

    Wenn man als Eingabe nur konstant viel zulässt (Hier 20 Schiffe 40 Raketen) läuft JEDER Algorithmus in O(1), weil IMMER was Konsantes rauskommt (bezogen auf die konstante Eingabe).
    In solch einem Fall kann man weder von O(n) noch O(log n) reden. Das geht nur, wenn n als Eingabe erlaubt ist (worauf sich die groß O Notation ja auch bezieht).



  • Optimizer schrieb:

    Dass du vorher mit Bounding Spheres testen willst ist zwar nett, aber eine bessere Zeitkomplexität erreichst du damit nicht. Wenn du alle Schiffe mit allen anderen testest, beträgt der Aufwand O(n²).

    Vorher brauchst du noch eine vernünftige Raumunterteilung (im einfachsten Fall ein Grid), so dass du nur mit Objekten testest, auf die es ankommt.

    Das war die erste Antwort. Und damit wurde die Frage beantwortet. Weiss nicht was hier noch rumdiskutiert wird 😉

    Man bastle ein Grid wo jede Zelle eine Liste hat. Dann gucke man alle Objekte durch und stecke sie in jede Zelle rein die sie schneiden.
    Jetzt braucht man bloss noch alle Objekte innerhalb einer Zelle gegeneinander zu prüfen, und fertig.


  • Mod

    Jester schrieb:

    rapso schrieb:

    Jester schrieb:

    rapso schrieb:

    hat eine laufzeit von O(n)

    Das glaub ich nicht. Wie willste verhindern, dass für mehr als konstant viele Objekte der Wert gleichzeitig unter 0 sinkt? Sobald das passierte haste mehr als Linearzeit.

    genauso wie du verhindern willst, dass ein binärbaum mit zwei elementen eine laufzeit von O(n) hat, statt der ueberall angegebenen O(log n)

    ich hab doch ein beispiel angegeben, das quadratische Laufzeit hat.

    und ich gab dir eines fuer einen binaerbaum bei dem suchen lineare zeit braucht.

    Ich glaub Dir ja, dass die Heuristik gut ist und in vielen Fällen auch schöne Ergebnisse liefert.

    wir glauben es nicht nur, wir nutzen das sogar um es mathematisch zu beweisen (egal ob beim binaerbaum oder collision-list).

    Aber ich denke nicht, dass sie die Komplexität senkt. Dazu muss man schon sowas wie ne Lokalisierung bringen, wie Optimizer ja vorgeschlagen hatte.

    wieso glaubst du sowas bei binaerbaeumen aber nicht bei collision-lists?


  • Mod

    Andreas XXL schrieb:

    Wenn man als Eingabe nur konstant viel zulässt (Hier 20 Schiffe 40 Raketen) läuft JEDER Algorithmus in O(1), weil IMMER was Konsantes rauskommt (bezogen auf die konstante Eingabe).
    In solch einem Fall kann man weder von O(n) noch O(log n) reden. Das geht nur, wenn n als Eingabe erlaubt ist (worauf sich die groß O Notation ja auch bezieht).

    lies dir was zur komplexitaet und laufzeitverhalten durch 😉



  • rapso schrieb:

    Andreas XXL schrieb:

    Wenn man als Eingabe nur konstant viel zulässt (Hier 20 Schiffe 40 Raketen) läuft JEDER Algorithmus in O(1), weil IMMER was Konsantes rauskommt (bezogen auf die konstante Eingabe).
    In solch einem Fall kann man weder von O(n) noch O(log n) reden. Das geht nur, wenn n als Eingabe erlaubt ist (worauf sich die groß O Notation ja auch bezieht).

    lies dir was zur komplexitaet und laufzeitverhalten durch 😉

    Man sieht, dass du nichts von der O Notation verstanden hast, wenn du MIR nach meiner Antwort empfielst WAS zur "komplexitaet und laufzeitverhalten" durchzulesen.

    Ist aber nit böse gemeint 🙂



  • Andreas XXL schrieb:

    rapso schrieb:

    Andreas XXL schrieb:

    Wenn man als Eingabe nur konstant viel zulässt (Hier 20 Schiffe 40 Raketen) läuft JEDER Algorithmus in O(1), weil IMMER was Konsantes rauskommt (bezogen auf die konstante Eingabe).
    In solch einem Fall kann man weder von O(n) noch O(log n) reden. Das geht nur, wenn n als Eingabe erlaubt ist (worauf sich die groß O Notation ja auch bezieht).

    lies dir was zur komplexitaet und laufzeitverhalten durch 😉

    Man sieht, dass du nichts von der O Notation verstanden hast, wenn du MIR nach meiner Antwort empfielst WAS zur "komplexitaet und laufzeitverhalten" durchzulesen.

    Ist aber nit böse gemeint 🙂

    OMG. "... wenn man als Eingabe nur konstant viel zulässt ..." dann labert man auch gar nicht rum. Was meinst du, worum es hier geht?


Log in to reply