Problème Pathfinding A*, mauvais chemin

[Melimelo]

http://www.creajeu{point car lien mort}net/forum/viewtopic.php?id=312

Ce que je trouve très drôle c'est qu'il est vraiment mieux traiter ici

[Plume]

HS déplacé. D'une, ce n'est pas le sujet du fil. De deux, ce genre de trollage n'amènera à rien. De trois, nous étions déjà au courant et nous savons pertinemment qu'il se prononce de manière infondée. CreaJeu n'a aucune prétention face à JeuWeb dans l'immédiat. Merci de ne pas lancer le débat.

@tchaOo°

[Sephi-Chan]

Je plussoie le monsieur. Le comportement de Raitosan a été stupide mais ce n'est pas une raison pour en faire autant.

JeuWeb ne doit pas être opposé à Creajeu. Si les communautés se tirent entre les pattes, ça ne peut être que néfaste pour les membres et pour la cause que nous soutenons tous : les jeux par navigateur.

La concurrence, c'est bien, mais il ne faut pas que ça dégénère.


Sephi-Chan

[Zamentur]

Donc dans ce tuto on vois que le résultat n'est pas le chemin le plus court si on utilise la diagonale.
http://www.siteduzero.com/tutoriel-3-343...vec-a.html

Donc pour l'optimisation dont j'ai parlé:
A chaque ajout de case au chemin
Vérifier qu'il n'y a pas de case adjacente en dehors de la précédente, qui soit contenue dans le chemin
Si c'est le cas -> on supprime les cases enregistré en plus

Et ainsi on obtient un des plus court chemin.


Après je pense surtout qu'il faut s'interroger sur le fait d'avoir le plus court chemin sur un grand nombre d'obstacle. Pour moi ce n'est pas réaliste, car bien souvent on fait des détours en allant dans un endroit qui est potentiellement le meilleur.
Sans compter que pour trouver le véritable plus court chemin c'est très couteux et donc inadapté. Même les jeux installé ne le font pas!

[jo_link_noir]

preso, je trouve que c'est réalisable et pas spécialement si coûteux, en temps en tout cas, j'ai pas tester en ressource serveur. On considère bien sur qu'on cherche pas un chemin sur 100.000 cases, faut pas être fous non plus :-°

Code PHP :

<?php

class Pathfinding

{

    //coordonnée x du joueur 1

    private $x;

    //coordonnée y du joueur 1

    private $y;

    //coordonnée x du joueur 2

    private $x2;

    //coordonnée y du joueur 2

    private $y2;

    //pa disponible par le joueur

    private $pa;

    //le cout du terrain

    private $terrain;



    //le parcours le moins couteux qui à été trouver

    private $parcours='';

    //le cout du parcours trouver

    private $cout=0;



    //liste du cout le moins élever pour un chemin sur une case (case1=>cout, case2=>cout....)

    private $case_cout = array();

    //pa restant pour le parcours le moins couteux

    private $pa_reste = 0;

    //facultatif, sers à compter le nombre de boucle effectuer pour trouver un résultat

    private $compteur = 0;



    /*cré le parcours le moins couteux en pa

        @param (int) $x

        @parma (int) $y

        @param (int) $x2

        @parma (int) $y2

        @parma (int) $pa

        @parma (array) $terrain (forme : [x][y]=>cout, ....)

        @return true si un parcours est trouver, sinon false*/

    public function __construct($x, $y, $x2, $y2 ,$pa ,$terrain)

    {

        //la variable time est à suprimer ainsi que le echo et la fonction p

        //(c'est juste pour afficher les resultat rapidement...

        //on peut le faire à l'exterieur de la fonction !)

        //la fonction p ressemble à ça :

        //function p($a){echo '<pre>'print_r($a);echo '</pre>'};

        $time=microtime(true);

        //les cases de départ et d'arrivées sont les même : on stop

            if($x === $x2 AND $y === $y2)

            {

                return false;

            }

        $this->x = $x;

        $this->y = $y;

        $this->x2 = $x2;

        $this->y2 = $y2;

        $this->pa = $pa;

        $this->terrain = $terrain;



        //on va rechercher le chemin le moins couteux

        $this->chemin_plus_court("$x,$y", $pa);

        $parcours=$this->chemin($x, $y, $pa);

        $time=microtime(true)-$time;

        echo '<br />pathfinding : '.$this->compteur()."

        boucle effetuer en ".($time*1000)." ms

        (<strong>parcours(x:$x, y:$y, x2:$x2, y2:$y2, pa:$pa)</strong>)";

        echo 'parcours avec un cout de <strong>'.$this->cout.'</strong> pa';

        p($this->parcours());

        p($this->pa());

        p($this->cout_parcours());

        return $parcours;

    }



