KI-Programmierung Teil 04: Wahrnehmung der Spielewelt

Voraussetzung für intelligentes Verhalten ist die Wahrnehmung der Spielewelt – nur wie nimmt ein Computergegner (bzw. eine intelligente Einheit oder AI Entity) die Spielewelt überhaupt wahr?
Betrachten wir ein praktisches Beispiel – zwei Einheiten bewegen sich aufeinander zu. Wird ein im Voraus festgelegter Mindestabstand unterschritten, nehmen die Einheiten Notiz voneinander. Die Wahrnehmung selbst kann gerichtet erfolgen (z.B. visuell) oder aber richtungsunabhängig (Rundumwahrnehmung mittels Radar oder durch Geräusche).

Die richtungsunabhängige Wahrnehmung lässt sich besonders einfach implementieren, da lediglich der quadratische Abstand zweier Einheiten mit der maximalen quadratischen Wahrnehmungsreichweite AllAroundPerceptionDistanceMaxSq verglichen werden muss:

DistanceVector = pAIEntity[i].WorldSpacePosition -
                             pAIEntity[j].WorldSpacePosition;

DistanceSq = D3DXVec3LengthSq(&DistanceVector);

// Rundum Wahrnehmung prüfen:
if(pAIEntity[i].AllAroundPerceptionDistanceMaxSq > DistanceSq)
   pAIEntity[i].AllAroundPerception[j] = true;

if(pAIEntity[j].AllAroundPerceptionDistanceMaxSq > DistanceSq)
   pAIEntity[j].AllAroundPerception[i] = true;

Bei der gerichteten Wahrnehmung müssen wir darüber hinaus Blickrichtung und Größe des Blickfeldes (field of view) berücksichtigen. Das klingt schwerer als es in Wirklichkeit ist, denn wir benötigen hierfür lediglich das Punktprodukt (Skalarprodukt) aus dem Blickrichtungs-Vektor (ViewDirection) der betreffenden Einheit und dem Annäherungsrichtungs-Vektor (NormalizedDistanceVector) einer zweiten Einheit.

Bei einem (symmetrischen) Blickfeld von beispielsweise 180° beträgt der Winkel (Blickfeldbegrenzungswinkel) zwischen der Blickrichtung und der äußeren Begrenzung des sichtbaren Bereichs 90°. Die Blickwinkel, unter denen die sichtbaren Einheiten wahrgenommen werden können, liegen also allesamt zwischen 0° und 90°. Der Kosinuswert des Blickwinkels entspricht dem zuvor berechneten Punktprodukt und ist für alle sichtbaren Einheiten größer als der Kosinuswert des Blickfeldbegrenzungswinkels (CosFieldOfView). In diesem speziellen Fall ist der Kosinuswert des Blickfeldbegrenzungswinkels gleich null (CosFieldOfView = cos(90°) = 0). Für Objekte außerhalb des sichtbaren Bereichs ist das Skalarprodukt daher stets kleiner als null. Hat das Punktprodukt hingegen einen Wert von eins, dann blickt die Einheit exakt in die Richtung, aus der sich die andere Einheit annähert. Der Blickwinkel zwischen der ViewDirection und dem Annäherungsrichtungs-Vektor (NormalizedDistanceVector) beträgt in diesem Fall 0°.

DistanceVector = pAIEntity[i].WorldSpacePosition -
                             pAIEntity[j].WorldSpacePosition;

DistanceSq = D3DXVec3LengthSq(&DistanceVector);
InvDistance = 1.0f/sqrtf(DistanceSq);

NormalizedDistanceVector = InvDistance*DistanceVector;

if(pAIEntity[j].DirectedPerceptionDistanceMaxSq > DistanceSq)
{
    dot = D3DXVec3Dot(&NormalizedDistanceVector,
                      &pAIEntity[j].ViewDirection);

    if(dot > pAIEntity[j].CosFieldOfView)
        pAIEntity[j].DirectedPerception[i] = true;
}

