4. Kollisionserkennung

Kollisionserkennung

  • A

    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.

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

    0
  • J

    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).

    0

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

    0
  • J

    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.

    0
  • ?

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

    0
  • R
    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.

    0
  • J

    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.

    0
  • R
    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.

    0
  • J

    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.

    0
  • R
    Mod

    Jester schrieb:

    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.

    eine map aus 2 elementen ist equivalent zu einer liste und hat eine laufzeit von O(n) beim suchen.

    0
  • J

    Die Liste hat bei 2 Elementen übrigens auch konstante Zeit. Sorry, aber das wird jetzt langsam lächerlich. Wenn Du von O-Kalkül und Komplexität nicht so viel weißt, dann steh halt dazu. Aber diese Argumente sind nun wirklich dünn.

    0
  • R
    Mod

    Jester schrieb:

    Die Liste hat bei 2 Elementen übrigens auch konstante Zeit. Sorry, aber das wird jetzt langsam lächerlich. Wenn Du von O-Kalkül und Komplexität nicht so viel weißt, dann steh halt dazu. Aber diese Argumente sind nun wirklich dünn.

    schoen dass nun du beleidigend werden kannst, wo du mich dazu auffordest.
    mir ist das auch zu dumm jetzt und da der frager wohl seine antwort hat -> closed.

    0
Anmelden zum Antworten