JeuWeb - Crée ton jeu par navigateur
Pathfinding ou Recherche de chemin - Version imprimable

+- JeuWeb - Crée ton jeu par navigateur (https://jeuweb.org)
+-- Forum : Discussions, Aide, Ressources... (https://jeuweb.org/forumdisplay.php?fid=38)
+--- Forum : Programmation, infrastructure (https://jeuweb.org/forumdisplay.php?fid=51)
+--- Sujet : Pathfinding ou Recherche de chemin (/showthread.php?tid=8208)



Pathfinding ou Recherche de chemin - Xenos - 14-09-2020

Ceci n'est qu'une ébauche de l'article sans explication pure et dure.

Pathfinding ou Recherche de chemin

Dans une série de cas, on aimerait pouvoir déterminer le chemin le plus court entre deux points. On va s'aider pour cela d'un algorithme qui s'appelle A* (ou A star). Il existe de nombreuses implémentations mais rarement en PHP.

Sur le forum, naholyr a transmis une implémentation de cette algorithme avec une série de commentaires.

/**
* Liste des cases adjacentes à [$x,$y] pour le tableau donné
*
* @param Array $tableau La liste des cases
* @param int $x
* @param int $y
* @return Array Liste des cases adjacentes (tableau de couples [$x,$y])
*/
function cases_adjacentes(&$tableau, $x, $y)
{
  $cases_adjacentes = array(
    array($x-1, $y-1), array($x-1, $y), array($x-1, $y+1),
    array($x,  $y-1), array($x,  $y), array($x,  $y+1),
    array($x+1, $y-1), array($x+1, $y), array($x+1, $y+1));
  // Exclure les murs et les cases "hors-tableau"
  return $cases_adjacentes;
}
 
/**
* Coût d'accès à la case [$x,$y] (selon le type de terrain)
*
* @param Array $tableau La liste des cases
* @param int $x
* @param int $y
* @return int coût d'accès
*/
function cout_case(&$tableau, $x, $y)
{
  switch ($tableau[$y][$x]) {
    // Adapter en fonction des types de terrain existant
    case 'mur':
      return 9999;
    default:
      return 1;
  }
}
 
/**
  * Chemin et coût total pour aller de ($x1,$y1) à ($x2,$y2)
  * Implémentation de A* avec une heuristique nulle
  * http://www.policyalmanac.org/games/aStarTutorial.htm
  * http://fr.wikipedia.org/wiki/Pathfinding
  * http://fr.wikipedia.org/wiki/Algorithme_A%2A
  *
  * @param Array $tableau La liste des cases
  * @param int $x1 X départ
  * @param int $y1 Y départ
  * @param int $x2 X arrivée
  * @param int $y2 Y arrivée
  * @param int $coutMax Cout maximum du déplacement autorisé
  * @param string $fonctionCout Nom de la fonction calculant le cout d'accès à une case,
  * fonction acceptant 3 paramètres : le plateau, X, et Y
  * @param string $fonctionHeuristique Nom de la fonction "d'heuristique" (détermine l'"intérêt" d'une
  * position intermédiaire par rapport à une autre, on prend typiquement la distance pour indiquer une
  * volonté d'utiliser le chemin le plus direct, quite parfois à ne pas utiliser le moins coûteux),
  * fonction acceptant 3 paramètres : le plateau, X, et Y
  * @return Array [ Array $chemin (liste des couples [x,y]), int $cout ]
  */
function chemin(&$tableau, $x1, $y1, $x2, $y2, $coutMax = null)
{
  // Note : pour simplifier les traitements et pouvoir utiliser des cases comme index de tableau,
  // on utilisera une représentation sous forme de chaine dans le déroulement de l'algo
  $open = array(); // liste ouverte (cases à traiter)
  $closed = array(); // liste fermée (cases traitées)
  $G = array(); // coût total cumulé d'accès par case
  $parent = array(); // case parente d'une autre (si $parent[$v] = $c,
  // alors on passe par $c pour atteindre $v)
  // Valeurs initiales
  $case1 = "$x1,$y1"; // case de départ
  $case2 = "$x2,$y2"; // case d'arrivée
  $open[] = $case1; // la case de départ est déjà traitée d'office
  $G[$case1] = 0; // coût de la case de départ = 0
  $c = null; // case courante
  while (true) {
    // si la liste ouverte est vide, alors échec dans la recherche du chemin
    if (count($open) == 0) {
      return false;
    }
    // trouver la case courante : celle qui a le coût le plus faible dans la liste ouverte
    $Gmin = null;
    $x = $y = $i = null;
    foreach ($open as $ic => $c) {
      list($xc,$yc) = explode(",", $c);
      if ($Gmin === null || $G[$c] < $Gmin) {
        $Gmin = $G[$c];
        $x = $xc; $y = $yc; $i = $ic;
      }
    }
    $c = "$x,$y"; // Nouvelle case courante
    if ($c == "$x2,$y2") {
      // Arrivée atteinte !
      break;
    }
    // déplacer dans la liste fermée
    $closed[] = "$x,$y"; // ajout dans la liste fermée
    array_splice($open, $i, 1); // suppression dans la liste ouverte
    // pour chaque case adjacente...
    $voisines = cases_adjacentes($tableau, $x, $y);
    foreach ($voisines as $voisine) {
      list($xx,$yy) = $voisine;
      $v = "$xx,$yy";
      if (in_array($v,$closed)) {
        // case déjà traitée, on l'ignore
        continue;
      }
      $cout = cout_case($tableau, $xx, $yy);
      if ($coutMax !== null && $G[$c] + $cout > $coutMax) {
        // coût total de déplacement jusqu'à cette case > coût maximum, on l'exclut
        continue;
      }
      // la case en cours d'analyse fait partie d'une des cases possibles pour le calcul
      // du chemin :
      if (!in_array($v, $open)) {
        // si elle est absente de la liste ouverte, on l'y ajoute
        $open[] = $v; // Ajout à la liste ouverte
        $G[$v] = $G[$c] + $cout; // Calcul de son coût total cumulé
        $parent[$v] = $c; // On note son parent (en l'occurrence la case courante)
      }
      else {
        // sinon, on récupère son coût précédemment calculée, et on le compare au nouveau
        $ancienG = $G[$v];
        $nouveauG = $G[$c] + $cout;
        if ($nouveauG < $ancienG) {
          // meilleur coût pour ce chemin : on a trouvé un meilleur parent pour cette case
          $parent[$v] = $c;
        }
      }
    }
  }
  // on a atteint la case d'arrivée, on remonte le chemin à l'envers
  $chemin = array(array($x2,$y2));
  $p = null; // parent de la case courante pendant le parcours du chemin inversé
  $coutTotal = 0; // cout total cumulé du chemin
  while ($p != $case1) { // tant que la prochaine case n'est pas la case de départ...
    list($x,$y) = explode(",", $c);
    $coutTotal += cout_case($tableau, $x, $y);
    $p = $parent[$c];
    array_unshift($chemin, explode(",",$p)); // ajout en tête (parcours inversé)
    $c = $p;
  }
  // on retourne le chemin et son coût total
  return array($chemin, $coutTotal);
}
 
// exemple (calcul du chemin de [2,3] à [7,5]) : list($chemin, $cout) = chemin($tableau, 2, 3, 7, 5);