Die Klasse CAIEntity wird uns im weiteren Verlauf zum Austesten neuer KI-Routinen dienen. Die Einheiten sind zugegebenermaßen noch recht dumm, denn ihre Bewegung erfolgt rein zufällig. Für diesen Random Walk ist die gleichnamige Methode RandomWalk() zuständig.
Unser eigentliches Interesse liegt augenblicklich jedoch bei der Wahrnehmung. Die in diesem Zusammenhang benötigten Parameter – die maximale Reichweite der Wahrnehmung sowie die Größe des Blickfeldes – müssen zunächst mithilfe der beiden Methoden Set_AllAroundPerceptionParameter() und Set_DirectedPerceptionParameter() eingestellt werden. Da jede Einheit separat wahrgenommen werden kann, muss zudem die Anzahl der wahrnehmbaren Einheiten mittels der Set_NumPerceptionObjects()-Methode festgelegt werden.

class CAIEntity
{
public:

    D3DXVECTOR3 WorldSpacePosition;
    D3DXVECTOR3 Velocity;
    D3DXVECTOR3 MovementDirection;

    D3DXVECTOR3 ViewDirection;

    // Rundum Wahrnehmung
    float AllAroundPerceptionDistanceMax;
    float AllAroundPerceptionDistanceMaxSq;

    // Jede Einheit kann separat wahrgenommen werden.
    // Der Arrayindex entspricht dem Index der wahrgenommenen
    // Einheit:

    bool* AllAroundPerception;

    // gerichtete Wahrnehmung
    float CosFieldOfView;
    float DirectedPerceptionDistanceMax;
    float DirectedPerceptionDistanceMaxSq;

    // Jede Einheit kann separat wahrgenommen werden.
   
// Der Arrayindex entspricht dem Index der wahrgenommenen
    // Einheit:

    bool* DirectedPerception;

    // Anzahl der wahrnehmbaren Objekte:
   
long NumPerceptionObjects;

    CAIEntity()
    {
        AllAroundPerception = NULL;
        DirectedPerception = NULL;

        NumPerceptionObjects = 0;

        WorldSpacePosition = g_NullVector;
        Velocity = g_NullVector;
        MovementDirection = g_NullVector;
        ViewDirection = g_NullVector;

        AllAroundPerceptionDistanceMax = 0.0f;
        AllAroundPerceptionDistanceMaxSq = 0.0f;
        AllAroundPerception = false;

        DirectedPerceptionDistanceMax = 0.0f;
        DirectedPerceptionDistanceMaxSq = 0.0f;
        CosFieldOfView = 1.0f;
        DirectedPerception = false;
    }

    ~CAIEntity()
    {
        SAFE_DELETE_ARRAY(AllAroundPerception)
        SAFE_DELETE_ARRAY(DirectedPerception)
    }

    // Wahrnehmungen zurücksetzen:
    void Reset_Perceptions(void)
    {
        for(long i = 0; i < NumPerceptionObjects; i++)
        {
            AllAroundPerception[i] = false;
            DirectedPerception[i] = false;
        }
    }

    void Set_NumPerceptionObjects(long numObjects)
    {
        SAFE_DELETE_ARRAY(AllAroundPerception)
        SAFE_DELETE_ARRAY(DirectedPerception)

        NumPerceptionObjects = numObjects;

        AllAroundPerception = new bool[NumPerceptionObjects];
        DirectedPerception = new bool[NumPerceptionObjects];

        for(long i = 0; i < NumPerceptionObjects; i++)
        {
            AllAroundPerception[i] = false;
            DirectedPerception[i] = false;
        }
    }

    void Set_AllAroundPerceptionParameter(float distance)
    {
        AllAroundPerceptionDistanceMax = distance;
        AllAroundPerceptionDistanceMaxSq  = AllAroundPerceptionDistanceMax;
        AllAroundPerceptionDistanceMaxSq *= AllAroundPerceptionDistanceMax;
    }