    /*récupère les case adjacentes à la case et les renvoies dans un ordre précis

     (la case la plus près du point d'arriver à la plus éloignée)

        @param (int) $x

        @parma (int) $y

        @return (array) case adjacente*/

    public function adjacente($x, $y)

    {

        //point d'arriver à gauche mi par defaut

        //(les autre point seront situés soit avant, soit après)

        $cases_adjacentes = array(

            array($x-1, $y)

        );



            //point d'arriver à droite

            if($x-$this->x2 < 0):

                array_unshift($cases_adjacentes, array($x+1, $y));

            else:

                $cases_adjacentes[] = array($x+1, $y);

            endif;



            //point d'arriver en haut

            if($y-$this->y2 > 0):

                array_unshift($cases_adjacentes, array($x, $y-1));

            else:

                $cases_adjacentes[] = array($x, $y-1);

            endif;



            //point d'arriver en bas

            if($y-$this->y2 < 0):

                array_unshift($cases_adjacentes, array($x, $y+1));

            else:

                $cases_adjacentes[] = array($x, $y+1);

            endif;



            //point d'arriver en bas à gauche

            if($x-$this->x2 > 0 AND $y-$this->y2 < 0):

                array_unshift($cases_adjacentes, array($x-1, $y+1));

            else:

                $cases_adjacentes[] = array($x-1, $y+1);

            endif;



            //point d'arriver en bas à droite

            if($x-$this->x2 < 0 AND $y-$this->y2 < 0):

                array_unshift($cases_adjacentes, array($x+1, $y+1));

            else:

                $cases_adjacentes[] = array($x+1, $y+1);

            endif;



            //point d'arriver en haut à gauche

            if($x-$this->x2 > 0 AND $y-$this->y2 > 0):

                array_unshift($cases_adjacentes, array($x-1, $y-1));

            else:

                $cases_adjacentes[] = array($x-1, $y-1);

            endif;



            //point d'arriver en haut à droite

            if($x-$this->x2 < 0 AND $y-$this->y2 > 0):

                array_unshift($cases_adjacentes, array($x+1, $y-1));

            else:

                $cases_adjacentes[] = array($x+1, $y-1);

            endif;



        return $cases_adjacentes;

    }



    /*calcule la distance entre 2 points  (en abslu)

        @param (int) $x

        @parma (int) $y

        @param (int) $x2

        @parma (int) $y2

        @return (int) distance entre les 2 coordonnées (en case)*/

    public function distance($x,$y)

    {

            $distance = abs($x - $this->x2) + abs($y - $this->y2);

            return $distance;

    }



    /*élimine les cases inaccessiblent du au manque de PA ou du à

    l'infranchisement d'un obstacle

        @param (int) $x

        @parma (int) $y

        @parma (int) $pa

        @return (array) case adjacente accessible (forme x,y,[cout])*/

    public function accessible($x,$y,$pa)

    {

        //la case d'arriver est déjà atteinte, pas la peine de continuer

            if($x!=$this->x2 OR $y!=$this->y2)

            {

                $case_accessible=array();

                $case_adjacentes = $this->adjacente($x,$y);

                    foreach($case_adjacentes as $case)

                    {

                        //si le terrain n'est pas définit, il est infranchissable

                        list($x,$y)=$case;

                            if(isset($this->terrain[$x][$y]))

                            {

                                //vérifi si le nombre de pa sera suffisament élever

                                //pour atteindre l'arrivée à partir de la case

                                //(cout_case + distance -*1)

                                    if($this->terrain[$x][$y] + $this->distance($case[0],$case[1]) - 1 <= $pa)

                                    {

                                        $case_accessible["$x,$y"] = $this->terrain[$x][$y];

                                    }

                            }

                    }

                return $case_accessible;

            }

        return array();

    }



    /*insere le chemin le moins coûteu en pa dans la variable

    $this->parcours, et les pa utilisais dans $this->cout

        @param (int) $x case en court de traitement (position x)

        @parma (int) $y idem mais pour la position y

        @parma (int) $pa qui reste à partir de la case traiter

        @fonc (string) $s representatif des case visiter (x,y;x,y...)

        @fonc (int) $cout reprentatif du cout des cases déjà parcouru

        @return true si un parcours est trouver*/

    public function chemin($x, $y, $pa, $s='', $cout=0)

