KI-Programmierung Teil 09: Entwurf eines Wegpunkte-Systems

Im letzten Teil unserer Artikelserie haben wir die Anforderungen an ein für den Einsatz in Computerspielen taugliches Wegpunkte-System definiert. Auf Basis dieser Erkenntnisse werden wir heute ein einfach zu verwendendes Framework entwerfen. Mit der Implementierung der eigentlichen Wegfindungs-Routinen befassen wir uns dann im nächsten Artikel.
Fassen wir die einzelnen Eckpunkte, die es beim Entwurf zu berücksichtigen gilt, noch einmal kurz zusammen:

• Geringer Rechenaufwand bei der Wegfindung (Verwendung eines Greedy-Algorithmus wann immer es möglich ist)
• Berücksichtigung des aktuellen Spielgeschehens bei der Wegfindung (Risiko-Chancen-Analyse bei der Wahl eines Weges)
• Berücksichtigung von Geländeformationen (Bsp. Steigungen, Bodenbeschaffenheit)
• Berücksichtigung von Wettereinflüssen (Bsp. rutschige Straßen, schlammige Wege)
• Unterschiedliche Bewegungskosten für die einzelnen Spieler-Fraktionen und -Einheiten
• Schnelle Reaktion auf lokale Ereignisse entlang eines Weges (Bsp. eine plötzliche Gefahrensituation)
• Wegpunkte müssen sich dynamisch aktivieren lassen (Bsp. Bau einer neuen Straße)
• Wegpunkte müssen sich dynamisch deaktivieren lassen (Bsp. eine zerstörte Brücke, eine blockierte Straße)

Bevor wir überhaupt mit dem Entwurf eines Wegfindungs-Frameworks beginnen können, müssen wir uns zuvor mit der Funktionsweise der Greedy-Wegfindung vertraut machen. Vereinfacht ausgedrückt ist diese Art der Wegfindung dem menschlichen Verhalten nachempfunden. In einer zeitkritischen Situation hält man sich normalerweise nicht lange mit der Planung einer möglichst optimalen Route zum Ziel auf. Stattdessen konzentriert man sich auf die Umgebung (benachbarte Wegpunkte, die man auf direktem Wege erreichen kann) und entscheidet sich für einen Wegabschnitt, der einen möglichst schnell zum gewählten Ziel bringt. Die Suche nach dem kürzesten Weg ist in vielen Situationen zweitrangig. In erster Linie achtet man darauf, dass der gewählte Wegabschnitt ein möglichst schnelles (gute Bodenbeschaffenheit, Straßen, möglichst keine Steigungen) und risikofreies (keine gegnerischen Einheiten in der Nähe) Vorankommen garantiert. Besagte Wegabschnitte zeichnen sich durch besonders geringe Bewegungskosten aus, wobei diese Kosten je nach Spieler-Fraktion durchaus unterschiedlich ausfallen können:

Beispiel:

Wegabschnitt von Einheiten der Fraktion A bewacht:

• Geringe Bewegungskosten für Einheiten der Fraktion A (Geleitschutz)
• Hohe Bewegungskosten für Einheiten der gegnerischen Fraktion B (Fraktion A greift mit großer Wahrscheinlichkeit die Einheiten von Fraktion B an)

Die CWaypoint-Klasse stellt die zentrale Komponente des Wegfindungs-Frameworks dar:

class CWaypoint
{
public:

    D3DXVECTOR3 WorldSpacePosition;

    // Liste mit benachbarten Wegpunkten, die auf direktem Wege
    // erreicht werden können:
    long   NumOtherWaypointsInRange;
    long*  OtherWaypointInRange;

    // individuelle Bewegungskosten (Wertebereich 0 bis 2) für die
    // einzelnen Spieler-Fraktionen und -Einheiten
    long NumOfMovementCostLists;
    CMovementCostList* MovementCostListForWaypointsInRange;

    CWaypoint();
    ~CWaypoint();

