<?php

if(isset($_GET['xDepart'], $_GET['yDepart'],$_GET['xArriver'], $_GET['yArriver']))

{

    /* ---------------------------------------------------------------------

     astar.php : Algorithme de recherche de chemin le plus court (le moins couteux) pour VDD

                    par la méthode A* ("pathfinding A star")

     

     AUTEUR(S) : Alexandre AUPETIT 

     VERSION   : 1.0 

     DATE      : 22/10/2006

     LICENCE : logiciel libre LGPL

            Ce code source peut être utilisé dans une application GPL ou non, les modifications effectuées 

            à cette source doivent être rendue publiques aux utilisateurs de l'application l'utilisant.



     Références

            http://www.supinfo-projects.com/fr/2006/pathfinding%5Ffr%5F2006/5/

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

            http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

            

    ------------------------------------------------------------------------ */



    /* ---------------------------------------------------------------------

    Fonction qui renvoie le coût de déplacement sur la case $X, $Y

    => A paramétrer pour VDD !!!!!!!!!!!!

    ------------------------------------------------------------------------ */

    function cout_terrain($X, $Y) {

            if (($X-$Y == 1)) return 1;



            return 2;

    }

    /* ---------------------------------------------------------------------

    Classe Noeud = 1 case d'un parcours

    Parent = case précédente dans le parcours

    X, Y : coord du point

    F, G, H : cout dans l'algo A*

    ------------------------------------------------------------------------ */

    class Noeud {

            var $cle = '';

            var $parent = null;

            var $X = 0;

            var $Y = 0;

            var $F = 0;

            var $G = 0;

            var $H = 0;

            //var $ecart_diag = 0; // hack pour rendre le parcours plus "droit"



            // Constructeur

            function Noeud ($cle, $parent, $X, $Y, $F, $G, $H) {

                    $this->cle = $cle;

                    $this->parent = $parent;

                    $this->X = $X;

                    $this->Y = $Y;

                    $this->F = $F;

                    $this->G = $G;

                    $this->H = $H;

            }



            // Affichage du noeud (debug)

            function affiche() {

                    echo "(" . $this->cle . ") X=" . $this->X ." Y=" . $this->Y ."&nbsp;&nbsp;&nbsp;  F=" . $this->F ." G=" . $this->G ." H=" . $this->H ."<br>";

            }

    }



    /* ---------------------------------------------------------------------

    Heuristique H : distance de Manhattan standard

            calcule le cout estimé minimal entre depart (point courant) et arrivee (arrivee finale du parcours)

      H doit être minimisée pour que A* trouve l'optimum

      Dans VDD le cout min d'un déplacement (route) est de 0.5 d'où le fact multiplicateur D = 0.5

      La distance dans VDD est simple avec coût diagonale = 1, on calcule le nb de cases

      

      cf http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

    ------------------------------------------------------------------------ */

    function Heuristique_Manhattan_Vdd ($X_depart, $Y_depart, $X_arrivee, $Y_arrivee) {

            return 0.5 * max (abs($X_arrivee - $X_depart), abs($Y_arrivee - $Y_depart) );

    }





    /* ---------------------------------------------------------------------

    Calcul de F, G, H, les variables de l'algorithme A*



    G = cout réel du déplacement pour aller du départ à ce point ($X, $Y)

    H = estimation du cout pour aller à l'arrivée $X_ARRIVEE, $Y_ARRIVEE

    F = G+H = cout total estimé du parcours allant de départ à arrivée et passant par ce point $X $Y

    ------------------------------------------------------------------------ */

    function calculFGH($X, $Y, $X_ARRIVEE, $Y_ARRIVEE, $G_precedent, &$F, &$G, &$H, &$cle) {

            $G = $G_precedent + cout_terrain($X, $Y);

            $H = Heuristique_Manhattan_Vdd($X, $Y, $X_ARRIVEE, $Y_ARRIVEE);

            $F = $G + $H;

            $cle = "$X,$Y";

    }



    /* ---------------------------------------------------------------------

    Calcul d'un noeud successeur au noeud courant (une des 8 cases autour)

    ------------------------------------------------------------------------ */

    function calcul_successeur($X, $Y, $X_ARRIVEE, $Y_ARRIVEE, $G_precedent, $noeud_courant, &$liste_ouvert, &$liste_ferme ) {

            $F_courant = 0;

            $G_courant = 0;

            $H_courant = 0;

            $cle_courant = '';



            // Heuristique H = estimation du coût de n?? au GOAL

            // Stocker dans G_tmp g(n??), le coût g(n) + le coût pour aller de n à n??

            // Stocker dans F_tmp f(n??), g(n??) + H ; c'est l'heuristique

            calculFGH($X, $Y, $X_ARRIVEE, $Y_ARRIVEE, $G_precedent, $F_courant, $G_courant, $H_courant, $cle_courant);

            //echo "F_courant=$F_courant G_courant=$G_courant, H_courant=$H_courant (cle_courant=$cle_courant)<br>";



            // Si n?? se trouve déjà dans OPEN avec un f(n??) meilleur on passe au point n?? suivant

            if ( isset($liste_ouvert[$cle_courant]) ) {

                    //DEBUG echo "Existe deja dans ouvert<br>";

                    if ($F_courant > $liste_ouvert[$cle_courant]->F) {

                            //DEBUG echo "F_courant trouvé moins bon que précedent<br>";

                            return false;

                    } else {

                            // Retirer n?? des deux listes OPEN et CLOSED

                            unset($liste_ouvert[$cle_courant]);

                    }

            }



            // Si n?? se trouve déjà dans CLOSED avec un f(n??) meilleur on passe au point n?? suivant

            if ( isset($liste_ferme[$cle_courant]) ) {

                    //DEBUG echo "Existe deja dans ferme<br>";

                    if ($F_courant > $liste_ferme[$cle_courant]->F) {

                            //DEBUG echo "F_courant trouvé moins bon que précedent<br>";

                            return false;

                    } else {

                            // Retirer n?? des deux listes OPEN et CLOSED

                            unset($liste_ferme[$cle_courant]);

                    }

            }



            /*  Mettre n dans parent(n')

                Mettre G_tmp dans g(n')

                Mettre F_tmp dans f(n??)

            */

            $noeud_elt = new Noeud ($cle_courant, $noeud_courant, $X, $Y, $F_courant, $G_courant, $H_courant);



            // Ajouter n?? à la liste OPEN

            //DEBUG $noeud_elt->affiche();

            $liste_ouvert[$cle_courant] = $noeud_elt;



            return true;

    }



    /* ---------------------------------------------------------------------

    Calcul du meilleur chemin entre $X_DEPART, $Y_DEPART et $X_ARRIVEE, $Y_ARRIVEE

    en moins de $NB_ITER_MAX itération (moyen de limiter la charge CPU)



    Retour :

    renvoie true si chemin trouvé, false sinon

    $parcours : liste des coordonnés des points visités

    ------------------------------------------------------------------------ */

    function calcul_meilleur_chemin($X_DEPART, $Y_DEPART, $X_ARRIVEE, $Y_ARRIVEE, $NB_ITER_MAX, &$parcours, &$cout_parcours)

    {

    //DEBUG echo "Creation du point de depart<br>";



    $nb_iter=0;



    //DEBUG echo "Initialiser la liste OPEN à vide <br>";

    $liste_ouvert = array();



    //DEBUG echo "Initialiser la liste CLOSED à vide <br>";

    $liste_ferme = array();



    //DEBUG echo "Ajouter START à la liste OPEN <br>";

    $G_courant = 0;

    $H_courant = Heuristique_Manhattan_Vdd($X_DEPART, $Y_DEPART, $X_ARRIVEE, $Y_ARRIVEE);

    $F_courant = $G_courant + $H_courant;

    $cle_courant="$X_DEPART,$Y_DEPART";

    //DEBUG echo "F_courant=$F_courant<br>";

    $noeud_courant = new Noeud ($cle_courant, NULL, $X_DEPART, $Y_DEPART, $F_courant, $G_courant, $H_courant);

    //DEBUG $noeud_courant->affiche();

    $liste_ouvert[$cle_courant] = $noeud_courant;

    /*C'est ici que on let la liste des cases bloquer :)

    $liste_ouvert["2,2"] = $noeud_courant;

    $liste_ouvert["1,2"] = $noeud_courant;

    $liste_ouvert["0,2"] = $noeud_courant;

    */

    

    $solution_trouvee=false;



    //DEBUG echo "Tant que la liste OPEN n'est pas vide <br>";

    while ( (count($liste_ouvert)>0) && ($nb_iter < $NB_ITER_MAX ) && (!($solution_trouvee)) ) {

            $F_min = 10000.0;

            $H_min = 10000.0;

            //DEBUG echo "  Retirer le noeud n de la liste OPEN tel que f(n) soit le plus petit <br>";

            foreach ( $liste_ouvert as $noeud_elt ) {

                    //DEBUG $noeud_elt->affiche();

                    if ( ($noeud_elt->F <= $F_min) && (!isset($liste_ferme[$noeud_elt->cle])) )  {

                    //if ( ($noeud_elt->F < $F_min) && (!isset($liste_ferme[$noeud_elt->cle])) )  {

                            if ( ($noeud_elt->F < $F_min) || (($noeud_elt->F == $F_min) && ($noeud_elt->H < $H_min) ) ) {

                                    $noeud_courant = $noeud_elt;

                                    $F_min=$noeud_elt->F;

                                    $H_min=$noeud_elt->H;

                                    //DEBUG echo "  Meilleur noeud trouvé <br>";

                            }



                    }

            }

            //DEBUG echo "  <b>Meilleur noeud</b> : ";

            //DEBUG $noeud_courant->affiche();



            //print_r($liste_ouvert); echo "<br>";



            //DEBUG echo "  Si n est le GOAL on a trouvé une solution ; traiter CLOSED et retourner la solution. <br>";

            if ( ($noeud_courant->X == $X_ARRIVEE) && ($noeud_courant->Y == $Y_ARRIVEE) ) {

                    //DEBUG echo "SOLUTION TROUVEE !!!!!!!!!!!!!!!!<br>";

                    $solution_trouvee=true;

                    break;

                    // traiter CLOSED et retourner la solution

            }



    //      $noeud_courant->affiche();







            //DEBUG echo "Pour chaque successeur n?? du noeud n<br>";

            /*

                    $X-1, $Y

                    $X-1, $Y-1

                    $X-1, $Y+1

                    $X, $Y-1

                    $X, $Y+1

                    $X+1, $Y

                    $X+1, $Y-1

                    $X+1, $Y+1

            */



            //print_r($liste_ouvert); echo "<br>";

            calcul_successeur($noeud_courant->X-1, $noeud_courant->Y, $X_ARRIVEE, $Y_ARRIVEE, $noeud_courant->G, $noeud_courant, $liste_ouvert, $liste_ferme);//gauche

            calcul_successeur($noeud_courant->X-1, $noeud_courant->Y-1, $X_ARRIVEE, $Y_ARRIVEE, $noeud_courant->G, $noeud_courant, $liste_ouvert, $liste_ferme);//diagonal haut gauche

            calcul_successeur($noeud_courant->X-1, $noeud_courant->Y+1, $X_ARRIVEE, $Y_ARRIVEE, $noeud_courant->G, $noeud_courant, $liste_ouvert, $liste_ferme);//diagonal bas gauche

            calcul_successeur($noeud_courant->X, $noeud_courant->Y-1, $X_ARRIVEE, $Y_ARRIVEE, $noeud_courant->G, $noeud_courant, $liste_ouvert, $liste_ferme);//haut

            calcul_successeur($noeud_courant->X, $noeud_courant->Y+1, $X_ARRIVEE, $Y_ARRIVEE, $noeud_courant->G, $noeud_courant, $liste_ouvert, $liste_ferme);//bas

            calcul_successeur($noeud_courant->X+1, $noeud_courant->Y, $X_ARRIVEE, $Y_ARRIVEE, $noeud_courant->G, $noeud_courant, $liste_ouvert, $liste_ferme);//droite

            calcul_successeur($noeud_courant->X+1, $noeud_courant->Y-1, $X_ARRIVEE, $Y_ARRIVEE, $noeud_courant->G, $noeud_courant, $liste_ouvert, $liste_ferme);//diagonal haut droite

            calcul_successeur($noeud_courant->X+1, $noeud_courant->Y+1, $X_ARRIVEE, $Y_ARRIVEE, $noeud_courant->G, $noeud_courant, $liste_ouvert, $liste_ferme);//diagonal bas droite

            //print_r($liste_ouvert); echo "<br>";



            // Ajouter n à la liste CLOSED

            $liste_ferme[$noeud_courant->cle] = $noeud_courant;



            // supprime n de ouvert ?????????

            unset($liste_ouvert[$noeud_courant->cle]);



    /*

    echo "OUVERT<br>";

    echo "<table border='1'>\n";

    for ($Y=-10; $Y < 20; $Y++) {

            echo "<tr>";

            for ($X=-10; $X < 20; $X++) {

                    echo "<td>";

                    $cle_tmp = "$X,$Y";

                    if ( isset($liste_ouvert[$cle_tmp]) ) {

                            //echo "x";

                            echo $liste_ouvert[$cle_tmp]->F;

                    } else {

                            echo "&nbsp;";

                    }



                    echo $val;

                    echo "</td>";

            }

            echo "</tr>\n";

    }

    echo "</table>\n";

    */



            $nb_iter++;

    }



    //DEBUG 

    //echo "Solution : ($nb_iter itérations)<br>";

    //DEBUG echo "cout = " . $noeud_courant->F . "<br>";

    $parcours="";

    $cout_parcours = $noeud_courant->F;

    do {

            //DEBUG echo "X=" . $noeud_courant->X . " Y=" . $noeud_courant->Y . "<br>"; 

            $parcours = $noeud_courant->cle . ';' . $parcours;

            $noeud_courant = $noeud_courant->parent;

    } while ($noeud_courant != NULL) ;





    /*DEBUG echo "<table border='1'>\n";

    for ($Y=-10; $Y < 20; $Y++) {

            echo "<tr>";

            for ($X=-10; $X < 20; $X++) {

                    echo "<td>";

                    $val= cout_terrain($X, $Y);

                    echo $val;

                    echo "</td>";

            }

            echo "</tr>\n";

    }

    echo "</table>\n";

    */



    unset($noeud_courant);



    // désallocation des listes et noeuds

    foreach ( $liste_ouvert as $noeud_elt ) {

            unset($liste_ouvert[$noeud_elt->cle]);

            unset($noeud_elt);

    }

    unset($liste_ouvert);



    //DEBUG echo "Fin !<br>\n";



    return $solution_trouvee;



    }







    # Main

    $parcours = "";

    $cout_parcours = 0;

    if (calcul_meilleur_chemin($_GET['xDepart'], $_GET['yDepart'], $_GET['xArriver'], $_GET['yArriver'], 400, $parcours, $cout_parcours)) {

            echo $parcours;

    } else {

            echo "Solution non trouvée !<br>";

    }



}

