A list,
1.1 The Search Area
Let’s say someone is moving from point A to point B, but there’s A wall between the two points. As shown in Figure 1, green is A, red is B, and the middle blue is the wall.
Figure 1
You’ll notice that we’re dividing the area we’re searching into squares. This is the first step in pathfinding, simplifying the search area, just like we did here. This particular method simplifies our search area to a 2-dimensional array. Each entry in the array represents a cell whose states are walkalbe and unwalkable. You find the path by figuring out which squares you need to go to get from A to B. Once the path is found, the character moves from the center of one square to the center of another until it reaches its destination.
The center point of the grid we call “Nodes.” If you read other articles about A* pathfinding algorithms, you’ll find that people often talk about nodes. Why not just describe it as square? Because it is possible to divide the search area into multiple morphologies other than squares, such as hexagons, rectangles, or even any number of morphologies. The nodes can be placed inside any polygon, in the center of a polygon, or on the edge of a polygon. We use this system because it’s the easiest.
1.2 Starting the Search
Once we have reduced the search area to a quantifiable set of nodes, as we did above, the next step is to find the shortest path. In A*, we start at the starting point, check its adjacent squares, and then expand around until we find the target.
This is how we begin our pathfinding journey:
1. Start with A and add it to an open list of squares. This open list is kind of like a shopping list. Now, of course, there’s only one item in the Open List, and that’s the starting point, A, and more and more items will be added over time. The cells in the Open list are paths that may or may not be traversed along the way. Basically an open list is a list of boxes to check.
2. Look at the squares adjacent to the starting point A (ignoring the squares occupied by walls, rivers, and other illegal terrain) and add the walkable or reachable squares to the open list. Set the starting point A to the parent (parent node or parent Square) of these squares. The contents of these parent nodes are important when tracing paths. Explained later.
3. Remove A from the open list and add it to the close list. Each square in the close list is no longer concerned with.
As shown in the figure below, the dark green box is the starting point, and the light blue box indicates that the box has been added to the Close list. The black squares next to it are checked, and their boxes are bright green. Each black square has A gray pointer to its parent, which is the starting point A.
Figure 2.
Next, we need to choose A square from the Open List adjacent to the starting point A and repeat the previous steps more or less as described below. But which square to choose? The one with the lowest F value.
1.3 Path Sorting
The key to figuring out the squares that make up the path is this equation:
F = G + H
Here,
G = The cost of moving from the starting point A to the specified square, along the path generated by reaching that square.
H = The estimated cost of moving from the specified square to the end point B. This is often called heuristics, and it’s a little confusing. Why do you call it that? Because it’s a guess. We don’t know the true distance until we find the path, because there are all kinds of things (walls, water, etc.) along the way. This tutorial will teach you one way to calculate H, and you can find other ways online.
Our path is created by iterating through the Open list, selecting the square with the lowest F value. This process is described in detail later. So let’s see how we compute the top equation.
As mentioned above, G is the cost of moving from the starting point A to the specified square. In this case, the cost of the horizontal and vertical moves is 10, and the cost of the diagonal moves is 14. These data are used because the actual diagonal movement distance is the square root of 2, or an approximate 1.414 times the cost of moving horizontally or vertically. I use 10 and 14 for simplicity. The ratio is right, we avoid the calculation of open and decimal. It’s not that we don’t have the ability or don’t like math. Using these numbers can also make computers faster. As you’ll see later, pathfinding algorithms are slow without these techniques.
Since we are calculating the G value along the path to a given square, the way to calculate the G value of that square is to find the G value of its father, and then add 10 or 14 depending on whether the father is straight or diagonal. This approach will become clearer as we get more squares away from the starting point.
There are many ways to estimate H. Here we use the Manhattan method to calculate the number of squares it takes to reach the target by moving horizontally or vertically from the current square, ignoring diagonal movements, and then multiply the total by 10. It’s called the Manhattan method because it’s like counting the number of blocks traversed from one location to another, and you can’t cross the blocks diagonally. And the important thing is to calculate H is to ignore obstacles in the path. This is an estimate of the remaining distance, not the actual distance, hence the name heuristic.
You add G and H and you get F. The results of our first step are shown in the figure below. Each box is labeled with the values F, G, and H, just like the box to the right of the starting point, with F in the top left, G in the bottom left, and H in the bottom right.
Figure 3
Ok, now let’s look at some of these squares. In the box marked with letters, G = 10. That’s because horizontally it’s only one square from where we started. The above, below, and left squares directly adjacent to the starting point have a G of 10, and the diagonal squares have a G of 14.
H value is obtained by estimating the Manhattan distance between the starting point and the end point (red square), which only moves horizontally and vertically, and ignores the walls along the way. Using this method, the square to the right of the starting point is 3 squares away from the end point, so H is equal to 30. The square above this square has a distance of 4 squares from the end (note that only transverse and longitudinal distances are counted), so H is equal to 40. For the other squares, you can use the same method to figure out how to get the H value.
The F value of each square, again, you just add the G value and the H value.
Continuing the Search
To continue searching, we select the node with the lowest F value from the Open List, and then do the following for the selected square:
4. Take it out of the open list and put it in the close list.
5. Check all adjacent squares and ignore squares that are in the close list or unwalkable (such as walls, water, or other illegal terrain). If they are not in the open lsit, add them to the Open list.
Set our selected square as the father of these newly added squares.
6. If an adjacent square is already in the Open list, check whether the path is better, that is, whether the value of G to reach that square through the current square (the one we selected) is smaller. If not, do nothing.
Conversely, if G is smaller, the father of that square is set to the current square (the one we selected), and then the F and G values of that square are recalculated. If you’re still confused, check out the image below.
Figure 4.
Ok, let’s see how it works. Of our initial nine squares, eight were in the Open list, and the starting point was put into the close list. Of these squares, the one to the right of the starting point has the lowest F value of 40, so we choose this one as the next one to deal with. Its frame is highlighted with blue lines.
First, we moved it from the open list to the close list (that’s why the blue line is highlighted). And then we check the squares next to it. The square to its right is the wall, which we ignore. The square to the left of it is the starting point, and in the close list, we also ignore it. The other four adjacent squares are in the Open list, and we need to check whether the path to get there is better through this square, using the G value to determine. Let’s look at the top square. It now has a G value of 14. If we get there via the current square, the G value will be 20(where 10 is the G value for reaching the current square, plus 10 for moving vertically from the current square to the upper square). Obviously 20 is bigger than 14, so this is not the optimal path. If you look at the picture you’ll understand. It’s better to move diagonally from the starting point to that square than to move horizontally and then vertically.
When we checked all four adjacent squares already in the Open list, we found no better path through the current square, so we didn’t make any changes. Now that we have checked all the adjacent squares of the current square and processed them, it is time to select the next square to be processed.
So we’re going through our open list again, and now it only has seven squares, and we need to select the one with the lowest F value. Now, what’s interesting is that this time we have two boxes with an F of 54, so which one do we choose? It doesn’t matter. In terms of speed, it is faster to select the last square to be added to the Open list. This results in a preference to use newly found squares first when approaching the target during pathfinding. But it doesn’t matter. (Different treatment of the same data causes two versions of A* to find different paths of the same length).
We select the box at the bottom right of the starting point, as shown in the image below.
Figure 5
This time, when we examine the adjacent squares, we find that the square to its right is the wall, so ignore it. Same thing up here.
Let’s also ignore the one under the wall. Why is that? Because you can’t move directly from the current square to that square without crossing the corner. You need to go down and then move to the square to get around the corner. (Note: The corner crossing rule is optional, depending on how your nodes are placed)
So we’re left with five adjacent squares. The two squares below the current square are not yet in the Open list, so add them and make the current square their father. Of the remaining three squares, two are already in the close list (one is the starting point and the one above the current square with the outer box highlighted) and we ignore them. The last square, which is the square to the left of the current square, we check to see if the current square to get there has a smaller value of G. No. So we are ready to select the next box to be processed from the Open List.
Repeat this process until the end point is also added to the Open List, as shown in the figure below.
Figure 6.
Notice that the two squares below the starting point have a different father. It had a G value of 28 and it was pointing to the upper right square. Now it has a G of 20, and it points to the square directly above it. This happens somewhere during pathfinding, where the G value is checked and becomes lower with the new path, so the parent node is reset and the G and F values are recalculated. Although this change is not significant in this case, in many cases it can lead to a dramatic change in pathfinding results.
So how do we determine the actual path? Very simple, start at the end, press the arrow and move to the parent, so you’re brought back to the beginning, and that’s your path. See the figure below. Moving from A to B is simply moving from the center of one square on the path to the center of another square, all the way to the destination. It’s that simple!
Figure 7.
Summary of the A* Method
Ok, now that you’ve read the whole introduction, let’s put all the steps together:
Add the starting point to the Open list.
2. Repeat the following process:
A. Iterate through the Open List and find the node with the smallest F value as the node to be processed.
B. Move this node to the close list.
C. For each of the eight adjacent squares of the current square?
◆ If it is not reachable or it is in the close list, ignore it. Otherwise, do the following.
◆ If it is not in the Open list, add it to the Open List and set the current square to its parent, recording the values of F, G and H for that square.
◆ If it is already in the Open list, check whether the path to it is better, using the G value as a reference. A smaller value of G means that this is a better path. If so, set its father to the current square and recalculate its G and F values. If your Open list is sorted by F, you may need to reorder it.
D. Stop when you
◆ Add the end point to the open list, where the path has been found, or
The open list is empty. There is no path at this time.
3. Save path. Starting at the end, each square moves along the parent node to the beginning, and that’s your path
Two, code demonstration
Grid map has obstacles on both sides of the diagonal can not pass, based on A star algorithm to achieve grid path planning clc close all G= [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0. 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0. 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0. 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0, 0, 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0. 0 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 0 0; 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0, 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0, 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0. 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0; 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0. 0 0 1 to 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0; 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0. 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 0 1; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0; 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0; 0 0 0 0 0; 0 0 0 0 0; 0 0 0 0; 0 0 0; 0 0 0; 0 0 0; 0 0; 0 0; 0 0; 0; 0; 0; 0; 0; Ditu. Qishi = [1, 1]; % beginning ditu mubiao = [20]; % the finish ditu. Daxiao = 20; Zhangai =[]; for i=1:ditu.daxiao for j=1:ditu.daxiao if (G(i,j)==1) zhangai=[zhangai;j,i]; End end end path=Astar(zhangai,ditu); % The shortest path b = G is solved by a-star algorithm; b(end+1,end+1) = 0; figure(4); Title (' Achieve grid path planning based on a-star algorithm, complete code or simulation consulting QQ1575304183, diagonal lines on both sides of obstacles can not pass ') colormap([1 1 1;0 0 0]); % create color pcolor (0.5: size (G, 2) + 0.5, 0.5: size (G, 1) + 0.5, b); % to grid color set (gca, 'XTick', 1: size (G, 1), 'YTick, 1: size (G, 2)); % set axis image xy; % Use the same data unit along each axis, keep consistent; plot(path(:,1),path(:,2),'-m','linewidth',2); A = path (1, 3);Copy the code