Java programming a * algorithm complete code

preface

A * search algorithm is commonly known as A-star algorithm. This is a path with multiple nodes on the graphics plane to find the lowest passing cost algorithm. Commonly used in games

A maze constructed by 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

Example code structure of this article:

Algorithm theory

The core formula of the algorithm is: F = G + H

Treat the nodes on the map as a grid.

G = the movement cost of moving from the starting point a to the specified node on the grid 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 along the diagonal

The distance is the root 2, or about 1.414 times, spent moving horizontally or vertically. For simplicity, we use 10 and 14 approximations.

Since we are calculating the g value leading to a grid along a specific path, the evaluation method is to take the g value of its parent node, and then increase 14 and 10 respectively according to whether it is diagonal or right angle (non diagonal) relative to the parent node. In this example

The need for two methods will become more, because we get more than one grid from outside the starting grid.

H = estimated movement consumption from the current grid to the end point B. Why is it called "estimation", because we can't know the length of the path in advance. Here we use the Manhattan method, which calculates the horizontal and vertical distance from the current grid to the destination grid

The sum of the number of 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 lattice with the smallest value of F is considered to be the priority path node.

Implementation steps

The algorithm is written in Java. First take a look at the content of the node class

We also need a map class. In the map construction method, I create a two-dimensional array of nodes to implement a maze map, including the start point and end point

Here are the most important astar classes

Operation process

1 start from starting point a and store it as a pending point in an "open list", which is a list of squares to be checked.

2 find all accessible or passable squares around the starting point and skip the impassable squares. Also add them to the open list. Save point a for all these squares as the parent. When we want to describe the path, the information of the parent square

Material is very important. Its specific purpose will be explained later.

3 delete starting point a from the open list, add it to a "close list", and save all squares that do not need to be checked again in the list.

After the above steps, the "open list" includes all nodes around starting point a except obstacles. Their parent nodes are all A. through the formula of F = G + H mentioned earlier, calculate the values of G, h and F of each node, and reduce them from small to small according to the value of F

Sort to large. And do the following for the node with the smallest F value

4. Delete it from the open list and add it to the closed list.

5. Check all adjacent grids. Skip those that cannot be passed (1. In the "closed list", 2. Obstacles) and add them to the open list if they are not already in it. Take the selected grid as the parent node of the new grid.

6. If an adjacent cell is already in the open list, check whether the current path is better. In other words, check whether the g value will be lower if we reach it with a new path. If not, 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 has been around the last node added to the "close list", and only one step is needed to reach end point B.

8. We add end point B to "close list"

9. In the last step, we will express the path from starting point a to ending point B. The role of the parent node is displayed. By "closing the parent node of the end node in the list" and changing its value value, the path can be displayed.

Look at the code

Finally, write a main method

Modify the map and test it again to see the effect