Labo de recherche de chemin A*

Déplacez-vous horizontalement ou verticalement sur une grille fixe 16 × 16. Chaque déplacement coûte un ; il n’y a ni diagonales ni cellules pondérées. Le coût du chemin compte les arêtes, donc un départ et un but partagés ont un coût zéro.

A* sélectionne une cellule ouverte de plus petit f = g + h. Ici g est le coût depuis le départ ; h est la distance de Manhattan, la distance euclidienne ou zéro (Dijkstra). Les égalités utilisent un plus petit h, puis l’ordre d’insertion ; améliorer une cellule ouverte conserve son ordre d’origine. Les trois heuristiques sont consistantes sur cette grille, donc les cellules fermées n’ont pas à être rouvertes. La recherche s’arrête quand le but est retiré de la frontière. Visitées compte ces retraits, y compris le but ; un pas retire au plus une cellule.

Comparer utilise le même plateau et la même politique d’égalité pour les trois exécutions. La grille affichée appartient à l’heuristique sélectionnée. Toutes renvoient un plus court chemin lorsqu’il est accessible ; les comptes de visitées dépendent du plateau et de la politique d’égalité. Cette petite implémentation pédagogique parcourt la frontière et a une borne au pire cas O(V²).

Choisissez un mode d’édition, puis cliquez ou glissez. Départ et but ne peuvent pas être peints comme murs ; placer un marqueur efface ce mur. Avec la grille focalisée, utilisez les flèches pour déplacer le curseur encadré et Espace ou Entrée pour éditer. Les coordonnées vont de 0 à 15, avec (0, 0) en haut à gauche.

Exécuter reprend une recherche en pause et redémarre une recherche terminée. Un pas met d’abord en pause. Réinitialiser la recherche conserve le plateau ; choisissez Vide pour l’effacer et restaurer les marqueurs. Éditer ou changer l’heuristique écarte la recherche et la comparaison. La vitesse n’affecte que l’animation. Quitter l’outil ou masquer la page l’arrête ; le plateau, l’heuristique, la vitesse, le mode d’édition et le curseur clavier sont conservés localement dans ce navigateur, mais pas la progression de la recherche. Une perte de focus ou une page masquée termine le tracé en cours. Les anciens plateaux enregistrés restent compatibles.

Sources : Hart, Nilsson et Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths (1968), pp. 101–102 ; correction de 1972 sur la consistance et les nœuds fermés.