Einsatz von verketteten Listen bei der Kollisionserkennung

Im letzten Artikel haben wir die Vorteile der Sektorisierung im Rahmen der Kollisionserkennung besprochen. Heute befassen wir uns mit dem Handling der in den Sektoren befindlichen Kollisionsobjekte und werden die Frage beantworten, wie man schnell und unkompliziert Zugriff auf diese erhält, um sie paarweise auf eine mögliche Kollision hin testen zu können.
Zur Lösung des Problems bieten sich unterschiedliche Vorgehensweisen an. Der in der nachfolgenden Abbildung skizzierte Ansatz behandelt den Einsatz von verketteten Listen. Diese Listen lassen sich problemlos in Echtzeit generieren. Zu diesem Zweck muss zunächst ermittelt werden, in welchem Sektor sich ein Kollisionsobjekt aktuell befindet. Ist der Sektor gefunden, wird die Liste mit den sich ebenfalls im Sektor befindlichen Kollisionsobjekten einfach um ein zusätzliches Element verlängert.

In unseren Programmbeispielen wird jedem Spiele-Objekt (Asteroid, Raumschiff, Projektil, usw.) eine Instanz der CCollisionObject-Klasse zugeordnet. Über den Zeiger pNextCollisionObject sind die einzelnen Kollisionsobjekte in der verketteten Liste miteinander verbunden.

class CCollisionObject
{
public:

    long ObjectType; // Art des Objekts
    long ObjectID;   // ID des Objekts

    CCollisionObject* pNextCollisionObject;

    CCollisionObject();
    ~CCollisionObject();

    void Reset(void);
    void Set_Type_And_ID(long Type, long ID);

};

Bevor ein Kollisionsobjekt mit einer verketteten Liste verknüpft werden kann, müssen zunächst die Listen, die im Rahmen eines früheren Prüflaufs generiert wurden, gelöscht werden. Konkret bedeutet dies, dass die Verbindungen zwischen den einzelnen Listen-Objekten (Knoten) getrennt werden müssen. Zu diesem Zweck muss der pNextCollisionObject-Zeiger lediglich auf NULL gesetzt werden:

void CCollisionObject::Reset(void)
{
pNextCollisionObject = NULL;
}

Mithilfe der Methode Set_Type_And_ID() erfolgt die Zuordnung zwischen Kollisionsobjekt und Spiele-Objekt. Die Variable ObjectType dient zum Speichern des Objekt-Typs (bsp. Asteroid) und die Variable ObjectID zur Identifizierung des Spiele-Objekts in einem Array.

void CCollisionObject::Set_Type_And_ID(long Type, long ID)
{
ObjectType = Type;
ObjectID = ID;
}

Am Beispiel des Camera Aligned Collision Grid aus dem vorangegangenen Artikel soll nachfolgend die Verwendung von verketteten Listen konkretisiert werden. Ausgangspunkt unserer Betrachtungen ist wiederum die CCameraAlignedCollisionGrid-Klasse, die zusätzlich zu ihren bisherigen Aufgaben nun auch für das Handling der Kollisionslisten zuständig sein wird. Verantwortlich hierfür sind die beiden neuen Methoden Reset_All_CollisionLists() sowie Update_CollisionList().

class CCameraAlignedCollisionGrid
{
public:

    // Das Grid umfasst insgesamt 8 Sektoren!

    long NumObjectsInsideCollisionArea[8];

    // Um möglichen Problemen bei der Kollisionserkennung an den
    // Sektorengrenzen zuvorzukommen, werden die Sektorengrenzen bei jedem
    // Test etwas verschoben. Die nachfolgende Variable dient zum Speichern
    // des Verschiebungsbetrags:
    float GridVarianceAmount;

    float ActualGridVarianceXDirection;
    float ActualGridVarianceYDirection;
    float ActualGridVarianceZDirection;

    long NumCollisionAreas;

    // Anfangs (Head) und End (Tail) Knoten der Kollisionslisten.
    // Pro Sektor wird eine Liste erstellt.
    CCollisionObject* pCollisionObjectHead[8];
    CCollisionObject* pCollisionObjectTail[8];

  CCameraAlignedCollisionGrid();
    ~CCameraAlignedCollisionGrid();

