Erfolgreiche Spieleentwicklung

wird auf diese Weise gezwungen, seine Einheiten aufzuteilen, um den Gegner abzufangen.
Bewegen sich vorgelagerte Einheiten auf einem Umweg zu ihrem Ziel, gewinnen die nachrückenden Einheiten etwas Zeit, um aufzuschließen, sodass der gemeinsame Bestimmungsort möglichst zeitgleich erreicht wird.
    Kommen wir nun zu den weiteren Anforderungen, die an die Arbeit einer vernünftigen Wegfindungsroutine zu stellen sind:
Der benötigte Zeitaufwand für die Wegfindung sollte möglichst gering sein.
Die Wegfindungsroutine muss auf Veränderungen in der Umgebung reagieren können. Beispielsweise könnte eine Brücke zeitweise unpassierbar werden oder eine Straße wird wieder instandgesetzt.
Der Spielverlauf (die momentane strategische bzw. taktische Situation) muss berücksichtigt werden. Sind feindliche Einheiten entlang eines Weges postiert, muss gegebenenfalls eine alternative Route gefunden werden.
    Zwei der bekanntesten Algorithmen, die im Rahmen der Wegfindung zum Einsatz kommen, sind der A*- sowie der D*-Algorithmus [2]. In seiner Grundform ist der A*-Algorithmus für die Echtzeitwegfindung in Computerspielen ungeeignet. Wird ein Wegabschnitt nach Abschluss der Berechnungen plötzlich unpassierbar (die Straße wird zerstört, gegnerische Einheiten errichten eine Blockade etc.), muss der Weg komplett neu bestimmt werden. Mithilfe des D*-Algorithmus ist es jedoch möglich, Teile des Weges neu zu berechnen, was insbesondere bei sehr langen Wegen zu einer wesentlichen Reduktion der Rechenzeit führt.
    Sowohl der A*- wie auch der D*-Algorithmus wurden dafür entworfen, immer den optimalen (den kürzesten) Weg zum Ziel zu finden, sofern er existiert. In einem Spiel ist die Suche nach dem optimalen Weg in der Regel jedoch gar nicht notwendig und manchmal sogar kontraproduktiv. Um möglichst viel Rechenzeit einzusparen, sollte man daher zunächst auf ein sehr viel schnelleres Suchverfahren zurückgreifen, bei dem ein Weg schrittweise bestimmt wird ( Greedy-Algorithmus ). Im Unterschied zum A*- bzw. D*-Algorithmus besitzt ein KI-Objekt hierbei keine Informationen über den kompletten Weg. Lediglich der als nächstes anzusteuernde Wegpunkt ist bekannt.
    Die Funktionsweise des im KI-Demo2 verwendeten Greedy-Algorithmus ist denkbar einfach. Bei Programmstart werden zunächst für alle Wegpunkte die Indizes der in der Nachbarschaft liegenden Wegpunkte aus einer Datei eingelesen, bzw. nach den Vorgaben des KI-Programmierers ermittelt (benachbarte Wegpunkte lassen sich auf direktem Weg erreichen). Zur Laufzeit lässt sich ein neuer Wegpunkt in maximal zwei Schritten bestimmen:
Ausgehend vom zuletzt angesteuerten Wegpunkt wird ein benachbarter Wegpunkt ausgewählt, der möglichst nahe (Annäherung) beim bzw. möglichst fern (Flucht) vom gewählten Ziel liegt (geringe Bewegungskosten durch Vermeidung von Umwegen).
Wird im Rahmen von Schritt 1 kein geeigneter Wegpunkt gefunden, dann wird ein benachbarter Wegpunkt ausgewählt, der zumindest in Richtung (Annäherung) bzw. in Gegenrichtung (Flucht) des gewählten Ziels liegt.
    Temporär oder permanent blockierte Wegpunkte (eine zerstörte Brücke, blockierte Straße etc.) werden bei der Wegfindung ignoriert. Bei der Berechnung der Bewegungskosten wird zusätzlich zum Abstand eines Wegpunkts zum gewählten Ziel ein weiterer Kostenfaktor (Standardwert: 1; Wertebereich: 0-2) berücksichtigt. Es ist Aufgabe des KI-Programmierers, zu entscheiden, welche Daten in die Berechnung dieses Faktors einfließen sollen. Betrachten wir hierzu einige Beispiele:
Wegpunkt liegt auf einer Anhöhe: Kostenfaktor > 1
KI-Einheiten sollen sich gezielt bei einem Wegpunkt sammeln: Kostenfaktor = 0
KI-Einheiten sollen einen Wegpunkt unter allen Umständen meiden: Kostenfaktor >> 1
    Im Detail erklärt
Wegfindung – Einführung: http://www.spieleprogrammierung.net/2010/03/ki-programmierung-teil-7-wegfindung.htm l
Entwurf eines Wegpunkte-Systems: http://www.spieleprogrammierung.net/2010/03/ki-programmierung-teil-9-entwurf-eines.html
Routinen für die Wegfindung: http://www.spieleprogrammierung.net/2010/03/ki-programmierung-teil-10-routinen-fur.html

4.5 Flocking (Schwarmverhalten)
    Als Spieler erwarten wir nicht nur immer detailreichere Umgebungen, sondern darüber hinaus auch lebendig wirkende Spielewelten. Verantwortlich hierfür ist die sogenannte Umgebungs-KI. Städte müssen selbstverständlich von Menschen bevölkert sein, und Vogelschwärme am Himmel sind mittlerweile genauso ein Muss wie Fischschwärme unter