JeuWeb - Crée ton jeu par navigateur - Problème Pathfinding A*, mauvais chemin

Pages : 1 2 3 4 5

Bonjour, j'ai un problème, lorsque je veut me déplacer sur ma carte, le chemin n'est pas le bon... pourtant je n'ai bloquer aucune case.
http://zeforiu.go1.cc/jeu/
cliquez sur l'image de la ville dans le menu à gauche pour voir la carte.

Voici le script PHP, il n'est pas de moi, mais c'est marquer dans le fichier

Code PHP :

<?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';
}
?>

Merci d'avance pour votre aide.

Coucou,

Je n'arrives pas à tester ton lien ...

Kéké

Le lien fonctionne pourtant bien... quand je clique dessus, il s'affiche...

Moi j'ai un truc écrit ("contenu") là où devrait être la carte

(Sur Safari, Firefox et IE7)

il faut que tu clique sur l'image d'une "ville" dans le menu, c'est un petit carré avec une ville miniature dessus

Le lien fonctionne je l'ai testé sous FF3.
Quand on clique sur ta carte, on a droit à une petite alerte JS

.
C'est le chemin de déplacement qui est mauvais ? Pourquoi? ce devrait etre quoi ?
Quand je clique, le chemin part bien d'en haut et va jusqu'à la cas où j'ai cliqué mais ca c'est du JS de toute manière, non ?

oui, mais par exemple, si tu clique sur la dernière case, tu vas voir, elle ne prend pas le plus court, ensuite clique à Gauche de celle-ci, et tu vas voir le chemin est pas le bon... même si on arrive du point de départ à l'arriver, le but de cet algorithme et de prendre le chemin le plus court et pas le plus long...

L'algorythme n'est alors pas le bon.
Je vais essayer d'en faire mais qui n'est pas forcément compatible avec le reste de ton script, juste que ce doit être général.

ok je te remerçie, bonne chance à toi.

Voici une version PHP d'une fonction permettant de déterminer le chemin le plus court:

Code PHP :

<?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;
}
?>

On calcule d'abord le pas et la boucle "trace" ensuite le chemin.
J'ai testé ce script de beaucoup de manière différente, si vous trouvez une erreur, dites le moi

.

Ci-joint le fichier permettant de tester.

Comment l'exploiter ?
Avec 2 boucle for lisant X et Y dans le tableau $way retourné.

NB: Le script peut être allégé en utilisant une boucle for avec 0 et 1 pour X et Y respectivement, on gagnerait 3 lignes(4 si on compte pas les {}) il me semble...

Pages : 1 2 3 4 5

JeuWeb - Crée ton jeu par navigateur

Raitosan

keke

Raitosan

blackduty

Raitosan

IGstaff

Raitosan

IGstaff

Raitosan

IGstaff