déplacement de plusieurs case

[phenix]

Bonjour à tous,

Je me trouve face a un problème sur ma map:

Quelques donnée:

La map a une dimention fixe (24*17).
Chaques cases est crée une à une en commencant par celle du haut, de droite a gauche.
Certain terrain sont infanchissable et doivent être contourné.
Je dispose de toute la map dans un tableau, tableau que je convertie en map par la suite.
Le déplacement d'une case coute 1 PM (point de mouvement).

Le problème: Comment calculer le coût d'un déplacement de plusieurs cases en tenant compte des décors qui doivent être contourné ?

Merci d'avance de votre aide,

Phenix

[naholyr]

Tu implémentes l'algorithme A* (cherche "algorithm A star" tu trouveras pas mal de doc) en choisissant pour heuristique la fonction constante nulle ça te donnera l'algorithme du "chemin le moins coûteux". En mettant un coût de 1 par case normale et de 9999 pour les murs, ça marchera tout seul


Edit : j'ai retrouvé une implémentation en PHP que j'avais faite. C'est extrait d'une classe "Plateau", donc c'est normal que tu y voies une mention à "$this" quelques fois. Les méthodes de cet objet qu'on utilise ici sont "distance" et "caseAdjacentes" dont les noms sont suffisamment clairs pour que je n'ai pas à te les fournir
Bref, à adapter à ton code, mais voici l'implémentation.
Dans ton cas il faudra utiliser une fonction de coût qui représente le coût pour aller sur une case (soit 1 ou 9999), et une fonction d'heuristique qui se contente de renvoyer 0 (donc le code sera grandement nettoyable).

Code PHP :

<?php 

