Ok, I read all that tutorial, well, there are a few sentences I didn't get. Written under the Figure 6

Quote: Note that the parent square for the square two squares below the starting square has changed from the previous illustration. Before it had a G score of 28 and pointed back to the square above it and to the right. Now it has a score of 20 and points to the square just above it. This happened somewhere along the way on our search, where the G score was checked and it turned out to be lower using a new path – so the parent was switched and the G and F scores were recalculated. While this change doesn't seem too important in this example, there are plenty of possible situations where this constant checking will make all the difference in determining the best path to your target.

I cannot understand why the parent changed in that way: is it become the block below the green block ? Shouldn't it be the down-left one ? From "Summary of the A* Method"

Quote: If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.

Does this means that the numbers are restored every time but the list can be unsorted ?

Quote:
Does this means that the numbers are restored every time but the list can be unsorted ?

I too am trying to implement this, and have read this tutorial. I believe what he means is that everytime you add a new node to the open list, you will need to resort that list,(or each time before you pull a node off it) in order to make sure that the node with the lowest F score is at the top. As far as unsorting it goes, I don't believe there is any need to ever unsort it. I believe you only need to know if there is atleast one node in the list, and what the node with the lowest F is.

Jeff

p.s. I'm a newb at this, so hopefully someone can confirm/correct me if I'm wrong/right

Quote: I believe you only need to know if there is at least one node in the list, and what the node with the lowest F is.

I haven't read that tutorial, but that case is best solved with a heap/priority queue. Adding and removing elements in a heap is O(log(n)) which will almost definitely be faster then resorting the list or even looping through and picking the smallest element.

I'm probably misunderstanding the word resort: what is the difference between adding/removing objects to the list and resorting the list ?

Here's a list:

1 2 3 4 5 6

Remove 4 from the list:

1 2 3 5 6

Add 7 to the list

7 1 2 3 5 6

Now resort the list

1 2 3 5 6 7

[smile]

Ok, I hope I understood :P

What about the parent changing I mentioned ? I can't understand the new direction of the pointer in that square.

I cut and past the considered area: look at down-left of the 2 images: before and after.

http://img111.imageshack.us/img111/8792/differencesrc2.png