Die Pfadfindung in Warman sitzt auf dem Terrain-System auf. Die Karte ist keine flache Ebene. Sie hat Klippen, erhöhte Plattformen, Rampen zwischen Höhenebenen und Wasser, das passierbar sein kann oder nicht. Die Pfadfindung muss all das bewältigen und gleichzeitig in einer Lockstep-Simulation laufen, in der jeder Client identische Ergebnisse berechnen muss.
Das 3D-Gitter
Das Gitter ist dreidimensional: X und Z bilden die Terrainoberfläche ab, Y die Höhenebenen. Jede Terrain-Zelle wird durch einen Dichtefaktor unterteilt (derzeit 2, sodass jede 1x1-Terrain-Zelle zu einem 2x2-Cluster von Pfadfindungsknoten wird). Die Y-Achse wird durch den Höhenbereich der Klippenschicht bestimmt. Wenn die höchste Klippe in einem Raum 4 Einheiten hoch ist, allokiert das Gitter genug Y-Ebenen, um das plus einen Puffer abzudecken.
Knoten werden nur dort erstellt, wo Terrain begehbar ist. Klippen-belegte Zellen, nicht-begehbare Texturtypen (wie tiefes Wasser oder Leere) und Out-of-Bounds-Positionen erzeugen keine Knoten. Das Gitter ist dünn besetzt, ein 30x30-Terrain-Raum mit einer Höhenebene erzeugt etwa 3.600 Knoten, nicht die 30x30xN, die ein vollständig gefülltes 3D-Array nahelegen würde.
Rampenknoten
Rampen sind der kniffligste Teil. Eine Rampe verbindet zwei Höhenebenen, sodass die Knoten auf einer Rampenzelle interpolierte Y-Positionen brauchen. Warman teilt den Höhenübergang der Rampe in Achtel: Das untere Knotenpaar sitzt bei 1/8 und 3/8 der Höhenstufe, das obere bei 5/8 und 7/8. Das erzeugt eine glatte Steigung, der Einheiten folgen können, ohne zwischen Höhenebenen zu teleportieren.
Die Interpolation hängt von der Rampenrichtung ab. Eine nach Norden gerichtete Rampe hebt die Knoten entlang der Z-Achse an, während eine nach Osten gerichtete Rampe sie entlang der X-Achse anhebt. Jede der vier Knotenpositionen innerhalb einer Zelle bekommt einen anderen Höhenversatz basierend auf dieser Richtung.
Oberflächenkonnektivität
Eine der wichtigeren Optimierungen ist die Oberflächenerkennung. Nachdem das Gitter aufgebaut ist, läuft eine BFS (Breitensuche) von jedem unbesuchten Knoten aus und flutet durch begehbare Nachbarn, um zusammenhängende Regionen zu entdecken. Jede Region wird zu einer „Oberfläche", einem HashSet<Node>, das jeden Knoten enthält, der von jedem anderen Knoten in der Menge erreichbar ist.
A*-Implementierung
Das A* selbst ist Standard: Ein Binary Heap für die offene Menge, ein HashSet für die geschlossene Menge, Manhattan-Distanz als Heuristik (da diagonale Bewegung auf einem Gitter gleich viel kostet wie kardinale). Nachbarn umfassen alle 16 anliegenden Positionen: 8 horizontale (4 kardinale + 4 diagonale) auf derselben Y-Ebene, plus 8 weitere eine Y-Ebene höher und tiefer. Das behandelt das Betreten und Verlassen von Rampen und Klippenkanten.
Diagonale Bewegung hat eine Einschränkung: Eine Einheit kann sich nur diagonal bewegen, wenn beide anliegenden kardinalen Zellen begehbar sind. Das verhindert Eckenabschneiden durch Wände. Wenn eine Einheit auf Position (5, 5) steht und sich zu (6, 6) bewegen will, müssen sowohl (6, 5) als auch (5, 6) begehbar sein. Andernfalls ist die Diagonale blockiert.
AstarModifiers
Nachdem das Gitter aus Terrain-Daten aufgebaut ist, bekommen AstarModifier-Komponenten die Gelegenheit, es zu verändern. Das sind MonoBehaviours, die im Level platziert werden und Knoten hinzufügen, entfernen oder modifizieren können. Ein Brücken-Doodad könnte begehbare Knoten auf einer bestimmten Höhe hinzufügen, die keiner Terrain-Zelle entsprechen. Ein blockierter Durchgang könnte Knoten als nicht-begehbar markieren. Modifikatoren werden in Prioritätsreihenfolge ausgeführt und können Mehrhöhen-Plattformen erzeugen, die das Terrain-System allein nicht darstellen kann.
Nach allen Modifikatoren wird die Oberflächen-BFS neu berechnet, damit die Konnektivität korrekt bleibt.
Der Agent
Der AstarAgent sitzt auf jeder Einheit und verwaltet die tatsächliche Bewegung. Wenn eine Einheit sich bewegen will, erhält der Agent einen Richtungsvektor, berechnet die gewünschte Position und prüft, ob der Zielknoten begehbar ist. Wenn ja, bewegt sich die Einheit dorthin. Wenn nicht, versucht der Agent achsengetrennte Bewegung, erst nur X, dann nur Z, um Wandgleiten zu ermöglichen. Das verhindert, dass der Spieler an diagonalen Wänden stecken bleibt.
Der Agent behandelt auch ein subtiles Problem mit Rampen. Einheiten, die sich auf Rampen bewegen, können eine Y-Position haben, die durch Interpolation leicht vom Gitter abdriftet. Wenn die aktuelle Position keinen gültigen Knoten auflöst, schnappt der Agent das Y zurück auf die Position des letzten bekannten guten Knotens, bevor der nächste Schritt verarbeitet wird. Das verhindert das „An-der-Rampenkante-stecken"-Problem, bei dem das Y einer Einheit technisch zwischen zwei Gitterebenen liegt und keine sie beansprucht.