In der Realität ist eine direkte Bewegung auf ein Ziel zu normalerweise nicht möglich, denn durch Hindernisse und Wegbegrenzungen (Straßen, Flüsse, Wälder, Gebäude sowie andere KI-Einheiten) wird die Bewegungsfreiheit mehr oder weniger stark eingeschränkt. Die nachfolgende Abbildung veranschaulicht das Problem und zeigt zugleich eine mögliche Lösung auf.
Längere Wege werden in kürzere Abschnitte unterteilt, deren Anfangs- bzw. Endpunkte man als Wegpunkte bezeichnet. Entlang dieser Abschnitte finden sich im Idealfall keinerlei Hindernisse, welche die Bewegung der KI-Einheiten beeinträchtigen könnten. Durch Kombination benachbarter Wegabschnitte lässt sich eine Vielzahl von möglichen Wegen hin zum gewählten Ziel konstruieren. Die Aufgabe einer Wegfindungs-Routine besteht nun darin, möglichst geeignete Wege unter Berücksichtigung des momentanen Spielgeschehens zu errechnen. Die Länge eines Weges spielt in vielen Fällen nur eine untergeordnete Rolle. Weitaus wichtiger ist eine vernünftige Risiko-Chancen-Analyse. Betrachten wir einige Beispiele:
- Führt ein Weg durch sicheres Terrain oder befinden starke gegnerische Truppenverbände in unmittelbarer Nähe?
- Bietet ein alternativer Weg die Möglichkeit für einen Überraschungsangriff?
- Besteht die Möglichkeit, die Truppen aufzuteilen, um den Gegner zu zwingen, das Gleiche zu tun?
Ein in einem Spiel verwendetes Wegpunkte-System darf unter keinen Umständen statisch sein. Im Spielverlauf können zu jeder Zeit einzelne Wegabschnitte zeitweise oder dauerhaft unpassierbar werden, so z. B. die Brücke zwischen den Wegpunkten B und C. Des Weiteren sollten einzelne KI-Einheiten solche Wegabschnitte meiden, entlang derer eine große Zahl feindlicher Einheiten positioniert sind. Kurzum, der aktuelle Spielverlauf muss bei der Wegfindung stets berücksichtigt werden!!!
In Abhängigkeit davon, ob bei der Wegfindung der komplette Weg ermittelt werden soll oder ob lediglich der als nächstes anzusteuernde Wegpunkt von Interesse ist, lassen sich die zum Einsatz kommenden Algorithmen in zwei Klassen unterteilen. Zu den bekanntesten Vertretern der ersten Klasse gehören der A*- sowie der D*-Algorithmus. Zum Preis einer verhältnismäßig langen Rechenzeit (abhängig von der Komplexität der Spielewelt) wird der optimale Weg zum Ziel gefunden, sofern ein solcher existiert. In einem Spiel gibt es jedoch – wie zuvor besprochen – das Problem, dass sich der optimale Weg im Spielverlauf ständig verändert. Als Folge davon müssten für alle Einheiten die Wege kontinuierlich neu berechnet werden, was aufgrund der erforderlichen Rechenzeit unmöglich ist. Im Schlimmsten Fall bewegt sich eine KI-Einheit „sehenden Auges“ auf eine gegnerische Übermacht zu, weil in der zur Verfügung stehenden Zeit keine Ausweichroute berechnet werden konnte.
Die zweite Klasse von Algorithmen, die sogenannten Greedy-Verfahren, bieten einen möglichen Ausweg aus der Misere an. Besagte Algorithmen kommen mit sehr viel weniger Rechenzeit aus, weil der Weg schrittweise berechnet wird. Auf lokale Gegebenheiten – z. B. Gegnerische Einheiten in der Nähe eines benachbarten Wegpunkts – kann die KI deutlich flexibler reagieren. Zwar ist der gewählte Weg normalerweise nicht optimal, in der Regel jedoch gut genug.
Gute Wege zeichnen sich dadurch aus, dass die Bewegungskosten hin zum Ziel möglichst niedrig sind. Je länger ein Weg ist, umso größer sind die anfallenden Kosten. Steigungen, die zu überwinden sind, erhöhen die Bewegungskosten ebenfalls. Zusätzlich zu den sogenannten geometrischen Kosten müssen zudem eine größere Anzahl weiterer Faktoren berücksichtigt werden (schlechtes Wetter kann einen Weg schwer passierbar machen, Wegpunkte sollten gemieden werden, wenn sich in der Nähe eine große Zahl gegnerischer Einheiten befindet, etc.). Zum Speichern der abstandsunabhängigen Bewegungskosten der einzelnen Gegner-Fraktionen verwenden wir im weiteren Verlauf die CMovementCostList-Klasse. Benachbarte Wegpunkte, die sich durch einen möglichst kleinen MovementCostValue auszeichnen, werden bei der Wegfindung bevorzugt angesteuert, Wegpunkte mit einem höheren MovementCostValue werden entsprechend gemieden:
class CMovementCostList
{
public:
long NumWaypointsInRange;
float* MovementCostValue; // Wertebereich: 0 bis 2
CMovementCostList();
~CMovementCostList();
void Init_MovementCostList(long NumWaypoints);
void Update_MovementCostList(float* pMovementCostList);
void Update_MovementCostList(float* pMovementCostList,
long NumEntries);
void Update_MovementCostList(float* pMovementCostList, long Offset,
long NumEntries);
void Clone_MovementCostList(CMovementCostList* pMovementCostList);
};
{
public:
long NumWaypointsInRange;
float* MovementCostValue; // Wertebereich: 0 bis 2
CMovementCostList();
~CMovementCostList();
void Init_MovementCostList(long NumWaypoints);
void Update_MovementCostList(float* pMovementCostList);
void Update_MovementCostList(float* pMovementCostList,
long NumEntries);
void Update_MovementCostList(float* pMovementCostList, long Offset,
long NumEntries);
void Clone_MovementCostList(CMovementCostList* pMovementCostList);
};