Now i'm using euclidean distance heuristic, multiplied by p factor (here is explained why i use p factor) and it still fails.
But euclidean distance it's not used when you can turn to any angle?
I'm in a tile based game and i can move only from tile to tile with 8 directions... it's still good?

I followed the pseudo-code written on Wikipedia: A* search algorithm

I did some corrections and i'm using this heuristic function:

h_diagonal(n) = min(abs(n.x-goal.x), abs(n.y-goal.y))
h_straight(n) = (abs(n.x-goal.x) + abs(n.y-goal.y))
h(n) = D2 * h_diagonal(n) + D * (h_straight(n) - 2*h_diagonal(n)))

Where D for me is 1 and D2 is 1.4.

I'll try to write the algorithm i use and then i explain my problem:

1)Add the starting node to the openlist
Loop until openlist is empty:
1)Find the best node looping through the openlist
2)Remove the best node from the openlist and add it to closed list
3)If the best node is the goal, reconstruct the path
4)Otherwise Get successors of the best node
Loop2 until there's successors:
1)If the node is not on closed list calculate new G cost adding 1 to the best node cost if the movement is x or y, and adding 1.4 if is diagonal
1.1)If the node is not on open list add to it, calculate the H cost
1.2)Otherwise if is on open list and the new G cost is lower than the old G cost of the expanded node, update the G cost with the new one
2)If 1.1 or 1.2 was true, update F cost and set best node as the parent of the current node.
End Loop2.
End Loop.

Ok the problem is that after the first cicle of Loop, when it tries to find another best node different from the starting one it doesn't find it, because there's only one with the same F cost of the starting one.
What to do in this case? set the current node as the bestnode?

Now it works!
Previously it doesn't work because there was a check about the distance from the goal of the expanded node, and to find the path A* was expanding nodes farther than the maximum distance allowed.
I simply increased this max distance..

Here's an image from the game (Ultima Online :P):



The red circle is the start, the black runes are the successors, the blue runes are the best nodes found and the brown runes are the best path.

However i still don't know what to do when, searching the best node, two F cost are equal.

No one knows?

From the look of the image, I think you're not selecting the correct node from the OPEN list. There's far too many blue nodes over on the right, after it gets out of the little cul-de-sac.

You should choose nodes from the OPEN list that have the smallest f() + h() value - that is, the current cost + heuristic cost. If I had to guess, I'd say you're only looking at the current cost, f(), when choosing nodes on the OPEN list.

That's just a guess though...

What i do is this (from the start):

Take the best node from the open list (taking the lowest F() cost), the first time is the starting node.
Expand all the neighbours of that node, calculate F cost and add them to the open list.
Loop this thing (but the second time there's also "if the node is already on the open list and have a G cost better than the old G cost, set the parent to the current best node).
So i'm taking the best F cost, but dunno why it goes on the right..
And for equal F costs? what i have to do? which node to choose?

PS: but F cost is the sum of G + H cost, why check F cost + H cost O.o.

Quote: Original post by Smjert
No one knows?

It doesn't matter. The guarantees of A* are satisfied regardless of your method of breaking ties.

Quote: Original post by Smjert
What i do is this (from the start):

Take the best node from the open list (taking the lowest F() cost), the first time is the starting node.
Expand all the neighbours of that node, calculate F cost and add them to the open list.
Loop this thing (but the second time there's also "if the node is already on the open list and have a G cost better than the old G cost, set the parent to the current best node).
So i'm taking the best F cost, but dunno why it goes on the right..
And for equal F costs? what i have to do? which node to choose?

PS: but F cost is the sum of G + H cost, why check F cost + H cost O.o.

Oh right, I don't call them "f", "g" and "h" in my code, I don't know why people use those names, it's really annoying [wink] Anyway, yeah, it's supposed to be g() + h().

But I'm pretty sure there's something wrong there. Whether it's your heuristic, or somewhere else. Try starting off with a map where there's no obstacles at all and see what happens. The algorithm should pretty much head straight towards the goal without stepping off track. Is that what happens?

I suggest you try your scene out on that interactive demo I linked to before. It'll show you what it should look like. It's also got a python implementation, which should hopefully help you to understand the algorithm a bit better. For example, I tried to recreate your map, and this is what happened:



Notice how once it got out of the hollow, it basically went straight for the target? That's what you should be seeing. It looks like you've got the basic algorithm right from your pseudocode, so there must be something else in there. I personally still suspect your heuristic. Have you tried a basic straight-line heuristic? Remember: the heuristic must always underestimate the actual cost of the path. I'm not sure you current one would do that.

A straight-line heuristic is not the best when you have different weights for diagonal vs. straight movements, but it's still underestimating and will still, therefore, find the optimal path. The only drawback is that it would be a little slower than a truely optimal heuristic. At this stage, accurate is better than fast :-)

By the way, when there's two f()'s that are the same, it doesn't matter which one you choose.

I call the F, G and H because these are their names.
If you read articles (standford, polymaniac (or something like that) wikipedia.. also university if i remember well :P).
Anyways first of all i forgot to thanks all of you for your quick answers ;).

About the map without obstacles: yes the output is very "clear", no extra unneeded expanded node or best node checked.

I'll try with other heuristics, and i'll let you know what are the results.

Quote: Original post by Smjert
I call the F, G and H because these are their names.
If you read articles (standford, polymaniac (or something like that) wikipedia.. also university if i remember well :P).

Yeah, I know, that's what I meant [smile]. It seems to be a common thing with academics to name variables with a single letter...