else

{

echo'Erreur';

}

?>

<?php

function way($Xa, $Ya, $Xb, $Yb) {

    $way = $Dif = array();

    $Xi = $Xa;

    $Yi = $Ya;

    $way[$Xa][$Ya] = 0;

    $Dif['X'][] = $Xb - $Xa;

    $Dif['Y'][] = $Yb - $Ya;

    $Dif['X'][] = ( !$Dif['X'][0] ) ? 1 : $Dif['X'][0];

    $Dif['Y'][] = ( !$Dif['Y'][0] ) ? 1 : $Dif['Y'][0];

    $Xp = abs($Dif['X'][0] / $Dif['Y'][1]);

    $Yp = abs($Dif['Y'][0] / $Dif['X'][1]);

    $Xp = ( $Xp > 1 ) ? 1 : $Xp;

    $Yp = ( $Yp > 1 ) ? 1 : $Yp;

    $Xp = ( $Dif['X'][0] < 0 ) ? -$Xp : $Xp;

    $Yp = ( $Dif['Y'][0] < 0 ) ? -$Yp : $Yp;

    $i = 1;

    while( $Xi != $Xb || $Yi != $Yb ) {

        $Xi += $Xp;

        $Yi += $Yp;

        echo "X{$i}= ".round($Xi)." | Y{$i}=".round($Yi)."<br />";

        $way[round($Xi)][round($Yi)] = $i;

        $i++;

    }

    return $way;

}

?>