I do not understand A * Pathfinding

Question

From what I understand:

Add the current node to the private list.

Find neighboring nodes in the current node, and if they are not invulnerable nodes, not a closed list, add that node to the open list with the parent being the current node, and calculate F, G and H. If the node already exists in the open list, check if going to this node through the current node will result in a lower G value - if so, make the parent node of this node the current node.

Find the node in the open list with the highest F value and make the current node which node.

Repeat until you reach the destination, then go to the parents of the node destination and you will return to the beginning of the node. This will be the best way.

So it makes sense for my brain, but when I actually try to do it on a chart, I think I don’t get it right.

(From the picture below) Go down from the green tile, which has an F value of 60. This is in the open list and has a lower F value than the lower right 74. Why is 74 selected instead of 60?

Answer 1

In my opinion, you should take a look at Amit A * Pages . They are really great at explaining how the algorithm works and how to make it work.

For your case, the chart displays the score of G from the first node in the open list. When you look at the website, the whole diagram is built first for the first evaluation of the node, and the author shows that the first best node is the one on the right. Then, moving forward, we use the estimate of G , based on the assessment of the current node plus the cost of moving the next , which is not shown in the diagram.

The website says:

And the last square, located to the left of the current square, checks to see if G will be lower if you go through the current square to get there . No dice.

In fact, it will be 24 (14 (current value) + 10 (cost of horizontal movement)), as well as the square under it, if I remember correctly.

Answer 2

The reason you don’t go to the square with the F-value of 60 is because it is on a “closed list”. Where, like the squares with the F-value of 88 and 74 are in the "open list" and can be checked on the next move.