KI-Programmierung Teil 12: Flocking (Schwarmverhalten), Boids

Schwarmverhalten wurde 1986 von Craig Reynolds zum ersten Mal im Rahmen einer Computersimulation modelliert. Die Simulation basiert auf drei Regeln, die die einzelnen Individuen (Boids genannt) befolgen müssen.


Hinweis:
Für den Einsatz in einem Computerspiel und für die Simulation kleinerer Schwärme lassen sich die Regeln etwas vereinfachen, um den benötigen Rechenaufwand zu reduzieren.

Alignment (vereinfacht): Bewege dich wie deine Nachbarn auf ein Ziel zu.

Alignment: Bewege dich in die Richtung, die der gemittelten Bewegungsrichtung deiner sichtbaren Nachbarn entspricht.


Kohäsion (vereinfacht): Bewege dich in Richtung des Schwarmmittelpunkts, wenn du dich zu weit vom Schwarm entfernst.

Kohäsion: Bewege dich in die Richtung, die der gemittelten Position deiner sichtbaren Nachbarn entspricht.

Separation: Bewege dich von deinem Nachbarn weg, falls er dir zu nahe kommt, um einen Zusammenstoß zu vermeiden.

Die Vereinfachungen beziehen sich primär auf die ersten zwei Regeln. Ohne diese Vereinfachungen ist einiges an zusätzlichem Rechenaufwand notwendig, da die Mittelwertberechnungen für jeden Boid separat unter Berücksichtigung des jeweiligen Sichtfeldes bzw. Wahrnehmungsbereichs durchgeführt werden müssen.

Hinweis:
Im Rahmen des hier vorgestellten Programmbeispiels werden wahlweise die vereinfachten wie auch die vollständigen Regeln berücksichtigt. Auf das der Schwarmbewegungen zugrundeliegende Bewegungsmodell werden wir an dieser nicht näher eingehen, da wir dieses bereits im vorangegangenen Artikel (KI-Programmierung Teil 11) ausführlich besprochen haben.

Zwei Arten des Schwarmverhaltens sollen im Folgenden behandelt werden:

  • Ein Schwarm mit gleichberechtigten Individuen
  • Ein Schwarm mit einem Anführer


Schwarm mit gleichberechtigten Individuen

Bei einem Schwarm mit gleichberechtigten Individuen wählen alle Mitglieder selbstständig ihr Ziel aus. Stünden mehrere Ziele zur Auswahl, dann würde sich der Hauptschwarm in mehrere kleinere Schwärme aufteilen, die jeweils ihre eigenen Ziele ansteuern würden.

Da wir jedoch im nachfolgenden Beispiel nur ein einziges Ziel zulassen, bleiben alle Schwarmmitglieder beisammen:

// Ziel festlegen:
for
(i = 0; i < NumBoids; i++)
    Boid[i].Set_Destination(&Destination);

// Für jedes Schwarmmitglied die gemittelte Position der sichtbaren
// Nachbarn berechnen. Diese Position soll im Rahmen der Kohäsions-Regel
// angesteuert werden, falls der Abstand zum Schwarm zu groß wird.

for(i = 0; i < NumBoids; i++)
    Boid[i].Calculate_Individual_Centroid(Boid, NumBoids, 25.0f);

// Bei Verwendung der vereinfachten Kohäsions-Regel, sollen die Individuen
// den Schwarmmittelpunkt ansteuern, falls sie sich zu weit vom Schwarm
// entfernen:

// Calculate_CentroidPosition(Boid, NumBoids);

// Für jedes Schwarm-Mitglied die Position des nächstgelegenden Nachbarn
// bestimmen. Kommt ein Nachbar einem Schwarmmitglied zu nahe, kann
// dieses sich im Rahmen der Separations-Regel von diesem Nachbarn
// wegbewegen, um einen Zusammenstoß zu vermeiden:

for(i = 0; i < NumBoids; i++)
    Boid[i].Find_ClosestNeighbour(Boid, NumBoids);


// Kohäsions- und Separationsregel befolgen:
for(i = 0; i < NumBoids; i++)
{
    // Falls nötig neue Bewegungsrichtung festlegen, damit der Schwarm
    // beisammen bleibt:

    Boid[i].Cohesion(100.0f);

    // Falls nötig neue Bewegungsrichtung festlegen, damit die
    // Schwarmmitglieder nicht mit ihren Nachbarn zusammenstoßen:

    Boid[i].Separation(20.0f, 50.0f);
}

