A* beschleunigen: Heuristiken mit Landmarken verbessern
Improving Heuristics for A* Pathfinding
Red Blob Games zeigt, wie man die Heuristik von A* mit Landmarken verbessert, um die Suche deutlich zu beschleunigen. Die Idee: Man berechnet die kürzesten Wege zu einigen ausgewählten Punkten (Landmarken) vorab und nutzt die Dreiecksungleichung, um eine bessere untere Schranke für die verbleibende Distanz zu erhalten. Der Artikel erklärt die Theorie, die Platzierung von Landmarken, eine automatisierte Methode und die Implementierung – mit Demos aus Dragon Age und Cogmind.
„Das ist die Kernidee: Es ist unpraktikabel, alle Kosten zu allen Orten vorzuberechnen, aber wenn wir die Kosten zu einem bestimmten Ort vorberechnet haben, können wir das nutzen, um die Kosten zu einem anderen Ort zu schätzen.“
- simonw
> Ich habe diese Technik 2007 kennengelernt und 2015 versucht, sie aufzuschreiben. Ich merkte, dass ich sie nicht genug verstand, um sie erklären zu können. Ich habe sie 2016, 2018, 2019, 2022, 2024 und 2026 immer wieder studiert. Ich habe diese Seite viele Male aufgegeben und neu gestartet. Und bis 2026 denke ich, dass ich sie gut genug verstehe, um diese Seite zu schreiben.
Herausragend.
- Groxx
Red Blob Games hat einige Artikel der Spitzenklasse, ich kann nur empfehlen, weiter zu stöbern, falls dich das auch nur im Entferntesten interessiert.
- tkocmathla
Normalerweise würde ich keinen Tippfehler anmerken, aber dieser macht es schwierig, das Ausmaß der möglichen Verbesserungen zu erfassen:
> die Anzahl der Knoten, die A* erkunden muss, sinkt von 12693 auf 12693