Tutorial pathfinding2

Von Teekannen und Bäumen oder PATHFINDING

Einleitung

Hallo und willkommen zu meiner - etwas anderen – Methode eine Wegfinderoutine (Ich liebe dieses Wort... :) zu basteln. Ich sage hier bewusst basteln, weil es evtl. effektivere Systeme gibt. Doch seht selbst...

Was ist an dieser Methode so anders?

Flo hat hier auf DGL bereits eine Möglichkeit aufgezeigt, Pathfinding zu verwenden. Doch erlaubt dieses System "nur" 8 verschiedene Richtungen, in welche die Einheiten sich bewegen können. Dieses oder ähnliche Systeme findet man häufig in 2D Strategiespielen, wo sich die Einheiten ja auch nur in eine bestimmte Anzahl Richtungen drehen können.

Dieses System jedoch hat diese Beschränkung nicht. Einheiten können in alle Richtungen bewegt werden und dadurch wird die Strecke, welche die Einheiten zurücklegen müssen auf ein Minimum reduziert. Dieses (oder ein ähnliches System) kommt bei den meisten 3D Strategiespielen vor, wo sich die Einheiten ja bekanntlich frei drehen können. Doch dieses System erfordert mehr Aufwand. Auch von Mathe bleibt man nicht verschont. Allerdings hält sich der Aufwand in Grenzen und erfreut am Ende dann umso mehr, wenn alles klappt. Ebenso wie die von Flo verwendete Methode, benötigt auch dieses System ein Spielfeld, welches sich aus Quadraten zusammensetzt.

Ein kleines Beispiel

Ihr habt euch vielleicht schon gefragt, was der Titel des Tutorials bedeutet. Nun, es sei euch hiermit verraten. Um die Technik etwas anschaulicher zu gestalten, soll das System anhand eines einfachen Beispiels erläutert werden. In diesem Beispiel soll eine Teekanne auf einem grünen Feld das Ziel darstellen und das blaue Feld ist der Startpunkt einer Einheit, die zu dem grünen Feld gelangen möchte.

Wie man auf dieser Übersichtskarte erkennen kann, befinden sich Hindernisse (Berge) zwischen dem Startpunkt und dem Zielpunkt.

Die Technik dahinter

Soweit, so gut. Doch woher weiß die Einheit auf dem Startfeld nun, wie sie zur Teekanne kommt? Wir brauchen einen Algorithmus, der den kürzesten Weg vom Startpunkt zur Teekanne ermittelt und dabei noch einigermaßen schnell ist. Wenn man sich überlegt, welchen Weg man selbst in diesem Beispiel wählen würde, kommt man auf folgende Kriterien, die dieser Weg erfüllt:

• Der Weg ist gültig, ist also begehbar
• Der Weg geht um die Hindernisse herum
• Es ist der kürzeste Weg

Für den Fall, dass keine direkte Verbindung vom Startpunkt zum Ziel, wie in diesem Beispiel, möglich ist, muss also ein Weg um die Hindernisse herum gefunden werden. Dieser Weg muss die oben genannten Kriterien erfüllen. Unser Algorithmus muss bis her das hier können:

• Selbstständiges Erkennen der Hindernisse
• Feststellung der Eckpunkte der Hindernisse

Es fehlen noch zwei Punkte auf der Liste. Einer davon handelt von den Kanten der Hindernisse. Man wird sich jetzt vielleicht wundern und sich fragen, was denn die Kanten der Hindernisse für eine Rolle spielen. Dies sei hiermit erklärt: Um festzustellen, ob überhaupt ein Hinderniss im Weg liegt, werden wir unseren Wunsch-Pfad gegen jede Hindernis-Kante testen um so festzustellen, ob diese sich schneiden. Sollte dies der Fall sein, liegt eine Kante eines Hindernisses im Weg. Eine Kante jedoch kommt selten allein und wie es der Zufall will, hängt ein Hinderniss mit dran, was uns folglich den Weg versperrt. Dafür brauchen wir die Kanten der Hindernisse ;).

