JeuWeb - Crée ton jeu par navigateur - Algo A* (AStar) en php

Pages : 1 2

Bonjour tout le monde,
Plusieurs fois sur le forum j'ai tenté d'utiliser divers script de pathfinding sans grand succès.
J'ai donc décidé d'essayer de développer ma propre version, que je vous présente toute fraiche après quelques heures de test, et surtout de lecture théorique.

Je vous la présente donc ici, brut de décoffrage, pour avoir vos avis, remarques, corrections et suggestions

Code PHP :

<html>
    
    <head>
        <style type="text/css" media="screen">
            tr { margin:0; padding:0; font-size:10px; }
            td { width:45px; height:50px; padding:5px 5px 5px 5px; background:#eee; }
            .D { background:lightgreen; }
            .A { background:red; }
            .mur { background:blue; }
            .ouvert { border:2px solid blue; }
            .fermee { border:2px solid red; }
            .chemin { background:#aaa; }
        </style>
    </head>
    
    <body>
        
    <?php
        class astar
        {
            
            public $map;
            public $liste_ouverte = array();
            public $liste_fermee = array();
            public $chemin = array();
            public $start = "2x2";
            public $end = "2x6";
            
            function __construct($map)
            {
                /* mise en place de la carte */
                $this->map = $map;
                $this->lignes = count($map);
                   $this->colonnes = count($map[0]);
                
                /* ajout du point de départ dans la liste ouvert et en tant que case courante */
                $this->liste_ouverte[$this->start] = array('node' => $this->start, 'parent' => 'n/c', 'g' => 0, 'h' => 0, 'f' => 9999);        
                $this->current = $this->start;
                
                /* boucle tant que l'arrivé n'a pas été atteinte */
                $ends = explode("x",$this->end);
                while(!isset($this->liste_fermee[$ends[0]."x".$ends[1]]))
                {
                    $this->get_adjacent_node();
                    $this->get_next_node();
                }
                
                /* on parcours la liste fermee pour reconstituer le chemin */
                $parent = $this->end;
                while($parent!=$this->start)
                {
                    $parent = $this->liste_fermee[$parent]['parent'];
                    $this->chemin[$parent] = 1;
                }    
                unset($this->chemin[$this->start]);
                    
                /* et on affiche la map */
                $this->draw_map();
            }
            
            function get_adjacent_node()
            {
                $node = explode("x",$this->current);
                $y = $node[0];
                $x = $node[1];
                if($this->is_free($y-1,$x)) $this->add_node($y-1,$x,$y."x".$x); //case haut
                if($this->is_free($y-1,$x+1,1)) $this->add_node($y-1,$x+1,$y."x".$x); //case haut droite
                if($this->is_free($y,$x+1)) $this->add_node($y,$x+1,$y."x".$x); //case droite
                if($this->is_free($y+1,$x+1,1)) $this->add_node($y+1,$x+1,$y."x".$x); //case bas droite
                if($this->is_free($y+1,$x)) $this->add_node($y+1,$x,$y."x".$x); //case bas 
                if($this->is_free($y+1,$x-1,1)) $this->add_node($y+1,$x-1,$y."x".$x); //case bas gauche
                if($this->is_free($y,$x-1)) $this->add_node($y,$x-1,$y."x".$x); //case gauche
                if($this->is_free($y-1,$x-1,1)) $this->add_node($y-1,$x-1,$y."x".$x); //case haut gauche
            }
            
            function add_node($y,$x,$parent)
            {
                /* on calcule g,h et f pour la case et on l'ajoute à la liste ouverte */
                $g = $this->get_g($y,$x,$parent);
                $h = $this->get_h($y,$x);
                $this->liste_ouverte[$y."x".$x] = array('node' => $y."x".$x, 'parent' => $parent, 'g' => $g, 'h' => $h, 'f' => $g + $h);
            }

            function get_g($y,$x,$parent)
            {
                /* on calcule le g de cette case en lui ajoutant celui de sa case parent */
                $pt = explode("x",$parent);
                $result = 0;
                if($x==$pt[1] || $y==$pt[0]) $result += 10;
                else  $result += 14;
                $result += $this->liste_ouverte[$parent]['g'];
                return $result;
            }
            
            function get_h($y,$x)
            {
                /* on calcule le nombre de case séparant cette case et celle d'arrivé, sans les diagonales */
                $end = explode("x",$this->end);
                $result = 0;
                if($x>$end[1]) $result += ($x-$end[1])*10;
                if($x<$end[1]) $result += ($end[1]-$x)*10;
                if($y>$end[0]) $result += ($y-$end[0])*10;
                if($y<$end[0]) $result += ($end[0]-$y)*10;
                return $result;
            }
            
            function is_free($y,$x,$diag=null)
            {
                /* on vérifie qu'on peut ajouter cette case dans la liste ouverte */
                if(!isset($this->map[$y][$x])) return false; // si elle n'existe pas, impossible
                elseif(isset($this->liste_ouverte[$y."x".$x])) return false; // si elle est déja en liste ouverte, impossible
                elseif(isset($this->liste_fermee[$y."x".$x])) return false; // si elle est en liste fermée, impossible
                elseif($this->map[$y][$x]==1) return false; // si c'est un mur, impossible
                elseif(isset($this->map[$y+1][$x]) && $diag==1 && $this->map[$y+1][$x]==1) return false; // si c'est un accés en diagonale et collé à un mur, impossible
                elseif(isset($this->map[$y-1][$x]) && $diag==1 && $this->map[$y-1][$x]==1) return false; // si c'est un accés en diagonale et collé à un mur, impossible
                else return true;
            }
            
            function get_next_node()
            {
                $min = "1000"; $node = "";
                /* on passe la case actuelle dans la liste fermée */
                $this->liste_fermee[$this->current] = $this->liste_ouverte[$this->current];
                /* on supprime la case actuelle de la liste ouverte */
                unset($this->liste_ouverte[$this->current]);
                /* on recherche la case ayant l'indice f le plus faible dans la liste ouverte */
                foreach($this->liste_ouverte as $ouverte)
                {
                    if($ouverte['f']<$min) { $node=$ouverte['node']; $min=$ouverte['f']; }
                }
                $this->current = $node;
                return $node;
            }
            
            function draw_map()
            {
                echo "<table cellspacing='1'>";
                        for($y=0;$y<$this->lignes;$y++)
                        {
                            echo "<tr>";
                            for ($x=0;$x<$this->colonnes;$x++) 
                            {    
                                echo "<td id='".$y."x".$x."' class='";
                                
                                    if($this->map[$y][$x]==="D") echo "D ";
                                    if($this->map[$y][$x]==="A") echo "A ";
                                    if($this->map[$y][$x]==1) echo "mur ";
                                    if(isset($this->liste_ouverte[$y."x".$x])) echo "ouvert ";
                                    if(isset($this->liste_fermee[$y."x".$x])) echo "fermee ";
                                    if(isset($this->chemin[$y."x".$x])) echo "chemin ";
                                
                                echo "'>";
                                    if(isset($this->liste_ouverte[$y."x".$x]))
                                    {
                                        echo "F = ".$this->liste_ouverte[$y."x".$x]['f'];
                                        echo "<br />G = ".$this->liste_ouverte[$y."x".$x]['g'];
                                        echo "<br />H = ".$this->liste_ouverte[$y."x".$x]['h'];
                                    }
                                    else echo $this->map[$y][$x];
                                echo "</td>";                    
                            }
                            echo "</tr>";
                        }
                echo "</table>";
            }
            
        }

        $table = '[    [0,0,0,0,1,0,0,0],
                    [0,0,0,0,1,0,0,0],
                    [0,0,"D",0,1,0,"A",0],
                    [0,0,0,0,1,0,0,0],
                    [0,0,1,1,0,0,0,0],
                    [0,0,0,0,0,0,0,0]
                   ]';
        $astar = new astar(json_decode($table,true));
    ?>
    
    </body>
    
</html> 

Merci d'avance à tous !

- bon à la lecture, j'avoue que pour les coordonnées, l'usage de chaine de caractère que tu explodes/concatènes .. bof; je comprends pas pourquoi tu utilise pas directement des tableaux avec les 2 coord. :/

- premier test qui m'est venu à l'esprit, m'a valu déjà un plantage: si y a pas de chemin entre le départ et l'arrivée: ben on est dans la merde... donc éviter la boucle infinie ce serait bien

Coucou,

J'avais à l'époque essayé celui là (qui se trouve dans le wiki de ce forum) :
http://wiki.jeuweb.net/tutoprog/pathfinding

Et ça avait aboutit... Peut-être as-tu travaillé pour des prunes (ou pour la joie d'avoir ré-inventé un algo ce qui peut-être un but en soit très important).
Si tu penses que ton algo est mieux, n'hésites pas à en indiquer la raison.
Si tu penses que ton algo est pire, n'hésites pas à voir si des points peuvent être amélioré sur l'algo actuellement présenté dans le Wiki.

Sache que de toutes les manières, un algo en PHP n'est pas la solution la plus optimisée qu'il soit car le PHP est bien plus lent que n'importe quelle implémentation en Assembleur ou en C/C++. C'est la raison pour laquelle on retrouve difficilement ce type d'algorithme dans ce langage.

PHP, c'est bien pour des choses basiques, pour le reste il y a la Vraie Programmation

(et je pèse mes mots

)

Kéké
Ps : j'utilise l'algo sur mon jeu

, mais j'ai conscience de ses faiblesses.

[Mode sais-pas-quoi ON]
Euh.. c'est quoi la fausse programmation?
[Mode sais-pas-quoi OFF]

Salut,
- La solution implémenté est loin d'être élégante j'en suis conscient, le but étant surtout de comprendre et d'implémenter cet algo, pas forcément intuitif dès de départ.
- Les cartes insolubles font également planter le script ce qui reste à régler

Je pense que mon script est mieux au niveau des commentaires, qui essayent de suivre l'algo ce qui permet d'apprendre et de l'intégrer plus facilement (j'ai toujours chercher à utiliser des scripts astar sur le net, rarement réussi du fait de l'austérité du code).
Par contre je sais bien que mon script est bien mauvais sur de nombreux points, trop verbeux, mal organisé et bugué

Voila voila, la prochaine étape serait de rendre plus propre le tout, et peut-être adapter ceci pour des cartes hexagonales.

Si y en a qui veulent se pencher dessus en carte hexa, je suis pret à y contribuer

(mais faut faire gaffe d'emblée aux différents types de cartes hexa possibles, suis pas sur que ce soit exactement la meme chose pour toutes...)

Je reviens vers vous, je teste actuellement la pathfinding sur une carte hexagonale, mais j'ai du mal à trouver les chemins les plus court.
Le problème en fait est de calcule les bon coûts G et H pour les cases, des idées ?

pour le g ça doit être tout bête: je crois bien que ce sera toujours le même poids à ajouter 10 (y a pas de "diagonale" à 14).

par contre pour le h, ça risque d'être un peu plus chiant à calculer... (enfin je sais pas mais avec certain système de coord, ça me parait pas évident)

Pour le G on est d'accord, j'ai tout mis à 10 en effet.
Par contre j'ai beau essayer tout les système de calcul de H que je trouve, aucun ne correspond vraiment.
En fait j'ai l'impression qu'il faut ajouter une sorte de système de "correction" de chemin, car tout les chemins générés actuellement sont correct, mais ont toujours une ou deux cases de détour totalement inutile.

tu utilise quel système de coordonnée hexa ?

c'est tordu parce que y a effectivement un truc; mais si tu prends un système de coordonnée pas ortho; mais aligné sur 60°; ça parait plus simple:
http://jmz.iki.fi/blog/programming/hexagonal_maps

Pages : 1 2

JeuWeb - Crée ton jeu par navigateur

mdcarter

wild-D

keke

Ruz

mdcarter

Ruz

mdcarter

wild-D

mdcarter

wild-D