Für die Pfadfindung benutzen wir eine Gittereinteilung der Karten gemäß ihrer Heightmapgrößen, die größten Karten haben dabei 256×256 Felder. Prinzipiell ist ein Feld dabei entweder betretbar oder unpassierbar. Ein kleines Beispiel:

Die schwarzen Felder umranden einen isolierten Bereich, der nicht betreten oder verlassen werden kann. Einheiten müssen ihren Weg um diesen Bereich finden. Als Grundlage dient die A*-Graphensuche.

Ein wesentliches Problem ist, dass eine A*-Suche über 256×256 Felder zu viel Zeit in Anspruch nehmen würde, sinnvolle Suchgrößen liegen wohl bei Ausschnitten von 60×60 Feldern. Das heißt, wir brauchen eine zweigeteilte hierarchische Suche, damit Einheiten auch über eine volle Kartenlänge navigieren können.

Unbewegliche Objekte auf der Karte (Fabriken, Flaggen, Dekoration) sind ebenfalls nicht passierbar, allerdings weder in Position noch Richtung mit dem Suchgitter angeglichen. Eine Fabrik, die vielleicht größenmäßig etwa 3×3 Feldern entsprechen könnte, kann völlig quer zum Gitter platziert sein. Es muss geklärt werden, welche der angrenzenden Felder noch als passierbar gelten und welche nicht mehr.

Andere Einheiten bzw. generell mobile Objekte stellen ebenfalls Hindernisse verschiedener Größen dar. Es braucht eine Strategie für die Wegsuche, halbwegs mit anderen Einheiten klarzukommen. Gerangel mit querlaufenden Einheitenverbänden wird sich kaum vermeiden lassen, aber zumindest innerhalb einer Gruppe, die einen gemeinsamen Bewegungsbefehl erhält, sollten möglichst wenig Reibereien entstehen.

Einheiten haben unterschiedliche Größen, grob als Abschätzung können Fahrzeuge evtl. etwa ein Feld belegen, Roboter eher 1/9 eines Feldes. Demzufolge könnten Roboter teilweise noch Felder betreten, die für Fahrzeuge bereits blockiert sind. Je nach Gemüt muss man dies entweder berücksichtigen und die Passierbarkeit von Feldern abweichend für Roboter und Fahrzeuge definieren, oder aber hier eben ein Auge zudrücken und ein etwas schlechteres Suchverhalten für die Roboter in Kauf nehmen. Theoretisch könnte man auch ein feineres Suchgitter für die Roboter anlegen, aber das vergrößert Problem Nr. 1 nur noch erheblich.

Roboter können durch Wasser schwimmen, Fahrzeuge nicht. Wasserfelder müssen entsprechend unterschiedlich behandelt werden. Natürlich ist die Passiergeschwindigkeit durchs Wasser geringer.

Brücken können Verbindungswege zwischen Stellen schaffen, die anderweitig nicht verknüpft wären. Brücken sind aber zerstörbar, d. h. die Verbindung kann variierend existieren oder auch nicht.

Da die detaillierte Pfadsuche über eine volle Map zu langsam ist, braucht es eine gröbere Einteilung, auf der ein erster gröberer Pfad gesucht werden kann. Zu diesem Zweck wird auf der Map eine Anzahl von Sektoren (haben nichts mit den zu erobernden Sektoren im Gameplay zu tun) konstruiert. Dazu wird, ausgehend von einem Feld auf der Karte, jedes benachbarte betretbare Feld zum Sektor hinzugefügt, allerdings nur innerhalb eines Rahmens von jeweils 32×32 Feldern. Dieser Fill-Ansatz wird so lange wiederholt, bis alle betretbaren Punkte der Karte zu einem Sektor gehören. Auf der vereinfachten Beispielsituation von oben würden z. B. die ersten zwei Sektoren wie folgt erstellt (in kleinerem Maßstab):