for(i = 0; i < NumBoids; i++)
{
    // Alignment-Regel befolgen:
    Boid[i].Calculate_Mean_DesiredMovementDirection(Boid, NumBoids, 10.0f);

    // Flugsteuerung:
    // Momentane Flugrichtung mit jedem Aufruf schrittweise an den
    // optimalen Zielanflugsvektor anpassen:
    Boid[i].Update_MovementDirection(0.95f, 1.0f);

    // Flugbewegung:
    Boid[i].Update_Movement(0.05f, 0.3f);
}

Schwarm mit einem Anführer

Bei einem Schwarm mit einem Anführer übernehmen die übrigen Schwarmmitglieder das vom Anführer gewählte Ziel. Hierbei kommt die Follow_The_Leader()-Funktion zum Einsatz. Die Bewegung des Anführers muss nun separat berechnet werden. Für die übrigen Schwarmmitglieder wird das Schwarmverhalten wie im vorangegangenen Abschnitt simuliert.

// Führungs-Boid:
// Ziel festlegen:

Boid[0].Set_Destination(&Destination);

// Flugsteuerung:
Boid[0].Update_MovementDirection(0.95f, 1.0f);

// Flugbewegung:
Boid[0].Update_Movement(0.05f, 0.3f);

// Alle übrigen Schwarm-Mitglieder übernehmen das vom Anführer
// gewählte Ziel:

Follow_The_Leader(0, Boid, NumBoids);

// Für die übrigen Schwarmmitglieder bleibt die Simulation des
// Schwarmverhaltens wie gehabt:

for(i = 1; i < NumBoids; i++)
    Boid[i].Calculate_Individual_Centroid(Boid, NumBoids, 25.0f);

// Nur bei Verwendung der vereinfachten Kohäsions-Regel!
// Calculate_CentroidPosition(Boid, NumBoids);


for(i = 1; i < NumBoids; i++)
    Boid[i].Find_ClosestNeighbour(Boid, NumBoids);

for(i = 1; i < NumBoids; i++)
{
    Boid[i].Cohesion(100.0f);
    Boid[i].Separation(20.0f, 50.0f);
}

for(i = 1; i < NumBoids; i++)
{
    Boid[i].Calculate_Mean_DesiredMovementDirection(Boid, NumBoids, 10.0f);
    Boid[i].Update_MovementDirection(0.95f, 1.0f);
    Boid[i].Update_Movement(0.05f, 0.3f);
}

Jedes einzelne Schwarmmitglied wird durch eine Instanz der CBoid-Klasse repräsentiert. Diese stellt eine Erweiterung der CMovableObject-Klasse aus dem vorangegangenen Artikel dar – ergänzt durch zusätzliche Methoden zur Simulation des eigentlichen Schwarmverhaltens. Für die konkrete Umsetzung der Schwarmbewegungen verwenden wir das bereits in der CMovableObject-Klasse implementierte Bewegungsmodell.
Verschaffen wir uns nun einen Überblick über die einzelnen Klassenmethoden.

Neu hinzugekommene Methoden, die für die Simulation des Schwarmverhaltens benötigt werden:

Set_ID(): Ordnet jeder CBoid-Instanz eine Identifikationsnummer zu.

Set_Random_WorldSpacePosition(): Legt eine zufällige Position im Weltkoordinatensystem fest.

Find_ClosestNeighbour(): Sucht den nächstgelegenen (sichtbaren) Nachbarn im Schwarm und speichert dessen Position.

Calculate_Individual_Centroid(): Berechnet die gemittelte Position – das so genannte geometrische Zentrum – aus der eigenen Position und der Positionen der (sichtbaren) Schwarmmitglieder.

Calculate_Mean_DesiredMovementDirection(): Berechnet die mittlere Bewegungsrichtung aus der eigenen Bewegungsrichtung und der Bewegungsrichtungen der (sichtbaren) Schwarmmitglieder.

Separation(): Wird der Abstand zum nächstgelegenen Nachbarn zu gering, dann wird eine neue Bewegungsrichtung festgelegt, die von diesem wegführt.