Der andere Punkt ist, aus den theoretisch möglichen Pfaden den Besten auszuwählen. Dies soll sich jetzt nur auf die Länge beziehen. Es gibt bekanntlich viele Wege nach Rom. So kann man eine Italien-Reise auch mit einem Ausflug in die Sahara kombinieren oder mal eben einen Abstecher nach Chile machen. Ähnlich ergeht es uns auch hier. Um den kürzesten Pfad zu ermitteln, werden wir von jedem möglichen Pfad die Länge der Einzelteile mit dem "Satz des Pythagoras" berechnen und diese zusammenzählen. Am Ende erhalten wir dann die Gesamtlänge eines Pfades. Machen wir das bei allen Pfaden, können wir anschließend bequem den kürzesten heraussuchen ;).

Somit steht fest, was unser Algorithmus können muss:

• Selbstständiges Erkennen der Hindernisse
• Feststellung der Eckpunkte der Hindernisse
• Berechnen der Kanten der Hindernisse
• Ermittlung des kürzesten Weges anhand dieser Daten

Erkennen der Hindernisse

Die sog. "obstacle detection" gestaltet sich besonders einfach: Da das Spielfeld in gleichmäßige Quadrate unterteilt ist, brauchen wir nur jedes Quadrat zu überprüfen, ob es durchlässig ist (eine Wiese oder ein Weg z.B.), oder ob es ein Hindernis darstellt (z.B. eine Mauer, ein Haus oder ein Berg). Diese Felder sind hier durchgängig rot gefärbt.

Eckpunkte der Hindernise errechnen

Auch hierbei kommt uns die quadratische Natur der Karte entgegen: Im Prinzip reicht es aus, wenn man die ganze Karte, Feld für Feld, abgeht und bei jedem "undurchlässigen" Feld dessen 8 unmittelbare Nachbarn überprüft. Hat z.B. ein einzelner Turm, der ein einziges Feld belegt, nur Wiese um sich herum, gleichen die Eckpunkte von diesem Hindernis den 4 Ecken des Quadrates auf dem er steht.

Anderes Beispiel: Betrachtet man das Ende eines langen Walls, der sich über mehrere Felder erstreckt, so hängen die Ecken dieses Hindernisses davon ab, in welcher Richtung diese Mauer weiterläuft. Geht sie z.B. nach Norden (Norden sei hier mal oben), befinden sich die beiden Eckpunkte dieses Teilstückes südlich davon (also unten). Hier sind nur zwei Eckpunkte nötig; im Gegensatz zu einem alleinstehenden Turm, um den man ja von allen Seiten herumgehen kann, hat man diese Freiheit nicht bei einem Hindernis, welches sich über mehrere Felder erstreckt. Man könnte zwar auch die beiden Eckpunkte nördlich des Feldes berücksichtigen, aber diese werden später nie benutzt werden, da der direkteste Pfad immer an den Ecken verläuft und niemals an den Kanten. Man möge mir hier für meine etwas unglückliche Ausdrucksweise verzeihen ;). Ich hoffe, man erkennt, was gemeint ist.

Ermitteln der Hindernis-Kanten

Die Kanten der Hindernisse werden auf ähnliche Art und Weise berechnet. Nimmt man sich einen einfachen Würfel zur Hand (zur Not tut es auch der Bildschirm vor dir ;) ), wird schnell klar, dass jede Kante von zwei Ecken begrenzt wird. Da unsere Karte Zweidimensional ist, kann auch jede Ecke max. zwei Kanten begrenzen. Also geht man auch hier die Karte Feld für Feld durch, bis man auf eine Ecke stößt. Man merkt sich diesen Punkt und geht weiter.

Stößt man nun auf die nächste Ecke, ist klar, dass zwischen diesen beiden Ecken eine Kante sein muss. Diese Prozedur macht man der Einfachheit halber bei den Linien und den Spalten getrennt. Also z.B. zuerst die horizontalen Linien und danach die vertikalen Linien.

Die Berechnung der Ecken und Kanten macht man wohl am Besten beim Laden des Levels oder beim Speichern im Leveleditor. Wenn sich an der Karte im Spielverlauf etwas ändert – sei es durch gefällte Bäume oder zerstörte Mauern – müssen diese Daten natürlich erneut berechnet werden.

