# Quick questions about the A* algorithm.

This topic is 4906 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I have been learning about the A* algorithm, but I am confused on a few points. First off, what if you discover that the path you have been following leads to a dead end? Do you backtrack to the second-to-last square, just before the dead end, and try another path, and continue backtracking along the next-best F valued squares until you find the solution, eliminating squares that lead to dead-ends in all directions from future consideration entirely? Also, what happens to a square on the "closed list"? Is this your final, absolute, no-going-back-to-revise-it path? Or is it just squares that will be on the path if it winds up leading to the destination? If the path you are on doesn't lead to the destination, do you put all the squares on the "closed list" back on the "opened list"? Thanks. By the way, if I am using incorrect terminology, I learned "closed list" and "open list" from this tutorial, which is pretty good, but left me with these questions. Thank you.

##### Share on other sites
Quote:
 Original post by silverphyre673I have been learning about the A* algorithm, but I am confused on a few points. First off, what if you discover that the path you have been following leads to a dead end? Do you backtrack to the second-to-last square, just before the dead end, and try another path, and continue backtracking along the next-best F valued squares until you find the solution, eliminating squares that lead to dead-ends in all directions from future consideration entirely?

No, there's no special handling needed for dead ends. A dead end simply will not result in adding any new nodes to the open list, and since a node is always popped before being visited, you won't revisit it again.

Quote:
 Also, what happens to a square on the "closed list"? Is this your final, absolute, no-going-back-to-revise-it path? Or is it just squares that will be on the path if it winds up leading to the destination?
Neither. The closed list is the list that, based on the current cost+heuristic computation, are not worth evaluating. If a shorter path is found to one of these nodes later on, it'll be reopened.

Quote:
 If the path you are on doesn't lead to the destination, do you put all the squares on the "closed list" back on the "opened list"? Thanks.

Your questions reveal a misunderstanding about the A* algorithm's paradigm. There is no such thing as a "path you are on". You might expand one node on one side of the field, and then the next node you expand is on the other side, down a completely different path. In fact, this is pretty common. A* operates on a node at a time: it picks the node that it thinks is most promising, and expands it outwards in multiple directions.

##### Share on other sites
So it basically is always expanding nodes with the lowest F value present? And the closed list contains nodes that aren't worth evaluating anymore?

So how do you know when to stop? Have you, for (almost - I know you can't get it 100% of the time) certain got the shortest path when you arrive at the destination? That is starting to make sense.

//Edit

Wait, I think I got it now, looking at the graphical representation of the finished algorithm on the article I linked to. Thanks. I'll let you know if I have more problems :)

//Edit 2

In the article, it says that

1) Add the starting square (or node) to the open list.

2) Repeat the following:

a) Look for the lowest F cost square on the open list. We refer to this as the current square.

b) Switch it to the closed list.

Now, since at first the starting square is the only square on the open list, it will be the current square. It will, by default, have the lowest F cost. However, I'm not sure why you want to switch it to the closed list. Also, at first, how would you assign it a G (movement cost) value? You are already on it, so do you just give it a G value of zero? Thanks. I think maybe I'm misunderstanding the point of the closed list.

[Edited by - silverphyre673 on August 12, 2005 1:54:19 AM]

##### Share on other sites
Quote:
 Original post by silverphyre673So it basically is always expanding nodes with the lowest F value present? And the closed list contains nodes that aren't worth evaluating anymore?So how do you know when to stop? Have you, for (almost - I know you can't get it 100% of the time) certain got the shortest path when you arrive at the destination?
Preeeetty much. Technically, you're certain you've got the shortest path when you pop the destination off the OPEN list. For most applications, though, it doesn't matter.

Quote:
 Now, since at first the starting square is the only square on the open list, it will be the current square. It will, by default, have the lowest F cost. However, I'm not sure why you want to switch it to the closed list.
Because you're done with it (or will be, at the end of the iteration). There's no reason to reexamine it. "closed" doesn't mean "worthless", it means "not worth examining at this time, because it's already been examined, and nothing new has been discovered about it since then".
Quote:
 Also, at first, how would you assign it a G (movement cost) value? You are already on it, so do you just give it a G value of zero?
Yep.
Quote:
 I think maybe I'm misunderstanding the point of the closed list.

The computed cost of a given node is dependent on its parent's cost. If that parent's cost is lowered later (because a shorter path was found to the parent), the parent should be reexamined so that the child nodes' costs can be updated. CLOSED is the list of nodes that have been explored and do not currently need to be reexamined.

##### Share on other sites
So at what point, if any, will you take a node off the closed list? It seems like you would have to, at some point.

Sorry I am so thick, but you are a big help. Thanks.

##### Share on other sites
Quote:
 Original post by silverphyre673So at what point, if any, will you take a node off the closed list? It seems like you would have to, at some point.

You take a node off the closed list, and put it on the open list, when you find a path to it that is shorter than the old shortest path to it. Other than that, you never remove nodes from the closed list.

##### Share on other sites
I think I've got it now, but let me make sure that the algorithm they give is correct. Can you verify this, please? You've been a big help.

1) Add the starting square (or node) to the open list.

2) Repeat the following:

a) Look for the lowest F cost square on the open list. We refer to this as the current square.

b) Switch it to the closed list.

c) For each of the 8 squares adjacent to this current square …

*

If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.
*

If it isn’t on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square.
*

If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.

d) Stop when you:

* Add the target square to the closed list, in which case the path has been found (see note below), or
* Fail to find the target square, and the open list is empty. In this case, there is no path.

3) Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path.

Thanks.

##### Share on other sites
A brief clarification here. You CAN ignore nodes on the closed list, as stated in your step (c), under certain restrictive circumstances, and often video game pathfinding fits these circumstances. The "can move stuff off the closed list" rule is for the general case. So yeah, that algorithm is correct, but in the general case you shouldn't ignore a node just because it's on the closed list. But yeah, that's it in a nutshell.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 13
• 9
• 15
• 14
• 46
• ### Forum Statistics

• Total Topics
634058
• Total Posts
3015288
×