Très intéressant ton lien wild-D à voir ce que je pourrais faire avec ça.
Mais j'ai déjà un autre problème à vous poser !
En effet j'ai entrepris l'importation de l'algo astar vu précédemment en javascript (en utilisant mootools).
Mais les deux algo, me donnent pour un même trajet des résultats (tout juste) différent. De peu, mais différent. Et je n'arrive pas à déterminer d'où, étant donné que j'ai repris exactement la même structure et les même calculs.
Je vous copie les deux scripts (épurés des fonctions d'affichages etc...)
Mais j'ai déjà un autre problème à vous poser !
En effet j'ai entrepris l'importation de l'algo astar vu précédemment en javascript (en utilisant mootools).
Mais les deux algo, me donnent pour un même trajet des résultats (tout juste) différent. De peu, mais différent. Et je n'arrive pas à déterminer d'où, étant donné que j'ai repris exactement la même structure et les même calculs.
Je vous copie les deux scripts (épurés des fonctions d'affichages etc...)
Code PHP :
<?php
class Astar
{
public $map;
public $lignes;
public $colonnes;
public $liste_ouverte = array();
public $liste_fermee = array();
public $liste_chemin = array();
public $start;
public $end;
public function __construct($map,$start,$end)
{
/* mise en place de la carte */
$this->map = $map;
$this->lignes = count($map);
$this->colonnes = count($map[0]);
$tmpstart = explode("x",$start); $this->start = array('y' => $tmpstart[0], 'x' => $tmpstart[1], 'yx' => $start); unset($tmpstart);
$tmpend = explode("x",$end); $this->end = array('y' => $tmpend[0], 'x' => $tmpend[1], 'yx' => $end); unset($tmpend);
$this->map[$this->start['y']][$this->start['x']] = "D";
$this->map[$this->end['y']][$this->end['x']] = "A";
/* ajout du point de départ dans la liste ouvert et en tant que case courante */
$this->liste_ouverte[$this->start['yx']] = array('node' => $this->start['yx'], 'parent' => 'n/c', 'g' => 0, 'h' => 0, 'f' => 9999);
$this->current = $this->start['yx'];
/* boucle tant que l'arrivé n'a pas été atteinte */
while(!isset($this->liste_fermee[$this->end['yx']]))
{
$this->get_adjacent_node();
$this->get_next_node();
}
/* on parcours la liste fermee pour reconstituer le chemin */
$parent = $this->end['yx'];
while($parent!=$this->start['yx'])
{
$parent = $this->liste_fermee[$parent]['parent'];
$this->liste_chemin[$parent] = 1;
}
unset($this->liste_chemin[$this->start['yx']]);
}
private function get_adjacent_node()
{
/* on explore les case adjacentes pour les ajouter ou non à la liste ouverte */
$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
}
private 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;
}
private 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);
}
private 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;
}
private 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['yx']);
return abs($x-$end[1])+abs($y-$end[0]);
}
private 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;
}
}
?>Code :
var AStar = new Class({
initialize: function()
{
this.map = JSON.decode($('map').get('html'));
this.start = $('map-start').get('html');
this.end = $('map-end').get('html');
this.lignes = this.map.length;
this.colonnes = this.map[0].length;
this.ouverte = new Hash();
this.fermee = new Hash();
this.chemin = new Hash();
this.go();
},
go: function()
{
this.current = this.start;
this.ouverte.set(this.start,new Hash({"parent":"n/c","g":0,"h":0,"f":9999}));
while(!$chk(this.fermee.get(this.end))) { this.getAdjNodes(this.current.split("x")); this.getNextNode(); }
this.getPath();
},
getPath: function()
{
var parent = this.end;
while(parent!=this.start)
{
parent = this.fermee.get(parent).get('parent');
this.chemin.set(parent,1);
}
this.chemin.erase(this.start);
this.chemin.set(this.end,1);
this.chemin.each(function(value,key) { $(key).addClass('chemin2'); } );
},
getAdjNodes: function(node)
{
node[0] = node[0].toInt(); node[1] = node[1].toInt();
var y = node[0]-1; var x = node[1]; if (this.free(y,x,0)) this.addNode(y,x,node[0]+"x"+node[1]);
var y = node[0]-1; var x = node[1]+1; if (this.free(y,x,1)) this.addNode(y,x,node[0]+"x"+node[1]);
var y = node[0]; var x = node[1]+1; if (this.free(y,x,0)) this.addNode(y,x,node[0]+"x"+node[1]);
var y = node[0]+1; var x = node[1]+1; if (this.free(y,x,1)) this.addNode(y,x,node[0]+"x"+node[1]);
var y = node[0]+1; var x = node[1]; if (this.free(y,x,0)) this.addNode(y,x,node[0]+"x"+node[1]);
var y = node[0]+1; var x = node[1]-1; if (this.free(y,x,1)) this.addNode(y,x,node[0]+"x"+node[1]);
var y = node[0]; var x = node[1]-1; if (this.free(y,x,0)) this.addNode(y,x,node[0]+"x"+node[1]);
var y = node[0]-1; var x = node[1]-1; if (this.free(y,x,1)) this.addNode(y,x,node[0]+"x"+node[1]);
},
getNextNode: function()
{
var min = 1000; var node = "";
this.fermee.set(this.current,this.ouverte.get(this.current));
this.ouverte.erase(this.current);
this.ouverte.each(function(value,key) { if(value.get('f')<min) { node = key; min = value.get('f'); } });
this.current = node;
},
free: function(y,x,diag)
{
if(!$chk(this.map[y])) return false;
else if(!$chk(this.map[y][x])) return false;
else if($chk(this.ouverte[y+"x"+x])) return false;
else if($chk(this.fermee[y+"x"+x])) return false;
else if(this.map[y][x]==1) return false;
else if(diag==1)
{
var p = y-1; var m = y+1;
if($chk(this.map[p])) { if(this.map[p][x]==1) return false; else return true; }
else if($chk(this.map[m])) { if(this.map[m][x]==1) return false; else return true; }
else return true;
}
else return true;
},
addNode: function(y,x,parent)
{
var g = this.getG(y,x,parent.split("x"));
var h = this.getH(y,x);
this.ouverte.set(y+"x"+x,new Hash({"parent":parent,"g":g,"h":h,"f":g+h}));
},
getG: function(y,x,parent)
{
var result = 0; if(x==parent[1] || y==parent[0]) result += 10; else result += 14;
if(this.ouverte.hasValue(parent[0]+"x"+parent[1])) result += this.ouverte.get(parent[0]+"x"+parent[1]).get('g');
return result;
},
getH: function(y,x) { var end = this.end.split("x"); return Math.abs(x-end[1])+Math.abs(y-end[0]); }
});Je peut uploader un screenshot des résultats si besoin, mais encore une fois les différences sont minimes (ex: la version javascript à + tendence à utiliser les diagonales, je ne comprend vraiment pas pourquoi)
Merci à tous pour vos réponses en tout cas
