déplacement de plusieurs case

[phenix]

Ton tableau est donc à deux dimensions (tableau de tableaux de terrains), et pour accéder à une case on prend $tableau[$y][$x] (tableau de lignes) ou $tableau[$x][$y] (tableau de colonnes) ?

On prend $tableau[$numéro de la case] :heuuu:

Voila le code:

Code PHP :

<?php 

echo '

<table class="table_map" cellspacing="0" cellpadding="0">';

            $x=0;

            while ($x<$hauteur)

                   {

                    echo '<tr>';

                    $y = 0;    

                    while ($y<$largeur)

                        {

                            $modul = $x*$largeur+$y;

                                echo recup_td($r[$modul],$modul,$tab_pos,$tab_objet,$position,$lieu,$quartier,$largeur,$guilde,$groupe,$tab_bat,$tab_case_dep,$tab_decor,$tab_pave,$tab_herbe);

                               $y++;

                           }

                       echo '</tr>';

                        $x++;

                    }

        echo '</table>'; 

[naholyr]

zOMG, Warning, requête dans une boucle, système de stockage étrange, aucun système de coordonnées directe.

Je ne peux rien pour toi tant que tu n'auras pas réglé ces problèmes, implémenter un A* en ayant une requête à chaque accès à une case, c'est du suicide. La réalisabilité de cet algorithme tient à la simplicité d'accès aux données de chaque case (calcul du coût, c'est le coût principal, si cette fonction n'est pas en O(1), laisse tomber).


Dans le doute, je te fournis quand-même ce que j'avais réalisé, il ne manquait qu'à remplir les trous, mais sans requête. C'est bourré de commentaires donc je te laisse à de saines lectures :

Code PHP :

<?php 

/**

 * Liste des cases adjacentes à [$x,$y] pour le tableau donné

 *

 * @param Array $tableau La liste des cases

 * @param int $x

 * @param int $y

 * @return Array Liste des cases adjacentes (tableau de couples [$x,$y])

 */

function cases_adjacentes(&$tableau, $x, $y)

{

  $cases_adjacentes = array(

    array($x-1, $y-1), array($x-1, $y), array($x-1, $y+1),

    array($x,   $y-1), array($x,   $y), array($x,   $y+1),

    array($x+1, $y-1), array($x+1, $y), array($x+1, $y+1));

  // Exclure les murs et les cases "hors-tableau"

  return $cases_adjacentes;

}



/**

 * Coût d'accès à la case [$x,$y] (selon le type de terrain)

 *

 * @param Array $tableau La liste des cases

 * @param int $x

 * @param int $y

 * @return int coût d'accès

 */

function cout_case(&$tableau, $x, $y)

{

  switch ($tableau[$y][$x]) {

    // Adapter en fonction des types de terrain existant

    case 'mur':

      return 9999;

    default:

      return 1;

  }

}



/**

  * Chemin et coût total pour aller de ($x1,$y1) à ($x2,$y2)

  * Implémentation de A* avec une heuristique nulle

  * http://www.policyalmanac.org/games/aStarTutorial.htm

  * http://fr.wikipedia.org/wiki/Pathfinding

  * http://fr.wikipedia.org/wiki/Algorithme_A%2A

  *

  * @param Array $tableau La liste des cases

  * @param int $x1 X départ

  * @param int $y1 Y départ

  * @param int $x2 X arrivée

  * @param int $y2 Y arrivée

  * @param int $coutMax Cout maximum du déplacement autorisé

  * @param string $fonctionCout Nom de la fonction calculant le cout d'accès à une case, 

  * fonction acceptant 3 paramètres : le plateau, X, et Y

  * @param string $fonctionHeuristique Nom de la fonction "d'heuristique" (détermine l'"intérêt" d'une

  * position intermédiaire par rapport à une autre, on prend typiquement la distance pour indiquer une 

  * volonté d'utiliser le chemin le plus direct, quite parfois à ne pas utiliser le moins coûteux), 

  * fonction acceptant 3 paramètres : le plateau, X, et Y

  * @return Array [ Array $chemin (liste des couples [x,y]), int $cout ]

  */

function chemin(&$tableau, $x1, $y1, $x2, $y2, $coutMax = null)

