📝 Ce que vous apprendrez

• Qu'est-ce que l'algorithme de recherche de chemin A* ?
• Comment il combine la recherche Dijkstra et la recherche Greedy Best-First
• Comment l'implémenter en JavaScript
• Analogie avec le monde réel et cas d'utilisation
• Fonctions heuristiques et meilleures pratiques en matière de performance

🔍 Qu'est-ce que l'algorithme A* ?

A* (prononcé A-star) est un algorithme de traversée de graphe et de recherche de chemin qui trouve le plus court chemin d'un nœud de départ à un nœud d'arrivée.

Il combine le coût de départ (appelé g) et une estimation heuristique du coût jusqu'à l'objectif (appelée h) pour former un score total f = g + h.

Contrairement à l'algorithme de Dijkstra, qui développe aveuglément tous les chemins proches, A* utilise des heuristiques pour donner la priorité aux nœuds qui semblent prometteurs.

🧭 Quand utiliser A* ?

• Lorsque vous avez besoin du chemin le plus court sur une carte ou une grille
• Lorsque les performances sont importantes et que vous n'êtes pas d'accord avec une recherche par force brute
• Dans les jeux en temps réel, la robotique, les systèmes de routage, etc.

📦 Concepts de base

Terme	Signification
g	Coût du début au nœud actuel
h	Estimation heuristique de l'objectif
f = g + h	Coût total estimé du chemin passant par le nœud
Open Set	Nœuds à évaluer (file d'attente prioritaire ou tableau)
Closed Set	Nœuds déjà évalués - Nœuds déjà évalués - Nœuds déjà évalués - Nœuds déjà évalués

💡 Heuristique : Distance de Manhattan

Pour les déplacements en grille (sans diagonales), l'heuristique courante est la distance de Manhattan :

function heuristic(a, b) {
  return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
}

Cela garantit la recevabilité - c'est-à-dire qu'il n'y a jamais de surestimation - ce qui garantit l'optimalité.

🧱 Mise en œuvre de JavaScript (exemple de grille)

function aStar(start, end, grid) {
  const openSet = [start];
  const closedSet = new Set();

  start.g = 0;
  start.f = heuristic(start, end);

  while (openSet.length > 0) {
    openSet.sort((a, b) => a.f - b.f);
    const current = openSet.shift();

    if (current === end) {
      return reconstructPath(current);
    }

    closedSet.add(current);

    for (const neighbor of getNeighbors(current, grid)) {
      if (neighbor.wall || closedSet.has(neighbor)) continue;

      const tentativeG = current.g + 1;

      if (!openSet.includes(neighbor) || tentativeG < neighbor.g) {
        neighbor.g = tentativeG;
        neighbor.f = neighbor.g + heuristic(neighbor, end);
        neighbor.previous = current;

        if (!openSet.includes(neighbor)) {
          openSet.push(neighbor);
        }
      }
    }
  }

  return []; // no path found
}

function reconstructPath(node) {
  const path = [];
  while (node) {
    path.unshift(node);
    node = node.previous;
  }
  return path;
}

🚧 Analogie avec le monde réel

Imaginez que vous naviguez dans une ville à l'aide d'une carte.

• g est la distance parcourue.
• X est une supposition en ligne droite jusqu'à votre destination.
• A* équilibre les deux, en vous aidant à choisir l'itinéraire qui semble le plus rapide et qui l'est réellement.

⚠️ Pièges courants

• ❌ Utilisation d'une heuristique inadmissible (surestimation du coût) - rupture de l'optimalité
• Oublier de mettre à jour le g d'un nœud lorsqu'un meilleur chemin est trouvé
• ❌ Ne pas utiliser de file d'attente prioritaire - le tri openSet each loop est inefficace

✅ Meilleures pratiques

• Utiliser un min-heap ou un heap binaire pour l'openSet pour les grandes grilles.
• Toujours s'assurer que l'heuristique est admissible et cohérente
• Visualisation des openSet/closedSet/path lors du débogage
• Pour les grilles pondérées, ajuster g en conséquence

🎯 Cas d'utilisation

• IA du jeu (recherche de chemin pour les PNJ)
• Planification des mouvements des robots
• Navigation basée sur une carte (par exemple, GPS)
• Résolution de casse-tête (par exemple, casse-tête à 8)

📘 Recap

• A* trouve le plus court chemin en utilisant f = g + h
• Il combine l'algorithme de Dijkstra avec une heuristique.
• C'est efficace et optimal (avec la bonne heuristique)
• Idéal pour la navigation en grille, les jeux et les agents intelligents