Zusammenfügen des Puzzles

Vereinfachen wir die Situation zunächst etwas: Angenommen, es gäbe auf der Karte keine Hindernisse, so könnte die Einheit geradewegs zur Teekanne steuern. (Auf der Abbildung sind die ehemaligen Hindernisse rot dargestellt und die Punkte, an denen die Einheit normalerweise mit den Hindernissen kollidieren würde, durch 4 grüne Markierungen hervorgehoben)

Da wir für so etwas kein Pathfinding bräuchten, wurden uns von der Requisite ein paar Berge zur Verfügung gestellt, die auch prompt in der Gegend platziert wurden.

Wir haben also nun die Ecken der Hindernisse (Felder: schwarz; Hindernisse: rot; Ecken: blau):

Dadurch können wir uns leicht die Kanten der Hindernisse berechnen:

Es liegt nahe, das Gebiet, in dem nach den Eckpunkten der Hindernisse gesucht wird, so einzuschränken, wie man auf dem nebenstehenden Bild sehen kann. Doch mal angenommen, in diesem Gebiet existiert ein Hindernis, welches nicht vollständig in dieses Gebiet passt. Dann nämlich liegen dessen Ecken außerhalb des Gebietes und die Einheit würde geradewegs in einen Berg laufen, weil sie meint, dass kein Hindernis da ist. Beschäftigen wir uns nun mit der Ermittlung der Punkte, die in der Abbildung hellgrün markiert sind. Dazu prüfen wir zuerst, ob zwischen Start- und Zielpunkt ein Hindernis liegt. Dies wird festgestellt, indem man alle Hinderniskanten auf einen Schnittpunkt mit der Strecke Anfangspunkt-Zielpunkt prüft. Wenn sich keine Strecken schneiden, ist ein direkter Weg möglich. Ansonsten liegt ein Hindernis dazwischen.

Berechnen der Schnittpunkte

Mittels ein wenig Mathematik dürfte die Berechnung des Schnittpunktes zweier Geraden nicht sehr schwer fallen. Interessant wird es jedoch deswegen, weil wir keine Geraden brauchen, sondern mit Strecken arbeiten müssen. Zur Erinnerung: Geraden haben die, in diesem Fall unangenehme, Eigenschaft, dass sie nicht aufhören. Etwas Besserung verschaffen hier Halbgeraden, wirkliche Linderung verspricht aber nur die Strecke, die glücklicherweise einen Anfangspunkt und einen Endpunkt hat. Mithilfe der allgemeinen Geradengleichung sollte man in der Lage sein, eine Funktion aufzustellen, die einem zurückliefert, ob und wo zwei Strecken sich schneiden. Für alle die, wie ich, ein paar Probleme dabei hatten, sei dieses Stückchen Code ans Herz gelegt, das hauptsächlich durch die Beiträge von Lars im Forum entstanden ist:

function LineIntersects(LineA, LineB: TLine): boolean;
var
  p1, p2,
  q1, q2: TDot;
  a1, b1, c1,
  a2, b2, c2: Single;
  s: TDot;
begin
  p1.X := LineA.A.X; p2.X := LineA.B.X;
  q1.X := LineB.A.X; q2.X := LineB.B.X;
  p1.Y := LineA.A.Y; p2.Y := LineA.B.Y;
  q1.Y := LineB.A.Y; q2.Y := LineB.B.Y;

  a1 := p2.y - p1.y; b1 := p1.x - p2.x; c1 := a1*p1.x + b1*p1.y;
  a2 := q2.y - q1.y; b2 := q1.x - q2.x; c2 := a2*q1.x + b2*q1.y;

  s.x := (c1*b2-c2*b1)/(a1*b2-a2*b1); s.y := (a1*c2-a2*c1)/(a1*b2-a2*b1);

  Schnittpunkt.X := S.X;
  Schnittpunkt.Y := S.Y;

  Result := True;

  if (s.y > p1.y) and (s.y > p2.y) then Result := False;
  if (s.y > q1.y) and (s.y > q2.y) then Result := False;
  if (s.y < p1.y) and (s.y < p2.y) then Result := False;
  if (s.y < q1.y) and (s.y < q2.y) then Result := False;
  if (s.x > p1.x) and (s.x > p2.x) then Result := False;
  if (s.x > q1.x) and (s.x > q2.x) then Result := False;
  if (s.x < p1.x) and (s.x < p2.x) then Result := False;
  if (s.x < q1.x) and (s.x < q2.x) then Result := False;
