/**

* 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);