Sortierphase vor der eigentlichen Kollisionsprüfung: Die „Broad Phase“

Einführung:
Wieso, weshalb, warum?

Das Prüfen von Kollisionen ist eine kostspielige Angelegenheit. Um die dafür benötigte CPU-Zeit weitestgehend zu minimieren, bietet es sich an, dass für jeden Frame vorab eine Liste erstellt wird, die nur noch die Objektpaare beinhaltet, bei denen die Kollisionswahrscheinlichkeit hoch ist.

Wenn sich also z.B. 100 Objekte in einer Szene befinden, und jedes Objekt die Kollision mit jedem anderen Objekt prüfen muss, würde die Kollisionsprüfung insgesamt 100 * (100 - 1) = 9.900 Male durchgeführt werden. Aus diesem Grund benötigen wir einen Algorithmus, der vorab anhand einer groben (und daher viel schnelleren) Messung herausfindet, ob sich zwei Objekte überhaupt schneiden können.
Dieses Verfahren wird „broad phase“ genannt.

Schritt 1:
Alle Objekte werden entlang einer der drei Achsen aufsteigend sortiert

Die Idee dahinter ist, dass sich Objekte nur dann berühren können, wenn sie sich auf allen drei Achsen schneiden. Wenn sich zwei Objekte zwar auf der x- und y-Achse schneiden, auf der z-Achse jedoch weit von einander entfernt sind, gibt es keine Kollision.
In diesem Tutorial wird die x-Achse als fest vorgegebene Achse verwendet.

In der obigen Abbildung wurden alle Objekte (A bis E) gemäß der Position ihrer linken Seite aufsteigend sortiert.
Dieses Detail ist wichtig:
Die Objekte müssen anhand der Position ihrer linken Seite – nicht ihrer Mitte! – sortiert werden.

Aus Gründen der Übersicht wurden die Objekte auf vertikaler Ebene voneinander getrennt. Stellen Sie sich bitte vor, dass alle Objekte eigentlich auf der gleichen Höhe liegen.

---

Schritt 2: Eine Schleife durchläuft alle (sortierten) Objekte einer Liste

Angefangen beim ersten Objekt der Liste wird nun eine Schleife gestartet, die nacheinander jedes Objekt betrachtet. In unserem Beispiel oben wäre dies das Objekt A.

• Für das Objekt A werden nun alle Objekte in der Liste nach A überprüft. Hierfür benötigen Sie eine zweite Schleife innerhalb der ersten.
  • Wenn As rechte Seite nun einen höheren Wert hat als die linke Seite des in der Liste benachbarten Objekts, schneiden sich A und das nachfolgende Objekt auf der x-Achse. Wir können also B als potenziellen Kollisionskandidat für A markieren und A als potenziellen Kandidaten für B.
  • Wenn As rechte Seite jedoch einen kleineren Wert hat als die linke Seite des benachbarten Objekts, werden sich die Objekte in keinem Fall schneiden können. Dies gilt auch für alle anderen Nachbarobjekte von A.
    Die innere Schleife kann abgebrochen werden.

Ohne diese Vorsortierung (broad phase) müsste z.B. Objekten B auf Kollisionen mit allen anderen Objekten prüfen: 4 Prüfungen.
Wenn die Vorsortierung abgeschlossen ist, muss B nur noch die Kollisionen mit C und D genauer überprüfen.

Der Code

// Diese Liste enthält alle zu betrachtenden Objekte:
private List<GameObject> _gameObjects; 

private void BroadPhaseCollisionDetection()
{
    // Sortiere die Objekte nach ihrer linken Seite aufsteigend:
    List<GameObject> sortedList = _gameObjects.OrderBy(x => x.LeftMostEdge).ToList();

    // Fange beim ersten Objekt der Liste an und durchlaufe 
    // in der äußeren Schleife nach und nach alle Objekte:
    for(int i = 0; i < sortedList.Count; i++)
    {
        // Die innere Schleife beginnt immer beim direkten
        // Nachbarn des aktuell in der äußeren Schleife
        // betrachteten Objekts (also i+1):
        for(int j = i+1; j < sortedList.Count; j++)
        {
            GameObject objectI = sortedList[i];
            GameObject objectJ = sortedList[j];
            if (objectJ.LeftMostEdge > objectI.RightMostEdge)
            {
                break;
            }
            else
            {
                objectI.AddCollisionCandidate(objectJ);
                objectJ.AddCollisionCandidate(objectI);
            }
        }
    }
}