end;

Erzeugung des Netzwerkes

Wir wissen nun, wie wir ermitteln können, ob Hindernisse im Weg sind und die Ermittlung der Eckpunkte sollte auch kein Problem darstellen. Somit haben wir eigentlich alles, was wir brauchen. Ab hier gibt es mehrere Möglichkeiten weiterzumachen. Man könnte z.B.:

• in einem einzigen Baum sämtliche möglichen Pfade speichern, was auf eine sehr kurze Zugriffszeit bei gleichzeitig erhöhten Speicherbedarf hinausläuft
• in jeder Node die von dieser Node erreichbaren Nodes speichern, was einen niedrigen Speicherverbrauch zur Folge hat bei einer durchaus akzeptablen Geschwindigkeit
• Jedesmal, wenn man einen Pfad braucht, alles neu berechnen ;)

Um den weiteren Ablauf zu erläutern, nehmen wir eine einfachere Karte zur Hand:

Man sieht hier bereits die möglichen Wege, die vom Start- zum Zielpunkt verfügbar wären. Prüft man nun, welche Nodes direkt vom Startpunkt sichtbar sind - also direkt erreichbar - stellt man fest, dass Node 1, 2 und Node 3 erreichbar sind. Das ist hier nur Zufall und nicht die Regel ;) Dargestellt in einer Baumstruktur sieht das in etwa so aus:

Was sollen diese roten Nodes (Node = Knoten) in dem Baum? Nun, ganz einfach: Wenn eine rote Node erreicht wird, wird der Baum an dieser Stelle nicht weiter abgegangen. Wäre dies nicht so, würde sich eine wunderbare Endlosschleife ergeben, gegen die selbst ein schwarzes Loch alt aus sähe ;). Um herauszufinden, ob eine Node bereits besucht wurde, speichert man die besuchten Nodes in ein Array und schaut jedes Mal im Array nach, ob die aktuelle Node darin enthalten ist. Wenn dem so ist, braucht diese Node nicht abgeganen zu werden, da wir hier schon einmal waren.

Als mögliche Pfade aus dem obigen Netzwerk ergeben sich:

• Start, 1, 2, 3, Ziel
• Start, 1, 3, Ziel
• Start, 2, 1, 3, Ziel
• Start, 2, 3, Ziel
• Start, 3, Ziel

Nun, im Prinzip war das auch schon das ganze Pathfinding. Aber auch nur prinzipiell... Denn gerade die Baumstruktur des Navigations-Netzwerkes schreit geradezu nach einer radikalen Optimierung. Und es gibt wahrlich noch genug Platz, wo man solche Optimierungen einbringen kann ;).

Ausblicke

Hier mal zur Abwechslung ein Screenshot vom Unreal Editor. Die Unreal-Engine verwendet ebenfalls Navigationsnetzwerke, damit die Bots ihren Weg finden. Die Äpfel stellen die PathNodes dar. In der Top-Ansicht sieht man, dass ein Pfad fehlt. Das ist aber ein Unreal-spezifisches Problem und hat mit unserem Pathfinding wenig gemeinsam.

Abschluss

Das hier ist mein erstes Tutorial, wo relativ viel Theorie vermittelt wird (werden soll ;) ). Es dauert ein bisschen, bis man bei Pathfinding brauchbare Ergebnisse hat, aber dann hat man ein solides System, welches einem durch alle Schwierigkeiten hindurch den Weg weisen wird ;).

Danken möchte ich an dieser Stelle dem Team von DGL und ganz besonders Phobeus, der mich beim Schreiben immer wieder mit diversen Erheiterungen... ähm... erheitert hat. ;)

Gruß,

Philipp