KI-Programmierung Teil 10: Routinen für die Wegfindung

Nachdem wir unser Wegpunkte-System im letzten Kapitel implementiert haben, befassen wir uns an dieser Stelle mit der eigentlichen Wegfindung. In diesem Zusammenhang werden wir zwei exemplarische Fälle betrachten, zum einen die Zufallsbewegung und zum anderen die zielgerichtete Bewegung auf ein Ziel zu bzw. von einem Ziel weg. Die komplette Implementierung aller Wegfindungs-Routinen finden Sie in den nachfolgenden Programmbeispielen:

OpenGL-Programmbeispiel:

http://www.spieleprogrammierung.net/2010/04/opengl-3-wegpunkte-navigation-download.html

OpenGL-Framework-Programmbeispiel:

http://www.graphics-and-physics-framework.spieleprogrammierung.net/2011/05/tutorial-13-wegfindung-flocking.html

Zufallsbewegung

Den Super-Gau der Wegfindung haben Sie sicher alle schon einmal in dem einen oder anderen Spiel miterleben dürfen; eine Einheit steckt plötzlich fest und findet nicht mehr zurück auf den richtigen Weg. Die Ursache des Problems ist in der Regel ein fehlerhaft erstelltes Wegpunkte-System. Für dieses Worst-Case-Szenario benötigen wir daher eine oder mehrere Fallback-Routinen, mit deren Hilfe sich die betroffene Einheit aus ihrer Lage befreien kann.

Eine mögliche Lösung, um sich aus dieser Situation zu befreien, ist eine Bewegung hin zu einem zufällig ausgewählten Wegpunkt. Für die zufällige Auswahl eines neuen Wegpunkts stellt uns die CWaypoint-Klasse die überladene Methode Select_RandomWaypointInRange() zur Verfügung. Nach dem Zufallsprinzip wird ein in der Nachbarschaft liegender Wegpunkt (benachbarte Wegpunkte sind auf direktem Weg erreichbar) ausgewählt.

Zielgerichtete Bewegung auf ein Ziel zu bzw. von einem Ziel weg

Für die zielgerichtete Bewegung auf ein Ziel zu bzw. von einem Ziel weg stehen in den Programmbeispielen zwei Funktionstypen samt ihrer Überladungen zur Verfügung:

• Select_WaypointInRange()
• Select_WaypointInRange_WithRandomMovementCostVariation()

Im Unterschied zum ersten Funktionstyp werden beim zweiten Typ die Bewegungskosten 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.

Entsprechend der gewählten Funktions-Überladung wird die Auswahl eines der benachbarten Wegpunkte wie folgt eingeschränkt:

• Alle Wegpunkte werden bei der Wegfindung berücksichtigt.
• Alle Wegpunkte innerhalb einer vorgegebenen Maximaldistanz werden bei der Wegfindung berücksichtigt.
• Ein einzelner Wegpunkt wird bei der Wegfindung ausgeschlossen.
• Ein einzelner Wegpunkt wird bei der Wegfindung ausgeschlossen; nur die innerhalb einer vorgegebenen Maximaldistanz liegenden Wegpunkte werden bei der Wegfindung berücksichtigt.
• Mehrere Wegpunkte werden bei der Wegfindung ausgeschlossen.
• Mehrere Wegpunkte werden bei der Wegfindung ausgeschlossen; nur die innerhalb einer vorgegebenen Maximaldistanz liegenden Wegpunkte werden bei der Wegfindung berücksichtigt.

Die Auswahl eines benachbarten Wegpunkts verläuft maximal in zwei Schritten. Im ersten Schritt wird ausgehend vom zuletzt angesteuerten Wegpunkt ein benachbarter Wegpunkt gesucht, der sich möglichst nahe (GetCloserToDestination=true) beim bzw. möglichst fern (GetCloserToDestination=false) vom gewählten Ziel befindet. Durch Vermeidung von Umwegen werden die Bewegungskosten verringert.

Wird im ersten Schritt kein geeigneter Wegpunkt gefunden, dann wird in Schritt 2 ein Wegpunkt gesucht, der sich zumindest in Richtung (GetCloserToDestination=true) bzw. Gegenrichtung (GetCloserToDestination=false) des gewählten Ziels befindet.

Als Rückgabewert liefern alle Wegfindungs-Routinen den Index des gewählten Wegpunkts.

Hier nun der Source Code der einfachsten Select_WaypointInRange()-Funktion (alle benachbarten Wegpunkte werden bei der Wegfindung ohne Beschränkungen berücksichtigt):

