<?php 

/**

  * Chemin et coût total pour aller de ($x1,$y1) à ($x2,$y2)

  * Calcul du "plus court chemin" (la notion de "court" étant basée sur le coût et pondérée par la 

  * fonction d'heuristique).

  *

  * Implémentation de A*

  * http://www.policyalmanac.org/games/aStarTutorial.htm

  * http://fr.wikipedia.org/wiki/Pathfinding

  * http://fr.wikipedia.org/wiki/Algorithme_A%2A

  *

  * @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($x1,$y1,$x2,$y2,$coutMax=null,$fonctionCout=null,$fonctionHeuristique=null) {

    //echo "<pre>";

    //echo "Chemin $x1,$y1 - $x2,$y2\n";

    // fonction de calcul du cout

    if (!$fonctionCout || !is_callable($fonctionCout)) {

        $fonctionCout = create_function('$board,$x,$y', 'return $board->optionCase($x,$y,\'cost\',1);');

    }

    // fonction de calcul de l'heuristique

    if (!$fonctionHeuristique || !is_callable($fonctionHeuristique)) {

        $fonctionHeuristique = create_function('$board,$x,$y,$x1,$y1,$x2,$y2', 'return $board->distance($x,$y,$x2,$y2);');

    }

    // listes

    $open = array(); // liste ouverte (cases à traiter)

    $closed = array(); // liste fermée (cases traitées)

    $H = array(); // Heuristique

    $G = array(); // Coût d'accès

    $parent = array(); // Case parente d'une autre

    // Valeurs initiales 

    $case1 = "$x1,$y1";

    $case2 = "$x2,$y2";

    $open[] = "$x1,$y1";

    $G[$case1] = 0;

    $H[$case1] = $fonctionHeuristique($this,$x1,$y1,$x1,$y1,$x2,$y2);

    $H[$case2] = 0;

    $c = null; // case courante

    while (true) {

        //echo "--------------------------------------------\n";

        //echo "Open : ".implode(" - ", $open)."\n";

        // 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 F = G+H le plus petit dans la liste ouverte

        $Fmin = null;

        $x = null;

        $y = null;

        $i = null;

        foreach ($open as $ic => $c) {

            list($xc,$yc) = explode(",", $c);

            $F = $G[$c] + $H[$c];

            //echo "    F($c) = {$G[$c]} + {$H[$c]} = $F\n";

            if ($Fmin === null || $F < $Fmin) {

                $Fmin = $F;

                $x = $xc;

                $y = $yc;

                $i = $ic;

            }

        }

        $c = "$x,$y";

        //echo "Case courante : $c\n";

        if ($c == "$x2,$y2") { // on a atteint la case d'arrivée

            //echo "Arrivée atteinte !\n";

            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 = $this->casesAdjacentes($x,$y);

        foreach ($voisines as $voisine) {

            list($xx,$yy) = $voisine;

            $v = "$xx,$yy";

            if (in_array($v,$closed)) { // case déjà traitée

                continue;

            }

            $cout = $fonctionCout($this,$xx,$yy);

            if ($coutMax !== null && $cout+$G[$c] > $coutMax) { // coût total de déplacement jusqu'à cette case > coût maximum

                continue;

            }

            // si absente de la liste ouverte, l'ajouter, et calculer toutes ses valeurs

            if (!in_array($v,$open)) {

                $open[] = $v;

                $G[$v] = $G[$c] + $cout;

                $H[$v] = $fonctionHeuristique($this,$xx,$yy,$x1,$y1,$x2,$y2);

                $parent[$v] = $c;

            }

            else {

                $ancienG = $G[$v];

                $nouveauG = $G[$v] + $cout;

                if ($nouveauG < $ancienG) { // meilleur coût pour ce chemin, le parent de cette case est donc à modifier pour coller au meilleur chemin

                    $parent[$v] = $c;

                }

            }

        }

    }

    // on a atteint la case d'arrivée, on remonte le chemin à l'envers

    // à ce niveau $c == "$x2,$y2"

    //echo "Hiérarchie : \n"; print_r($parent); echo "\n";

    $chemin = array(array($x2,$y2));

    $p = null;

    $coutTotal = 0;

    $c1 = "$x1,$y1";

    while ($p != $c1) {

        list($x,$y) = explode(",", $c);

        //var_dump($c,$x,$y);

        $coutTotal += $fonctionCout($this,$x,$y);

        $p = $parent[$c];

        //echo "    Parent($c) = $p\n";

        //var_dump(explode(",",$p));

        array_unshift($chemin, explode(",",$p));

        //print_r($chemin);

        $c = $p;

    }

    //echo "Chemin : \n"; print_r($chemin); echo "\n";

    return array($chemin, $coutTotal);

}