    void Disable_WaypointInRange(long WaypointID);
    void Enable_WaypointInRange(long WaypointID);

    void Set_MovementCostValue_ForWaypointInRange(long CostListID,
         float movementCostValue, long WaypointID);

    void Set_MovementCostValues_ForWaypointInRange(
         float* pWaypointMovementCostValues, long WaypointID);

    void Reset_OtherWaypointsInRange(void);

    void Set_WorldSpacePosition(D3DXVECTOR3* pPosition);

    void Init_List_Of_OtherWaypointsInRange(long NumWaypoints,
         long* pWaypointList, long NumOfMovementCostValueLists);

    void Update_MovementCostListForWaypointsInRange(long CostListID,
         float* pMovementCostList);

    void Set_NewWaypointInRange(long WaypointID,
         long NumOfMovementCostValueLists);

    void Set_NewWaypointInRange(long WaypointID,
         long NumOfMovementCostValueLists,
         float* pWaypointMovementCostValues);

    long Select_RandomWaypointInRange(void);
    long Select_RandomWaypointInRange(long IDOfPreviousWaypoint,
         bool movingToPreviousWaypointPossible = false);
};

Verschaffen wir uns nun eine Übersicht über die einzelnen Methoden der CWaypoint-Klasse:

• Set_WorldSpacePosition(): Legt die Position des Wegpunkts in der Spielewelt fest.
• Set_NewWaypointInRange(): Fügt der Nachbarschafts-Liste einen weiteren Wegpunkt hinzu.
• Init_List_Of_OtherWaypointsInRange(): Legt die Wegpunkte in der Nachbarschaft mittels einer vorgegebenen Nachbarschafts-Liste fest.
• Disable_Waypoint():Überprüft, ob der zu deaktivierende Wegpunkt in der Nachbarschafts-Liste gespeichert und damit erreichbar ist und deaktiviert diesen falls vorhanden.
• Enable_Waypoint(): Überprüft, ob der zu reaktivierende Wegpunkt in der Nachbarschafts-Liste gespeichert und damit erreichbar ist und reaktiviert diesen falls vorhanden.
• Reset_NumOtherWaypointsInRange(): Setzt die Anzahl der Wegpunkpunkte in der Nachbarschafts-Liste auf null zurück.
• Select_RandomWaypointInRange(): Wählt aus der Nachbarschafts-Liste einen zufälligen Wegpunkt aus. Darüber hinaus ist es möglich, einen Wegpunkt von der Auswahl auszuschließen. Auf diese Weise kann verhindert werden, dass sich eine KI-Einheit nach der Auswahl wieder zu dem Wegpunkt zurückbewegt, von dem sie zuletzt gekommen ist.
• Set_MovementCostValue_ForWaypointInRange(): Legt für eine einzelne oder für alle Spieler-Fraktionen die Bewegungskosten zu den benachbarten Wegpunkten fest.
• Update_MovementCostListForWaypointsInRange(): Aktualisiert die Bewegungskosten zu den benachbarten Wegpunkten für eine einzelne oder für alle Spieler-Fraktionen.

Die einzelnen Wegpunkte lassen sich nach belieben aktivieren (Bau einer neuen Straße, etc.) und deaktivieren (zerstörte Brücke, Straße etc.). Deaktivierte Wegpunkte bleiben von der Wegfindung ausgeschlossen. Wird ein Wegabschnitt zeitweilig oder dauerhaft unpassierbar, lassen sich die begrenzenden Wegpunkte mithilfe der Disable_Waypoint()-Funktion deaktivieren. Die begrenzenden Wegpunkte neuer Wegabschnitte können entsprechend mithilfe der Enable_Waypoint()-Funktion aktiviert werden:

void Disable_Waypoint(long WaypointID, CWaypoint* pWaypointArray,
                      long NumWaypoints)
{
    if(WaypointID < 0)
        return;

    if(WaypointID >= NumWaypoints)
        return;

    for(long i = 0; i < NumWaypoints; i++)
    {
        if(i == WaypointID)
            continue;

        pWaypointArray[i].Disable_WaypointInRange(WaypointID);
    }
}