Von jedem Sektor wird ein ungefährer Mittelpunkt bestimmt, anschließend wird mit einer Graphensuche limitiert auf je zwei Sektoren überprüft, ob zwischen den Mittelpunkten der Sektoren eine direkte Verbindung besteht und wie teuer (Weglänge) diese ist. Daraus wird ein Wegnetz zwischen den Sektoren konstruiert, das von Einheiten für eine grobe Pfadsuche benutzt werden kann. Die detaillierte Pfadsuche ist dann nur noch zwischen den Pfadmittelpunkten von je zwei Sektoren nötig, um dort dynamisch auf Veränderungen des Suchgraphen zu reagieren.

Es ist klar, dass durch die gröbere Vorsuche eine Abschätzung getroffen wird, denn je nachdem, wo die Einheit sich befindet und wo sie hin will, mögen die Sektorenmittelpunkte eine gute oder mäßige Orientierung bieten. Dadurch kann es sein, dass insbesondere bei extrem verwinkelten Karten nicht aus jeder Situation wirklich der optimale Pfad gefunden wird. Auf normalen Karten sollte es aber eigentlich auch keine nennenswerten Patzer geben.

Brücken müssen zwingend als eigene Sektoren behandelt werden, diese werden gleich zu Beginn erstellt und die Felder der Brücke dann von der weiteren Sektorenkonstruktion ausgenommen. Auf diese Weise kann die Brückenzerstörung auch auf Sektorenebene korrekt behandelt werden. Wenn Brücken in normalen Sektoren eingelagert wären, könnte es leicht passieren, dass mit der Zerstörung von Brücken die Pfadsuche kein gültiges Ergebnis mehr finden würde. Bei Wasser könnte man das ähnlich machen, damit die unterschiedliche Passierbarkeit von Wasser zwischen Fahrzeugen und Robotern berücksichtigt werden kann. Alternativ könnte man auch für Fahrzeuge und Roboter ein unterschiedliches Sektorenmapping konstruieren, bei den Robotern wäre das Wasser dann einfach normal in einem Sektor enthalten. Könnte evtl. einfacher zu handhaben sein.

Zusammenfassend wäre das Vorgehen bei einer anstehenden Pfadsuche etwa dieses:

1. Ermittle die Felder, in denen Start- und Zielpunkt liegen.
2. Ermittle die Sektoren, in denen Start- und Zielfeld liegen.
3. Suche einen groben Pfad zwischen dem Start- und Zielsektor.
4. Plane auf feiner Ebene Pfade zwischen den gewählten Sektorenmittelpunkten sowie vom jeweiligen Sektormittelpunkt zum Start- bzw. Zielfeld
5. Glätte die Pfade, soweit möglich.

Es gibt neuere Ansätze für eine Modifizierung der A*-Pfadsuche, die koordinierte Truppenbewegungen unterstützt, aber das wird für uns wohl eher zu kompliziert. Ein ganz guter Kompromiss, der in meinen Augen funktionieren könnte, ist der: Nur momentan stehende Einheiten werden als Hindernisse in die Pfadsuche einbezogen (nur auf feiner Ebene, nicht auf Sektorenebene), sich bewegende Einheiten werden hingegen ignoriert. Dies sollte ermöglichen, dass in einer Gruppe von Einheiten, die einen Bewegungsbefehl erhält, die hinteren Einheiten nicht Pfade um ihre Vorderen planen, was ziemlich unsinnig wäre. Um Kollisionen trotzdem aus dem Weg zu gehen, werden Steering Behaviours verwendet, die den Wegpunkten der Pfadsuche folgen und Hindernissen dynamisch ausweichen. Wenn sie sich dabei selbst ins “Abseits” manövrieren, müssen sie ihren Pfad von der aktuellen Position neu planen.

Falls eine Suche zwischen zwei Sektorenmittelpunkten fehlschlägt, weil der Durchgang von stehenden Einheiten versperrt wird, wird die Sektorenverbindung temporär gestrichen und eine neue Suche auf Sektorenebene gestartet.