Cohesion(): Wird der Abstand vom geometrischen Zentrum des Schwarms zu groß, dann wird eine neue Bewegungsrichtung festgelegt, die wieder zum Schwarm zurückführt.

Hier nun die bereits bekannten Methoden der CMovableObject-Klasse:

Set_Destination(): Speichert die aktuelle Zielposition und berechnet den optimalen Zielanflugsvektor (MovementDirectionDesired).

Update_Movement(): Berechnet die aktuelle Position (Flugbewegung).

Update_MovementDirection(): Passt die momentane Flugrichtung mit jedem Aufruf schrittweise an den optimalen Zielanflugsvektor an.

Set_RotationVelocity(): Legt die Rotationsgeschwindigkeit bei der Kurskorrektur und damit die Manövrierfähigkeit fest.

Set_WorldSpacePosition(): Legt die Position im Weltkoordinatensystem fest.


Und hier die vollständige Implementierung der CBoid-Klasse:

class CBoid
{
public:

    long ID;

    D3DXVECTOR3 DestinationPosition;
    D3DXVECTOR3 WorldSpacePosition;

    // tatsächliche Bewegungsrichtung:
    D3DXVECTOR3 MovementDirection;

    // angestrebte Bewegungsrichtung, die
    // auf direktem Wege zum Ziel führt:
    D3DXVECTOR3 MovementDirectionDesired;

    // horizontale und vertikale Achse
    // zur Beschreibung der Orientierung:
    D3DXVECTOR3 HorizontalAxis;
    D3DXVECTOR3 VerticalAxis;

    // Zentrum des Schwarms:
    D3DXVECTOR3 CentroidPosition;

    D3DXVECTOR3 PositionOfClosestNeighbour;

    float RotationVelocity;

    // Orientierung im 3D-Raum:
    D3DXMATRIXA16 OrientationMatrix;

    CBoid()
    {
        RotationVelocity = 0.0f;

        CentroidPosition    = g_NullVector;
        DestinationPosition = g_NullVector;
        WorldSpacePosition  = g_NullVector;

        MovementDirectionDesired = D3DXVECTOR3(0.0f, 0.0f, 1.0f);

        // anfängliche Ausrichtung/Orientierung:
        HorizontalAxis    = D3DXVECTOR3(1.0f, 0.0f, 0.0f);
        VerticalAxis      = D3DXVECTOR3(0.0f, 1.0f, 0.0f);
        MovementDirection = D3DXVECTOR3(0.0f, 0.0f, 1.0f);

        D3DXMatrixIdentity(&OrientationMatrix);
    }

    ~CBoid()
    {}

    void Set_ID(long id)
    {
        ID = id;
    }

    void Set_Destination(D3DXVECTOR3* pPosition)
    {
        DestinationPosition = *pPosition;

        // Aus der neuen Zielposition wird nun die angestrebte
        // Bewegungsrichtung berechnet, die auf direktem Wege zum Ziel führt

       MovementDirectionDesired = DestinationPosition - WorldSpacePosition;

        D3DXVec3Normalize(&MovementDirectionDesired,
                          &MovementDirectionDesired);
    }

    void Update_Movement(float vel, float minDistanceSqToDestination)
    {
        D3DXVECTOR3 DistanceVector = WorldSpacePosition -
                                     DestinationPosition;

        if(D3DXVec3LengthSq(&DistanceVector) < minDistanceSqToDestination)
            return;

        WorldSpacePosition += MovementDirection*vel;
    }