/**

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

  * Calcul du "plus court chemin" (la notion de "court" étant basée sur le coût et pondérée par la 

  * fonction d'heuristique).

  *

  * Implémentation de A*

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

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

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

  *

  * @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($x1,$y1,$x2,$y2,$coutMax=null,$fonctionCout=null,$fonctionHeuristique=null) {

    //echo "<pre>";

    //echo "Chemin $x1,$y1 - $x2,$y2\n";

    // fonction de calcul du cout

    if (!$fonctionCout || !is_callable($fonctionCout)) {

        $fonctionCout = create_function('$board,$x,$y', 'return $board->optionCase($x,$y,\'cost\',1);');

    }

    // fonction de calcul de l'heuristique

    if (!$fonctionHeuristique || !is_callable($fonctionHeuristique)) {

        $fonctionHeuristique = create_function('$board,$x,$y,$x1,$y1,$x2,$y2', 'return $board->distance($x,$y,$x2,$y2);');

    }

    // listes

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

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

    $H = array(); // Heuristique

    $G = array(); // Coût d'accès

    $parent = array(); // Case parente d'une autre

    // Valeurs initiales 

    $case1 = "$x1,$y1";

    $case2 = "$x2,$y2";

    $open[] = "$x1,$y1";

    $G[$case1] = 0;

    $H[$case1] = $fonctionHeuristique($this,$x1,$y1,$x1,$y1,$x2,$y2);

    $H[$case2] = 0;

    $c = null; // case courante

    while (true) {

        //echo "--------------------------------------------\n";

        //echo "Open : ".implode(" - ", $open)."\n";

        // 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 F = G+H le plus petit dans la liste ouverte

        $Fmin = null;

        $x = null;

        $y = null;

        $i = null;

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

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

            $F = $G[$c] + $H[$c];

            //echo "    F($c) = {$G[$c]} + {$H[$c]} = $F\n";

            if ($Fmin === null || $F < $Fmin) {

                $Fmin = $F;

                $x = $xc;

                $y = $yc;

                $i = $ic;

            }

        }

        $c = "$x,$y";

        //echo "Case courante : $c\n";

        if ($c == "$x2,$y2") { // on a atteint la case d'arrivée

            //echo "Arrivée atteinte !\n";

            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 = $this->casesAdjacentes($x,$y);

        foreach ($voisines as $voisine) {

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

            $v = "$xx,$yy";

            if (in_array($v,$closed)) { // case déjà traitée

                continue;

            }

            $cout = $fonctionCout($this,$xx,$yy);

            if ($coutMax !== null && $cout+$G[$c] > $coutMax) { // coût total de déplacement jusqu'à cette case > coût maximum

                continue;

            }

            // si absente de la liste ouverte, l'ajouter, et calculer toutes ses valeurs

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

                $open[] = $v;

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

                $H[$v] = $fonctionHeuristique($this,$xx,$yy,$x1,$y1,$x2,$y2);

                $parent[$v] = $c;

            }

            else {

                $ancienG = $G[$v];

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

                if ($nouveauG < $ancienG) { // meilleur coût pour ce chemin, le parent de cette case est donc à modifier pour coller au meilleur chemin

                    $parent[$v] = $c;

                }

            }

        }

    }

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

    // à ce niveau $c == "$x2,$y2"

    //echo "Hiérarchie : \n"; print_r($parent); echo "\n";

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

    $p = null;

    $coutTotal = 0;

    $c1 = "$x1,$y1";

    while ($p != $c1) {

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

        //var_dump($c,$x,$y);

        $coutTotal += $fonctionCout($this,$x,$y);

        $p = $parent[$c];

        //echo "    Parent($c) = $p\n";

        //var_dump(explode(",",$p));

        array_unshift($chemin, explode(",",$p));

        //print_r($chemin);

        $c = $p;

    }

    //echo "Chemin : \n"; print_r($chemin); echo "\n";

    return array($chemin, $coutTotal);

} 

[Zamentur]

Ben faudrait nous présenter ton tableaux...
Honnêtement je l'aurais mis dans une table SQL mais peut être n'y a t'il pas besoin.

Mais comme tu sembles être à l'aise avec les tableaux je te propose de créer un array avec un numéro identifiant pour le terrain en clef et le nombre de PM en valeur.
De là tu pourra calculer le cout de ton chemin avec un simple appel à ton tableaux

C'est peut être pas la meilleur solution mais là tu ne presente pas grand chose

[phenix]

Merci de votre aide

@naholyr:

J'avais déjà entendu parler de cette algorithme, mais je n'en avait jamais vu.

Par contre, ta fonction a l'aire intéressante, par contre, c'est d'un niveau de programmation que je n'ai pas :heuuu: (autodidacte, on ma enseigner les bases du PHP, pour le reste, je me suis débrouiller tout seul).

D'abord j'ai du mal, une fonction heuristique, sa consiste en quoi ? Wikipédia n'est pas d'une grande aide (http://fr.wikipedia.org/wiki/Heuristique)

En faite, plus je lis ta fonction, plus elle me parait obscure :pleure2:.

Déjà, je me demande ou insérer le tableau de la map (pour info, mon tableau ressemble a quelques chose comme $tab_pos = array('herbe','rocher','pave',etc.)) ?

Dans ton cas il faudra utiliser une fonction de coût qui représente le coût pour aller sur une case (soit 1 ou 9999), et une fonction d'heuristique qui se contente de renvoyer 0 (donc le code sera grandement nettoyable).

Une fonction qui représente le cout d'une case ? Je dispose de tableau contenant tout les types de case infranchissables et toute les case franchissable, il suffit de faire un teste pour savoir si la case est franchissable ou non. Par contre la fonction heuristique, je me demande de quoi tu parle, comme tout a l'heure.

Honnêtement je l'aurais mis dans une table SQL mais peut être n'y a t'il pas besoin.

Je me serait retrouver avec un table de 19000 entré qui parte dans tout les sens, ici, je stocke les map dans des fichier que j'explode pour obtenir mon tableau, ensuite, 2 boucles et une fonction ce charge de le transformé en map. C'est plus pratique qu'une base de donnée niveau "visibilité", tout est bien classer. Une base de donnée n'est pas plus rapide que lire un fichier .

Mais comme tu sembles être à l'aise avec les tableaux je te propose de créer un array avec un numéro identifiant pour le terrain en clef et le nombre de PM en valeur.
De là tu pourra calculer le cout de ton chemin avec un simple appel à ton tableaux

Le cout oui, seulement, je ne voie pas comment tu dit "passe par la case a coter parce que celle la tu peux pas passer au travers".

Phenix, merci de votre aide.

[Lys91]

Je pense que ce que tu cherches à faire c'est ça :
http://fr.wikipedia.org/wiki/Recherche_de_chemin

Ce n'est pas vraiment un problème de programmation mais d'algorithmique et de mathématique bon courage, c'est un sujet plutôt passionnant

[naholyr]

La notion d'heuristique, franchement je n'ai jamais bien compris ce que ça signifiait :lol:
Mais dans le cas de l'algorithme A*, la fonction d'heuristique sert à "pondérer" l'intérêt d'un chemin : plus sa valeur est élevée, moins la case est "intéressante" dans le cadre de cette recherche de chemin. En général on prend pour heuristique la distance entre la case courante et la case d'arrivée, ainsi durant la recherche du meilleur chemin on considèrera qu'un chemin qui fait un grand détour sera "moins bon" qu'un chemin plus direct (parfois même s'il est plus coûteux). En utilisant une fonction d'heuristique constante, on supprime cette notion et seul le coût du chemin entre en compte.

La fonction d'heuristique permet de vraiment "personnaliser" l'algorithme. Dans le domaine de l'IA on pourra utiliser des heuristiques plus complexes : par exemple lors du calcul du meilleur chemin, on mettre une grande valeur aux cases de forêt pour représenter le fait qu'il essaiera au maximum d'éviter les chemin boisés

Bref, c'est intéressant mais pas appliqué dans ton cas... En revanche je n'ai pas compris la structure de ton tableau, il n'est pas à deux dimensions ?

[Michu]

Une heuristique est une donnée que tu possède à priori et qui te permet de simplifier les choses en général.

Je vais te donner un exemple concret pour l'encodage musical.

Une heuristique de ce type de codage et de savoir que l'oreille humaine ne percoit que les fréquences dans l'intervalle 30 - 30 000Hz.
donc par conséquent on peut virer sans problèmes toutes les fréquences en dehors de cet intervalle ( gain de place) sans perte de qualité.

voilou

[naholyr]

Une heuristique est une donnée que tu possède à priori et qui te permet de simplifier les choses en général.

En fait je dirais que c'est plutôt l'inverse, ce serait plutôt une approximation permettant de simplifier un problème plus complexe.

Une heuristique, où méthode approximative, est donc le contraire d'un algorithme exact qui trouve une solution optimale pour un problème donné.

Je vais te donner un exemple concret pour l'encodage musical.

Une heuristique de ce type de codage et de savoir que l'oreille humaine ne percoit que les fréquences dans l'intervalle 30 - 30 000Hz.
donc par conséquent on peut virer sans problèmes toutes les fréquences en dehors de cet intervalle ( gain de place) sans perte de qualité.

Dans ce cas, l'heuristique n'est pas le fait de savoir que l'oreille humaine ne perçoit qu'une certaine plage de fréquences, mais c'est plutôt le fait de limiter l'encodage à cette plage. La différence est floue, parce que c'est juste une question de vocabulaire, donc on donne l'impression de jouer sur les mots

[phenix]

En revanche je n'ai pas compris la structure de ton tableau, il n'est pas à deux dimensions ?

C'est pourtant (trop?) simple:

Dans un fichier:

herbe*pave*eau*herbe*panneau*coin_pave*bazar*etc...

je lit le fichier.

j'explode avec les *

et j'ai un joli tableau que je lit avec 2 boucles pour construire la map. Chaque fois, les <td> sont construit au moyen d'un fonction qui détermine l'image a placer dans le td, de quel manière etc...

En faite, ce que je voudrais c'est un truc du style:

function on_y_va(x_case_depard,y_case_depard,x_case_arriver,y_case_arriver,tableau _de_la_map)
{
trouve le coût du déplacement en prenant le plus court chemin.
}

Maintenant je ne sais pas si le tableau peux être utiliser dans la fonction de naholyr.

Une heuristique est une donnée que tu possède à priori et qui te permet de simplifier les choses en général.

En résumé, cela veux dire supprimer tout ce qui est inutile ?

Amicalement,

Phenix

[naholyr]

Oui, l'idée de l'heuristique en algorithmique, c'est de simplifier un problème en trouvant la méthode d'approximation qui permettra de trouver le résultat le plus proche de la réalité possible.

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) ?