    {

        //définit les cases adjacentes est accessible

        $cases = $this->accessible($x, $y, $pa);



            if($cases != array())

            {

                $return=false;

                //création du chemin (on parcours dans une boucle

                //les case adjacente accessible)

                    foreach($cases as $key=>$cout_case)

                    {

                        $this->compteur();

                        list($xx,$yy)=explode(',',$key);

                        //un chemin est trouver création du tableau de parcours

                        //(forme : [0]=>tableau des cases, [1]=>tableau du cout)

                        //et stop la continuité de la recherche de parcours pour ce terrain

                            if($xx==$this->x2 AND $yy==$this->y2)

                            {

                                //le chemin trouver et le plus court

                                    if($this->parcours_plus_court($pa) === true)

                                    {

                                        //on enregistre le parcours et on

                                        //arrete la boucle du foreach

                                        $this->parcours = $s.$key;

                                        $this->cout = $cout+$cout_case;

                                        return true;

                                    }

                            }

                        //elimine les chemins qui dépasse les pa du chemin trouver

                        //et ceux qui viennent sur des cases avec un chemin eyant

                        //moins de pa utiliser (pa - distance)

                            elseif($this->chemin_plus_court($key, $pa) === true AND $this->pa_reste < $pa - $this->distance($xx,$yy))

                            {

                                //traite la case suivante en rapellant la fonction chemin

                                if($this->chemin($xx, $yy, $pa-$cout_case, "$s$key;", $cout+$cout_case) === true)

                                {

                                    $return = true;

                                }

                            }

                    }

                return $return;

            }

        return false;

    }



    /*vérifie si les pa restant sont plus élever que ceux enregistrer,

    retourne true et sauvegarde les pa dans ce cas, false dans le cas contraire

        @param (int) $pa_reste

        @static (int) $reste

        @return (bolen) true si $pa_reste>$reste false dans le cas contraire*/

    public function parcours_plus_court($pa_reste)

    {

            if($pa_reste > $this->pa_reste)

            {

                $this->pa_reste = $pa_reste;

                return true;

            }

        return false;

    }



    /*vérifie si les pa restant dans une case sont plus élever que ceux enregistrer, 

    retourne true et sauvegarde les pa dans ce cas,

    false dans le cas contraire et true si la case n'avais pas été enregistrer

        @param (int) $pa_reste

        @static (array) $reste du maximum de pa q'un chemin a eu sur cette une case (forme [x,y]=>pa_reste)

        @return (bolen) true si $pa_reste>$reste false dans le cas contraire*/

    public function chemin_plus_court($key, $pa_reste)

    {

            if(isset($this->case_cout[$key]))

            {

                    if($pa_reste > $this->case_cout[$key])

                    {

                        $this->case_cout[$key] = $pa_reste;

                        return true;

                    }

                return false;

            }

        $this->case_cout[$key] = $pa_reste;

        return true;

    }



    public function compteur()

    {

        return $this->compteur++;

    }



    //retourne le parcours forme ([0]=>"x,y", [1]=>"x,y"....)

    public function parcours()

    {

        return explode(';', $this->parcours);

    }



    //retourne les pa restant

    public function pa()

    {

        return $this->pa-$this->cout;

    }



    //retourne les pa utiliser

    public function pa_utiliser()

    {

        return $this->cout;

    }



    //retourne le cout du parcours ([x,y]=>cout

    public function cout_parcours()

    {

        $cout = array();

            foreach($this->parcours() as $case)

            {

                list($x,$y)=explode(',',$case);

                $cout[$case] = $this->terrain[$x][$y];

            }

        return $cout;

    }

}

?>

[Cartman34]

A mon avis c'est très lourd pour pas grand chose...j'espère que ca gère les obstacles sinon c'est pas terrible.
Même un script gérant les obstacle pourrait être bien plus court car il ne s'agit que de quelques excceptiosn et calculs en plus sur une 30aines de lignes (à tout casser)

[jo_link_noir]

Encore heureux qu'il gère les obstacles, sinon c'est trop facile est vraiment sans intérêt. Il peut aussi faire des cases avec un coût négatif, position ou nul (mais ça va pas beaucoup servir XD) et je pense qu'il reste assez souple, mais ça n'engage que moi. Bon après c'est vrai qu'il est peut-être lourd et je n'ai pas de script pour le comparer.
Après si on vire tout ce qui est inutile dans le constructeur est tout les if/else dans la fonction case_adjacente il n'est pas si grand que ça au final.

Pour info j'en avait faire un autre d'environ cinquante lignes mais j'avais une erreur de mémoire dépasser... alors j'ai garder celui là.