    void Set_GridVarianceAmount(float amount = 10.0f);

    void Reset_All_CollisionAreas(void);
    void Reset_All_CollisionLists(void);

    void Update_CollisionList(CCollisionObject* pCollisionObject,
                             long AreaID);
};

Bevor eine neue Kollisionsliste erstellt werden kann, müssen die bestehenden Listen (die im vorangegangenen Prüflauf verwendet wurden) zunächst gelöscht werden. Über den ersten Schritt – die Trennung der Verbindungen zwischen den einzelnen CCollisionObject-Instanzen – haben wir bereits gesprochen (siehe CCollisionObject::Reset()). Der zweite Schritt besteht darin, die Zeiger auf die Anfangs- und Endknoten der Listen auf NULL zu setzen:

void CCameraAlignedCollisionGrid::Reset_All_CollisionLists(void)
{
    for(long i = 0; i < NumCollisionAreas; i++)
    {
        pCollisionObjectHead[i] = NULL;
        pCollisionObjectTail[i] = NULL;
    }
}

Innerhalb der Update_CollisionList()-Methode werden die einzelnen CCollisionObject-Instanzen an das Ende einer sich im Aufbau befindlichen Liste angehängt. Verantworlich für die Zuordnung zu einer Liste ist der Parameter AreaID.

Beim Aufbau der Kollisionslisten sind die folgenden drei Fälle zu berücksichtigen:

Aufnahme der ersten CCollisionObject-Instanz in die Liste
Aufnahme der zweiten CCollisionObject-Instanz in die Liste
Anhängen weiterer CCollisionObject-Instanzen an das Listenende

void CCameraAlignedCollisionGrid::Update_CollisionList(
     CCollisionObject* pCollisionObject, long AreaID)
{
    NumObjectsInsideCollisionArea[AreaID]++;

    // erstes Kollisionsobjekt in die Liste eintragen:
    if(pCollisionObjectHead[AreaID] == NULL)
    {
        pCollisionObjectHead[AreaID] = pCollisionObject;
        pCollisionObjectTail[AreaID] = pCollisionObject;
    }
    // zweites Kollisionsobjekt in die Liste eintragen:
    else if(pCollisionObjectHead[AreaID] != NULL &&
           pCollisionObjectHead[AreaID] == pCollisionObjectTail[AreaID])
    {
     pCollisionObjectHead[AreaID]->pNextCollisionObject = pCollisionObject;
     pCollisionObjectTail[AreaID] = pCollisionObject;
    }
    else // weitere Kollisionsobjekte in die Liste eintragen:
    {
     pCollisionObjectTail[AreaID]->pNextCollisionObject = pCollisionObject;
     pCollisionObjectTail[AreaID] = pCollisionObject;
    }
}

Wie bereits im vorherigen Artikel beschrieben, erzeugen wir für jedes Spiele-Objekt wiederum eine Instanz der CCameraAlignedCollisionArea-Klasse. Primär verantwortlich ist diese Klasse nun jedoch für das Handling der einzelnen CollisionObject-Instanzen.

class CCameraAlignedCollisionArea
{
public:

    CCameraAlignedCollisionGrid* pCameraAlignedCollisionGrid;
    long AreaID;

    CCollisionObject* CollisionObject;

    CCameraAlignedCollisionArea();
    ~CCameraAlignedCollisionArea();

    void Set_CollisionGrid(
         CCameraAlignedCollisionGrid* pUsedCameraAlignedCollisionGrid);

    void Find_ActualCollisionArea(D3DXVECTOR3* pCameraSpacePosition);

    void Find_ActualCollisionArea_And_Update_CollisionList(
         D3DXVECTOR3* pCameraSpacePosition);

    void Reset_CollisionObject(void);
};

Die Reset_CollisionObject()-Methode ist dafür zuständig, die CollisionObject-Instanz aus einer bestehenden Kollisionsliste zu entfernen:

void CCameraAlignedCollisionArea::Reset_CollisionObject(void)
{
CollisionObject->Reset();
}