    void Update_MovementDirection(float precision, float frameTime)
    {
        float dot, dotTest;

        // Abweichung vom Ziel ermitteln:
        dot = D3DXVec3Dot(&MovementDirectionDesired, &MovementDirection);

        // Bewegungsrichtung OK:
        if(dot > precision)
            return;

        float RotationVel = RotationVelocity*frameTime;

        D3DXMATRIXA16 FrameRotationMatrix;
        D3DXVECTOR3 TestDir;

        // Durchführen möglicher Kurskorrekturen . . .

        // . . . durch Drehung um die vertikale Achse:
        D3DXMatrixRotationAxis(&FrameRotationMatrix, &VerticalAxis,
                               RotationVel);

        Multiply3DVectorWithRotationMatrix(&TestDir, &MovementDirection,
                                           &FrameRotationMatrix);

        dotTest = D3DXVec3Dot(&MovementDirectionDesired, &TestDir);

        // neue Flugrichtung ist besser!
       
if(dotTest > dot)
            OrientationMatrix = OrientationMatrix*FrameRotationMatrix;

        // neue Flugrichtung ist schlechter, darum den Drehsinn ändern:
        else
        {
            D3DXMatrixRotationAxis(&FrameRotationMatrix, &VerticalAxis,
                                   -RotationVel);

           Multiply3DVectorWithRotationMatrix(&TestDir, &MovementDirection,
                                              &FrameRotationMatrix);

            dotTest = D3DXVec3Dot(&MovementDirectionDesired, &TestDir);

            if(dotTest > dot)
                OrientationMatrix = OrientationMatrix*FrameRotationMatrix;
        }

        // . . . durch Drehung um die horizontale Achse:
       
D3DXMatrixRotationAxis(&FrameRotationMatrix, &HorizontalAxis,
                               RotationVel);

        Multiply3DVectorWithRotationMatrix(&TestDir, &MovementDirection,
                                           &FrameRotationMatrix);

        dotTest = D3DXVec3Dot(&MovementDirectionDesired, &TestDir);

        // neue Flugrichtung ist besser!
        if(dotTest > dot)
            OrientationMatrix = OrientationMatrix*FrameRotationMatrix;

        // neue Flugrichtung ist schlechter, darum den Drehsinn ändern:
        else
        {
            D3DXMatrixRotationAxis(&FrameRotationMatrix, &HorizontalAxis,
                                   -RotationVel);

           Multiply3DVectorWithRotationMatrix(&TestDir, &MovementDirection,
                                              &FrameRotationMatrix);

           dotTest = D3DXVec3Dot(&MovementDirectionDesired, &TestDir);

           if(dotTest > dot)
               OrientationMatrix = OrientationMatrix*FrameRotationMatrix;
        }

        // lokale Achsen aus der Orientierungsmatrix auslesen:

        HorizontalAxis.x = OrientationMatrix._11;
        HorizontalAxis.y = OrientationMatrix._12;
        HorizontalAxis.z = OrientationMatrix._13;

        VerticalAxis.x = OrientationMatrix._21;
        VerticalAxis.y = OrientationMatrix._22;
        VerticalAxis.z = OrientationMatrix._23;

        MovementDirection.x = OrientationMatrix._31;
        MovementDirection.y = OrientationMatrix._32;
        MovementDirection.z = OrientationMatrix._33;

        D3DXVec3Normalize(&HorizontalAxis, &HorizontalAxis);
        D3DXVec3Normalize(&VerticalAxis, &VerticalAxis);
        D3DXVec3Normalize(&MovementDirection, &MovementDirection);
    }

    void Set_RotationVelocity(float vel)
    {
        RotationVelocity = vel;
    }

    void Set_Random_WorldSpacePosition(float minX, float maxX,
                                       float minY, float maxY,
                                       float minZ, float maxZ)
    {
        WorldSpacePosition = D3DXVECTOR3(frnd(minX, maxX),
                                         frnd(minY, maxY),
                                         frnd(minZ, maxZ));
    }

    void Set_WorldSpacePosition(D3DXVECTOR3* pWorldSpacePosition)
    {
        WorldSpacePosition = *pWorldSpacePosition;
    }

    void Separation(float MinSquareDistance,
                    float SeparationSquareDistance)
    {
        // Abstand zu einem Nachbarn ist zu gering.
        // Neue Zielposition so festlegen, dass sich der
        // Abstand wieder vergrößert:

        D3DXVECTOR3 DistanceVector = WorldSpacePosition -
                                     PositionOfClosestNeighbour;

        if(D3DXVec3LengthSq(&DistanceVector) < MinSquareDistance)
        {
            DistanceVector *= SeparationSquareDistance;
            Set_Destination(&DistanceVector);
        }
    }

    void Cohesion(float MaxSquareDistance)
    {
        // Abstand zum Zentrum des Schwarms zu groß.
        // Schwarmzentrum als neue Zielposition festlegen:

        D3DXVECTOR3 DistanceVector = CentroidPosition - WorldSpacePosition;

        if(D3DXVec3LengthSq(&DistanceVector) > MaxSquareDistance)
            Set_Destination(&CentroidPosition);
    }