    void Set_DirectedPerceptionParameter(float distance,
                                         float cosFieldOfView)
    {
        CosFieldOfView = cosFieldOfView;
        DirectedPerceptionDistanceMax = distance;
        DirectedPerceptionDistanceMaxSq  = DirectedPerceptionDistanceMax;
        DirectedPerceptionDistanceMaxSq *= DirectedPerceptionDistanceMax;
    }

    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 RandomWalk(long DirectionChangeFactor, float minVelocity,
                                                float maxVelocity)
    {
        // zu schnelle Richtungsänderungen vermeiden:
        if(DirectionChangeFactor < 5)
            DirectionChangeFactor = 5;

        if(lrnd(0, DirectionChangeFactor) == 3)
        {
            MovementDirection = D3DXVECTOR3(frnd(-1.0f, 1.0f),
                                            frnd(-1.0f, 1.0f),
                                            frnd(-1.0f, 1.0f));

            D3DXVec3Normalize(&MovementDirection, &MovementDirection);

            // In diesem speziellen Beispiel gilt Augen geradeaus:
            ViewDirection = MovementDirection;

            float velocityAmount = frnd(minVelocity, maxVelocity);

            Velocity = MovementDirection*velocityAmount;
        }

        WorldSpacePosition += Velocity;
    }
};


Innerhalb der Check_AIEntity_DistancesAndPerception()-Funktion werden zunächst die Abstände zwischen den Einheiten bestimmt. Anhand eines solchen Abstands kann dann die mögliche Wahrnehmung der jeweils anderen Einheit bestimmt werden.

void Check_AIEntity_DistancesAndPerception(CAIEntity* pAIEntity,
                                           long NumEntities)
{
    long i, j;

    // Wahrnehmungen zurücksetzen:
    for(i = 0; i < NumEntities; i++)
    {
        pAIEntity[i].Reset_Perceptions();
    }

    D3DXVECTOR3 DistanceVector;
    D3DXVECTOR3 NormalizedDistanceVector;
    float DistanceSq;
    float InvDistance;
    float dot;

    for(i = 0; i < NumEntities; i++)
    {
        for(j = i+1; j < NumEntities; j++)
        {
            DistanceVector = pAIEntity[i].WorldSpacePosition -
                             pAIEntity[j].WorldSpacePosition;

            DistanceSq = D3DXVec3LengthSq(&DistanceVector);
            InvDistance = 1.0f/sqrtf(DistanceSq);

            NormalizedDistanceVector = InvDistance*DistanceVector;

            // Rundum Wahrnehmung prüfen:
            if(pAIEntity[i].AllAroundPerceptionDistanceMaxSq > DistanceSq)
                pAIEntity[i].AllAroundPerception[j] = true;

            if(pAIEntity[j].AllAroundPerceptionDistanceMaxSq > DistanceSq)
                pAIEntity[j].AllAroundPerception[i] = true;

            // gerichtete Wahrnehmung prüfen:
            if(pAIEntity[i].DirectedPerceptionDistanceMaxSq > DistanceSq)
            {
                // Negatives Vorzeichen, weil NormalizedDistanceVector in
                // Richtung von pAIEntity[i] zeigt!!!!
                dot = -D3DXVec3Dot(&NormalizedDistanceVector,
                                   &pAIEntity[i].ViewDirection);

                if(dot > pAIEntity[i].CosFieldOfView)
                    pAIEntity[i].DirectedPerception[j] = true;
            }

            if(pAIEntity[j].DirectedPerceptionDistanceMaxSq > DistanceSq)
            {
                dot = D3DXVec3Dot(&NormalizedDistanceVector,
                                  &pAIEntity[j].ViewDirection);

                if(dot > pAIEntity[j].CosFieldOfView)
                    pAIEntity[j].DirectedPerception[i] = true;
            }
        }
    }
}