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.“