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.

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


Horizontal and vertical moves increment 10, diagonal increments 14. I am followig this tutorial ... http://www.policyalm...tarTutorial.htm

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.

14 10 14
10 10
14 10 14

Next iterations F score gives me node 205, so I then calculate G cost from node 205 and I get the following:

28 24 28
24 24
28 24 28

And one more iterations F score gives me node 256, so I calculate G cost from node 256:

42 38 42
38 38
42 38 42

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.

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:
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 -
- - - - -

...


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.

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?

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:

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)

- - - - - -
- - - - - -
- - (0) - - -
- - - - - -
- - - - - -


Then I calculate G cost for all adjacent nodes to 3,3:

- - - - - -
- 14 10 14 - -
- 10 (0) 10 - -
- 14 10 14 - -
- - - - - -


Lowest F takes me to node 154 (i.e. 4,4). So I move to 4,4, and recalculate G for all adjacent nodes:

- - - - - -
- 14 10 14 - -
- 10 28 24 28 -
- 14 24 (28) 24 -
- - 28 24 28 -

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:

- - - - - -
- 14 10 14 - -
- 10 28 24 28 -
- 14 24 42 38 42
- - 28 38 (28) 38
- - - 42 38 42

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.

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.

Per the tutorial, my heuristic is ...

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.

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.

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.

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.

[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.

Per the tutorial, my heuristic is ...

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...

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?

How do you combine your horizontal and vertical counts?

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.

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?

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?

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