{

  // Note : pour simplifier les traitements et pouvoir utiliser des cases comme index de tableau,

  // on utilisera une représentation sous forme de chaine dans le déroulement de l'algo

  $open = array(); // liste ouverte (cases à traiter)

  $closed = array(); // liste fermée (cases traitées)

  $G = array(); // coût total cumulé d'accès par case

  $parent = array(); // case parente d'une autre (si $parent[$v] = $c, 

  // alors on passe par $c pour atteindre $v)

  // Valeurs initiales

  $case1 = "$x1,$y1"; // case de départ

  $case2 = "$x2,$y2"; // case d'arrivée

  $open[] = $case1; // la case de départ est déjà traitée d'office

  $G[$case1] = 0; // coût de la case de départ = 0

  $c = null; // case courante

  while (true) {

    // si la liste ouverte est vide, alors échec dans la recherche du chemin

    if (count($open) == 0) {

      return false;

    }

    // trouver la case courante : celle qui a le coût le plus faible dans la liste ouverte

    $Gmin = null;

    $x = $y = $i = null;

    foreach ($open as $ic => $c) {

      list($xc,$yc) = explode(",", $c);

      if ($Gmin === null || $G[$c] < $Gmin) {

        $Gmin = $G[$c];

        $x = $xc; $y = $yc; $i = $ic;

      }

    }

    $c = "$x,$y"; // Nouvelle case courante

    if ($c == "$x2,$y2") {

      // Arrivée atteinte !

      break;

    }

    // déplacer dans la liste fermée

    $closed[] = "$x,$y"; // ajout dans la liste fermée

    array_splice($open, $i, 1); // suppression dans la liste ouverte

    // pour chaque case adjacente...

    $voisines = cases_adjacentes($tableau, $x, $y);

    foreach ($voisines as $voisine) {

      list($xx,$yy) = $voisine;

      $v = "$xx,$yy";

      if (in_array($v,$closed)) {

        // case déjà traitée, on l'ignore

        continue;

      }

      $cout = cout_case($tableau, $xx, $yy);

      if ($coutMax !== null && $G[$c] + $cout > $coutMax) {

        // coût total de déplacement jusqu'à cette case > coût maximum, on l'exclut

        continue;

      }

      // la case en cours d'analyse fait partie d'une des cases possibles pour le calcul

      // du chemin :

      if (!in_array($v, $open)) {

        // si elle est absente de la liste ouverte, on l'y ajoute

        $open[] = $v; // Ajout à la liste ouverte

        $G[$v] = $G[$c] + $cout; // Calcul de son coût total cumulé

        $parent[$v] = $c; // On note son parent (en l'occurrence la case courante)

      }

      else {

        // sinon, on récupère son coût précédemment calculée, et on le compare au nouveau

        $ancienG = $G[$v];

        $nouveauG = $G[$c] + $cout;

        if ($nouveauG < $ancienG) {

          // meilleur coût pour ce chemin : on a trouvé un meilleur parent pour cette case

          $parent[$v] = $c;

        }

      }

    }

  }

  // on a atteint la case d'arrivée, on remonte le chemin à l'envers

  $chemin = array(array($x2,$y2));

  $p = null; // parent de la case courante pendant le parcours du chemin inversé

  $coutTotal = 0; // cout total cumulé du chemin

  while ($p != $case1) { // tant que la prochaine case n'est pas la case de départ...

    list($x,$y) = explode(",", $c);

    $coutTotal += cout_case($tableau, $x, $y);

    $p = $parent[$c];

    array_unshift($chemin, explode(",",$p)); // ajout en tête (parcours inversé)

    $c = $p;

  }

  // on retourne le chemin et son coût total

  return array($chemin, $coutTotal);

}



// exemple (calcul du chemin de [2,3] à [7,5]) : list($chemin, $cout) = chemin($tableau, 2, 3, 7, 5); 

[mdcarter]

Je me permet de déterrer ce sujet,
j'ai tenté l'implémentation de ton algo naholyr, le soucis étant que l'algo s'amuse à passer en plein milieu d'une case qui à un "cout" de 9999 O_o
J'ai beau lire et relire le code, j'ai du mal à tout saisir, même après plusieurs articles sur A*


Oui c'est un test, les graph ne sont pas de moi évidemment

[wild-D]

ben en théorie; son algo passera automatiquement par une case 9999 si il n'y pas de chemin pour se rendre de la case de départ à la case d'arrivée.:p

d'après moi y manque un détail genre vérifier que le poids du chemin n'est pas supériieur à 9999) donc à priori c'est une vérif à faire en post traitement de la boucle (après avoir déplier la solution : ou pendant que tu déplie la solution t'assurer que y a pas de case à 9999) pour que t'ai un résultat cohérent (et tu retourne genre chemin le plus court = rester sur place ou alors un code d'erreur FALSE).

p.s.
note que si il te retourne le passage par une case 9999 alors qu'il y a des chemins plus court, là c'est que y a un beug

re-edit; en fait non, t'es censé pas dépasser coutmax; sauf que faut pas le laisser à NULL, ou éviter de lui donner une valeur astoomique ^^ c'est là que les ennui peuvent apparaitre

[mdcarter]

J'ai essayer plusieurs valeur du coutmax, cela ne change jamais le chemin pris par le script
Et oui je confirme (voir ci-dessus) il y à des chemins plus court sans montagne (case à 9999)

[wild-D]

moi y en avait pas regardé les images :p
j'ai été voir 10bgn.png
y a un petit truc:
si je regarde l'image elle est apparemment avec un système à cases hexagonales; or a priori l'algo fourni est pour un système traditionnel (cases carrées).
Mon avis ça doit poser problème; faut suremment faire des adaptation sur la définitions des cases adjacentes, etc...

[Ruz]

un algo pour cases hexagonales???
hum, là, ca m'intéresse tout de suite plus ^^...

Me pencherai sur ca dès que j'ai du temps...