    void Find_ClosestNeighbour(CBoid* pBoid, long NumBoids)
    {
         D3DXVECTOR3 DistanceVector;

         float DistanceSq;

         float MinDistanceSq = 100000000000.0f;

         for(long i = 0; i < NumBoids; i++)
         {
             if(i == ID)
                 continue;

             // Überprüfen, ob sich ein anderes Schwarmmitglied im
             // Wahrnehmungsbereich befindet:

             DistanceVector = pBoid[i].WorldSpacePosition -
                              WorldSpacePosition;

             DistanceSq = D3DXVec3LengthSq(&DistanceVector);

             // Neuer Nachbar gefunden, der sich dichter beim
             // Schwarmmitglied aufhält als der letzte Nachbar:
             if(DistanceSq < MinDistanceSq)
             {
                 MinDistanceSq = DistanceSq;
                 PositionOfClosestNeighbour = pBoid[i].WorldSpacePosition;
             }
         }
    }

    void Calculate_Individual_Centroid(CBoid* pBoid, long NumBoids,
                                       float maxCentroidDistanceSq)
    {
        D3DXVECTOR3 DistanceVector;
        float DistanceSq;

        CentroidPosition = g_NullVector;

        long BoidsCount = 0;

        for(long i = 0; i < NumBoids; i++)
        {
            // Überprüfen, ob sich ein anderes Schwarmmitglied im
            // Wahrnehmungsbereich befindet:

            DistanceVector = pBoid[i].WorldSpacePosition -
                             WorldSpacePosition;

            DistanceSq = D3DXVec3LengthSq(&DistanceVector);

            // Anderes Schwarmmitglied im Wahrnehmungsbereich, dessen
            // Position bei der Mittelwertberechnung berücksichtigen:
            if(DistanceSq < maxCentroidDistanceSq)
            {
                BoidsCount++;
                CentroidPosition += pBoid[i].WorldSpacePosition;
            }
        }

        CentroidPosition /= (float)(BoidsCount);
    }

    void Calculate_Mean_DesiredMovementDirection(CBoid* pBoid,
         long NumBoids, float maxCalculationDistanceSq)
    {
        D3DXVECTOR3 DistanceVector;
        float DistanceSq;

        D3DXVECTOR3 MeanDirection = g_NullVector;

        for(long i = 0; i < NumBoids; i++)
        {
            // Überprüfen, ob sich ein anderes Schwarmmitglied im
            // Wahrnehmungsbereich befindet:

            DistanceVector = pBoid[i].WorldSpacePosition -
                             WorldSpacePosition;

            DistanceSq = D3DXVec3LengthSq(&DistanceVector);

            // Anderes Schwarmmitglied im Wahrnehmungsbereich, dessen
            // Bewegungsrichtung bei der Mittelwertberechnung
            // berücksichtigen:

            if(DistanceSq < maxCalculationDistanceSq)
            {
                MeanDirection += pBoid[i].MovementDirectionDesired;
            }
        }

        D3DXVec3Normalize(&MovementDirectionDesired, &MeanDirection);
    }
};


Hilfsfunktion zur Berechnung des Schwarmzentrums im Rahmen einer vereinfachten Schwarmsimulation

void Calculate_CentroidPosition(CBoid* pBoid, long NumBoids)
{
    long i;

    D3DXVECTOR3 CentroidPosition = g_NullVector;

    for(i = 0; i < NumBoids; i++)
        CentroidPosition += pBoid[i].WorldSpacePosition;

    CentroidPosition /= (float)NumBoids;

    for(i = 0; i < NumBoids; i++)
        pBoid[i].CentroidPosition = CentroidPosition;
}

Hilfsfunktion für die Festlegung der Zielposition im Rahmen der Schwarmsimulation mit einem Anführer

void Follow_The_Leader(long IDOfLeader, CBoid* pBoid, long NumBoids)
{
    long i;

    for(i = 0; i < NumBoids; i++)
    {
        if(i != IDOfLeader)
        {
            pBoid[i].Set_DestinationPosition(
                     &pBoid[IDOfLeader].WorldSpacePosition);
        }
    }
}