Here's a situation where A star fails (sorry for the horrible image xD): The black line is an obstacle. Lets call A the starting node, B the bestnode among the expanded nodes and C the real bestnode (better F cost value than A). What i thought is to expand the adiacent nodes of A and to make B the node with the best F cost value among the other, even if it's not better than A value. Do this until you find a C node, from there use A* algorithm with C as the starting point. The only thing is that i think it will create a path like this (the blue one): There's a way to make it look as the green one? Also if you imagine a narrower "exit".. the blue paths could be very long. I add that i'm using A* in a tile based game and the algorithm don't know how is the map, where's the obstacle etc etc, it's all calculated at runtime.

Have you tried running that through A*? I'm pretty sure it will work in the way you want it to, as long as your heuristic is correct.

Yes, A* is complete, which means that it will always find a solution if one exists. Why do you think that A* would fail in this situation?

Quote:

Original post by Codeka Have you tried running that through A*? I'm pretty sure it will work in the way you want it to, as long as your heuristic is correct.

Check them again :P

And yes i tested it.
The heuristic function takes the deltas (x y and z) make them positive, multiply x and y by two and then add all the results and multiplies all with 1.0 + a p factor where p is minimummovementcost/longestpathexpected (i did 1/100).
So the resulting function is (2*(x+y)+z) * (1.0 + p) (assuming that x,y and z are already positive).
I created a overestimated heur function (since each x or y movement cost 1 and diagonal movement cost 1.4) to make A* expand faster the nodes even if i don't get the shortest path (anyway this algorithm is used by monsters, so if they are a bit "dumb" it's not a problem).

So, imho, the only way the algorithm can reach the point i want to go is to go backward, but going backward the nodes will have worse F cost than the starting one..

Edit: ops, i reread what i wrote and i found why it won't work.
When i read A* articles i understood that the node to find should be the best, better also than the prevoius node and not only the best among the nodes on the open list.
So this way i'll have what i want right?

Quote:

Original post by Smjert So, imho, the only way the algorithm can reach the point i want to go is to go backward, but going backward the nodes will have worse F cost than the starting one..

So? This virtually always happens with A*. Once the starting node is added to the closed list, other nodes with higher costs will be expanded. If your code does not correctly find a path here, your code has a bug in it, probably related to the closed-list.

Quote:

When i read A* articles i understood that the node to find should be the best, better also than the prevoius node and not only the best among the nodes on the open list.

You'll have to define what you mean by "the node to find". The goal node? The next node to expand? For that matter, what do you mean by "the previous node"? The node that was just expanded, or the current node's parent node? And what do you mean by "best"-- lowest heuristic, lowest cost+heuristic, actually on the best path, or what? If you use the actual terminology of the algorithm you're working with, rather than just making stuff up as you go along, you're likely to get better help for your problems, and it will probably help you understand the algorithm better yourself.

Quote:

Original post by Smjert So, imho, the only way the algorithm can reach the point i want to go is to go backward, but going backward the nodes will have worse F cost than the starting one..

Right, it'll start off going forwards, but when it finds the way forward is blocked, it'll start looking at the nodes that go backwards.

Don't look at the first few nodes that A* expands and expect to be able to predict the final result. You need to let it calculate the complete path. That's why you've got the "open" list sorted by "estimated cost + current cost".

Quote:

(2*(x+y)+z) * (1.0 + p)

This is an unusual heuristic. Have you tried simply using the euclidean distance? That is:

sqrt(x*x + y*y + z*z)

I think your problem is that you're stopping A* when you find a path (the blue line) rather than continuing until you find the shortest path (somewhere between the blue and green lines).
If you continue to run A* until the open list is empty then you'll always get the shortest path.

Quote:

Original post by SimonHx I think your problem is that you're stopping A* when you find a path (the blue line) rather than continuing until you find the shortest path (somewhere between the blue and green lines). If you continue to run A* until the open list is empty then you'll always get the shortest path.

Oh this is an interesting thing, i thought that when it reaches the goal node that path it's already the best.
Anyway as i said i don't really need the shortest path, but only something in the middle, since as i said this algorithm is used by monster only when the find an obstacle (the other times they simply calculate the target direction and move forward) and it hasn't to be the best.
But check my edit.. am i right?

Quote:

Original post by Smjert Oh this is an interesting thing, i thought that when it reaches the goal node that path it's already the best.

When it expands the goal node it's the best. Not when you first encounter it. But since you're not using an admissible heuristic, that's not true for you.

Here's a site which lets you test the algorithm and here's what I got for your test case:



As you can see, the red nodes are all the nodes it searched looking for a solution, but ultimately discarded. It eventually chose the yellow line, which is what you were expecting.