Auf Basis der in einem CCameraAlignedCollisionGrid-Objekt festgelegten Sektorengrenzen lässt sich mithilfe der Find_ActualCollisionArea_And_Update_CollisionList()-Methode derjenige Kollisionssektor ermitteln, in dem sich das betreffende Kollisionsobjekt momentan befindet. Darüber hinaus ist diese Methode auch dafür verantwortlich, dass die CollisionObject-Instanz der korrekten Kollisionsliste zugeordnet wird:

void CCameraAlignedCollisionArea::
     Find_ActualCollisionArea_And_Update_CollisionList(
     D3DXVECTOR3* pCameraSpacePosition)
{
    if(pCameraAlignedCollisionGrid == NULL)
        return;

    if(pCameraSpacePosition->x >
      pCameraAlignedCollisionGrid->ActualGridVarianceXDirection)
    {
        if(pCameraSpacePosition->z >
          pCameraAlignedCollisionGrid->ActualGridVarianceZDirection)
        {
            if(pCameraSpacePosition->y >
              pCameraAlignedCollisionGrid->ActualGridVarianceYDirection)
            {
                AreaID = 0;

                pCameraAlignedCollisionGrid->Update_CollisionList(
                CollisionObject, AreaID);

                return;
            }
            else // if(pCameraSpacePosition->y <=
            // pCameraAlignedCollisionGrid->ActualGridVarianceYDirection)
            {
                AreaID = 1;

                pCameraAlignedCollisionGrid->Update_CollisionList(
                CollisionObject, AreaID);

               return;
            }
        }
        else // if(pCameraSpacePosition->z <=
        // pCameraAlignedCollisionGrid->ActualGridVarianceZDirection)
        {
            if(pCameraSpacePosition->y >
              pCameraAlignedCollisionGrid->ActualGridVarianceYDirection)
            {
                AreaID = 2;

                pCameraAlignedCollisionGrid->Update_CollisionList(
                CollisionObject, AreaID);

                return;
            }
            else // if(pCameraSpacePosition->y <=
            // pCameraAlignedCollisionGrid->ActualGridVarianceYDirection)
            {
                AreaID = 3;

                pCameraAlignedCollisionGrid->Update_CollisionList(
                CollisionObject, AreaID);

                return;
          }
        }
    }
    else // if(pCameraSpacePosition->x <=
    // pCameraAlignedCollisionGrid->ActualGridVarianceXDirection)
    {
        if(pCameraSpacePosition->z >
           pCameraAlignedCollisionGrid->ActualGridVarianceZDirection)
       {
            if(pCameraSpacePosition->y >
               pCameraAlignedCollisionGrid->ActualGridVarianceYDirection)
            {
                AreaID = 4;

                pCameraAlignedCollisionGrid->Update_CollisionList(
                CollisionObject, AreaID);

                return;
            }
            else //if(pCameraSpacePosition->y <=
            // pCameraAlignedCollisionGrid->ActualGridVarianceYDirection)
            {
                AreaID = 5;

                pCameraAlignedCollisionGrid->Update_CollisionList(
                CollisionObject, AreaID);

                return;
            }
        }
        else //if(pCameraSpacePosition->z <=
        // pCameraAlignedCollisionGrid->ActualGridVarianceZDirection)
        {
            if(pCameraSpacePosition->y >
              pCameraAlignedCollisionGrid->ActualGridVarianceYDirection)
            {
                AreaID = 6;

                pCameraAlignedCollisionGrid->Update_CollisionList(
                CollisionObject, AreaID);

                return;
            }
            else //if(pCameraSpacePosition->y <=
            // pCameraAlignedCollisionGrid->ActualGridVarianceYDirection)
            {
                AreaID = 7;

                pCameraAlignedCollisionGrid->Update_CollisionList(
                CollisionObject, AreaID);

                return;
            }
        }
    }
}

Am Beispiel eines Asteroidenfeldes soll nachfolgend die Verwendung der Klassen CCameraAlignedCollisionGrid sowie CCameraAlignedCollisionArea verdeutlicht werden. Im Rahmen der Kollisionsberechnungen sind hierbei die folgenden Schritte erforderlich:

