# help calculating G cost of A* algorithm

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

## Recommended Posts

I am trying to implement the A* algorithm for pathfinding and having trouble understanding G cost.

Here is a small grid area of node id's from a larger grid.
[code]
52 53 54 55 56
102 103 104 105 106
152 153 154 155 156
202 203 204 205 206
252 253 254 255 256
[/code]

Horizontal and vertical moves increment 10, diagonal increments 14. I am followig this tutorial ... [url="http://www.policyalmanac.org/games/aStarTutorial.htm"]http://www.policyalm...tarTutorial.htm[/url]

Node 103 is my starting node. So the lowest F score above takes me to node 154 from 103. I have calculated the G cost as follows from node 153.
[code]
14 10 14
10 10
14 10 14
[/code]
Next iterations F score gives me node 205, so I then calculate G cost from node 205 and I get the following:
[code]
28 24 28
24 24
28 24 28
[/code]
And one more iterations F score gives me node 256, so I calculate G cost from node 256:
[code]
42 38 42
38 38
42 38 42
[/code]
Am I calculating G cost correctly?

Something I don't understand is after I choose the lowest F score, the G cost of 4 nodes is always the same and therefore I can't choose a lowest G cost at this point.

Any help much appreciated.

##### Share on other sites
You didn't tell us what node you are trying to reach or what your heuristic is, so we can't know what node minimizes F at each stage. The G cost for a particular node should only decrease, so if you find a new way to reach it that takes longer, you don't update it.

If you could post the full 5x5 matrix of G costs after each step, it would be much more clear whether you understand it or not. It should be something like this:
[code]Initially:
- - - - -
- 0 - - -
- - - - -
- - - - -
- - - - -

After expanding 103:
14 10 14 - -
10 0 10 - -
14 10 14 - -
- - - - -
- - - - -

After expanding 154:
14 10 14 - -
10 0 10 28 -
14 10 14 24 -
- 28 24 28 -
- - - - -

...
[/code]

##### Share on other sites
[quote name='alvaro' timestamp='1331603111' post='4921538']
You didn't tell us what node you are trying to reach or what your heuristic is, so we can't know what node minimizes F at each stage. The G cost for a particular node should only decrease, so if you find a new way to reach it that takes longer, you don't update it.
[/quote]

So I'm looking at your grid and I don't get something.

After expanding to 154, why does node 2,4 in your example not equal 20. It's 28. But it's only down 2 "10" vertical moves away. Same for node 4,2, it's 2 "10" horizontal moves away. Yet node 4,4 is 28 because it is 2 "14" moves diagonally.

Is G cost only ever calculated 1 time after moving to the current node and just when adding it to the open list? You don't calculate G cost for nodes already on the open list?

##### Share on other sites
[quote name='alvaro' timestamp='1331603111' post='4921538']
If you could post the full 5x5 matrix of G costs after each step, it would be much more clear whether you understand it or not. It should be something like this:[/quote]

The node in parenthesis is the node I just moved to after finding lowest F score.

My grid is 50x50, and the initial node starts at 3,3 (i.e. node 103)
[code]
- - - - - -
- - - - - -
- - (0) - - -
- - - - - -
- - - - - -
[/code]

Then I calculate G cost for all adjacent nodes to 3,3:
[code]
- - - - - -
- 14 10 14 - -
- 10 (0) 10 - -
- 14 10 14 - -
- - - - - -
[/code]

Lowest F takes me to node 154 (i.e. 4,4). So I move to 4,4, and recalculate G for all adjacent nodes:
[code]
- - - - - -
- 14 10 14 - -
- 10 28 24 28 -
- 14 24 (28) 24 -
- - 28 24 28 -
[/code]
In the above, (4,4) was 14 then I added 14 equalling 28 and compared it to adjacent node 3,3 which is 28. (4,4) was 14 and I added 10 equalling 24 and compared it to adjacent node 4,3 which is 24. I did this for all 8 nodes surrounding the current node. Several nodes are always same. Here there are 4 nodes of 24 which is smaller than 28. Not just one being the better path.

Next lowest F takes me to node 205 (i.e. 5,5), move to 5,5, and recalculate G:
[code]
- - - - - -
- 14 10 14 - -
- 10 28 24 28 -
- 14 24 42 38 42
- - 28 38 (28) 38
- - - 42 38 42
[/code]
Everytime I recalulate G, I take the G of the current node, and at 10 or 14 depending on directon, and compare it to the adjacent nodes G. Current node is always higher in my case.

