pathfinding A* en php?

bonjour

je cherche un script en php de l'algo de pathfinding A*.
quelqu'un en a-t-il deja creer un ? ou si non, une idée pour le realiser ?

merci

Yop!
  Y'a l'air d'avoir un article pas torp mal ici: http://blog.lalex.com/post/2003/09/15/Traduction-:-article-sur-le-pathfinding-A

@++

R@f

merci ça m'a permis de faire un script rapide .
mais bizarrement, il bug. c'est a dire que durant la recherche du chemin, il concidere comme la case "arrivée" atteinte ( or ça ne devrait pas etre le cas ), et je sais pas pq ! ( et ça m'enerve ! )

voila le script ( je l'ai fait rapidement, donc ne faites pas gaffe a l'horreur dos il s'agit lol )
relancez le plusieur foit ac F5, et vous verrez qu'il se plante de tps en tps ....

<?php

$tableau = array();

// largeur et hauteur du tableau
$largeur_tableau = 15;
$hauteur_tableau = 15;

// coodronnées de départ et d'arrivée
$depart = array(mt_rand(0, $largeur_tableau), mt_rand(0, $hauteur_tableau));
$arrivée = array(mt_rand(0, $largeur_tableau), mt_rand(0, $hauteur_tableau));

// si les coordonnées de départ et d'arrivée sont identiques
while ($arrivée == $depart) $arrivée = array(mt_rand(0, $largeur_tableau), mt_rand(0, $hauteur_tableau));

// creation des coordonnées de la case en cours
$coordonnées_courant = $depart ;

// création du tableau, et ttibution de valeur aux case ( 0=infranchissables; 1=franchissables )
for($i=0; $i<=$hauteur_tableau; $i++) for($j=0; $j<=$largeur_tableau; $j++) $tableau[$i][$j] = (mt_rand(0, 20)==0)?"0":"1";

// les cases de départs et d'arriovées ot une valeur de
$tableau[$depart['0']][$depart['1']] = "1";
$tableau[$arrivée['0']][$arrivée['1']] = "1";

// listes des cases explorées
$liste_cases_explorees = array();
$liste_cases_explorees[] = $depart['0'].'/'.$depart['1'];



// coordonnées des cases accessibles

// les 8 cases autour de la case en cours sont accessibles

//$cases_annexes = array(    array ('1', '1', '1', '0', '0', '-1', '-1', '-1'),
//                        array ('-1', '0', '1', '-1', '1', '-1', '0', '1'));

// seules les 4 case de haut , de bas, a gauche et a droite sont accessibles
$cases_annexes = array(    array ('0', '1', '-1', '0'), array ('1', '0', '0', '-1') );


$stop=0;

//boucle  du pathfinding
// elle ne s'arrete que si la case d'arrivé est atteinte, ou apres 100 boucles

while(($coordonnées_courant['0'] != $arrivée['0'] && $coordonnées_courant['1']!=$arrivée['1']) && $stop <= "100"){

$stop++;

$f = array() ;

// analyse des cases autour de la case en cours

for ($k=0; $k<=(count($cases_annexes['0'])-1); $k++){

 $x_case_annexe = ( $coordonnées_courant['0']+$cases_annexes['0'][$k] );
 $y_case_annexe = ( $coordonnées_courant['1']+$cases_annexes['1'][$k] );


 if($tableau[$x_case_annexe][$y_case_annexe]=="1" && !in_array($x_case_annexe .'/'. $y_case_annexe, $liste_cases_explorees )){

// calcul de la distance de la case en cour a la case annexe en cours d'analyse
  $dist_origine_case_annexe_x = abs( ($coordonnées_courant['0']+$cases_annexes['0'][$k]) - $coordonnées_courant['0']);
  $dist_origine_case_annexe_y = abs( ($coordonnées_courant['1']+$cases_annexes['1'][$k]) - $coordonnées_courant['1']);

  $g =  sqrt(($dist_origine_case_annexe_x*$dist_origine_case_annexe_x)+($dist_origine_case_annexe_y*$dist_origine_case_annexe_y)) ;


// calcul de la distance de la case annexe en cours d'analyse et du point d'arrivé
  $dist_final_case_annexe_x = abs( ($coordonnées_courant['0']+$cases_annexes['0'][$k]) - $arrivée['0']);
  $dist_final_case_annexe_y = abs( ($coordonnées_courant['1']+$cases_annexes['1'][$k]) - $arrivée['1']);

  $h  =  sqrt(($dist_final_case_annexe_x*$dist_final_case_annexe_x)+($dist_final_case_annexe_y*$dist_final_case_annexe_y)) ;


$f[] = array( ($g+$h), $x_case_annexe, $y_case_annexe) ;


 }
 
 
}
// tri des valeurs par distance ascendantes
 sort($f);
 
// selection de la case la plus proche du point d'arrivé
$coordonnées_courant['0'] = $f['0']['1'];
$coordonnées_courant['1'] = $f['0']['2'];

$liste_cases_explorees[] =  $coordonnées_courant['0'] .'/'.$coordonnées_courant['1'] ;

 
}

// affichage de la liste des cases explorées
echo '<pre>';
print_r($liste_cases_explorees);
echo '</pre>';

?>

<table>
<?php
// affichage du talbeau

for($i=0; $i<=$hauteur_tableau; $i++) {
 echo '<tr>';
 for($j=0; $j<=$largeur_tableau; $j++){
  echo '<td  style="background-color:#';
 if ($tableau[$i][$j] ==0) echo "FF0000";
 elseif ($depart['0']==$i && $depart['1']==$j ) echo "00FF00";  
 elseif ($arrivée['0']==$i && $arrivée['1']==$j ) echo "0000ff";
 elseif  (in_array($i.'/'.$j, $liste_cases_explorees) ) echo "ffff00";
 
 echo ' ">';
 if ($depart['0']==$i && $depart['1']==$j ) echo "depart";  
 elseif ($arrivée['0']==$i && $arrivée['1']==$j ) echo "arrivée";
 else echo $i. '/'. $j ;
 echo '</td>';
 }
 echo '</tr>';
}

?>
</table>