Spiele wie Stronghold Crusader (Firefly Studios, 2002) setzen einen Grafikstil um, der allgemein gerne als 2.5D Bezeichnet wird. In diesem Beitrag wird ein Ansatz erläutert, das Pathfinding (Wegfindung) von Agenten auf einem 2.5D Raster umzusetzen. Zusätzlich, wie spezifische Problemstellungen des Genres gelöst wurden und wie das Pathfinding erweitert werden kann.
Für das Pathfinding von Agenten auf einem 2.5D Raster wird eine angepasste Form des A*-Algorithmus verwendet. Falls Fragen dazu bestehen, was der A*-Algorithmus ist: In einem früheren Artikel habe ich seine Funktionsweise erklärt. Doch was genau bedeutet 2.5D eigentlich? Nun, es heißt, dass Grafiken zwar im zweidimensionalen Raum platziert und gerendert werden, doch das Bild, was sie ultimativ ergeben, soll den Anschein erwecken drei Dimensionen abzubilden.
Einheiten müssen die Möglichkeit haben auf Mauern zu steigen, wenn ein geeigneter Aufgang vorhanden ist. Gruppen von Einheiten müssen mit einem einzigen Befehl zur einer Zielposition gehen können und dort eigene Positionen einnehmen. Beide Problemstellungen wurden gelöst, indem die einzelnen Knoten des A*-Algorithmus statt der boolischen Information, ob der Knoten begehbar ist oder nicht, Informationen über sowohl die vertikale Höhe des Knoten enthalten, als auch, ob schon eine Einheit diesen Knoten belegt. Mit diesen beiden Informationen können Regeln für den A*-Algorithmus definiert werden.
Ein benachbarter Knoten gilt nur als begehbar, wenn seine Höhendifferenz einen vorher festgelegten Wert x nicht überschreiten. Durch diese Regel können sowohl Treppenaufgänge, als auch Steigungen im Terrain realisiert werden. Wenn x = 5 und benachbarte Felder wie in der nächsten Abbildung eine zusammenhängenden Mauerformation bilden, ist es für einen Agenten möglich einen Pfad von Punkt A zu Punkt B zu errechnen.
In der Regel möchten Spieler:innen nicht nur eine einzelne Einheit zu einem gewünschten Punkt bewegen, sondern eine Einheitengruppe. Dabei stellt sich einmal die Problematik, dass nicht alle Einheiten die selbe Zielposition haben können. Dieses Problem wird dadurch gelöst, dass vor der Berechnung eines Pfades jeder Einheit eine eigene Zielposition (um die Position des Mauszeigers) zugewiesen wird. Eine weitere Problematik bezieht sich auf die Positionierung der Einheitengruppe, wenn der Zielpunkt auf einer Mauer liegt.
Für die Positionierung von Einheitengruppen mit einer einzigen Zielposition, wird durch die Einheitengruppe iteriert. Die erste Einheit beansprucht den Zielknoten für sich. Für jede weitere Einheit werden geeignete, naheliegende Knoten ausgewählt. Bei der Auswahl wird unter allen Knoten nach Höhe sortiert und anschließend nach Entfernung zum Zielknoten. Die Priorisierung des Höhenwerts bei der Sortierung hat zur Folge, dass die Einheiten sich eher auf naheliegenden Knoten positionieren, welche die selbe oder eine ähnliche Höhe zum Zielknoten haben.
Wenn zum Beispiel eine Gruppe von Fernkampf-Einheiten zum Knotenpunkt B geschickt wird, nehmen die Einheiten die verbleibenden Knoten auf der Mauer ein, anstatt die direkt benachbarten Knoten oberhalb, rechts und links von Punkt B wählen.
Mit einem Pathfinding dieser Art ist es möglich Einheiten auf offener Fläche oder verwinkelten Mauerstrukturen zu platzieren, ohne einen anderen Algorithmus nutzen zu müssen. Das verringert nicht nur die Fehleranfälligkeit, sondern erhöht auch die Wartbarkeit des Codes.