Hi, I've read the tutorial about A* and I've build a version into my game. It works quite well, but when I correctly follow what it does, it will return a path (even the shortest of the ones it finds (every node that has the same distance (and thus needs to be chosen randomly) I go through, so noone would be left out)). However, it can be possible that it is not the shortest of all ways. The point is, that when I try to improve it, that I find out it had unlimited ways of getting from A to B. That is true, there are, in theory, unlimited ways of going from A to B... However, I don't want my script to find all ways (which is unlimited) ofcourse. What am I doing wrong? What feature in A* have I not implemented? I do roughly this: It gets a node, checks for the surrounding nodes and chooses the smallest approx. distance. Of that node it checks for surrounding nodes too...picks the one with the smallest approx. distance to its goal...etc etc etc. For every node I check for surrounding nodes, I get maximal 8 new nodes which have to be checked (or less, if it is not walkable). This will make for every handled node 8 new nodes...that increases quite fast into unlimited nodes. What am I doing wrong? Thanks in advanced. Decrius

If I understand you correctly, your current approach is to select the "next node" as being the neighbor of the "previous node" which minimizes the "distance to origin + heuristic" total.

The correct approach for A* is to select the "next node" as being the neighbor of any previously explored node and minimizing the "distance to origin + heuristic" total. Which means you will usually have to test more than just eight nodes. However, each node is only tested once, and the heuristic, if chosen correctly, should help prune the search tree even further.

Quote: Original post by Decrius
I go through, so noone would be left out)). However, it can be possible that it is not the shortest of all ways.

That is true, A* does not necessarily guarantee that the path returned will be the shortest; however in most cases it does a pretty good job at generating an optimal path.

If you want to guarantee the shortest path then you could use Dijkstras Algorithm. Only problem with that algorithm is that it is much more brute force and not as convergent as A*. Depends what you want really, good paths that are quick to find (but not unnecessarily the best) or the best possible paths that are really slow to find.

Quote: Original post by Darragh

Quote: Original post by Decrius
I go through, so noone would be left out)). However, it can be possible that it is not the shortest of all ways.

That is true, A* does not necessarily guarantee that the path returned will be the shortest; however in most cases it does a pretty good job at generating an optimal path.

Actually A* is intended to use an admissible heuristic, so it is guaranteed to find the optimal path. That is, the heuristic that estimates the cost from a given node to the goal node should return an optimistic value compared to the actual cost.
In the case of path-finding an optimistic estimate would be a distance which is less than or equal to the actual distance; the length of a straight line between the two points would typically satisfy this condition.

Quote: Original post by dmatter

Quote: Original post by Darragh

Quote: Original post by Decrius
I go through, so noone would be left out)). However, it can be possible that it is not the shortest of all ways.

That is true, A* does not necessarily guarantee that the path returned will be the shortest; however in most cases it does a pretty good job at generating an optimal path.

Actually A* is intended to use an admissible heuristic, so it is guaranteed to find the optimal path. That is, the heuristic that estimates the cost from a given node to the goal node should return an optimistic value compared to the actual cost.
In the case of path-finding an optimistic estimate would be a distance which is less than or equal to the actual distance; the length of a straight line between the two points would typically satisfy this condition.

No. It is not guaranteed to find the optimal path for A*. Don't confuse "it's very likely/probably" with "guaranteed". A* will return the optimal path if the true path cost matched exactly to the heuristic. Which is very hard, since a convex obstacle will definately make the heuristic not match the cost (in most cases).
Like been said, Dijkstras will return optimal path always. While A* will often return the optimal one.

Quote:
For every node I check for surrounding nodes, I get maximal 8 new nodes which have to be checked (or less, if it is not walkable). This will make for every handled node 8 new nodes...that increases quite fast into unlimited nodes.

ToohrVyk already explained your mistake here. But I'll repeat something that might not be very clear. The A* formula is F = G + H, where G is the true cost and H is the heuristic. You're talking about comparing H values, while you need to compare F values. Plus that, ToohrVyk explained that you're also comparing against the wrong nodes.

Edit: G is the cost travelled so far. So if making one step costs "1", then the second parsed node will contain G = (G from it'sparent) + G from this node. In the example the second node (assuming they're both related) will have a G = 2:

---
| 2 |
--- --- ---
| 1 | 2 | 3 |
--- --- ---
| 2 |
---

Hope this helps
Dark Sylinc

Thanks guys, I see my mistake. I'm rewriting the code completely now :)

As for dijsktra's method: I want the shortest path, but if it is not exactly the shortest one it should be no problem. And since dijkstra's method is much more CPU consuming, I think its better to use the A* method.

Sometimes 2 nodes around one parent-node have the same H value, then you can randomly take one of the nodes OR you could try both. The second method would result in 2 possible paths. At the end I could choose for the shortest.
Would that be correct? Would that higher the chance of getting the shortest path?

Thanks for your help se far,
Decrius

Quote: Original post by Matias Goldberg
No. It is not guaranteed to find the optimal path for A*. Don't confuse "it's very likely/probably" with "guaranteed".

I didn't [smile]
Like I said, if the heuristic function is admissible, i.e. it gives an underestimate (Edit: More accurately, it does not give an over-estimate) of the distance, then the A* search is admissible also.

Quote: A* will return the optimal path if the true path cost matched exactly to the heuristic.

Correct, although in this case the A* search will examine the most optimal set of nodes, that is it will only examine those nodes which are actually on the optimal path.

Quote: Like been said, Dijkstras will return optimal path always. While A* will often return the optimal one.

No, A* will return the optimal path if the heuristic is admissible. Look in any good state space search algorithms book.

[Edited by - dmatter on March 8, 2008 12:01:50 PM]

Quote: Original post by dmatter
if the heuristic is admissible

There we go, when is the heuristic admissible? I use the method of counting width and height differences...works ok, but could be better I guess.

Quote: Original post by Decrius

Quote: Original post by dmatter
if the heuristic is admissible

There we go, when is the heuristic admissible?

I answered this in a post above.
For spatial pathfinding, an admissible heuristic might be one that returns an "as the crow flies" distance from the current node's position to the goal node's position, this is the straight line distance between the two points and is regardless of whether such a straight line path is walkable or not.

Quote: I use the method of counting width and height differences...works ok, but could be better I guess.

I'm not sure I follow.

Quote: Original post by Decrius
Thanks guys, I see my mistake. I'm rewriting the code completely now :)

As for dijsktra's method: I want the shortest path, but if it is not exactly the shortest one it should be no problem. And since dijkstra's method is much more CPU consuming, I think its better to use the A* method.

As *correctly* staten above, if you use an admissible heuristic with A*, you will always get the shortest path (if it exist). You can also use an non-admissible heuristic. Then you are not guaranteed a shortest-path BUT, if you are clever about your heuristic, you can sometime reduce the search time.

Quote: Original post by Decrius
Sometimes 2 nodes around one parent-node have the same H value, then you can randomly take one of the nodes OR you could try both. The second method would result in 2 possible paths. At the end I could choose for the shortest.
Would that be correct? Would that higher the chance of getting the shortest path?

Again, if you use an admissible heuristic, it wont matter which of these two nodes you try first.

It is a good exercise to do the proof that A* will always return the shortest-path with an admissible heuristic. Typical first-semester assignement in CS :)