Kollisionserkennung



  • Also ich habe mal eine Frage, die nicht direkt etwas mit Spieleprogrammierung zu tun hat, aber im entfernten Sinne doch:
    Ich habe ein Programm, indem eine Kollisionerkennung implementiert werden muss und die Frage ist jetzt, wie man das optimal macht.
    Im Moment mache ich es so, dass ich ein Objekt Bewege und nach jeder Bewegung für jedes andere Objekt kontrolliere, ob die beiden kollidiert sind. Da ich aber mitunter über tausend Objekte habe, habe ich mit dieser Methode eine sehr schlechte Laufzeit. Das Objekt, das bewegt wird, wird über einen festgelegten Vektor immer weiter bewegt.

    Hat eine von euch eine Idee, wie man das omptimieren kann?

    Vielen Dank schonmal

    Felix



  • 2D: Quadtree
    3D: Octree



  • Hi,

    wie Sgt. Nukem schon sagte ist eine gute Optimierung erstmal Bäume einsetzen (Ja ich schäme mich, aber ich bin mit ihm einer Meinung :D).

    Diese "Bäume" unterteilen Dein Modell in kleine Häppchen.

    Quadtree
    Ein Quadtree schnapp sich Deine Ansammlung und teilt sie in 2 Dimensionen auf.

    Am besten ein kleines Beispiel:

    +-------------------------------------> X-Achse
     |  
     |   +---------------+---------------+
     |   |               |       |       |
     |   |               |       |       |
     |   |               |       |       |
     |   |               |       |_______|
     |   |               |       |       |
     |   |               |       |       |
     |   |               |       |       |
     |   |               |       |       |
     |   +---------------+-------+-------+
     |   |       |       |       |       |
     |   |       |       |       |       |
     |   |       |       |       |       |
     |   |_______|_______|_______|_______|
     |   |       |   |   |       |       |
     |   |       |___|___|       |       |
     |   |       |   |   |       |       |
     |   |       |   |   |       |       |
     |   +---------------+---------------+
     |  
    \|/  Y-Achse
    

    Dein Modell wird in kleine Rechtecke aufgeteilt, erst wird das ganze mit einem Rechteck "umschlungen" und dann je nach Einstellung (z.B. eine Bestimmte Anzahl Punkte soll in einem Rechteck sein) wird das Model weiter unterteilt, usw. usw. usw. bis jedes Leaf (Blatt) den Einstellungen entsprechen.

    Diese Technik wird sehr gerne bei Spielen mit Terrain (FarCry usw.) benutzt oder auch in Rollenspielen wie z.B. Sacred oder Diablo.

    Octree
    Der "Bruder" dieses Baumes ist der Octree, er unterteilt Dein Objekt in 3 Dimensionen (X,Y und Z) und ist ansonsten fast Äquivalent zu dem Quadtree. Hier sind es keine Rechtecke mehr sondern Würfel.

    Dieser Baum wird sehr gerne für Kollisionsabfragen angewendet, für Terrains oder kleine 3D Shooter.

    BSP-Baum
    Bekannt aus Doom und Quake ist der BSP Baum, früher zum Rendern benutzt um alles schön von hinten nach vorne zu sortieren, heute mehr im Einsatz für Kollisionsabfragen.

    Der BSP Baum unterteilt alles in feine Leafs auf bis sie Konvex sind. Ist jedoch ein Node noch nicht Konvex sondern konkav bzw. komplex wird er gesplittet.

    Nehmen wir an wir benutzen einen BSP Baum um jedes Dreieck aufzuteilen, dann sähe das so aus:

    Root-Node
    
                    -------
                    | /| /
                    |/ |/
                    ----
    
                      |
                      |
                     \|/
                 Splittung 1
                    /   \
                   /     \
                  /       \
                |/_       _\|
    
             Node A        Leaf A
    
             ----           ----  
             | /|           | /
             |/ |           |/
             ----           -
    
              |
              |
             \|/
          Splittung 2
            /   \
           /     \
          /       \
        |/_       _\|         
    
        Leaf B     Leaf C
    
        ----         -
        | /         /|
        |/         / | 
        -         ----
    

    Immer wird weiter gesplittet bis nur noch Leafs da sind. Auch hier kommt es wieder auf die Anforderungen an was der Baum erreichen soll.

    Ob er nun in Konvexe stückchen aufteilt oder in Dreiecke, das ist alles Einstellungssache.

    Diese 3 Baumarten werden Rekursiv erstellt.

    Welchen Baum man nun benutzt liegt bei jedem selber und es kommt auf die Anwendung an, ein Quadtree eignet sich nicht sonderlich gut ein 3D Modell zu unterteilen und ein Octree ist nicht gut um ein 2D Terrain aus einem 2D Spiel zu unterteilen. Es kommt alles auf den Anwendungsbereich an.

    Zur Kollisionsabfrage: Man sagt in 3D Spielen ist der Spitzenreiter für Kollisionsabfragen der BSP Baum, aber das muss jeder für sich selber heraus finden.

    - Patrick, der hofft, dass das evtl. noch andere interessiert hat.



  • Erstmal Danke, ich habe nur noch ein paar Nachfragen:

    1. Im Moment mache ich die Kollisionserkennung Pixelgenau. Soll ich dann den Quadtree so genau machen, dass das auch auf einen Pixel genau ist?

    2. Wenn ich den Quadtree habe, gucke ich also sozusagen einfach nur in dem Quadtree nach, ob es zu einer Kollision gekommen ist, anstatt für alle Objekte zu überprüfen, ob es eine Kollision gab, oder?

    3. Wenn ich den Quadtree sowieso Pixelgenau mache, kann ich doch auch einfach ein Array benutzen, in dem alle Pixel abgespeicher werden, oder?

    Felix

    P.S: Alles in 2D



  • Phoemuex schrieb:

    Erstmal Danke, ich habe nur noch ein paar Nachfragen:

    1. Im Moment mache ich die Kollisionserkennung Pixelgenau. Soll ich dann den Quadtree so genau machen, dass das auch auf einen Pixel genau ist?

    Nein, das wäre total ineffizient.

    Zudem ist pixelgenaue Kollision meistens für'n &§&§§@ !

    Phoemuex schrieb:

    1. Wenn ich den Quadtree habe, gucke ich also sozusagen einfach nur in dem Quadtree nach, ob es zu einer Kollision gekommen ist, anstatt für alle Objekte zu überprüfen, ob es eine Kollision gab, oder?

    Du überprüfst Kollisionen nur mit Objekten, die im gleichen Knoten des Baumes verankert sind.
    Sonderfall, falls Objekte zwischen zwei Frames die Knoten wechseln.



  • Phoemuex

    Zu 1.: da muss ich Sgt. Nukem wieder zustimmen (Oh das ist ein schlechtes Omen :D), würdest du es so 30x30 pixel belassen wäre es evtl. noch ok, aber so? Speicherverbrauch und total ineffektiv.

    Und wie Sgt. Nukem schon sagte (Oh Gott ein 3. mal :D) ist Pixelgenaue die Kollisionsabfrage sowieso nicht besonders gut. Bei kleinen Arcarde spielen wie ein R-Type clone gehts noch aber wenns mehr wird... Sayônara Speed.

    Zu 2.: Siehe Sgt. Nukem



  • Puh, bei so vielen Objekten pixelgenaue Kollision? Wieviel FPS hast du, 0,1? 😉
    Wenn es die Objekte erlauben, vereinfach sie einfach zu Vierecken, und teste, ob die Vierecke sich überlappen. Wenn ja, kannst du danach notfalls noch eine pixelgenaue Kollision durchführen.

    Gruß,
    🙂 Domme



  • Also erstmal zu Dark: Ich habe noch ziemlich viele Frames (wenn ich sie anzeigen lassen würde), weil ich ja auch keinerlei Grafik habe, sondern nur die Dinger durch die Gegend schiebe, sogar ohne sie zu sehen. 😃

    Und jetzt würde mich nur mal interessieren, wie so ein Quadtree nachher aufgebaut ist, weil ich mir das trotzdem nicht genau vorstellen kann. Speichert man in den Ästen dann nur die Pixel oder die Objekte oder was?? Könnte vielleicht jemand mal Pseudo-Code posten?

    Aber ansonsten ist das genau das was ich suche (glaube ich jedenfalls). Also schonmal vielen Dank soweit.

    Felix

    EDIT: Ac ja, was haben eigentlich Sgt. Nukem und nix da gegeneinander??

    Ja ich schäme mich, aber ich bin mit ihm einer Meinung



  • Phoemuex schrieb:

    Speichert man in den Ästen dann nur die Pixel oder die Objekte oder was??

    Die Objekte.

    Deine "pixelgenaue Kollision" kannst Du weiterhin benutzen, wenn Du willst.
    Du mußt nur weniger als "n * (n-1)" Kollisionen gegeneinander prüfen. 👍



  • nach was sortiert man die objekte in den baum ein? nach der position der oberen linken ecke? nach der mitte der boundingbox? oder nach was ganz anderen?
    ich habs nicht ganz verstanden 😃
    geloescht



  • Nur mal so als blöde Frage... deine Aufgabe stammt nicht zufällig aus der 1. Aufgabe des BWINF? 😃



  • ZzetT schrieb:

    Nur mal so als blöde Frage... deine Aufgabe stammt nicht zufällig aus der 1. Aufgabe des BWINF? 😃

    wieso sollte sie? das geht hier doch in eine völlig andre richtung Oo


Log in to reply