Kollisionserkennung



  • 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?



  • Evolver schrieb:

    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?

    Wie DU siehst geht es um maximal 20 Schiffe und maximal 40 Laser/Raketen! Das hat der ursprüngliche Ersteller GENAU SO geschrieben.

    Also ist es hier ABSOLUT SINNLOS irgendwie die groß O Notation zu verwenden.


  • Mod

    Andreas XXL schrieb:

    Wie DU siehst geht es um maximal 20 Schiffe und maximal 40 Laser/Raketen! Das hat der ursprüngliche Ersteller GENAU SO geschrieben.

    Also ist es hier ABSOLUT SINNLOS irgendwie die groß O Notation zu verwenden.

    😮 verarscht du uns gerade?



  • rapso schrieb:

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

    Dann ist der Beweis vermutlich falsch. Oder ihr steckt mehr Annahmen rein als hier gegeben sind. Aber lass doch mal sehen. Oder erklär mir, warum das von mir gegebene Beispiel nicht quadratische Zeit braucht.

    Nochmal, falls das nicht so klar rübergekommen ist:

    frame 1:

    x  x  x
    

    frame 2:

    x x   x
    

    frame 3:

    x  x  x
    

    frame 4

    x   x x
    

    frame 5 = frame 1

    Da mußte alle paar Frames Kollisionen prüfen, wenn ich Deine Idee richtig verstanden habe. Also für den mittleren mit allen Objekten.

    Von diesen 3er-Pärchen setze ich nun n Stück ab. Dann muss für 1/3 der Objekte alle paar Frames alle Objekte durchgeprüft werden. Macht 1/3*n^2 Laufzeit alle paar Frames. Das ergibt insgesamt quadratische Laufzeit, da "alle paar Frames" hier eine konstante Anzahl Frames ist. Daher greift auch kein Amortisierungsargument.

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

    Moment mal, wir reden hier doch von dieser halbe distanz-heuristik oder? Dass das einsortieren in ein grid oder ähnliches die Komplexität will ich ja garnicht bezweifeln.

    @AndreasXXL: Und weil mein Speicher nur ne feste Größe hat kann ich ja garkeine größeren Probleme unterbringen. Deswegen geht alles in O(1).



  • hustbaer schrieb:

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

    Ich finde die Diskussion aus einem anderen Grund unsinnig. Beruehren sich alle n Objekte untereinander, dann dauert bereits die Ausgabe aller Kollisionen O(n^2). Beweist man nun also, das ein Algo schneller ist, beweist man gleichzeitig seine Fehlerhaftigkeit, da offensichtlich einige Kollisionen nicht ausgegeben werden. f'`8k

    Gruß, TGGC (\-/ has leading)



  • TGGC schrieb:

    hustbaer schrieb:

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

    Ich finde die Diskussion aus einem anderen Grund unsinnig. Beruehren sich alle n Objekte untereinander, dann dauert bereits die Ausgabe aller Kollisionen O(n^2). Beweist man nun also, das ein Algo schneller ist, beweist man gleichzeitig seine Fehlerhaftigkeit, da offensichtlich einige Kollisionen nicht ausgegeben werden. f'`8k

    Da hast Du mal recht. Man kann aber in solchen Fällen verfeinerte Analysen machen und den reporting-Aufwand getrennt rechnen. Für n Strecken kann man beispielsweise in O(k + n log n) Zeit alle Schnittpunkte berechnen. Dabei bezeichnet k die Anzahl der Schnittpunkte. Gibt es also nur wenige Schnittpunkte, dann ist der Algorithmus schneller.



  • Andreas XXL schrieb:

    Evolver schrieb:

    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?

    Wie DU siehst geht es um maximal 20 Schiffe und maximal 40 Laser/Raketen! Das hat der ursprüngliche Ersteller GENAU SO geschrieben.

    Also ist es hier ABSOLUT SINNLOS irgendwie die groß O Notation zu verwenden.

    Sinnlos ist es, wenn n == 1, 2 oder 3 ist und nicht bei 20-40. Wieso ist die O-Notation sinnlos, nur weil wir n kennen????


  • Mod

    Jester schrieb:

    Oder erklär mir, warum das von mir gegebene Beispiel nicht quadratische Zeit braucht.

    bevor ich mir die muehe mache, eklaere mir weshalb ein binaerbaum O(log n) bei der suche hat, wenn das bei meinem beispiel garnicht stimmt:

    std::map<int,int> bla;
    bla[0]=1;
    bla[17]=1;
    

    Moment mal, wir reden hier doch von dieser halbe distanz-heuristik oder? Dass das einsortieren in ein grid oder ähnliches die Komplexität will ich ja garnicht bezweifeln.

    wir reden hier ueber die nutzung von statistik zur bestimmung der laufzeit, was auf unsere beiden wort-case beispiele wohl nicht zutrifft, aber irgendwie willst/kannst du das nicht verstehen, weshalb ich das beispiel eines binearbaumes die ganze zeit mit angebe.



  • rapso schrieb:

    Jester schrieb:

    Oder erklär mir, warum das von mir gegebene Beispiel nicht quadratische Zeit braucht.

    bevor ich mir die muehe mache, eklaere mir weshalb ein binaerbaum O(log n) bei der suche hat, wenn das bei meinem beispiel garnicht stimmt:

    std::map<int,int> bla;
    bla[0]=1;
    bla[17]=1;
    

    huh? Das hat doch O(log n) Zugriffszeit?

    Moment mal, wir reden hier doch von dieser halbe distanz-heuristik oder? Dass das einsortieren in ein grid oder ähnliches die Komplexität will ich ja garnicht bezweifeln.

    wir reden hier ueber die nutzung von statistik zur bestimmung der laufzeit, was auf unsere beiden wort-case beispiele wohl nicht zutrifft, aber irgendwie willst/kannst du das nicht verstehen, weshalb ich das beispiel eines binearbaumes die ganze zeit mit angebe.[/quote]

    Also möchtest Du sagen, dass es in durchschnittlichen Szenen nur lineare Zeit braucht? Dann sag das doch. Die Aussage "das hat Laufzeit O(n)" ist jedenfalls so wie si weiter oben im Thread steht falsch. Beweise (Gegenbeispiele) warum das nicht in jeder Szene so ist gibt's ja nun schon mindestens zwei. Da hilft's auch nix wenn Du mich jetzt beschimpfst.


  • Mod

    Jester schrieb:

    std::map<int,int> bla;
    bla[0]=1;
    bla[17]=1;
    

    huh? Das hat doch O(log n) Zugriffszeit?[/quote]
    suchen auf dieser map dauert 0.5n (falls beide werte gleich oft gesucht werden) -> O(n)

    Also möchtest Du sagen, dass es in durchschnittlichen Szenen nur lineare Zeit braucht? Dann sag das doch. Die Aussage "das hat Laufzeit O(n)" ist jedenfalls so wie si weiter oben im Thread steht falsch. Beweise (Gegenbeispiele) warum das nicht in jeder Szene so ist gibt's ja nun schon mindestens zwei. Da hilft's auch nix wenn Du mich jetzt beschimpfst.

    dann ist ein Binearbaum in durchschnittlichen scenarien beim suchen O(log n) aber die aussage "das laufzeitverhalten eines (balanzierten) Binaerbaumes ist O(Log n)" ist falsch?

    eklaere mir bitte den unterschied.



  • Nein, da sind beide Aussagen richtig. Wenn der Baum balanciert ist haste immer O(log n). Wenn Du sagst ein bestimmte Verfahren hat O(n) Laufzeit, dann bedeutet das, es braucht immer Linearzeit, egal welche Eingabe. Wenn es jetzt ungünstige Eingaben gibt, die diese Grenze sprengen, dann ist es nicht in O(n).

    Zu dem beispiel mit der map sage ich nur: O(...). Es gibt zwei Elemente, also haste konstante Zugriffszeit. Und konstante Zeit ist insbesondere in O(log n) Zeit. Also prima.


Anmelden zum Antworten