Preface
A* search algorithm is commonly known as A-star algorithm. This is an algorithm that has multiple nodes on the graph plane to find the lowest cost of passing. Commonly used in games
A maze constructed through a two-dimensional array, "%" represents the wall, A is the starting point, B is the end point, "#" represents the obstacle, and "*" represents the path calculated by the algorithm
Code structure of this article:
% % % % % % % % % % oooo % oo # oo % % A o # o B % % oo # oo % % oooo % % % % % % % % ================================================================================================================ % % % % % oo * oo % % o * # * o % % A o # o B % % oo # oo % % oo % % % % % % % % <
Algorithm Theory
The core formula of the algorithm is: F=G+H
Think of nodes on the map as a grid.
G=The movement consumption of moving to the specified node on the grid from the starting point A along the generated path. In this example, we make the horizontal or vertical movement cost 10 and the diagonal direction cost 14. We take these values because we are along the diagonal
The distance is the root number 2 or about 1.414 times the amount taken to move horizontally or vertically. For simplicity, we approximate using 10 and 14.
Since we are calculating the G value leading to a square along a specific path, the method of evaluating is to take the G value of its parent node, and then add 14 and 10 respectively according to its diagonal direction or right angle (non-diagonal) relative to the parent node. In the example, this
The demand for each method becomes more because we have obtained more than one square from outside the starting grid.
H=The estimated movement consumption from the current grid to the end point B. Why is it called "estimation"? Because we have no way to know the length of the path in advance. Here we use the Manhattan method, which calculates horizontal and vertical from the current grid to the destination grid.
The sum of the number of squares of the squares, ignoring the diagonal direction. Then multiply the result by 10.
The value of F is the sum of G and H, which is the standard we use to judge the priority path. The grid with the smallest value of F is considered to be the priority path node.
Implementation steps
The algorithm is written in Java, first look at the content of the node class
package a_star_search; /** * Node class* @author zx * */ public class Node { private int x; //x coordinates private int y; //y coordinates private String value; //The value of the node private double FValue = 0; //F value private double GValue = 0; //G value private double HValue = 0; //H value private boolean Reachable; //Is it reachable (Is it an obstacle) private Node PNode; //Parent node public Node(int x, int y, String value, boolean reachable) { super(); this.x = x; this.y = y; this.value = value; Reachable = reachable; } public Node() { super(); } public int getX() { return x; } public void setX(int x) { this.x = x; } public int getY() { return y; } public void setY(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 Reachable; } public void setReachable(boolean reachable) { Reachable = reachable; } public Node getPNode() { return PNode; } public void setPNode(Node pNode) { PNode = pNode; } }Also need a map class. In the map construction method, I implement a maze map by creating a two-dimensional array of nodes, which includes the start and end points.
package a_star_search;public class Map {private Node[][] map;//node array private Node startNode;//start private Node endNode;//end point public Map() {map = new Node[7][7];for (int i = 0;i<7;i++){for (int j = 0;j<7;j++){map[i][j] = new Node(i,j,"o",true);}}for (int d = 0;d<7;d++){map[0][d].setValue("%");map[0][d].setReachable(false);map[d][0].setValue("%");map[d][0].setReachable(false);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);}}<span style="white-space:pre"> </span>//Show 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;}public void 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 void setEndNode(Node endNode) {this.endNode = endNode;}}Here are the most important AStar classes
Operation process
1 Start at the starting point A and save it as the pending point into a "Open List", which is a list of the squares to be checked.
2 Find all accessible or passable squares around the starting point and skip the unpassable squares. Add them to the opening list as well. Save point A for all these grids as the "parent grid". When we want to describe the path, the parent square
Material is very important. Its specific purpose will be explained later.
3 Delete the starting point A from the open list and add it to a "close list" to save all squares that do not need to be checked again.
After the above steps, the "Open List" contains all nodes around the starting point A except for the obstacles. Their parent nodes are all A. Through the formula F=G+H mentioned earlier, they calculate the G, H, and F values of each node, and according to the value of F, they are small
Sorting to large. And do the following operations on the node with the smallest F value
4. Remove it from the on list and add it to the off list.
5. Check all adjacent grids. Skip those that are not passed (1. in the "Close List" and 2. Obstacles) and add them to the Open List if they are not already in it. Take the selected square as the parent node of the new square.
6. If an adjacent grid is already in the open list, check whether the current path is better. In other words, check if the G value will be lower if we reach it with a new path. If not, then nothing
Do. (Here, there is no judgment in my code)
7. We repeat this process until the target grid (end point "B") is added to the "Open List", indicating that end point B is already around the previous node added to the "Close List". You only need to take one step to reach end point B.
8. We add end point B to the "Close List"
9. In the last step, we need to represent the path from starting point A to end point B. The role of the parent node is displayed. By changing the value of the parent node of the end point node in the "Close the list", you can display the path by following the clues.
Check out the code
package a_star_search;import java.util.ArrayList;public class AStar {/** * Use ArrayList array as "Open List" and "Close List" */ArrayList<Node> open = new ArrayList<Node>();ArrayList<Node> close = new ArrayList<Node>();/** * Get H value* @param currentNode: Current node* @param endNode: End point* @return */public double getHValue(Node currentNode,Node endNode){ return (Math.abs(currentNode.getX() - endNode.getX()) + Math.abs(currentNode.getY() - endNode.getY()))*10;}/** * Get G value* @param currentNode: current node* @return */public double getGValue(Node currentNode){if(currentNode.getPNode()!=null){if(currentNode.getX()==currentNode.getPNode().getX()||currentNode.getY()==currentNode.getPNode().getY()){//Judge the positional relationship between the current node and its parent node (horizontal? Diagonal) return currentNode.getGValue()+10;}return currentNode.getGValue()+14;}return currentNode.getGValue();}/** * Get F value: G + H * @param currentNode * @return */public double getFValue(Node currentNode){return currentNode.getGValue()+currentNode.getHValue();}/** * Add the nodes around the selected node to the "Open List" * @param node * @param map */public void inOpen(Node node,Map map){int x = node.getX();int y = node.getY();for (int i = 0;i<3;i++){for (int j = 0;j<3;j++){//The judgment condition is: the node is reachable (that is, it is not an obstacle, not in the closed list), the opening list is not included, and it is not selected 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]);//The selected node is used as the parent node 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.getEndNode()));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]);}}}}/** * Sort the nodes in the open list from small to large by F value* @param arr */public void sort(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);}}}}/** * Add node to "Close List" * @param node * @param open */public void inClose(Node node,ArrayList<Node> open){if(open.contains(node)){node.setReachable(false);//Set unreachable open.remove(node);close.add(node);}}public void search(Map map){//Operate the nodes around the starting point, that is, inOpen(map.getMap()[map.getStartNode().getX()][map.getStartNode().getY()],map);close.add(map.getMap()[map.getStartNode().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().getX()][map.getStartNode().getY()]);sort(open);//Repeat the steps do{inOpen(open.get(0), map);inClose(open.get(0), open);sort(open);}while(!open.contains(map.getMap()[map.getEndNode().getX()][map.getEndNode().getY()]);// When you know that the end point is included in the open list, loop exit 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="white-space:pre"> </span>node = map.getMap()[map.getEndNode().getX()][map.getEndNode().getY()]; //<span style="white-space:pre"> </span>while(!(node.getX() ==map.getStartNode().getX()&&node.getY() ==map.getStartNode().getY())){ //<span style="white-space:pre"> </span>node.getPNode().setValue("*"); //<span style="white-space:pre"> </span>node = node.getPNode(); //<span style="white-space:pre"> </span>}}//<span style="white-space:pre"> </span>map.getMap()[map.getStartNode().getX()][map.getStartNode().getY()].setValue("A");}}Finally write a Main method
package a_star_search; public class 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(); } }Modify the map and test it to see the effect
% % % % % % % % % % oooo % oo # oo % % A o # o B % % oo # oo % % oooo % % % % % % % % % ====================================================================================% % % % % % % oo # oo % % A o # o B % % oo # oo % % oo % % % % % % % % % %
Summarize
To ensure that the shortest path (the optimal solution) is found, the key lies in the selection of the estimation function h(n): the actual distance value of the estimation value h(n)<=n to the target node. In this case, there are many points searched, the search range is large, and the efficiency is low. But can get
Optimal solution. If the estimated value > actual value, the search number of points is small, the search range is small, and the efficiency is high, but it cannot guarantee that the optimal solution is obtained.
The biggest feeling is: the most taboo thing about fishing for three days and two days of drying the net. The amount may not be large, but it must be continuity, and the key is persistence.
I hope every programmer can happily type in code and do what he likes to do.
The above is all the content of this article about Java programming and implementing the complete code of A* algorithm. I hope it will be helpful to everyone. Interested friends can continue to refer to other related topics on this site. If there are any shortcomings, please leave a message to point it out.