This is the top corner of a 50x50 grid. The path being traversed is (3,3), (4x4), (5x5) ... making a diagonal path going downwards and to the right from 3,3. The node I'm trying to reach is 25,47.

I think I'm just not understanding how G is supposed to be calculated after each iteration of lowest F score. I've reread the tutorial over and over, but that part doesn't come clear to me.

##### Share on other sites
[quote name='alvaro' timestamp='1331603111' post='4921538']
You didn't tell us what node you are trying to reach or what your heuristic is, so we can't know what node minimizes F at each stage.
[/quote]

Per the tutorial, my heuristic is ...
[quote]
H = the estimated movement cost to move from that given square on the grid to the final destination, point B. This is often referred to as the heuristic,
[/quote]

All I do is count blocks vertically and horizontally to come up w/ H cost. And then my F score is the sum of G + H.

##### Share on other sites
[quote name='rrlangly' timestamp='1331607107' post='4921553']
After expanding to 154, why does node 2,4 in your example not equal 20. It's 28. But it's only down 2 "10" vertical moves away. Same for node 4,2, it's 2 "10" horizontal moves away. Yet node 4,4 is 28 because it is 2 "14" moves diagonally.[/quote]
That's because I haven't expanded node 104, so I haven't found the more straight path to get there with a cost of only 20.

[quote]Is G cost only ever calculated 1 time after moving to the current node and just when adding it to the open list? You don't calculate G cost for nodes already on the open list?
[/quote]
No, G is calculated when adding the node to the open list and any other time it appears in an expansion, but we always keep the minimum value, not the latest.

##### Share on other sites
[quote name='rrlangly' timestamp='1331607685' post='4921555']
[quote name='alvaro' timestamp='1331603111' post='4921538']
You didn't tell us what node you are trying to reach or what your heuristic is, so we can't know what node minimizes F at each stage.
[/quote]

Per the tutorial, my heuristic is ...
[quote]
H = the estimated movement cost to move from that given square on the grid to the final destination, point B. This is often referred to as the heuristic,
[/quote][/quote]
That's not your heuristic: It's the definition of a heuristic. What function specifically are you using? Euclidean distance is a popular choice...

[quote]All I do is count blocks vertically and horizontally to come up w/ H cost. And then my F score is the sum of G + H.
[/quote]
How do you combine your horizontal and vertical counts?

##### Share on other sites
[quote name='alvaro' timestamp='1331608622' post='4921560']
How do you combine your horizontal and vertical counts?
[/quote]

I just add them together and that becomes H.

If I start at 3,3 and the destination is 8,10 ... (8-3=5, 10-3=7) so my H=(5+7)=14. I think the tutorial calls it a manhatton algorithm because it's like counting city blocks, only horiz/vert count.

##### Share on other sites
Yes, that's called the Manhattan distance. That explains why you are exploring diagonal movements first.

Anyway, is it clear now how you handle updates to G?

##### Share on other sites
[quote name='alvaro' timestamp='1331611165' post='4921563']
Yes, that's called the Manhattan distance. That explains why you are exploring diagonal movements first.

Anyway, is it clear now how you handle updates to G?
[/quote]

I won't say its clear, but you've given me much to think about. Let me chew on this a bit. Thanks.

##### Share on other sites
Here's a question I have ...

Why doesn't the open list just contain the current working nodes (current node + adjacent nodes to current node) instead of all the nodes that all current nodes ever run into. There can never be a better path than an adjacent node near a current working node so why keep the history of all inspected nodes on the open list since they can't be a better path. Guess that means the open list would only ever contain about 8-9 nodes at most. Or am I leaving something out?

##### Share on other sites
Of course there can be a better path. Your program will start to greedily explore some path towards the goal, guided by the heuristic, and it may run into an alley with no exit. You would then have to pick one of the other nodes that the heuristic didn't favor the first time around and go from there.

##### Share on other sites
Ugh, my code works, it finds the target, but I know it's not right. I think I'll try to find another tutorial to see if it explains certain things differently that might clear things up for me.

##### Share on other sites
I learned A* from one of [url="http://www.cs.princeton.edu/%7Ers/"]Robert Sedgewick's books[/url], and I really like the level of technicality (simple enough to understand, detailed enough to actually get things implemented). He has books in several programming languages, although I don't think the code is particularly idiomatic. The old editions were just one volume, but now apparently it has been divided into several parts: What you want is part 5, which deals with graphs. See if you can find it at the library of a local university.

