Pathfinding A* en php?

Signaler
Messages postés
151
Date d'inscription
samedi 1 novembre 2003
Statut
Membre
Dernière intervention
30 juillet 2018
-
Messages postés
151
Date d'inscription
samedi 1 novembre 2003
Statut
Membre
Dernière intervention
30 juillet 2018
-
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

2 réponses

Messages postés
2268
Date d'inscription
mercredi 27 novembre 2002
Statut
Membre
Dernière intervention
13 septembre 2013
3
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

La boîte à bouts de codes
"On dit que seulement 10 personnes au monde comprenaient Einstein. Personne ne me comprends. Suis-je un génie???"
Messages postés
151
Date d'inscription
samedi 1 novembre 2003
Statut
Membre
Dernière intervention
30 juillet 2018
1
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 identiqueswhile ($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 '';
print_r($liste_cases_explorees);
echo '

';

?>

<?php
// affichage du talbeau

for($i=0; $i<=$hauteur_tableau; $i++) {
 echo '----
';
 for($j=0; $j<=$largeur_tableau; $j++){
  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 ', ';
 }
 echo '';
}

?>