long Select_WaypointInRange(CWaypoint* pWaypoint, long ActualWaypointID,
                            long DestinationWaypointID,
                            D3DXVECTOR3* pDestinationPos, long CostListID,
                            bool GetCloserToDestination)
{
    if(ActualWaypointID < 0)
        return -1;

    if(pWaypoint[ActualWaypointID].NumOtherWaypointsInRange == 0)
        return -1;

    D3DXVECTOR3 DistanceVector = *pDestinationPos -
                pWaypoint[ActualWaypointID].WorldSpacePosition;

    float distanceSq = D3DXVec3LengthSq(&DistanceVector);

    D3DXVECTOR3 NewDistanceVector;
    float newDistanceSq;

    long NumOtherWaypointsInRange = pWaypoint[ActualWaypointID].
                                    NumOtherWaypointsInRange;

    long IDOfSelectedWaypoint = -1;
    float savedDistanceSq = distanceSq;

    long id;
    float movementCost;

    if(GetCloserToDestination == true)
    {
        for(long i = 0; i < NumOtherWaypointsInRange; i++)
        {
            id = pWaypoint[ActualWaypointID].OtherWaypointInRange[i];

            // inaktiver Wegpunkt
            if(id < 0)
                continue;

            movementCost = pWaypoint[ActualWaypointID].
            MovementCostListForWaypointsInRange[CostListID].
            MovementCostValue[i];

            NewDistanceVector = *pDestinationPos -
                                 pWaypoint[id].WorldSpacePosition;

            newDistanceSq = movementCost*
                            D3DXVec3LengthSq(&NewDistanceVector);

            if(newDistanceSq <= savedDistanceSq ||
               DestinationWaypointID == IDOfSelectedWaypoint)
            {
                savedDistanceSq = newDistanceSq;
                IDOfSelectedWaypoint = id;

                if(DestinationWaypointID == IDOfSelectedWaypoint)
                    break;
            }
        }
        // Wegpunkt mit der besten Richtung zum Ziel suchen
        if(IDOfSelectedWaypoint == -1)
        {
            D3DXVECTOR3 Direction1;
            D3DXVec3Normalize(&Direction1, &DistanceVector);
            D3DXVECTOR3 Direction2;

            float dot;
            float savedDot = -1.0f;

            for(long i = 0; i < NumOtherWaypointsInRange; i++)
            {
                id = pWaypoint[ActualWaypointID].OtherWaypointInRange[i];

                // inaktiver Wegpunkt
                if(id < 0)
                    continue;

                NewDistanceVector = pWaypoint[id].WorldSpacePosition-
                                    pWaypoint[ActualWaypointID].
                                    WorldSpacePosition;

                D3DXVec3Normalize(&Direction2, &NewDistanceVector);

                movementCost = pWaypoint[ActualWaypointID].
                MovementCostListForWaypointsInRange[CostListID].
                MovementCostValue[i];

                dot = D3DXVec3Dot(&Direction1, &Direction2)+
                      1.0-movementCost;

                if(dot >= savedDot)
                {
                    savedDot = dot;
                    IDOfSelectedWaypoint = id;
                }
            }
        }
    }
    else //if(GetCloserToDestination == false)
    {
        for(long i = 0; i < NumOtherWaypointsInRange; i++)
        {
            id = pWaypoint[ActualWaypointID].OtherWaypointInRange[i];

            // inaktiver Wegpunkt
            if(id < 0)
                continue;

            movementCost = 2.0f-pWaypoint[ActualWaypointID].
            MovementCostListForWaypointsInRange[CostListID].
            MovementCostValue[i];

            NewDistanceVector = *pDestinationPos -
                                 pWaypoint[id].WorldSpacePosition;

            newDistanceSq = movementCost*
                            D3DXVec3LengthSq(&NewDistanceVector);

            if(newDistanceSq >= savedDistanceSq)
            {
                savedDistanceSq = newDistanceSq;
                IDOfSelectedWaypoint = id;
            }
        }
        // Wegpunkt mit der schlechtesten Richtung zum Ziel suchen
        if(IDOfSelectedWaypoint == -1)
        {
            D3DXVECTOR3 Direction1;
            D3DXVec3Normalize(&Direction1, &DistanceVector);
            D3DXVECTOR3 Direction2;

            float dot;
            float savedDot = 1.0f;

            for(long i = 0; i < NumOtherWaypointsInRange; i++)
            {
                id = pWaypoint[ActualWaypointID].OtherWaypointInRange[i];

                // inaktiver Wegpunkt
                if(id < 0)
                    continue;

                NewDistanceVector = pWaypoint[id].WorldSpacePosition-
                                    pWaypoint[ActualWaypointID].
                                    WorldSpacePosition;

                D3DXVec3Normalize(&Direction2, &NewDistanceVector);

                movementCost = pWaypoint[ActualWaypointID].
                MovementCostListForWaypointsInRange[CostListID].
                MovementCostValue[i];

                dot = D3DXVec3Dot(&Direction1, &Direction2)-
                      1.0+movementCost;

                if(dot <= savedDot)
                {
                    savedDot = dot;
                    IDOfSelectedWaypoint = id;
                }
            }
        }
    }
    return IDOfSelectedWaypoint;
}