Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

I don't understand A* Pathfinding

From what I understand:

Add the current node to the closed list.

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

Find the node on the open list with the highest F value, and make the current node that node.

Repeat until you end up in your destination, then go through the parents of the destination node, and you will come back to your start node. That will be the best path.

So, this makes sense to my brain, but when I actually try it out on a diagram, I think I'm not understanding it correctly.

(From the picture below) Go down from the starting green tile, the one with a F value of 60. That is on the open list, and has a lower F value than bottom-right 74 one. Why is the 74 one picked instead of the 60?

A*

like image 738
apscience Avatar asked Jun 18 '11 12:06

apscience


People also ask

HOW DOES A * pathfinding work?

A* algorithmA* assigns a weight to each open node equal to the weight of the edge to that node plus the approximate distance between that node and the finish. This approximate distance is found by the heuristic, and represents a minimum possible distance between that node and the end.

IS A * pathfinding good?

A* is the most popular choice for pathfinding, because it's fairly flexible and can be used in a wide range of contexts. A* is like Dijkstra's Algorithm in that it can be used to find a shortest path. A* is like Greedy Best-First-Search in that it can use a heuristic to guide itself.

WHAT IS A * pathfinding used for?

This optimization results in shortest paths being found more quickly. The A* algorithm can be used to find shortest paths between single pairs of locations, where GPS coordinates are known.


1 Answers

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

As for your case, the diagram shows the G score from the first node on the open list. When you look at the website, the whole diagram is built first for the first node evaluation, and the author shows that the first best node is the one to the right. Then, moving forward uses the G score based on the score of the current node plus the moving cost of the next one, which is not shown on the diagram.

It is said on the website though:

And the last square, to the immediate left of the current square, is checked to see if the G score is any lower if you go through the current square to get there. No dice.

It's G score would actually be 24 (14 (current cost) + 10 (horizontal movement cost)), just like the square below it, if I remember correctly.

like image 61
Jesse Emond Avatar answered Oct 22 '22 04:10

Jesse Emond