Kollisionsobjekte aus bestehenden Kollisionslisten entfernen
Anzahl der Kollisionsobjekte in allen Sektoren auf Null setzen und die Sektorengrenzen nach dem Zufallsprinzip variieren
Anfangs- und Endknoten der nicht mehr benötigten Kollisionslisten auf NULL setzen
Den momentanen Kollisionssektor der einzelnen Objekte ermitteln und die Kollisionslisten updaten
Nacheinander alle Kollisionssektoren durchgehen und diejenigen Sektoren überspringen, in denen sich weniger als 2 Kollisionsobjekte befinden, da dort keine Kollision möglich ist
Kollisionstests für alle Asteroiden durchführen, die sich im selben Sektor befinden

// Kollisionsobjekte aus bestehenden Kollisionslisten entfernen:
for(i = 0; i < NumAsteroids; i++)
    Asteroid[i].CameraAlignedCollisionArea->Reset_CollisionObject();

// Anzahl der Kollisionsobjekte in allen Sektoren auf Null setzen und die // Sektorengrenzen nach dem Zufallsprinzip variieren:
CameraAlignedCollisionGrid.Reset_All_CollisionAreas();

// Anfangs- und Endknoten der nicht mehr benötigten Kollisionslisten auf
// NULL setzen:
CameraAlignedCollisionGrid.Reset_All_CollisionLists();

// Den momentanen Kollisionssektor der einzelnen Objekte ermitteln und die
// Kollisionslisten updaten:
for(i = 0; i < NumAsteroids; i++)
    Asteroid[i].CameraAlignedCollisionArea->
    Find_ActualCollisionArea_And_Update_CollisionList(
    &Asteroid[i].CameraSpacePosition);

long Asteroid_ID1, Asteroid_ID2;

CCollisionObject* pCollisionObject_Asteroid1 = NULL;
CCollisionObject* pCollisionObject_Asteroid2 = NULL;

// Nacheinander alle Kollisionssektoren durchgehen:
for(long k = 0; k < CameraAlignedCollisionGrid.NumCollisionAreas; k++)
{
// wenn sich weniger als 2 Objekte im Gebiet befinden, dann ist eine
// Kolllision ausgeschlossen
if(CameraAlignedCollisionGrid.NumObjectsInsideCollisionArea[k] < 2)
    continue;

// Adressen der ersten beiden Kollisionsobjekte aus der Liste auslesen:
pCollisionObject_Asteroid1 = CameraAlignedCollisionGrid.
                             pCollisionObjectHead[k];

pCollisionObject_Asteroid2 = CameraAlignedCollisionGrid.
                             pCollisionObjectHead[k]->pNextCollisionObject;

// Alle Kollisionsobjekte in der Liste paarweise auf eine mögliche
// Kollision hin testen:
for(i = 0; i < CameraAlignedCollisionGrid.NumObjectsInsideCollisionArea[k]; i++)
{
// Index des ersten Kollisionspartners ermitteln:
Asteroid_ID1 = pCollisionObject_Asteroid1->ObjectID;

for(j=i+1; j < CameraAlignedCollisionGrid.NumObjectsInsideCollisionArea[k]; j++)
{
    // Index des zweiten Kollisionspartners ermitteln:
    Asteroid_ID2 = pCollisionObject_Asteroid2->ObjectID;

    // Adresse des nächsten Kollisionsobjekts aus der Liste auslesen:
    if(pCollisionObject_Asteroid2->pNextCollisionObject != NULL)
        pCollisionObject_Asteroid2 = pCollisionObject_Asteroid2->
                                     pNextCollisionObject;

    // Hier werden die Kollisionstests durchgeführt

}

// Adressen der nächsten Kollisionsobjekte aus der Liste auslesen:

if(pCollisionObject_Asteroid1->pNextCollisionObject != NULL)
    pCollisionObject_Asteroid1 = pCollisionObject_Asteroid1->
                                 pNextCollisionObject;

if(pCollisionObject_Asteroid1->pNextCollisionObject != NULL)
    pCollisionObject_Asteroid2 = pCollisionObject_Asteroid1->
                                 pNextCollisionObject;
}
}

3D-Spieleentwicklung - Vulkan - OpenGL - GLSL - OpenCL - OpenAL

Seiten

Einsatz von verketteten Listen bei der Kollisionserkennung