La fonction de coût

La fonction de coût permet donc d'estimer le coût pour arriver à notre objectif. Cette fonction peut être plus ou moins simple selon le problème auquel nous avons affaire. Si nous sommes sur une carte non plate (avec des montagnes, des creux, marais, etc), le coût ne sera pas le même que pour traverser une plaine, et donc la fonction d'estimation sera plus compliquée.

Dans le cas d'illustration de cette page, nous allons considérer un terrain plat, un labyrinthe, avec des cases simples ou des murs. La fonction qui vient naturellement à l'esprit pour estimer le coût dans ce cadre est l'estimation de la distance, le distance à vol d'oiseau (sans obstacle, car si on connaît les obstacles c'est qu'on connaît la carte).

    def dist(self, case):
        """ retourne la distance euclidienne (au carré) à une autre case. """
        return ((self.x - case.x) * (self.x - case.x) +
                (self.y - case.y) * (self.y - case.y))

Il existe d'autres distances du plan (distance de Manhattan par exemple).

La recherche d'un chemin

Voici la fonction de recherche de chemin. Elle procède comme l'algorithme énoncé au début: on parcours les chemins possibles en privilégiant le moins coûteux. Deux conditions d'arrêt de la recherche:

• l'objectif est atteint
• toutes les cases possibles ont été explorées sans atteindre l'objectif

Dans le contexte de cette illustration, une fois dans une case (noeud), nous pouvons nous déplacer que dans les 4 directions gauche, haut, droite, bas. C'est une des contraintes de déplacement qui a été choisie.

    def cherche_chemin(self, grille, debut, fin):
        """ L'algorithme de recherche du chemin par A*.  """
        if __debug__:
            print(grille)
        fini = False
        debut.cout = debut.dist(fin)
        self.liste_ouverte.append(debut)
        while self.liste_ouverte and not fini:
            # parmi les possibilités on choisi celle de plus faible coût
            noeud = min(self.liste_ouverte, key=lambda x: x.cout)
            self.liste_ouverte.remove(noeud)
            self._explore_noeud(noeud, grille, 'gauche', fin)
            self._explore_noeud(noeud, grille, 'haut', fin)
            self._explore_noeud(noeud, grille, 'droite', fin)
            self._explore_noeud(noeud, grille, 'bas', fin)
            self.liste_fermee.append(noeud)

            fini = (noeud.cout == 0)

La fonction _explore_noeud() détermine quoi faire avec la case dans la direction donnée.

• est-ce un mur ? Dans ce cas on ne fait rien
• est-ce une case déjà visitée ? Dans ce cas on ne fait rien non plus, on est déjà passé par là
• est-ce une case pas encore visitée mais déjà la liste de nos possibilités ? Dans ce cas, le coût de cette case est mis à jour si le nouveau chemin pour l'atteindre est moins coûteux
• est-ce une nouvelle possibilité ? Alors on l'ajoute dans la liste ouverte des possibilités avec son coût et sa case parente.

    def _explore_noeud(self, noeud, grille, direction, fin):
        new_case = Case.Case(noeud.x + DECALAGE_X[direction],
                             noeud.y + DECALAGE_Y[direction])
        if 0 <= new_case.x < self.size and 0 <= new_case.y < self.size:
            if __debug__:
                print(direction)
                print('{} {} {}'.format(new_case.x, new_case.y,
                                        grille[new_case.y][new_case.x]))
            if grille[new_case.y][new_case.x] >= 0:  # Case libre
                if __debug__:
                    print('case libre')
                if new_case not in self.liste_ouverte:
                    # Pas dans la liste ouverte
                    if new_case in self.liste_fermee:
                        if __debug__:
                            print('')
                        # il est present
                        # on fait rien
                    else:
                        new_case.cout = new_case.dist(fin)
                        new_case.parent = noeud
                        self.liste_ouverte.append(new_case)
                        if grille[new_case.y][new_case.x] != 1:
                            self.canvas.create_rectangle(
                                31 * new_case.x + 2, 31 * new_case.y + 2,
                                31 * new_case.x + 31, 31 * new_case.y + 31,
                                fill='darkgray', outline='lightgray')
                else:
                    # le noeud existe deja
                    meme_case = self.liste_ouverte[
                        self.liste_ouverte.index(new_case)]
                    if meme_case.cout > new_case.dist(fin):
                        meme_case.cout = new_case.dist(fin)
                        meme_case.parent = noeud

Pour calculer les coordonnées de la nouvelle case potentielle, il y a l'utilisation de DECALAGE_X et DECALAGE_Y. En effet pour éviter de faire 4 tests qui se ressemble, j'ai préféré utiliser un dictionnaire avec le décalage par rapport à la direction choisie:

DECALAGE_X = {'gauche': -1, 'haut': 0, 'droite': 1, 'bas': 0}
DECALAGE_Y = {'gauche': 0, 'haut': -1, 'droite': 0, 'bas': 1}

Illustration de l'algorithme de recherche de chemin A*:

Dans la grille ci-dessous il est possible de placer des murs, le point de départ et d'arriver pour effectuer une recherche de chemin.

Pour cela

• clic gauche: placement d'un mur (rouge)
• double clic gauche: placement du point de départ/arrivé

Une fois le point de d'arrivé fixé, l'algorithme de recherche démarre.

• les cases grises foncés sont les cases potentielles à explorer,
• les cases bleues sont les cases faisant parti du chemin trouvé.

Un troisième double clic gauche réinitialise la grille (pas les murs).