Sektorisierung der Spielewelt: Camera Aligned Collision Grid (an der Kamera ausgerichtete Kollisionsbereiche)

Mit zunehmender Anzahl der Spieleobjekte wirkt sich die für die Durchführung der Kollisionstests benötigte Rechenzeit zunehmend negativ auf die Performance eines Spiels aus. Ohne weitere Optimierungen müssten alle Objekte paarweise auf eine mögliche Kollision hin getestet werden, was die Anzahl der benötigten Prüfläufe schnell in die Höhe treibt:

• 2 Objekte: 1 Kollisionstest
• 3 Objekte: 3 Kollisionstests
• 4 Objekte: 6 Kollisionstests
• 16 Objekte: 120 Kollisionstests
• 100 Objekte: 4950 Kollisionstests
• N Objekte: 0.5*N*(N-1) Kollisionstests

Das Ziel aller Optimierungstechniken muss es sein, die Anzahl der zu testenden Objektpaarungen so klein wie möglich zu halten. Eine Möglichkeit, dies zu erreichen, besteht darin, bestimmte Paarungen (Bsp. Waffenprojektil – Waffenprojektil) von vorneherein auszuschließen.
Die mit Abstand wichtigste Technik zur Vermeidung unnötiger Kollisionstests besteht jedoch in der Sektorisierung der Spielewelt. Hierbei wird die Anzahl der möglichen Objektpaarungen dadurch reduziert, dass nur diejenigen Objekte auf eine Kollision hin überprüft werden, die sich im selben Sektor befinden.

Um den Vorteil der Sektorisierung besser verstehen zu können, verteilen wir in einem konkreten Beispiel 16 Objekte paarweise auf 8 Sektoren. Da sich in jedem Sektor nur zwei Objekte befinden, ist pro Sektor nur eine einzige Kollision möglich. Insgesamt reduziert sich damit die Anzahl der durchzuführenden Kollisionsausschluss-Tests (Bsp. ein Bounding-Sphären-Test) von 120 auf lediglich 8.

Nachdem die Vorteile der Sektorisierung auf der Hand liegen, stellt sich nunmehr die wichtige Frage, wie genau die Sektorisierung der Spielewelt eigentlich erfolgen sollte. Unabhängig von der gewählten Technik bietet es sich an, die Spielewelt zunächst in einem ersten Schritt grob zu unterteilen und die Sektorisierung dann schrittweise zu verfeinern.

Im Rahmen dieses Artikels werden wir uns lediglich mit Schritt 1 befassen.

In der nachfolgenden Abbildung ist skizziert, wie sich ausgehend von der Kameraposition die Spielewelt in 8 verschiedene Kollisionsbereiche (Sektoren) unterteilen lässt:

Vor der Durchführung der Kollisionsausschluss-Tests müssen wir zunächst die Anzahl der Kollisionsobjekte in den einzelnen Sektoren des Kollisionsgitters ermitteln. In unseren Programmbeispielen kommt zu diesem Zweck die CCameraAlignedCollisionGrid-Klasse zum Einsatz.

class CCameraAlignedCollisionGrid
{
public:

    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;

    CCameraAlignedCollisionGrid();
    ~CCameraAlignedCollisionGrid();

    void Set_GridVarianceAmount(float amount = 10.0f);
    void Reset_All_CollisionAreas(void);
};

Mögliche Komplikationen bei der Durchführung der Kollisionstests ergeben sich immer dann, wenn sich Kollisionsobjekte an den Sektorengrenzen einander annähern, sich dabei jedoch in unterschiedlichen Sektoren befinden. Da die Kollisionsausschluss-Tests nur für Objekte innerhalb desselben Sektors durchgeführt werden, würden mögliche Kollisionen in diesen speziellen Fällen unentdeckt bleiben. Abhilfe kann jedoch dadurch geschaffen werden, indem man die Sektorengrenzen, wie in der nachfolgenden Funktion gezeigt, vor jedem Testdurchlauf ein wenig variiert:

void CCameraAlignedCollisionGrid::
     Reset_All_CameraAlignedCollisionAreas(void)
{
    NumObjectsInsideCollisionArea[0] = 0;
    NumObjectsInsideCollisionArea[1] = 0;
    NumObjectsInsideCollisionArea[2] = 0;
    NumObjectsInsideCollisionArea[3] = 0;
    NumObjectsInsideCollisionArea[4] = 0;
    NumObjectsInsideCollisionArea[5] = 0;
    NumObjectsInsideCollisionArea[6] = 0;
    NumObjectsInsideCollisionArea[7] = 0;

    // Sektorengrenzen nach dem Zufallsprinzip variieren:

    if(lrnd(1, 3) == 1)
        ActualGridVarianceXDirection = GridVarianceAmount;
    else
        ActualGridVarianceXDirection = -GridVarianceAmount;

    if(lrnd(1, 3) == 1)
        ActualGridVarianceYDirection = GridVarianceAmount;
    else
        ActualGridVarianceYDirection = -GridVarianceAmount;

    if(lrnd(1, 3) == 1)
        ActualGridVarianceZDirection = GridVarianceAmount;
    else
        ActualGridVarianceZDirection = -GridVarianceAmount;
}

