Jump to content
  • Advertisement
Sign in to follow this  
silverphyre673

Quick questions about the A* algorithm.

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by silverphyre673
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?

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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by silverphyre673
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?
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by silverphyre673
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.

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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!