0

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.

user1359819
  • 33
  • 3

2 Answers2

1

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.

Yusuf X
  • 14,513
  • 5
  • 35
  • 47
  • Yeah this sounds like my issue. It just wants to go the lowest cost step and doesn't even attempt to move away from it. What would be the way to ensure that it goes to a different node other than the lowest cost? – user1359819 Apr 26 '12 at 23:09
  • What language are you implementing it in? Chances are, someone else already did. – Yusuf X Apr 26 '12 at 23:49
  • C# (not XNA). Is there a simple implementation out there in C#? I tried to download one but it required paying for it. – user1359819 Apr 27 '12 at 00:01
  • Now you're talking. There are many free ones, including tutorials: http://stackoverflow.com/questions/2138642/simplest-c-sharp-implementation-of-a-algorithm – Yusuf X Apr 27 '12 at 00:21
  • Thanks Yusuf. Those examples are really helpfull. Hopefully I can use them to create my own instead of just using their code. Feel like a bit of an idiot not being able to figure this out on my own. – user1359819 Apr 27 '12 at 00:53
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...

Scott Hunter
  • 48,888
  • 12
  • 60
  • 101
  • I've checked my heuristics by having the map populate the numbers for each coordinate and they add up when I calculate them. I think I need a way to have a node be chosen when it is not actually a lower F value, but is the only other option (such as going in a U shape where you have to move farther away before you can get closer again) – user1359819 Apr 26 '12 at 23:20
  • Wait -- As @Yusuf_X suggested, you have to keep a record of ALL the possible open (i.e. uncompleted) paths. If not, you're not doing A* properly, you're doing hill climbing, which suffers from just the kind of local-minima problem you seem to be describing. – Scott Hunter Apr 26 '12 at 23:29
  • By open paths, do you mean the adjacent nodes to the current node? Because I am doing that. It checks the adjacent nodes to see which is best (lowest F value). I have an OpenList and a ClosedList, and I add the best node out of the ones available to the ClosedList and then check that nodes adjacent nodes. – user1359819 Apr 26 '12 at 23:33