EDIT: Never mind. I am looking through his website, and it doesn't look like there is much about A* there. I swear it was there in some older edition...

##### Share on other sites
This is confusing me when my node runs into invalid terrain.

Lowest F score is 1675, so I drop it off of the open list and add to closed list.
[code]
1574 1575 1576
1624 1625 1626
1674 1675 1676
1724 1725 1726 (this row is a wall)
[/code]
Path is travelling downward (1575, 1625, 1675).
So now I search for a better path of nodes on open list by lowest G cost. G cost for each of these nodes is:
[code]
382 378 382
392 388 392
402 398 402
X X X
[/code]
Current node is 1675.
398 + 10 = 408 for horiz/vert nodes, no better path found.
398 + 14 = 412 for diagonal nodes, no better path found.

Now I search all adjacent nodes to 1675 that are not already on the open list. This adds nodes 1724, 1725, and 1726 (the illegal terrain nodes). Because they're illegal, they DO NOT go on the open list.

So now I start a new iteration and its time to select the lowet F score on the open list and switch it to the closed list.

The problem is, my lowest F score on the open list is now like 10 rows up. And from here on out my nice clean path that I could see it traversing has just transported itself across my grid and things just get whacky.

Any ideas?

##### Share on other sites
This is expected behavior. You got to a point where the search cannot continue, so the search resumes elsewhere. What gets whacky?

##### Share on other sites
I guess that's good. Good that you think it should work like that, bad that I don't understand whats happening. Although now it just keeps running, it never finds a path. I had it working before, even though at some points the path solution before a wall looked like a christmas tree. But I'm thinking now that that was my fault in the way I was printing the nodes.

So at the point where I explained that it goes from node 1675 and seems to reset at 1174 (about ~10 rows back up) ... how can it continue to find a path if several of the nodes that it tried to find a solution with the first time are no longer on the open list. They're on the closed list now and unavailable to be traversed again.

##### Share on other sites
The path that A* finds is not the sequence of nodes expanded: That's just the procedure used to find the path, with attempts that don't work out included. The search ends whenever you pick the goal to be expanded. Whenever that happens, you need to reconstruct the path. The easiest way to do that is to store the parent of each node (the node we reached it from, when we updated its G cost), follow the sequence of parents from the goal to the start and then reverse the list. Alternatively, if you remember all the G costs, you can find the neighbor of the goal that minimizes the sum of G and the cost to move to the goal, then find the neighbor of that node that minimizes the sum of G and the cost to move to that node, etc.

##### Share on other sites
Ah, ok. So I think I'm starting to get it. When I had no obstacles in my path, The path was always the lowest F score and that's what I would store (and print) for my path. And it worked fine. Then once I started adding obstacles, I would see huge blotchy type areas and I wasn't using parents as I should, rather, I was still thinking like a path w/ no obstacles. I haven't fixed this yet, but at least now I think I understand what should be happening. Thanks for your help.

##### Share on other sites
I see my path taking shape, but trying to debug areas where the parent is wrong.

If a better path was found because it has a lower G cost, and then after G, H, and F scores along w/ its parent has been updated ... do I then drop it from the open list to closed list? Or does a better path found mean that better path node stays on the open list?

So far the only time I see that I ever drop a node from the open to closed list is when a node is checked for the low F score. And up until my path is screwed up, I can see when I backtrace for parent nodes, they're all on the closed list. So my path looks good from the start to point of screw-up and all those nodes are on the closed list. At the point of screwup, I see nodes on the open list.

##### Share on other sites
[quote name='rrlangly' timestamp='1332121554' post='4923164']
I see my path taking shape, but trying to debug areas where the parent is wrong.

If a better path was found because it has a lower G cost, and then after G, H, and F scores along w/ its parent has been updated ... do I then drop it from the open list to closed list? Or does a better path found mean that better path node stays on the open list?[/quote]
It stays on the open list.

[quote]So far the only time I see that I ever drop a node from the open to closed list is when a node is checked for the low F score. And up until my path is screwed up, I can see when I backtrace for parent nodes, they're all on the closed list. So my path looks good from the start to point of screw-up and all those nodes are on the closed list. At the point of screwup, I see nodes on the open list.
[/quote]
So your algorithm finishes but then you have trouble when recovering the path? I don't know how that can ever lead to a node in that's not in the closed list. Check wherever you assign a parent in your code. It should be obvious that the node was just put in the closed list at that point.

Oh, and you should never put a node from the closed list back in the open list.