A* Pfadfindungsalgorithmus
- Kirishanth Rajaraj
- 02. Sep, 2024
- Experimente
Pfadfindung
Hast du dich jemals gefragt, wie man den kürzesten möglichen Weg von Punkt A nach Punkt B finden kann? Die einfachste Methode wäre, alle möglichen Wege zu erkunden und sich den kürzesten auszusuchen. Das ist der Dijkstra-Algorithmus. Aber das ist ein sehr zeitaufwendiger und langsamer Prozess – sowohl für Menschen als auch für Computer. Deshalb gibt es den A*-Algorithmus. Hier ist ein Vergleich:
Wie A* funktioniert:
Hier ist die Karte, die ich oben verwendet habe. Lassen wir sie kleiner werden, um es besser zu verstehen:
Die Kernidee dieses Algorithmus ist, dass man für jeden benachbarten Punkt deiner aktuellen Position einen Wert setzt: die Distanz zum Startpunkt (G-Kosten, oben links) und die Distanz zum Zielpunkt (H-Kosten, oben rechts).
Man summierst diese Werte, was wir als F-Kosten definieren (mittlere große Zahl), vergleichst die F-Kosten aller Nachbarn und wählst den mit dem niedrigsten Wert – also den besten nächsten Schritt. Dies wiederholt man, bis man das Ziel erreicht.
Es gibt eine Wikipedia-Seite über den A*-Algorithmus mit einer Implementierung in Pseudocode, die ich als Referenz für meine Version in p5.js verwendet habe:
