DPathfinding bzw. Wegfindung ist in der Informatik die algorithmengestützte Suche nach dem oder den optimalen Wegen (englisch path – Pfad) von einem gegebenen Startpunkt zu einem oder mehreren Zielpunkten. Die Einsatzgebiete reichen von Netzwerk-Flussanalyse über Routenplanung bis zu Computerspielen.
In vielen, aber nicht notwendigerweise in allen Fällen ist die Suche nach dem optimalen Weg zwischen zwei Punkten auch die Suche nach der kostengünstigsten oder kürzesten Route mit den wenigsten Hindernissen. 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 die Luftlinie zwischen einem gegebenen Start- und einem gegebenen Zielpunkt. Die Suche wird häufig durch andere Faktoren mitbestimmt, die den Begriff des Optimums verzerren und dadurch andere Routen sinnvoller erscheinen lassen, wie z. B.:
nicht oder nur bedingt passierbare Hindernisse, die den direkten Weg versperren
variable Kosten in der Fortbewegung, z. B. für erhöhten Energieverbrauch gegen Strömung
mehrdimensionale Kostenmodelle in der Fortbewegung, z. B. Zeit vs. Energie vs. Gefahren
die Rasterung bzw. Diskretisierung der 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
nicht kartesische Koordinaten
In vielen, aber nicht notwendigerweise in allen Fällen ist die Suche nach dem optimalen Weg zwischen zwei Punkten auch die Suche nach der kostengünstigsten oder kürzesten Route mit den wenigsten Hindernissen. 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 die Luftlinie zwischen einem gegebenen Start- und einem gegebenen Zielpunkt. Die Suche wird häufig durch andere Faktoren mitbestimmt, die den Begriff des Optimums verzerren und dadurch andere Routen sinnvoller erscheinen lassen, wie z. B.:
nicht oder nur bedingt passierbare Hindernisse, die den direkten Weg versperren
variable Kosten in der Fortbewegung, z. B. für erhöhten Energieverbrauch gegen Strömung
mehrdimensionale Kostenmodelle in der Fortbewegung, z. B. Zeit vs. Energie vs. Gefahren
die Rasterung bzw. Diskretisierung der 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
nicht kartesische Koordinaten
...als Startbare
Datei
Software zur Veranschaulichung der Zahlenumrechung
