Kollisionserkennung



  • Ich hab mir vor einiger Zeit einen kleinen Algorithmus zur Kollisionserkennung überlegt. Die Objekte werden in ein Array "gerendert". Überrall, wo sich das Objekt befindet, wird ein Pointer auf das Objekt in das Array geschrieben. Bei jedem Schreibvorgang muss überprüft werden, ob schon ein Pointer in dem Array ist. Wenn schon ein Pointer drin steht, hat man eine Kollision zwischen dem Objekt auf das der Pointer in dem Array zeigt und dem Objekt, das gerade gerendert wird.

    Ich hab, um zu beweisen, dass es funtioniert eine Test-Implementierung für die Zweidimensionale gemacht:

    main.cpp:

    #include <iostream>
    
    #include "object.hpp"
    
    using namespace std;
    
    int main()
    {
        const unsigned short int x = 800;                            /*Größe des Arrays in x-Richtung*/
        const unsigned short int y = 600;                            /*Größe des Arrays in y-Richtung*/
    
        rectangle ***pointer = new rectangle **[x];	                 /*Pointer Array erstellen*/
        for(unsigned int i = 0; i < x; ++i)
        {
            pointer[i] = new rectangle *[y];
        }
    
        for(unsigned int i = 0; i < x; i++)	                        /*Initialisierung des Pointer-Arrays*/
        {                                                            /*mit 0-Pointern*/
            for(unsigned int b = 0; b < y; b++)
            {
                pointer[i][b] = 0;
            }
        }
    
        rectangle *r1 = new rectangle("Miau", 0, 0, 10, 10);        /*Render*/
        r1->render(pointer);
        rectangle *r2 = new rectangle("Katze", 9, 9, 10 , 10);
        r2->render(pointer);
        rectangle *r3 = new rectangle("Nuss", 18, 9, 10 , 10);
        r3->render(pointer);		
    
        return 0;
    }
    

    object.hpp:

    #ifndef __OBJECT__HPP__
    #define __OBJECT__HPP__
    
    #include <iostream>
    #include <string>
    
    using namespace std;
    
    class rectangle
    {
        public:
    
        int px;
        int py;
        int b;
        int h;
        string name;
    
        rectangle(const string nname, const int nx, const int ny, const int nb, const int nh)
        {
            px = nx;
            py = ny;
            b = nb;
            h = nh;
            name = nname;
        }
    
        void render(rectangle ***pointer)
        {
            for(unsigned int i = 0; i < b; i++)			
            {
                for(unsigned int b = 0; b < h; b++)
                {
                    if(pointer[i+px][b+py] == 0)
                    {
                        pointer[i+px][b+py] = this;
                    }
                    else
                    {
                        cout << "Collision " << name << " " << pointer[i+px][b+py]->name << endl;					
                    }
                }
            }
        }
    };
    


  • Klar funktioniert das (grundsätzlich, deinen Code hab' ich nicht ausprobiert, ist aber auch nicht so schwer zu implementieren).
    Die Frage ist nur wofür man es braucht.
    "Ungenaue" Kollisionserkennung, die dafür mit besser abschätzbaren Formen wie Rechtecken oder Kreisen arbeitet ist meist besser.
    Die allermeisten 2D Games die ich kenne machen das auch so.



  • Hm - das wär mir zu aufwendig und vorallem bei komplizierteren Formen (Rechteck ist ja ohnehin trivial) zu kompliziert.

    Um pixelgenaue Kollisionen bei 2D zu erkennen reicht es den stencil-buffer in Zusammenhang mit occlusion queries zu verwenden.



  • Den Stencil-Buffer zu verwenden klingt für mich aber auch einigermassen kompliziert, wenn man eine halbwegs generische Lösung basteln will.

    Auch stelle ich es mir schwierig vor z.B. bei einer erkannten Kollision das Objekt noch zu bewegen (z.B. zurücksetzen so dass es nicht mehr kollidiert) bevor das nächste Frame gerendert wird.
    Ebenso das Entkoppeln von Grafik und Physik-Frames...
    Bzw. das Erkennen von Kollisionen von Objekten die gerade nicht sichtbar sind (brauch man auch manchmal).

    Wenn man mit Rechtecken und/oder Kreisen nicht auskommt gibt's immer noch Libraries wie Box2D die man einbinden kann, ohne dass man viel selber Programmieren muss.

    mMn. ist Pixelgenaue Kollisionsabfrage die auf den sichtbaren Grafiken basiert eine "Billiglösung", die schlecht (nervig) für den Spieler ist. Und Pixelgenaue Kollisionsabfrage die nicht auf den sichtbaren Grafiken basiert, sondern auf eigenen Kollisionsmasken-Bitmaps halte ich für unnötig.


Anmelden zum Antworten