Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


help calculating G cost of A* algorithm


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
21 replies to this topic

#1 rrlangly   Members   -  Reputation: 110

Like
0Likes
Like

Posted 12 March 2012 - 03:47 PM

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.

Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 15390

Like
0Likes
Like

Posted 12 March 2012 - 07:45 PM

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

...


#3 rrlangly   Members   -  Reputation: 110

Like
0Likes
Like

Posted 12 March 2012 - 08:51 PM

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?

#4 rrlangly   Members   -  Reputation: 110

Like
0Likes
Like

Posted 12 March 2012 - 08:52 PM

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.

#5 rrlangly   Members   -  Reputation: 110

Like
0Likes
Like

Posted 12 March 2012 - 09:01 PM

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,


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.

#6 Álvaro   Crossbones+   -  Reputation: 15390

Like
0Likes
Like

Posted 12 March 2012 - 09:13 PM

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?

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.

#7 Álvaro   Crossbones+   -  Reputation: 15390

Like
0Likes
Like

Posted 12 March 2012 - 09:17 PM


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,

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.

How do you combine your horizontal and vertical counts?

#8 rrlangly   Members   -  Reputation: 110

Like
0Likes
Like

Posted 12 March 2012 - 09:31 PM

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.

#9 Álvaro   Crossbones+   -  Reputation: 15390

Like
0Likes
Like

Posted 12 March 2012 - 09:59 PM

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?

#10 rrlangly   Members   -  Reputation: 110

Like
0Likes
Like

Posted 12 March 2012 - 10:07 PM

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.

#11 rrlangly   Members   -  Reputation: 110

Like
0Likes
Like

Posted 13 March 2012 - 02:35 PM

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?

#12 Álvaro   Crossbones+   -  Reputation: 15390

Like
0Likes
Like

Posted 13 March 2012 - 03:04 PM

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.

#13 rrlangly   Members   -  Reputation: 110

Like
0Likes
Like

Posted 13 March 2012 - 03:10 PM

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.

#14 Álvaro   Crossbones+   -  Reputation: 15390

Like
0Likes
Like

Posted 13 March 2012 - 03:17 PM

I learned A* from one of Robert Sedgewick's books, 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...

#15 rrlangly   Members   -  Reputation: 110

Like
0Likes
Like

Posted 13 March 2012 - 08:40 PM

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.
1574	1575	1576
1624	1625	1626
1674	1675	1676
1724	1725	1726 (this row is a wall)
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:
382	 378	 382
392	 388	 392
402	 398	 402
X	   X	   X
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?

#16 Álvaro   Crossbones+   -  Reputation: 15390

Like
0Likes
Like

Posted 13 March 2012 - 09:38 PM

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

#17 rrlangly   Members   -  Reputation: 110

Like
0Likes
Like

Posted 13 March 2012 - 10:16 PM

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.

I didn't read anything about resetting any lists in the tutorial.

#18 Álvaro   Crossbones+   -  Reputation: 15390

Like
0Likes
Like

Posted 13 March 2012 - 10:50 PM

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.

#19 rrlangly   Members   -  Reputation: 110

Like
0Likes
Like

Posted 14 March 2012 - 07:30 PM

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.

#20 rrlangly   Members   -  Reputation: 110

Like
0Likes
Like

Posted 18 March 2012 - 07:45 PM

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.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS