Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

In A* after the finding the next node with the lowest F value, you have to search the adjacent nodes again. When you find a node that was already in the open list, you're supposed to check if the g score for that node would be lower if you went through the current node to get there. My question is, what is the point of this? Won't it always be the same? If you take G = 14 for diagonal and G = 10 for horizontal/vertical wouldn't the G always be more if you went through 2 nodes instead of one?

Say the last node on the closed list's G value was 50. It has an adjacent square to the right with a G value of 60. Your current node has a G value of 64. If you went through the current node to get to the node adjacent to the one with the G value of 50, the G would be 74. You could switch the numbers all you want but the recalculated G would always be higher so what is the point of recalculating it?

share|improve this question
add comment

3 Answers

up vote 3 down vote accepted

If you take G = 14 for diagonal and G = 10 for horizontal/vertical wouldn't the G always be more if you went through 2 nodes instead of one?

Yes, but that is only one specific case. In that case, you would not have to check if the g-score would be lower and potentially re-add the node to the open list, because, in your graph, we can guarantee it will have the lowest g-score the first time it is added to the open list.

However, this is not true for all graphs.


We can formalize this. If the heuristic we use satisfies these two constraints:

for all nodes x,y with an edge between them,  h(x) <= h(y) + c(x,y)  
h(goal) = 0

then we call the heuristic consistent (or, less commonly, "monotone"). In that case, we don't need to recheck the g-scores or readd a node to the open-list.

Since your heuristic satisfies those constraints, it is consistent.

share|improve this answer
    
You're making a big assumption, because OP hasn't said anything about his heuristic. For all we know, it's not even admissible. –  Peter Taylor Sep 6 '13 at 14:43
    
I don't understand, why are you using h? What is h in this case? If it's heuristic, why do we have to take the heuristic into a account? –  Mastrolinie Sep 6 '13 at 15:12
    
@Mastrolinie: Yes it's the heuristic, and I mention it because it is the answer to your question. Whether or not the heuristic is consistent determines whether you need to look at the g-score more than once (and possibly readd a node to the open list) –  BlueRaja - Danny Pflughoeft Sep 6 '13 at 15:42
    
But I don't understand why we need to consider the heuristic. Aren't we only checking if the G is higher or lower? As far as I'm aware of, G is calculated independently from the heuristic. –  Mastrolinie Sep 6 '13 at 18:18
1  
So most of the time I'm not going to have to recalculate it if it the G of a node already on the open list would be lower had I gone through the current node to get to it, unless my heuristic is inconsistent, which rarely is the case, right? –  Mastrolinie Sep 6 '13 at 21:12
show 4 more comments

What BlueRaja said. Essentially A* allows you to also consider a weighted graph. Imagine that same game grid but some tiles are mountains, others are swamp and others are road. These different movement costs mean there is a faster route. For example, following the road around a mountain, rather than going over it. If the road is step cost 1, and the mountain is step cost 100. That is either a really long road, or the road is just more efficient.

share|improve this answer
    
But what does recalculating the cost have to do with that? Say the current node is a road and the destination point is over the mountain. The node adjacent to the top of the current node is a mountain and the mountain ends exactly where the destination is. Like in your example, there's a road going around the mountain. Using the A* algorithm, it's going to choose the road and no matter how many times it recalculates it, the road is going to stay the best option. So what exactly is the point of recalculating the G value if you went through the current node to get there? –  Mastrolinie Sep 6 '13 at 18:27
    
So you are going along the road. And you are adjacent to your destination, but A road block of step cost a million is in your way. The destination is added to your open list, but may not be the shortest. You go back to the mountain and cross a few tiles. You arrive adjacent to your destination again. The cost to get to the destination is no longer a million, but only a few hundred, since you're coming from the mountain. The cost is updated. –  mwjohnson Sep 7 '13 at 3:13
add comment

In A* after the finding the next node with the lowest F value, you have to search the adjacent nodes again. When you find a node that was already in the open list, you're supposed to check if the g score for that node would be lower if you went through the current node to get there. My question is, what is the point of this? Won't it always be the same?

Only if you visit the nodes in order of increasing G value.

If you take G = 14 for diagonal and G = 10 for horizontal/vertical wouldn't the G always be more if you went through 2 nodes instead of one?

Yes.

However, you're visiting the nodes in order of increasing F value. Depending on the details of the heuristic, this may not be the same as the order of increasing G value.

share|improve this answer
    
So basically you're saying that if we're checking if the F is lower had we gone through the current node to get there, It wouldn't always be the same, which I'm aware of. But if you were only comparing the G value, it would still always be higher, correct? –  Mastrolinie Sep 6 '13 at 18:21
    
No, because the different between F(P) and G(P) is just H(P) which is assumed constant. –  Peter Taylor Sep 6 '13 at 20:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.