<?
/* ---------------------------------------------------------------------
astar.php : Algorithme de recherche de chemin le plus court (le moins couteux) pour VDD
par la méthode A* ("pathfinding A star")
AUTEUR(S) : Alexandre AUPETIT
VERSION : 1.0
DATE : 22/10/2006
LICENCE : logiciel libre LGPL
Ce code source peut être utilisé dans une application GPL ou non, les modifications effectuées
à cette source doivent être rendue publiques aux utilisateurs de l'application l'utilisant.
Références
http://www.supinfo-projects.com/fr/2006/pathfinding%5Ffr%5F2006/5/
http://fr.wikipedia.org/wiki/Algorithme_A%2A
http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
------------------------------------------------------------------------ */
/* ---------------------------------------------------------------------
Fonction qui renvoie le coût de déplacement sur la case $X, $Y
=> A paramétrer pour VDD !!!!!!!!!!!!
------------------------------------------------------------------------ */
function cout_terrain($X, $Y) {
if (($X-$Y == 1)) return 0.5;
return 2;
}
/* ---------------------------------------------------------------------
Classe Noeud = 1 case d'un parcours
Parent = case précédente dans le parcours
X, Y : coord du point
F, G, H : cout dans l'algo A*
------------------------------------------------------------------------ */
class Noeud {
var $cle = '';
var $parent = null;
var $X = 0;
var $Y = 0;
var $F = 0;
var $G = 0;
var $H = 0;
//var $ecart_diag = 0; // hack pour rendre le parcours plus "droit"
// Constructeur
function Noeud ($cle, $parent, $X, $Y, $F, $G, $H) {
$this->cle = $cle;
$this->parent = $parent;
$this->X = $X;
$this->Y = $Y;
$this->F = $F;
$this->G = $G;
$this->H = $H;
}
// Affichage du noeud (debug)
function affiche() {
echo "(" . $this->cle . ") X=" . $this->X ." Y=" . $this->Y ." F=" . $this->F ." G=" . $this->G ." H=" . $this->H ."<br>";
}
}
/* ---------------------------------------------------------------------
Heuristique H : distance de Manhattan standard
calcule le cout estimé minimal entre depart (point courant) et arrivee (arrivee finale du parcours)
H doit être minimisée pour que A* trouve l'optimum
Dans VDD le cout min d'un déplacement (route) est de 0.5 d'où le fact multiplicateur D = 0.5
La distance dans VDD est simple avec coût diagonale = 1, on calcule le nb de cases
cf http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
------------------------------------------------------------------------ */
function Heuristique_Manhattan_Vdd ($X_depart, $Y_depart, $X_arrivee, $Y_arrivee) {
return 0.5 * max (abs($X_arrivee - $X_depart), abs($Y_arrivee - $Y_depart) );
}
/* ---------------------------------------------------------------------
Calcul de F, G, H, les variables de l'algorithme A*
G = cout réel du déplacement pour aller du départ à ce point ($X, $Y)
H = estimation du cout pour aller à l'arrivée $X_ARRIVEE, $Y_ARRIVEE
F = G+H = cout total estimé du parcours allant de départ à arrivée et passant par ce point $X $Y
------------------------------------------------------------------------ */
function calculFGH($X, $Y, $X_ARRIVEE, $Y_ARRIVEE, $G_precedent, &$F, &$G, &$H, &$cle) {
$G = $G_precedent + cout_terrain($X, $Y);
$H = Heuristique_Manhattan_Vdd($X, $Y, $X_ARRIVEE, $Y_ARRIVEE);
$F = $G + $H;
$cle = "$X,$Y";
}
/* ---------------------------------------------------------------------
Calcul d'un noeud successeur au noeud courant (une des 8 cases autour)
------------------------------------------------------------------------ */
function calcul_successeur($X, $Y, $X_ARRIVEE, $Y_ARRIVEE, $G_precedent, $noeud_courant, &$liste_ouvert, &$liste_ferme ) {
$F_courant = 0;
$G_courant = 0;
$H_courant = 0;
$cle_courant = '';
// Heuristique H = estimation du coût de n?? au GOAL
// Stocker dans G_tmp g(n??), le coût g(n) + le coût pour aller de n à n??
// Stocker dans F_tmp f(n??), g(n??) + H ; c'est l'heuristique
calculFGH($X, $Y, $X_ARRIVEE, $Y_ARRIVEE, $G_precedent, $F_courant, $G_courant, $H_courant, $cle_courant);
//DEBUG echo "F_courant=$F_courant G_courant=$G_courant, H_courant=$H_courant (cle_courant=$cle_courant)<br>";
// Si n?? se trouve déjà dans OPEN avec un f(n??) meilleur on passe au point n?? suivant
if ( isset($liste_ouvert[$cle_courant]) ) {
//DEBUG echo "Existe deja dans ouvert<br>";
if ($F_courant > $liste_ouvert[$cle_courant]->F) {
//DEBUG echo "F_courant trouvé moins bon que précedent<br>";
return false;
} else {
// Retirer n?? des deux listes OPEN et CLOSED
unset($liste_ouvert[$cle_courant]);
}
}
// Si n?? se trouve déjà dans CLOSED avec un f(n??) meilleur on passe au point n?? suivant
if ( isset($liste_ferme[$cle_courant]) ) {
//DEBUG echo "Existe deja dans ferme<br>";
if ($F_courant > $liste_ferme[$cle_courant]->F) {
//DEBUG echo "F_courant trouvé moins bon que précedent<br>";
return false;
} else {
// Retirer n?? des deux listes OPEN et CLOSED
unset($liste_ferme[$cle_courant]);
}
}
/* Mettre n dans parent(n')
Mettre G_tmp dans g(n')
Mettre F_tmp dans f(n??)
*/
$noeud_elt = new Noeud ($cle_courant, $noeud_courant, $X, $Y, $F_courant, $G_courant, $H_courant);
// Ajouter n?? à la liste OPEN
//DEBUG $noeud_elt->affiche();
$liste_ouvert[$cle_courant] = $noeud_elt;
return true;
}
/* ---------------------------------------------------------------------
Calcul du meilleur chemin entre $X_DEPART, $Y_DEPART et $X_ARRIVEE, $Y_ARRIVEE
en moins de $NB_ITER_MAX itération (moyen de limiter la charge CPU)
Retour :
renvoie true si chemin trouvé, false sinon
$parcours : liste des coordonnés des points visités
------------------------------------------------------------------------ */
function calcul_meilleur_chemin($X_DEPART, $Y_DEPART, $X_ARRIVEE, $Y_ARRIVEE, $NB_ITER_MAX, &$parcours, &$cout_parcours)
{
//DEBUG echo "Creation du point de depart<br>";
$nb_iter=0;
//DEBUG echo "Initialiser la liste OPEN à vide <br>";
$liste_ouvert = array();
//DEBUG echo "Initialiser la liste CLOSED à vide <br>";
$liste_ferme = array();
//DEBUG echo "Ajouter START à la liste OPEN <br>";
$G_courant = 0;
$H_courant = Heuristique_Manhattan_Vdd($X_DEPART, $Y_DEPART, $X_ARRIVEE, $Y_ARRIVEE);
$F_courant = $G_courant + $H_courant;
$cle_courant="$X_DEPART,$Y_DEPART";
//DEBUG echo "F_courant=$F_courant<br>";
$noeud_courant = new Noeud ($cle_courant, NULL, $X_DEPART, $Y_DEPART, $F_courant, $G_courant, $H_courant);
//DEBUG $noeud_courant->affiche();
$liste_ouvert[$cle_courant] = $noeud_courant;
$solution_trouvee=false;
//DEBUG echo "Tant que la liste OPEN n'est pas vide <br>";
while ( (count($liste_ouvert)>0) && ($nb_iter < $NB_ITER_MAX ) && (!($solution_trouvee)) ) {
$F_min = 10000.0;
$H_min = 10000.0;
//DEBUG echo " Retirer le noeud n de la liste OPEN tel que f(n) soit le plus petit <br>";
foreach ( $liste_ouvert as $noeud_elt ) {
//DEBUG $noeud_elt->affiche();
if ( ($noeud_elt->F <= $F_min) && (!isset($liste_ferme[$noeud_elt->cle])) ) {
//if ( ($noeud_elt->F < $F_min) && (!isset($liste_ferme[$noeud_elt->cle])) ) {
if ( ($noeud_elt->F < $F_min) || (($noeud_elt->F == $F_min) && ($noeud_elt->H < $H_min) ) ) {
$noeud_courant = $noeud_elt;
$F_min=$noeud_elt->F;
$H_min=$noeud_elt->H;
//DEBUG echo " Meilleur noeud trouvé <br>";
}
}
}
//DEBUG echo " <b>Meilleur noeud</b> : ";
//DEBUG $noeud_courant->affiche();
//print_r($liste_ouvert); echo "<br>";
//DEBUG echo " Si n est le GOAL on a trouvé une solution ; traiter CLOSED et retourner la solution. <br>";
if ( ($noeud_courant->X == $X_ARRIVEE) && ($noeud_courant->Y == $Y_ARRIVEE) ) {
//DEBUG echo "SOLUTION TROUVEE !!!!!!!!!!!!!!!!<br>";
$solution_trouvee=true;
break;
// traiter CLOSED et retourner la solution
}
// $noeud_courant->affiche();
//DEBUG echo "Pour chaque successeur n?? du noeud n<br>";
/*
$X-1, $Y
$X-1, $Y-1
$X-1, $Y+1
$X, $Y-1
$X, $Y+1
$X+1, $Y
$X+1, $Y-1
$X+1, $Y+1
*/
//print_r($liste_ouvert); echo "<br>";
calcul_successeur($noeud_courant->X-1, $noeud_courant->Y, $X_ARRIVEE, $Y_ARRIVEE, $noeud_courant->G, $noeud_courant, $liste_ouvert, $liste_ferme);
calcul_successeur($noeud_courant->X-1, $noeud_courant->Y-1, $X_ARRIVEE, $Y_ARRIVEE, $noeud_courant->G, $noeud_courant, $liste_ouvert, $liste_ferme);
calcul_successeur($noeud_courant->X-1, $noeud_courant->Y+1, $X_ARRIVEE, $Y_ARRIVEE, $noeud_courant->G, $noeud_courant, $liste_ouvert, $liste_ferme);
calcul_successeur($noeud_courant->X, $noeud_courant->Y-1, $X_ARRIVEE, $Y_ARRIVEE, $noeud_courant->G, $noeud_courant, $liste_ouvert, $liste_ferme);
calcul_successeur($noeud_courant->X, $noeud_courant->Y+1, $X_ARRIVEE, $Y_ARRIVEE, $noeud_courant->G, $noeud_courant, $liste_ouvert, $liste_ferme);
calcul_successeur($noeud_courant->X+1, $noeud_courant->Y, $X_ARRIVEE, $Y_ARRIVEE, $noeud_courant->G, $noeud_courant, $liste_ouvert, $liste_ferme);
calcul_successeur($noeud_courant->X+1, $noeud_courant->Y-1, $X_ARRIVEE, $Y_ARRIVEE, $noeud_courant->G, $noeud_courant, $liste_ouvert, $liste_ferme);
calcul_successeur($noeud_courant->X+1, $noeud_courant->Y+1, $X_ARRIVEE, $Y_ARRIVEE, $noeud_courant->G, $noeud_courant, $liste_ouvert, $liste_ferme);
//print_r($liste_ouvert); echo "<br>";
// Ajouter n à la liste CLOSED
$liste_ferme[$noeud_courant->cle] = $noeud_courant;
// supprime n de ouvert ?????????
unset($liste_ouvert[$noeud_courant->cle]);
/* DEBUG
echo "OUVERT<br>";
echo "<table border='1'>\n";
for ($Y=-10; $Y < 20; $Y++) {
echo "<tr>";
for ($X=-10; $X < 20; $X++) {
echo "<td>";
$cle_tmp = "$X,$Y";
if ( isset($liste_ouvert[$cle_tmp]) ) {
//echo "x";
echo $liste_ouvert[$cle_tmp]->F;
} else {
echo " ";
}
echo $val;
echo "</td>";
}
echo "</tr>\n";
}
echo "</table>\n";
*/
$nb_iter++;
}
//DEBUG
//echo "Solution : ($nb_iter itérations)<br>";
//DEBUG echo "cout = " . $noeud_courant->F . "<br>";
$parcours="";
$cout_parcours = $noeud_courant->F;
do {
//DEBUG echo "X=" . $noeud_courant->X . " Y=" . $noeud_courant->Y . "<br>";
$parcours = $noeud_courant->cle . ';' . $parcours;
$noeud_courant = $noeud_courant->parent;
} while ($noeud_courant != NULL) ;
/*DEBUG echo "<table border='1'>\n";
for ($Y=-10; $Y < 20; $Y++) {
echo "<tr>";
for ($X=-10; $X < 20; $X++) {
echo "<td>";
$val= cout_terrain($X, $Y);
echo $val;
echo "</td>";
}
echo "</tr>\n";
}
echo "</table>\n";
*/
unset($noeud_courant);
// désallocation des listes et noeuds
foreach ( $liste_ouvert as $noeud_elt ) {
unset($liste_ouvert[$noeud_elt->cle]);
unset($noeud_elt);
}
unset($liste_ouvert);
//DEBUG echo "Fin !<br>\n";
return $solution_trouvee;
}
# Main
$parcours = "";
$cout_parcours = 0;
if (calcul_meilleur_chemin(5, 0, 15, 10, 400, $parcours, $cout_parcours)) {
echo "Solution trouvée !<br>";
echo $parcours;
echo "<br>en $cout_parcours PA<br>";
} else {
echo "Solution non trouvée !<br>";
}
?>