void Enable_Waypoint(long WaypointID, CWaypoint* pWaypointArray,
                     long NumWaypoints)
{
    if(WaypointID < 0)
        return;

    if(WaypointID >= NumWaypoints)
        return;

    for(long i = 0; i < NumWaypoints; i++)
    {
        if(i == WaypointID)
            continue;

        pWaypointArray[i].Enable_WaypointInRange(WaypointID);
    }
}

Für jeden Wegpunkt lässt sich eine Liste der direkt erreichbaren Wegpunkte (Nachbarschafts-Liste) bereits im Vorfeld definieren, abspeichern und mittels der CWaypoint-Methode Init_List_Of_OtherWaypointsInRange() einlesen. Alternativ dazu lassen sich etwaige Nachbarschaftsbeziehungen auch mithilfe der beiden nachfolgenden Funktionen berechnen:

void Calculate_OtherWaypointsInRange(CWaypoint* pWaypointArray,
     long NumWaypoints, long NumWaypointsInRangeMax,
     float MaxWaypointDistanceSq, long NumOfMovementCostValueLists);

void Calculate_OtherWaypointsInRange_ForASingleWaypoint(long WaypointID,
     CWaypoint* pWaypointArray, long NumWaypoints,
     long NumWaypointsInRangeMax, float MaxWaypointDistanceSq,
     long NumOfMovementCostValueLists);

Müssen für einen bestimmten Wegpunkt die Bewegungskosten für eine der Spieler-Fraktionen geändert werden, kann die Set_Waypoint_MovementCostValue-Funktion verwendet werden:

void Set_Waypoint_MovementCostValue(long CostListID,
     float movementCostValue, long WaypointID, CWaypoint* pWaypointArray,
     long NumWaypoints);

Beispiel:

Im Zuge eines Großangriffs sollen die militärischen Einheiten der Fraktion A einen ganz bestimmten Wegpunkt gezielt ansteuern. Nichtmilitärische Einheiten der Fraktion B sollen infolgedessen den besagten Wegpunkt wenn möglich meiden. Zu diesem Zweck müssen die Bewegungskosten für die nichtmilitärischen Einheiten maximiert werden.

Verantwortlich für die zielgerichtete Bewegung auf ein Ziel zu bzw. von einem Ziel weg sind die Funktionen

• Select_WaypointInRange() sowie
• Select_WaypointInRange_WithRandomMovementCostVariation(),

die uns als Rückgabewert die ID des anzusteuernden Wegpunkts liefern. Im Unterschied zum ersten Funktionstyp werden beim zweiten Typ die Bewegungskosten zusätzlich nach dem Zufallsprinzip variiert. Als Resultat dieser Variationen weicht eine KI-Einheit häufiger einmal vom direkten Weg ab und nimmt stattdessen einige Umwege in kauf. In Abhängigkeit von eventuell erforderlichen Beschränkungen (Reichweite, zu ignorierende Wegpunkte) bei der Wegfindung kann der Anwender zwischen den folgenden Funktionen wählen:

// Wegfindung ohne Beschränkungen:
long Select_WaypointInRange(CWaypoint* pWaypoint, long ActualWaypointID,
     long DestinationWaypointID, D3DXVECTOR3* pDestinationPos,
     long CostListID, bool GetCloserToDestination = true);

long Select_WaypointInRange_WithRandomMovementCostVariation(
     CWaypoint* pWaypoint, long ActualWaypointID,
     long DestinationWaypointID, D3DXVECTOR3* pDestinationPos,
     float RandomFactor, long CostListID,
     bool GetCloserToDestination = true);

// Wenn die maximale Reichweite bei der Bewegung beschränkt ist, dann sind
// die folgenden Funktionen zu verwenden:
long Select_WaypointInRange(CWaypoint* pWaypoint, long ActualWaypointID,
     long DestinationWaypointID, float MaxMovementDistanceSq,
     D3DXVECTOR3* pDestinationPos, long CostListID,
     bool GetCloserToDestination = true);

