A* Algorithm and use of F and G heuristics

Question

I've got my A* algorithm working to a degree. It will follow the player around in a space, but it will not go around an object which involves moving farther away from the target in order to get around it. When it realises the next node has a higher F value (is farther away from the target), it will refuse to go there and will just keep looking for a lower F value (closer node to the target) without finding one (it's stuck in a never ending loop).

I think my understanding of the use of heuristics might be the problem.

My A* always moves to the next node which has the lowest F value (H+G). I never take the G or H value into account other than adding them in F.

On tutorials I've read, they talk of using the G value, but I thought the F value was the only important one.

Could someone just sum up how I use the heuristic values please. I think I'm almost there, it's just the use of the heuristics is confusing.

Answer 1

You've got it. H tells you how far it actually took to get to that node; G is the estimate for how much farther you have to go. If you only considered G, then you'd take the path closest to the goal, even if it took a VERY long time to get to that node. That's why you use F (=H+G), so that the first time you reach a goal, you know it is the one w/ the shortest path .

Now, if you have an infinite number of paths, then trying to find the optimal one may be a problem. Or your path-generation algorithm may be buggy (for example, causing you to re-consider paths). As you haven't given much more detail as to the problem, I can't say much more that might be useful.

Then again, you may have a bad (or worse, non-admissible) heuristic function...

Answer 2

Are you keeping a priority queue of alternate path segments? If you just look at the lowest-cost next step, you won't be able to go around obstacles.