Für jedes Kollisionsobjekt muss eine Instanz der CCameraAlignedCollisionArea-Klasse angelegt werden. Auf Basis der in einem CCameraAlignedCollisionGrid-Objekt festgelegten Sektorengrenzen lässt sich mithilfe der Find_ActualCollisionArea()-Methode derjenige Kollisionssektor ermitteln, in dem sich das betreffende Objekt momentan befindet.

class CCameraAlignedCollisionArea
{
public:

    CCameraAlignedCollisionGrid* pCameraAlignedCollisionGrid;
    long AreaID;

    CCameraAlignedCollisionArea();
    ~CCameraAlignedCollisionArea();

    void Set_CollisionGrid(
         CCameraAlignedCollisionGrid* pUsedCameraAlignedCollisionGrid);

    void Find_ActualCollisionArea(D3DXVECTOR3* pCameraSpacePosition);
};

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

    if(pCameraSpacePosition->x >
       pCameraAlignedCollisionGrid->ActualGridVarianceXDirection)
    {
    if(pCameraSpacePosition->z >
       pCameraAlignedCollisionGrid->ActualGridVarianceZDirection)
    {
    if(pCameraSpacePosition->y >
       pCameraAlignedCollisionGrid->ActualGridVarianceYDirection)
    {
        AreaID = 0;
        pCameraAlignedCollisionGrid->NumObjectsInsideCollisionArea[0]++;
        return;
    }
    else //if(pCameraSpacePosition->y <=
              pCameraAlignedCollisionGrid->ActualGridVarianceYDirection)
    {
        AreaID = 1;
        pCameraAlignedCollisionGrid->NumObjectsInsideCollisionArea[1]++;
        return;
    }
    }

    else //if(pCameraSpacePosition->z <=
              pCameraAlignedCollisionGrid->ActualGridVarianceZDirection)
    {
    if(pCameraSpacePosition->y >
       pCameraAlignedCollisionGrid->ActualGridVarianceYDirection)
    {
        AreaID = 2;
        pCameraAlignedCollisionGrid->NumObjectsInsideCollisionArea[2]++;
        return;
    }
    else //if(pCameraSpacePosition->y <=
              pCameraAlignedCollisionGrid->ActualGridVarianceYDirection)
    {
        AreaID = 3;
        pCameraAlignedCollisionGrid->NumObjectsInsideCollisionArea[3]++;
        return;
    }
    }
    }
    else // if(pCameraSpacePosition->x <=
               pCameraAlignedCollisionGrid->ActualGridVarianceXDirection)
    {
    if(pCameraSpacePosition->z >
       pCameraAlignedCollisionGrid->ActualGridVarianceZDirection)
    {
    if(pCameraSpacePosition->y >
       pCameraAlignedCollisionGrid->ActualGridVarianceYDirection)
    {
        AreaID = 4;
        pCameraAlignedCollisionGrid->NumObjectsInsideCollisionArea[4]++;
        return;
    }
    else //if(pCameraSpacePosition->y <=
              pCameraAlignedCollisionGrid->ActualGridVarianceYDirection)
    {
        AreaID = 5;
        pCameraAlignedCollisionGrid->NumObjectsInsideCollisionArea[5]++;
        return;
    }
    }
    else //if(pCameraSpacePosition->z <=
              pCameraAlignedCollisionGrid->ActualGridVarianceZDirection)
    {
    if(pCameraSpacePosition->y >
       pCameraAlignedCollisionGrid->ActualGridVarianceYDirection)
    {
        AreaID = 6;
        pCameraAlignedCollisionGrid->NumObjectsInsideCollisionArea[6]++;
        return;
    }
    else //if(pCameraSpacePosition->y <=
              pCameraAlignedCollisionGrid->ActualGridVarianceYDirection)
    {
        AreaID = 7;
        pCameraAlignedCollisionGrid->NumObjectsInsideCollisionArea[7]++;
        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:

• Anzahl der Kollisionsobjekte in allen Sektoren auf Null setzen und die Sektorengrenzen nach dem Zufallsprinzip variieren
• Den momentanen Kollisionssektor der einzelnen Objekte ermitteln
• Kollisionstests für alle Asteroiden durchführen, die sich im selben Sektor befinden

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

// Die jeweiligen Kollisionsgebiete für alle Objekte ermitteln:
for(i = 0; i < NumAsteroids; i++)
    Asteroid[i].CameraAlignedCollisionArea.Find_ActualCollisionArea(
                &Asteroid[i].CameraSpacePosition);

for(i = 0; i < NumAsteroids; i++)
{
    for(j = i+1; j < NumAsteroids; j++)
    {
        // Kollisionstest nur durchführen, wenn sich die Asteroiden
        // im selben Sektor befinden:
        if(Asteroid[i].CameraAlignedCollisionArea.AreaID ==
           Asteroid[j].CameraAlignedCollisionArea.AreaID)
        {
            // Hier werden die Kollisionstests durchgeführt
        }
    }
}