Improving Heuristics for A* Pathfinding
Cette technique améliore l'heuristique d'A* en utilisant des points de repère («landmarks») pour mieux refléter les murs et la topologie du graphe, ce qui réduit le nombre de nœuds explorés. Un heuristique parfaite qui connaît tous les murs et le but existe mais est impraticable à calculer et à stocker pour chaque objectif. En précalculant pour chaque landmark les distances depuis tous les nœuds (avec Dijkstra ou BFS) on peut appliquer l'inégalité triangulaire pour obtenir la borne cost(B,X) ≥ cost(B,L) - cost(X,L) et combiner ces bornes (max) en une heuristique différentielle plus informée. Concrètement, on alloue un tableau cost[node][landmark], on lance une recherche depuis chaque landmark pour remplir ce tableau puis on remplace dans la fonction heuristique traditionnelle par le maximum entre l'heuristique de base et les différences de coûts (ou la valeur absolue pour les graphes non orientés), sans modifier l'algorithme A* lui‑même. Plusieurs landmarks couvrent mieux la carte, leur placement peut être manuel, basé sur analyses aléatoires ou automatisé, et il faut prendre en compte que des changements de graphe peuvent rendre l'heuristique temporairement sur‑estimée (non admissible) ou moins efficace; des démonstrations montrent de fortes améliorations sur labyrinthes et cartes pièce‑couloir.