FR 
English
Українська🎮 Pathfinding NPC de jeu — Recherche A* en direct
Regardez le véritable algorithme de recherche A* explorer en direct les nœuds d'une carte de jeu simulée selon le coût réel f=g+h, trouvant des chemins de PNJ prouvés les plus courts autour des obstacles, plus vite que Dijkstra pur.
À propos de la simulation de recherche A* en direct
Les moteurs de jeu se posent constamment la même question : quel est le chemin praticable le plus court d'un PNJ vers sa cible sur une carte pleine de murs, de terrain et d'autres obstacles ? La recherche A* (Hart, Nilsson & Raphael, 1968) est la réponse de référence — une recherche de graphe best-first qui maintient une véritable file de priorité ordonnée selon f(n) = g(n) + h(n), où g(n) est le coût réel accumulé depuis le départ et h(n) est une estimation heuristique admissible de la distance restante. Cette simulation exécute l'algorithme réel — véritable ensemble ouvert, véritable ensemble fermé, véritables pointeurs parents — sur une carte de jeu en grille que vous pouvez modifier, et exécute simultanément l'algorithme de Dijkstra pur (A* avec h(n) = 0) sur la carte identique, afin que vous puissiez observer, nœud par nœud, exactement combien de travail l'heuristique permet d'économiser.
🔬 Ce que ça montre
Deux grilles côte à côte partageant une même carte d'obstacles : la grille de gauche exécute un véritable A* avec une heuristique de distance octile, la grille de droite exécute Dijkstra avec l'heuristique forcée à zéro. Les cellules cyan sont dans l'ensemble ouvert (découvertes, mises en file, pas encore expansées), les cellules ambre sont dans l'ensemble fermé (expansées, finalisées), et le chemin de couleur accentuée est l'itinéraire le plus court reconstruit via les pointeurs parents une fois le nœud objectif extrait. Les compteurs en direct totalisent le nombre réel de nœuds que chaque file de priorité a effectivement extraits.
🎮 Comment l'utiliser
Choisissez un mode — Mur, Départ ou Objectif — puis cliquez sur n'importe quelle cellule de l'une ou l'autre grille pour modifier la carte partagée ; les deux recherches se relancent instantanément. Utilisez Labyrinthe aléatoire pour générer une nouvelle disposition d'obstacles, Effacer les murs pour repartir d'un terrain ouvert, et le curseur de vitesse d'expansion pour ralentir la révélation à des fins pédagogiques ou l'accélérer pour voir immédiatement le chemin final. Relecture redémarre l'animation nœud par nœud sans recalculer la recherche.
💡 Le saviez-vous ?
Puisque l'algorithme de Dijkstra est mathématiquement identique à A* avec h(n)=0, les deux panneaux exécutent exactement le même chemin de code avec un seul nombre modifié — c'est pourquoi il s'agit d'une comparaison équitable, à conditions égales, plutôt que de deux implémentations sans rapport. Sur des cartes ouvertes, A* expanse souvent moins de la moitié des nœuds que Dijkstra ; sur des cartes où un mur force les deux algorithmes à faire un long détour, l'écart se réduit car aucun ne peut raccourcir la géométrie que l'heuristique ne peut pas voir à travers.
Questions fréquentes
Qu'est-ce que la recherche A* et en quoi diffère-t-elle de l'algorithme de Dijkstra ?
Les deux sont des recherches de graphe best-first qui extraient à chaque étape le nœud de plus faible coût d'une file de priorité (l'ensemble ouvert). L'algorithme de Dijkstra ordonne cette file uniquement selon g(n), le coût réel accumulé depuis le nœud de départ, si bien qu'il explore vers l'extérieur dans toutes les directions de façon égale, comme des ondulations sur un étang. A* ordonne la même file selon f(n) = g(n) + h(n), en ajoutant une estimation heuristique admissible h(n) de la distance restante jusqu'à l'objectif. Ce terme supplémentaire oriente l'expansion vers l'objectif, si bien qu'A* ferme généralement bien moins de nœuds que Dijkstra tout en garantissant de retourner le même chemin de coût minimal, car une exécution de Dijkstra est mathématiquement identique à une exécution d'A* avec h(n) = 0 pour chaque nœud — c'est exactement ainsi que cette simulation implémente la comparaison sur une carte partagée.
Qu'est-ce qui rend une heuristique admissible, et pourquoi cela garantit-il qu'A* trouve le chemin le plus court ?
Une heuristique h(n) est admissible si elle ne surestime jamais le coût réel restant du nœud n à l'objectif — elle peut sous-estimer ou être exacte, mais jamais trop optimiste dans le mauvais sens. Sur une grille où les déplacements diagonaux coûtent √2 et les déplacements orthogonaux coûtent 1, la distance en ligne droite (octile) jusqu'à l'objectif est toujours inférieure ou égale au coût réel restant du chemin autour des obstacles, elle est donc admissible. Avec une heuristique admissible, A* est garanti de ne jamais finaliser un nœud avec une valeur g sous-optimale : tout chemin qu'il déclare le plus court l'est réellement, ce qui explique pourquoi la simulation peut affirmer qu'A* et Dijkstra aboutissent toujours au même coût de chemin, pas seulement à un coût similaire.
Qu'est-ce que la distance octile et pourquoi est-elle utilisée sur les cartes en grille autorisant le déplacement en diagonale ?
La distance octile est l'heuristique pour les grilles à 8 directions : étant donné |dx| et |dy| cellules de séparation horizontale et verticale, le chemin le plus court possible (en ignorant les obstacles) se déplace en diagonale min(|dx|,|dy|) fois au coût de √2 chacune, puis parcourt les |dx|−|dy| cellules restantes en orthogonal au coût de 1 chacune. La formule (|dx|+|dy|) + (√2−2)·min(|dx|,|dy|) calcule exactement cela. La distance euclidienne ou de Manhattan classique surestimerait (brisant l'admissibilité sur une grille à déplacement diagonal) ou sous-estimerait de façon trop lâche, c'est pourquoi la distance octile est le choix serré et admissible que cette simulation utilise pour le h(n) d'A*.
Pourquoi A* expanse-t-il généralement moins de nœuds que Dijkstra ?
Dijkstra n'a aucune notion de l'emplacement de l'objectif, si bien que son front d'expansion croît comme un front d'onde à peu près circulaire centré sur le départ, touchant chaque nœud dans un certain rayon de coût avant d'atteindre l'objectif. L'ordre f = g + h d'A* maintient près de la tête de la file de priorité les nœuds qui pointent vers l'objectif, si bien que son front s'étire en une forme allongée orientée vers l'objectif et saute de grandes régions de l'autre côté de la carte que Dijkstra devrait quand même visiter. Les compteurs en direct de cette simulation totalisent le nombre réel de nœuds que chaque algorithme a effectivement extraits et fermés de sa propre file de priorité sur la carte d'obstacles identique, donc l'écart que vous voyez est une différence réelle et mesurée plutôt que supposée — et sur des cartes où la ligne droite vers l'objectif est bloquée par un grand obstacle, l'écart peut se réduire voire disparaître, ce que la simulation montrera honnêtement.
Quelle est la différence entre l'ensemble ouvert et l'ensemble fermé ?
L'ensemble ouvert est le front : les nœuds qui ont été découverts (atteints depuis un voisin) et placés dans la file de priorité, mais pas encore expansés. L'ensemble fermé regroupe les nœuds déjà extraits de la file et dont tous les voisins ont été examinés — leur coût g le plus court depuis le départ est finalisé et ne changera plus. Dans la visualisation, les cellules cyan sont dans l'ensemble ouvert (candidats encore considérés) et les cellules ambre sont dans l'ensemble fermé (entièrement traitées) ; une fois l'objectif extrait de l'ensemble fermé, l'algorithme s'arrête et reconstruit le chemin en remontant les pointeurs parents de l'objectif vers le départ.
A* peut-il échouer à trouver le chemin le plus court, ou échouer à trouver un chemin quelconque ?
A* est garanti de trouver le chemin le plus court chaque fois qu'il en existe un et que son heuristique est admissible — l'heuristique de distance octile de cette simulation satisfait cette condition sur chaque carte que vous construisez. Ce qu'A* ne peut pas faire, c'est trouver un chemin qui n'existe pas : si vous encerclez complètement l'objectif de murs, A* et Dijkstra épuiseront tous deux leurs ensembles ouverts et signaleront qu'aucun chemin n'a été trouvé, ce que le panneau de statistiques affichera explicitement plutôt que d'afficher silencieusement un itinéraire périmé.
Une file de priorité en tas binaire expanse les nœuds dans un véritable ordre best-first selon f(n)=g(n)+h(n) sur la grille de gauche et f(n)=g(n) sur la grille de droite ; les deux reconstruisent le chemin le plus court via de véritables pointeurs parents une fois l'objectif extrait de l'ensemble fermé.
3D · Moteur de rendu Three.js / WebGL · Cible 60 FPS · fonctionne entièrement côté client, sans installation