Das war es schon! 🙂
Weitere Verbesserungen könnten sein:

• Wenn die x-Achse nicht immer die richtige Achse zum Testen ist, kann man die Achse für jeden neuen Frame dynamisch wechseln. Dafür muss im vorangegangen Frame lediglich gemessen werden, auf welcher Achse die Objekte die größten Positionsunterschiede aufweisen.
  Dies findet man heraus, indem man die Varianz berechnet.

// Definiere die Achse, die getestet werden soll (Standard: x)
private Axis _axis = Axis.X; 
private List<GameObject> _gameObjects;

private void BroadPhaseCollisionDetectionWithVariance()
{
    // Sortiere je nach gewählter Achse alle Objekte entlang 
    // dieser Achse:
    List<GameObject> sortedList = null;
    if(_axis == Axis.X)
        sortedList = _gameObjects.OrderBy(x => x.LeftMostEdge).ToList();
    else if(_axis == Axis.Y)
        sortedList = _gameObjects.OrderBy(y => y.BottomMostEdge).ToList();
    else
        sortedList = _gameObjects.OrderBy(z => z.BackMostEdge).ToList();

    // Um die Varianz zu messen, summieren wir die 
    // Positionen (und die quadratischen Werte davon) aller Objekte auf:
    Vector3 centerSum = new Vector3(0, 0, 0);
    Vector3 centerSqSum = new Vector3(0, 0, 0);

    for(int i = 0; i < sortedList.Count; i++)
    {
        GameObject objectI = sortedList[i];

        // Hier wird die Mitte des Objekts erfragt und 
        // anschließend zu den beiden Summenvariablen addiert:
        Vector3 currentCenter = objectI.GetCenter();
        centerSum += currentCenter;
        centerSqSum += (currentCenter * currentCenter);

        for(int j = i+1; j < sortedList.Count; j++)
        {
            GameObject objectJ = sortedList[j];
            
            // Je nach gewählter Achse müssen nun die 
            // entsprechenden Kanten (links/rechts, oben/unten, usw.)
            // überprüft werden:
            float edgeI = _axis == Axis.X ? objectI.RightMostEdge : _axis == Axis.Y ? objectI.TopMostEdge : objectI.FrontMostEdge;
            float edgeJ = _axis == Axis.X ? objectJ.LeftMostEdge: _axis == Axis.Y ? objectJ.BottomMostEdge : objectJ.BackMostEdge;
            if (edgeJ > edgeI)
            {
                break;
            }
            else
            {
                objectI.AddCollisionCandidate(objectJ);
                objectJ.AddCollisionCandidate(objectI);
            }
        }
    }

    // Teile die aufsummierten Positionen durch die Anzahl
    // der Objekte in der Liste:
    centerSum /= sortedList.Count;
    centerSqSum /= sortedList.Count;
    
    // Berechne die Varianz:
    Vector3 variance = centerSqSum - (centerSum * centerSum);

    // Wir beginnen mit der Varianz auf der x-Achse:
    float maxVar = Math.Abs(variance.X);
    _axis = Axis.X;

    // Ist die Varianz entlang der y-Achse größer
    // ist dort am meisten los. Dies wird unsere 
    // neue Testachse für den nächsten Durchgang:
    if (Math.Abs(variance.Y) > maxVar)
    {
        maxVar = Math.Abs(variance.Y);
        _axis = Axis.Y;
    }
    
    // Wenn aber die Varianz entlang der z-Achse
    // noch größer ist, dann nehmen wir stattdessen
    // lieber diese:
    if(Math.Abs(variance.Z) > maxVar)
    {
        maxVar = Math.Abs(variance.Z);
        _axis = Axis.Z;
    }      
}

• Es kann sinnvoll sein, auf jeder Seite der Objekte einen kleinen Toleranzbereich anzulegen. Da die Vorsortierung vor der eigentlich Kollisionsprüfung stattfindet und sich die Objekte zwischendurch eventuell noch bewegen können, kann es sein, dass ein Objekt so stark verschoben wird, dass es bei der Vorsortierung noch mit keinem Objekt kollidierte – inzwischen aber schon.