Pathfinding

Grundidee und Ziel

Pathfinding beziehungsweise Wegfindung bezeichnet in der Informatik die algorithmengestützte Suche nach dem oder den optimalen Wegen von einem gegebenen Startpunkt zu einem oder mehreren Zielpunkten. Der englische Begriff „path“ bedeutet „Pfad“. Pathfinding wird unter anderem bei der Netzwerk-Flussanalyse, der Routenplanung und in Computerspielen eingesetzt.

In vielen, aber nicht in allen Fällen bedeutet die Suche nach dem optimalen Weg zugleich die Suche nach der kürzesten oder kostengünstigsten Route mit den wenigsten Hindernissen. Das ist das klassische Lernbeispiel. In der Praxis ist der optimale Weg jedoch nur selten einfach die Luftlinie zwischen Start- und Zielpunkt. Entscheidend ist, wie „optimal“ im jeweiligen Problem bestimmt wird.

Einflussfaktoren auf den optimalen Weg

Die direkte Route kann durch verschiedene Bedingungen ungeeignet oder unmöglich sein:

• Nicht oder nur bedingt passierbare Hindernisse können den direkten Weg versperren.
• Die Kosten der Fortbewegung können unterschiedlich sein. Gegen eine Strömung kann beispielsweise mehr Energie erforderlich sein.
• Es können mehrere Kosten gleichzeitig berücksichtigt werden, etwa Zeit, Energieverbrauch und Gefahren.
• Die Umwelt kann gerastert oder diskretisiert sein, also ähnlich wie ein Schach- oder Spielfeld in einzelne Felder eingeteilt werden.
• Eine Route kann bestimmte Zwischenpunkte enthalten müssen. Außerdem kann es sinnvoll sein, günstige Abbruchmöglichkeiten für die Route offenzulassen.
• Es können nicht kartesische Koordinaten verwendet werden.

Deshalb muss ein Pathfinding-Verfahren nicht nur Entfernungen, sondern je nach Anwendung auch Hindernisse, unterschiedliche Bewegungs- oder Zeitkosten und weitere Vorgaben berücksichtigen.

Wichtige Algorithmen

Für unterschiedliche Anforderungen wurden zahlreiche Algorithmen entwickelt. Fast alle besitzen besondere Vor- und Nachteile.

Eine weit verbreitete Methode ist der A*-Algorithmus. Dabei wird die Umgebung als Karte beziehungsweise als Graph interpretiert. Ein Graph besteht hier aus Knoten und Verbindungen zwischen ihnen. Zuerst werden Start- und Zielknoten festgelegt. Anschließend erhält jedes Feld ausgehend vom Startpunkt einen Wert, der proportional zur Entfernung ansteigt. Heuristiken, also Schätzungen für die Kosten zwischen Knoten, unterstützen die Berechnung. Der optimale Weg ist der Weg, bei dem das Zielfeld den geringsten Wert erhält.

Auch Hindernisse mit zusätzlichen Kosten können berücksichtigt werden. Ein Sumpf kann beispielsweise so behandelt werden, dass der Wert pro Feld um 2 statt um 1 ansteigt. Dadurch kann ein schnellerer, aber längerer Weg außen um den Sumpf herum günstiger sein als der direkte Weg durch ihn.

Wenn keine Heuristik vorhanden ist, mit der sich die Kosten zwischen Knoten abschätzen lassen, kann der Algorithmus von Dijkstra anstelle des A*-Algorithmus eingesetzt werden. Der Bellman-Ford-Algorithmus kann alle kürzesten Pfade von einem Knoten zu allen anderen Knoten berechnen, auch in einem Graphen mit negativen Kantengewichten. Sollen dagegen die günstigsten Pfade zwischen allen Knotenpaaren bestimmt werden, kommen der Min-Plus-Matrixmultiplikations-Algorithmus oder der Algorithmus von Floyd und Warshall infrage.

Pathfinding in Computerspielen und Optimierung

Im Bereich der Computerspiele reicht die Geschichte des Pathfindings von Spieleklassikern wie Pac-Man bis in die Gegenwart. In Pac-Man sorgten einfache Pathfinding-Algorithmen dafür, dass sich Gespenster als Computergegner durch ein virtuelles Labyrinth bewegten. In heutigen Echtzeit-Strategiespielen dienen solche Verfahren der Routenplanung ganzer Militärverbände; in Ego-Shootern unterstützen sie die Orientierung computergesteuerter Bot-Gegner.

Echtzeit-Strategiespiele verwenden in der Regel zweidimensionale Karten, die in einzelne Kacheln unterteilt sind. Eine besondere Schwierigkeit entsteht, wenn Wege dynamisch versperrt werden, etwa weil mehrere Einheiten gleichzeitig eine enge Passage durchqueren. Bei Ego-Shootern spielt die dritte Dimension eine größere Rolle. Dort wird häufig mit Wegpunkten gearbeitet, an denen sich die Künstliche Intelligenz orientiert.

„Gutes“ Pathfinding ist fast immer mit hoher Komplexität verbunden. Im Computerspiel Age of Empires II beanspruchte das Pathfinding auf damals handelsüblicher Hardware allein 60 bis 70 Prozent der gesamten CPU-Leistung während des Spielens.

Daher werden Pathfinding-Algorithmen gezielt optimiert. Ein Ansatz besteht in Vorberechnungen: Die Laufzeit wird reduziert, während der Speicherbedarf steigt. Ein anderer Ansatz nutzt vorteilhafte Annahmen über den konkreten Anwendungsfall. Liegt beispielsweise zwischen A und B eine unüberwindbare Schlucht, über die nur eine einzige Brücke führt, kann das Programm berücksichtigen, dass die Route zwangsläufig über diese Brücke verläuft. Verschiedene Pathfinding-Algorithmen sind in der freien Python-Bibliothek NetworkX implementiert.