Pathfinding
Pathfindingbzw.Wegfindungist in derInformatikdiealgorithmengestützteSuche nach dem oder den optimalen Wegen (englischpath– Pfad) von einem gegebenen Startpunkt zu einem oder mehreren Zielpunkten. Die Einsatzgebiete reichen vonNetzwerk-Flussanalyse überRoutenplanungbis zuComputerspielen.
Aufgabenspektrum
[Bearbeiten|Quelltext bearbeiten]
rot: Weg
blau: Zielfeld
grau: Hindernis
In vielen, aber nicht notwendigerweise inallenFällen ist die Suche nach demoptimalenWeg zwischen zwei Punkten auch die Suche nach derkostengünstigstenoderkürzestenRoutemit den wenigstenHindernissen.Dabei handelt es sich zwar um das „klassische Lernbeispiel “, aber die richtige Antwort auf ein Pathfinding-Problem ist in der Praxis nur selten auch wirklich dieLuftliniezwischen einem gegebenen Start- und einem gegebenen Zielpunkt. Die Suche wird häufig durch andere Faktoren mitbestimmt, die den Begriff desOptimumsverzerren und dadurch andere Routen sinnvoller erscheinen lassen, wie z. B.:
- nicht oder nur bedingt passierbare Hindernisse, die den direkten Weg versperren
- variableKostenin der Fortbewegung, z. B. für erhöhten Energieverbrauch gegen Strömung
- mehrdimensionale Kostenmodelle in der Fortbewegung, z. B. Zeit vs. Energie vs. Gefahren
- dieRasterungbzw.Diskretisierungder Umwelt, ähnlich einem Schach- oder Spielfeld
- die Notwendigkeit, auf der Route bestimmte Zwischenpunkte zu passieren oder günstige Abbruchmöglichkeiten für die Route offenzulassen
- nichtkartesische Koordinaten
Algorithmen
[Bearbeiten|Quelltext bearbeiten]Um den Anforderungen an Pathfinding je nach Kontext zu entsprechen, wurde in der Vergangenheit eine Vielzahl von Algorithmen entwickelt, von denen fast alle ihre speziellen Vor- und Nachteile haben.
Eine weit verbreitete Pathfinding-Methode ist derA*-Algorithmus,bei dem die Umgebung als Karte alsGraphinterpretiert wird und zur BerechnungHeuristikenverwendet werden. Zuerst müssen Start- und Zielknoten festgelegt werden. Danach erhält jedes Feld vom Startpunkt aus einen Wert, der proportional zur Entfernung ansteigt. Der optimale Weg ist derjenige, bei dem das Zielfeld den geringsten Wert erhält. Hindernisse, die zwar zu bewältigen sind, aber einen Zeitverlust aufbringen, können dadurch leicht berücksichtigt werden. (Ein Beispiel dafür wäre ein Sumpf, bei dem der Wert pro Feld beispielsweise 2 statt 1 ansteigt und deshalb möglicherweise ein schnellerer, aber längerer Weg außen herum existiert.)
Hat man keineHeuristik,um die Kosten zwischen Knoten abzuschätzen, kann man statt des A*-Algorithmus denAlgorithmus von Dijkstraverwenden. Um alle kürzesten Pfade von einem Knoten zu allen anderen Knoten auch in einem Graphen mitnegativenKantengewichten berechnen zu können, kann derBellman-Ford-Algorithmusverwendet werden. Sucht man nicht nur diegünstigstenPfade eines Knotens zu allen anderen Knoten im Graph, sondern die günstigsten Pfade zwischenallenKnotenpaaren, so kann man denMin-Plus-Matrixmultiplikations-Algorithmusoder denAlgorithmus von Floyd und Warshallverwenden.
Anwendungsbeispiele
[Bearbeiten|Quelltext bearbeiten]Im Computerspiele-Bereich reicht die Historie des Pathfindings von Spiele-Klassikern wiePac-Manbis in die Gegenwart. Während bei Pac-Man z. B. einfache Pathfinding-Algorithmen dafür sorgten, dass sich Gespenster als Computergegner durch ein virtuellesLabyrinthbewegten, dienen sie heute inEchtzeit-Strategiespielender Routenplanung ganzer Militärverbände und inEgo-Shooternder ausgefeilten Orientierung computergesteuerterBot-Gegner. Echtzeit-Strategiespiele basieren in der Regel auf zweidimensionalen Karten, die in einzelne Kacheln unterteilt sind. Besondere Schwierigkeiten ergeben sich z. B. bei Wegen, die dynamisch versperrt werden, etwa wenn mehrere Einheiten gleichzeitig eine enge Passage durchqueren. In Ego-Shootern, bei deren Karten die dritte Dimension eine wichtigere Rolle spielt, wird häufig mit Wegpunkten gearbeitet, an denen sich dieKünstliche Intelligenzorientiert. Fast immer ist „gutes “Pathfinding auch mit hoherKomplexitätverbunden. Im ComputerspielAge of Empires IIz. B. nahm allein das Pathfinding auf damals handelsüblicher Hardware 60 bis 70 Prozent der gesamten CPU-Leistung während des Spielens in Anspruch.[1]
Entsprechend große Anstrengungen werden unternommen, um Pathfinding-Algorithmen zu optimieren. Die Lösungskonzepte reichen von Vorberechnungen (d. h. Reduzierung derLaufzeitauf Kosten vonSpeicherbedarf) bis hin zu vorteilhaften Annahmen, die ein Programm bzgl. seines konkreten Anwendungsfalls bereits im Vorfeld treffen kann (z. B. „zwischen A und B liegt eine unüberwindbare Schlucht, über die nur eine einzige Brücke führt, also wird die Route zwangsläufig dort entlang führen und nicht woanders “).[2]
Verschiedene Algorithmen sind in der freienPython-BibliothekNetworkXimplementiert.[3]
Siehe auch
[Bearbeiten|Quelltext bearbeiten]Einzelnachweise
[Bearbeiten|Quelltext bearbeiten]- ↑Gamasutra,Dave C. Pottinger, 2000:„Terrain Analysis in Realtime Strategy Games “(vom 21. Dezember 2008 imInternet Archive) (MS Word;980 kB)
- ↑3dpathfinding.homeunix.org(vom 7. Juni 2007 imInternet Archive)Technische Universität München, Daniel Kastenholz, 2006:„3D Pathfinding “
- ↑Algorithms - Shortest Paths.In:NetworkX 2.2 documentation.Abgerufen am 24. Oktober 2018(englisch).