long Select_WaypointInRange_WithRandomMovementCostVariation(
     CWaypoint* pWaypoint, long ActualWaypointID,
     long DestinationWaypointID, float MaxMovementDistanceSq,
     D3DXVECTOR3* pDestinationPos, float RandomFactor, long CostListID,
     bool GetCloserToDestination = true);

// Soll bei der Wegfindung ein einzelner Wegpunkt ausgeschlossen werden,
// dann sind die folgenden Funktionen zu verwenden:
long Select_WaypointInRange(CWaypoint* pWaypoint, long ActualWaypointID,
     long DestinationWaypointID, long IgnoreWaypointWithID,
     D3DXVECTOR3* pDestinationPos, long CostListID,
     bool GetCloserToDestination = true);

long Select_WaypointInRange_WithRandomMovementCostVariation(
     CWaypoint* pWaypoint, long ActualWaypointID,
     long DestinationWaypointID, long IgnoreWaypointWithID,
     D3DXVECTOR3* pDestinationPos, float RandomFactor, long CostListID,
     bool GetCloserToDestination = true);

// Sollen bei der Wegfindung mehrere Wegpunkte ausgeschlossen werden, dann
// sind die folgenden Funktionen zu verwenden:
long Select_WaypointInRange(CWaypoint* pWaypoint, long ActualWaypointID,
     long DestinationWaypointID, long* pIgnoreWaypointsWithID,
     long NumWaypointsToIgnore, D3DXVECTOR3* pDestinationPos,
     long CostListID, bool GetCloserToDestination = true);

long Select_WaypointInRange_WithRandomMovementCostVariation(
     CWaypoint* pWaypoint, long ActualWaypointID,
     long DestinationWaypointID, long* pIgnoreWaypointsWithID,
     long NumWaypointsToIgnore, D3DXVECTOR3* pDestinationPos,
     float RandomFactor, long CostListID,
     bool GetCloserToDestination = true);

// Soll bei der Wegfindung ein einzelner Wegpunkt ausgeschlossen
// und die Bewegungsreichweite eingeschränkt werden, dann sind
// die folgenden Funktionen zu verwenden:
long Select_WaypointInRange(CWaypoint* pWaypoint, long ActualWaypointID,
     long DestinationWaypointID, long IgnoreWaypointWithID,
     float MaxMovementDistanceSq, D3DXVECTOR3* pDestinationPos,
     long CostListID, bool GetCloserToDestination = true);

long Select_WaypointInRange_WithRandomMovementCostVariation(
     CWaypoint* pWaypoint, long ActualWaypointID,
     long DestinationWaypointID, long IgnoreWaypointWithID,
     float MaxMovementDistanceSq, D3DXVECTOR3* pDestinationPos,
     float RandomFactor, long CostListID,
     bool GetCloserToDestination = true);

// Sollen bei der Wegfindung mehrere Wegpunkte ausgeschlossen
// und die Bewegungsreichweite eingeschränkt werden, dann sind
// die folgenden Funktionen zu verwenden:
long Select_WaypointInRange(CWaypoint* pWaypoint, long ActualWaypointID,
     long DestinationWaypointID, long* pIgnoreWaypointWithID,
     long NumWaypointsToIgnore, float MaxMovementDistanceSq,
     D3DXVECTOR3* pDestinationPos, long CostListID,
     bool GetCloserToDestination = true);

long Select_WaypointInRange_WithRandomMovementCostVariation(
     CWaypoint* pWaypoint, long ActualWaypointID,
     long DestinationWaypointID, long* pIgnoreWaypointWithID,
     long NumWaypointsToIgnore, float MaxMovementDistanceSq,
     D3DXVECTOR3* pDestinationPos, float RandomFactor, long CostListID,
     bool GetCloserToDestination = true);