Préface
A * L'algorithme de recherche est communément appelé algorithme A-star. Il s'agit d'un algorithme qui a plusieurs nœuds sur le plan du graphique pour trouver le coût de passage le plus bas. Couramment utilisé dans les jeux
Un labyrinthe construit par un tableau bidimensionnel, "%" représente le mur, a est le point de départ, b est le point final, "#" représente l'obstacle, et "*" représente le chemin calculé par l'algorithme
Structure du code de cet article:
%%%%%%%%% oooo% oo # oo%% a o # o b%% oo # oo%% oooo%%%%%% ====================================================================================================================================. oo * oo%% o * # * o%% a o # o b%% oo # oo%% oo%%%%%%% <
Théorie de l'algorithme
La formule centrale de l'algorithme est: f = g + h
Considérez les nœuds sur la carte comme une grille.
G = La consommation de mouvement de se déplaçant vers le nœud spécifié sur la grille du point de départ A le long du chemin généré. Dans cet exemple, nous faisons le coût de mouvement horizontal ou vertical 10 et le coût de la direction diagonale 14. Nous prenons ces valeurs parce que nous sommes le long de la diagonale
La distance est la racine numéro 2 ou environ 1,414 fois la quantité prise pour se déplacer horizontalement ou verticalement. Pour plus de simplicité, nous approximations en utilisant 10 et 14.
Étant donné que nous calculons la valeur G menant à un carré le long d'un chemin spécifique, la méthode d'évaluation est de prendre la valeur G de son nœud parent, puis d'ajouter 14 et 10 respectivement en fonction de sa direction diagonale ou de son angle droit (non diagonal) par rapport au nœud parent. Dans l'exemple, ceci
La demande pour chaque méthode devient plus car nous avons obtenu plus d'un carré de l'extérieur de la grille de départ.
H = La consommation de mouvement estimée de la grille actuelle au point final B. Pourquoi est-ce appelé "estimation"? Parce que nous n'avons aucun moyen de connaître la longueur du chemin à l'avance. Ici, nous utilisons la méthode de Manhattan, qui calcule horizontal et vertical de la grille actuelle à la grille de destination.
La somme du nombre de carrés des carrés, ignorant la direction diagonale. Multipliez ensuite le résultat par 10.
La valeur de F est la somme de G et H, qui est la norme que nous utilisons pour juger du chemin prioritaire. La grille avec la plus petite valeur de F est considérée comme le nœud de chemin de la priorité.
Étapes de mise en œuvre
L'algorithme est écrit en Java, regardez d'abord le contenu de la classe de nœuds
package a_star_search; / ** * Classe de nœuds * @author zx * * / public class node {private int x; // x coordonne privilégiée int y; // Y coordonne la valeur de chaîne privée; // la valeur du nœud privé double fValue = 0; // valeur f privée double gvalue = 0; // GA VALUE privé Double hvalue = 0; // HAUTE H VALEUR PRIVATE BOOLEAN ACHETABLE; // est-il accessible (est-ce un obstacle) nœud privé PNode; // Nœud de nœud parent nœud public (int x, int y, valeur de chaîne, booléen accessible) {super (); this.x = x; this.y = y; this.value = valeur; Accessible = accessible; } public node () {super (); } public int getX () {return x; } public void setx (int x) {this.x = x; } public int gety () {return y; } public void sey (int y) {this.y = y; } public String getValue () {return Value; } public void setValue (String Value) {this.value = value; } public double getFValue () {return fValue; } public void setFValue (double fValue) {fValue = fValue; } public double getGValue () {return gvalue; } public void setGValue (double gvalue) {gvalue = gvalue; } public double gethValue () {return hvalue; } public void SethValue (double hvalue) {hvalue = hvalue; } public boolean isReachable () {return accesableable; } public void setReachable (booléen accespaitable) {accesableable = accesableable; } Node public getPNode () {return pNode; } public void setPnode (node pNode) {pnode = pNode; }}Besoin également d'une classe de carte. Dans la méthode de construction de la carte, j'implémente une carte de labyrinthe en créant un tableau de nœuds bidimensionnel, qui comprend les points de début et d'extrémité.
package a_star_search; public class map {nœud privé [] [] map; // nœud nœud nœud privil Node (i, j, "o", true);}} pour (int d = 0; d <7; d ++) {map [0] [d] .setValue ("%"); map [0] [d] .SetReachable (false); map [d] [0] .setValue ("%"); map [d] [0] .SetReachable (fal se); map [6] [d] .setValue ("%"); map [d] [6] .setValue ("%"); map [d] [6] .setReachable (false);} map [3] [1] .setValue ("a"); startnode = map [3] [1]; map [3] [5] .setValue ("b"); endnode = map [3] [5]; for (int k = 1; k <= 3; k ++) {map [k + 1] [3] .setValue ("#"); map [k + 1] [3] .SetReachable (false);}} <pypre map public void showmap () {for (int i = 0; i <7; i ++) {for (int j = 0; j <7; j ++) {System.out.print (map [i] [j] .getValue () + "");} system.out.println ("");}} public node [] [] getMap () {return map;} setMap (node [] [] map) {this.map = map;} public node getStartNode () {return startNode;} public void SetStartNode (node startNode) {this.startNode = startNode;} public node getEndnode () {return endnode;} public vide setenDnode (node endnode) {this.endNode = endnode;}}Voici les classes ASTAR les plus importantes
Processus de fonctionnement
1 Commencez au point de départ A et enregistrez-le en attente dans une "liste ouverte", qui est une liste des carrés à vérifier.
2 Trouvez tous les carrés accessibles ou passables autour du point de départ et ignorez les carrés impassables. Ajoutez-les également à la liste d'ouverture. Enregistrer le point A pour toutes ces grilles comme la "grille parent". Lorsque nous voulons décrire le chemin, le parent carré
Le matériel est très important. Son objectif spécifique sera expliqué plus tard.
3 Supprimez le point de départ A de la liste ouverte et ajoutez-le à une "liste de clôture" pour sauver tous les carrés qui n'ont plus besoin d'être vérifiés.
Après les étapes ci-dessus, la "liste ouverte" contient tous les nœuds autour du point de départ A à l'exception des obstacles. Leurs nœuds parents sont tous A. à travers la formule F = G + H mentionné plus tôt, ils calculent les valeurs G, H et F de chaque nœud, et selon la valeur de F, ils sont petits
Tri à grand. Et effectuez les opérations suivantes sur le nœud avec la plus petite valeur F
4. Supprimez-le de la liste ON et ajoutez-le à la liste OFF.
5. Vérifiez toutes les grilles adjacentes. Évitez ceux qui ne sont pas passés (1. Dans la "liste de clôture" et 2. Obstacles) et ajoutez-les à la liste ouverte si elles ne sont pas déjà dedans. Prenez le carré sélectionné comme nœud parent du nouveau carré.
6. Si une grille adjacente est déjà dans la liste ouverte, vérifiez si le chemin actuel est meilleur. En d'autres termes, vérifiez si la valeur G sera inférieure si nous l'atteignons avec un nouveau chemin. Sinon, alors rien
Faire. (Ici, il n'y a pas de jugement dans mon code)
7. Nous répétons ce processus jusqu'à ce que la grille cible (point final "B") soit ajoutée à la "liste ouverte", indiquant que le point final B est déjà autour du nœud précédent ajouté à la "liste de clôture". Il vous suffit de faire un pas pour atteindre le point final B.
8. Nous ajoutons le point final B à la "liste de clôture"
9. Dans la dernière étape, nous devons représenter le chemin du point de départ A au point final B. Le rôle du nœud parent est affiché. En modifiant la valeur du nœud parent du nœud de point final dans "Fermer la liste", vous pouvez afficher le chemin en suivant les indices.
Découvrez le code
Package a_star_search; Importer java.util.arrayList; classe publique Astar {/ ** * Utilisez ArrayList Array comme "Liste ouverte" et "Liste de fermeture" * / ArrayList <Node> Open = New ArrayList <NODE> (); ArrayList <Node> Close = New ArrayList <Node> (); / ** * GET H VALUE * @PARAM Point * @return * / public Double GethValue (Node CurrentNode, nœud EndNode) {return (math.abs (currentNode.getx () - endnode.getx ())) * 10;} / ** * GET G GET GETAG currentNode) {if (currentNode.getPnode ()! = null) {if (currentNode.getx () == currentNode.getPnode (). getX () || currentNode.gety () == CurrentNode.getPnode (). Gety ()) {// Jugez la relation de position entre le nœud actuel et son nœud parent (Horizontal? Diagon) currentNode.getGValue () + 10;} return currentNode.getGValue () + 14;} return currentNode.getGValue ();} / ** * Get F Valeur: G + H * @param CurrentNode * @return * / public Double GetFvalue (NODE COURTHNODE) {return CurrentNode. * Ajoutez les nœuds autour du nœud sélectionné à la "Liste ouverte" * @param nœud * @param map * / public void inpen (nœud nœud, map map) {int x = node.getx (); int y = node.gety (); for (int i = 0; i <3; i ++) {pour (int j = 0; j <3; j ++) {// la condition de jugement est: la réalité (j <3; j ++) { est, ce n'est pas un obstacle, pas dans la liste fermée), la liste d'ouverture n'est pas incluse, et elle n'est pas sélectionnée if (map.getmap () [x-1 + i] [y-1 + j] .isReachable () &&! open.contains (map.getmap () [x-1 + i] [y-1 + j]) & &! (x == (x-1 + i) && y == (y-1 + j))) {map.getmap () [x-1 + i] [y-1 + j] .setpnode (map.getmap () [x] [y]); // le Le nœud sélectionné est utilisé comme nœud parent map.getmap () [x-1 + i] [y-1 + j] .setGValue (getGValue (map.getmap () [x-1 + i] [y-1 + j])); map.getmap () [x-1 + i] [y-1 + j] .sethvalue (gethValue (map.getmap () [x-1 + i] [y-1 + j], map.ge.ge TendNode ())); map.getmap () [x-1 + i] [y-1 + j] .setfValue (getFValue (map.getmap () [x-1 + i] [y-1 + j])); open.add (map.getmap () [x-1 + i] [y-1 + j]);}}}} / ** * Trier les nœuds dans la liste ouverte de la petite à grande valeur b par f * @param arr * / public void tri (arrayList <Node> arr) {for (int i = 0; i <arr.size () - 1; i ++) {for (int j = i + 1; j <arr.size (); j ++) {if (arr.get (i) .getfvalue ()> arr.get (j) .getfValue ()) {node tmp = new node (); tmp = arr.get (i); arr.set (i, arr.get (j)); arr.set (j, tmp);}}}} / ** * Ajouter le nœud à "close la liste" * @param nœud * @param open * / public Void Inclose (Node, araye <node * @param open * / public incline Open) {if (open.Contains (node)) {node.setReachable (false); // set inapparable Open.Remove (node); close.add (node);}} public void search (map map) {// fonctionne les nœuds autour du point de départ, c'est-à-dire, c'est-à-dire, inopen (map.getmap () [map.getStartNode (). getX ()] [map.getStartNode (). gety ()], map); close.add (map.getmap () [map.getStart Node (). Getx ()] [map.getStartNode (). GetX ()] [map.getStartNode (). Gety ()]); map.getmap () [map.getStartNode (). Getx ()] [map.g etstartNode (). gety ()]. setReachable (false); map.getmap () [map.getStartNode (). getX ()] [map.getStartNode (). gety ()]. setPnode (map.getmap () [map.getStartNode (). Do {Inopen (open.get (0), map); inclose (open.get (0), open); tri (open);} while (! open.contains (map.getmap () [map.gettendNode (). getX ()] [map.gettendNode (). gety ()]); // lorsque vous savez que le point final est inclus dans la liste ouverte, Loop exit Loop extérieur inClose(map.getMap()[map.getEndNode().getX()][map.getEndNode().getY()], open);showPath(close,map);}/** * Mark the path* @param arr * @param map */public void showPath(ArrayList<Node> arr,Map map) {if(arr.size()>0){Node node = new Node (); // <span style = "blanc-espace: pre"> </ span> node = map.getmap () [map.getEndNode (). GetX ()] [map.getEndNode (). Gety ()]; == map.getStartNode (). gety ())) {// span style = "white-space: pre"> </ span> node.getpnode (). setValue ("*"); style = "blanc-espace: pre"> </span> map.getmap () [map.getStartNode (). getX ()] [map.getStartNode (). gety ()]. setValue ("a");}}Écrivez enfin une méthode principale
package a_star_search; classe publique MAINTest {public static void main (String [] args) {map map = new Map (); Astar Astar = new Astar (); map.showmap (); astar.search (map); System.out.println("============================================================================================ ==============================================================================================================================. ==============================================================================================================================. =================================================================================================================================. map.showmap ();}}Modifiez la carte et testez-la pour voir l'effet
%%%%%%%% oooo% oo # oo%% a o # o b%% oo # oo%% oooo%%%%%%%% ===============================================================================================================================. %%%%%
Résumer
Pour s'assurer que le chemin le plus court (la solution optimale) est trouvé, la clé réside dans la sélection de la fonction d'estimation H (n): la valeur de distance réelle de la valeur d'estimation H (n) <= n au nœud cible. Dans ce cas, il y a de nombreux points recherchés, la plage de recherche est grande et l'efficacité est faible. Mais peut obtenir
Solution optimale. Si la valeur estimée> valeur réelle, le numéro de recherche de points est faible, la plage de recherche est faible et l'efficacité est élevée, mais elle ne peut garantir que la solution optimale est obtenue.
Le plus grand sentiment est: la chose la plus taboue à propos de la pêche pendant trois jours et deux jours de séchage sur le filet. Le montant peut ne pas être important, mais il doit être la continuité et la clé est la persistance.
J'espère que chaque programmeur pourra taper avec plaisir de taper le code et faire ce qu'il aime faire.
Ce qui précède est tout le contenu de cet article sur la programmation Java et la mise en œuvre du code complet d'un algorithme *. J'espère que ce sera utile à tout le monde. Les amis intéressés peuvent continuer à se référer à d'autres sujets connexes sur ce site. S'il y a des lacunes, veuillez laisser un message pour le signaler.