A la base, l'algorithme est conçu pour un ordinateur (perso, je tente en ce moment de l'adapter sur calculatrice CASIO 35+E). Il faudra donc l'adapter à minecraft (par ex. , la matrice I pourrait être un rectangle constitué de blocs verts, rouges ou bleus)
J'ai tenté d'être le plus simple posible, mais si tu as une question, n'hésite pas à la poser !
Pour rendre l'explication plus facile, on considérera l'algorithme comme une personne se déplaçant sur le graphe.
Un noeud est un endroit où l'algorithme peut aller. Comme on est dans Minecraft, je parlerai de "case".
Un graphe est un ensemble de noeuds.
Le noeud que l'algorithme vient de quitter est le parent du noeud où se trouve l'algorithme actuellement.
Une matrice est un tableau en 2 dimensions.
Le coût d'un noeud est sa distance au départ, calculée comme ceci(avec C le coût, [X;Y] les coordonnées du noeud et [D;E] les coordonnées du départ :
X>D⇒X-D→C
D>X⇒D-X→C
Y>E⇒C+(Y-E)→C
E>Y⇒C+(E-Y)→C
Plus le coût est petit, plus le chemin sera court.
L'algorithme A* stocke les infos de 3 façons différentes :
-la liste ouverte, à savoir les noeuds qui pourraient être la suite du chemin. Les informations contenues sont les coordonées X et Y du noeud et son coût. Ces infos sont fusionnées en une seule valeur égale à 1 00 00 C + 1 00 X + Y (note : si X est supérieur à 99 99 ou si Y est supérieur à 99, il y aura corruption pour éviter ça, il faudrait fusionner les valeurs avec plus d'espace, par exemple 1 000 000 C+1 000 X + Y.)
-la matrice I, contenant le statut des cases :
0 : inconnu ou "stand by"(liste ouverte)
1 : dejà choisi comme chemin
2 : obstacle
3 : arrivée
La matrice II contient les coordonnées X et Y des parents sous la forme (X×100+Y)
Pour commençer, mettre la case de départ dans la Liste ouverte (c'est le seul chemin possible)
Commencer la boucle :
Ici, c'est le moment le plus important : on va choisir la suite du chemin. On sélectionne donc la case avec le meilleur C(=le plus petit C) qu'on supprime de la liste ouverte et qu'on marque comme "choisi" dans la matrice 1(ça évite d'essayer deux fois le même chemin !). Ce noeud est constituée comme "actuelle" (dans mon image, l'algorithme est situé dessus et regarde les 4 cases autour).
Les autres cases dans la liste ouverte sont gardées pour plus tard, au cas où le chemin actuel est un cul de sac (c'est pour ça qu'on a la matrice I, sinon l'algorithme recommencerait à se diriger vers le cul-de-sac : il ne faut jamais marcher deux fois sur la même case !).
Pour chacun des 4 cases à côté de la case actuelle, on regarde la valeur dans la matrice I :
Si 2(obstacle) ou 1(vu et choisi) : ne rien faire car on ne peut pas marcher sur les obstacles et que on ne doit pas prendre deux fois le même chemin.
Si 0(inconnu ou liste ouverte) : mettre la variable CASE ACTUELLE comme parent(donc dans la matrice II). Calculer son coût C et le mettre dans la liste ouverte en compagnie de ses coordonnées.
Si 3(arrivée) : on retrouve le chemin grâce aux parents, l'algorithme est fini !
Puis on recommence la boucle.
P.S. : si tu veux, je peux également te passer le brouillon du programme sur Casio 35+ E.
EDIT : A* ne trouve pas toujours le meilleur chemin, mais il trouve toujours un chemin, et cela rapidement et simplement (comparé à l'algorithme de Dijkstra qui attends d'avoir testé toutes les possibilités pour donner une réponse, ce qui serait lent dans Minecraft).
J'ai tenté d'être le plus simple posible, mais si tu as une question, n'hésite pas à la poser !
Pour rendre l'explication plus facile, on considérera l'algorithme comme une personne se déplaçant sur le graphe.
Un noeud est un endroit où l'algorithme peut aller. Comme on est dans Minecraft, je parlerai de "case".
Un graphe est un ensemble de noeuds.
Le noeud que l'algorithme vient de quitter est le parent du noeud où se trouve l'algorithme actuellement.
Une matrice est un tableau en 2 dimensions.
Le coût d'un noeud est sa distance au départ, calculée comme ceci(avec C le coût, [X;Y] les coordonnées du noeud et [D;E] les coordonnées du départ :
X>D⇒X-D→C
D>X⇒D-X→C
Y>E⇒C+(Y-E)→C
E>Y⇒C+(E-Y)→C
Plus le coût est petit, plus le chemin sera court.
L'algorithme A* stocke les infos de 3 façons différentes :
-la liste ouverte, à savoir les noeuds qui pourraient être la suite du chemin. Les informations contenues sont les coordonées X et Y du noeud et son coût. Ces infos sont fusionnées en une seule valeur égale à 1 00 00 C + 1 00 X + Y (note : si X est supérieur à 99 99 ou si Y est supérieur à 99, il y aura corruption pour éviter ça, il faudrait fusionner les valeurs avec plus d'espace, par exemple 1 000 000 C+1 000 X + Y.)
-la matrice I, contenant le statut des cases :
0 : inconnu ou "stand by"(liste ouverte)
1 : dejà choisi comme chemin
2 : obstacle
3 : arrivée
La matrice II contient les coordonnées X et Y des parents sous la forme (X×100+Y)
Pour commençer, mettre la case de départ dans la Liste ouverte (c'est le seul chemin possible)
Commencer la boucle :
Ici, c'est le moment le plus important : on va choisir la suite du chemin. On sélectionne donc la case avec le meilleur C(=le plus petit C) qu'on supprime de la liste ouverte et qu'on marque comme "choisi" dans la matrice 1(ça évite d'essayer deux fois le même chemin !). Ce noeud est constituée comme "actuelle" (dans mon image, l'algorithme est situé dessus et regarde les 4 cases autour).
Les autres cases dans la liste ouverte sont gardées pour plus tard, au cas où le chemin actuel est un cul de sac (c'est pour ça qu'on a la matrice I, sinon l'algorithme recommencerait à se diriger vers le cul-de-sac : il ne faut jamais marcher deux fois sur la même case !).
Pour chacun des 4 cases à côté de la case actuelle, on regarde la valeur dans la matrice I :
Si 2(obstacle) ou 1(vu et choisi) : ne rien faire car on ne peut pas marcher sur les obstacles et que on ne doit pas prendre deux fois le même chemin.
Si 0(inconnu ou liste ouverte) : mettre la variable CASE ACTUELLE comme parent(donc dans la matrice II). Calculer son coût C et le mettre dans la liste ouverte en compagnie de ses coordonnées.
Si 3(arrivée) : on retrouve le chemin grâce aux parents, l'algorithme est fini !
Puis on recommence la boucle.
P.S. : si tu veux, je peux également te passer le brouillon du programme sur Casio 35+ E.
EDIT : A* ne trouve pas toujours le meilleur chemin, mais il trouve toujours un chemin, et cela rapidement et simplement (comparé à l'algorithme de Dijkstra qui attends d'avoir testé toutes les possibilités pour donner une réponse, ce qui serait lent dans Minecraft).
Dernière édition:
