next »

[michalko]

Hello everyone. This is my first post so please forgive me if I broke any rules unintentionally.

I am following probably the most known article on A* pathfinding on the Internet.

I have two questions;

Question 1:

I am a bit stuck and confused at the stage when the author gets to the 3rd cell (one down and one to the right from the start). What I don't seem to be understanding is why the 4th one (the next one after the 3rd) is the one straight down from the third and not the immediate left?

note: Mathematically for the Manhattan method H = 10 * SQRT(currentX - destinationX)^2 + (currentY - destinationY)^2)

G is 10 for both: left and down.

So when I am calculating the next F (next node) the one on the immediate left calculates to 60 and the starting node is the parent.

Calculating F for the one directly below the current cell also evaluates to 60 but the parent is the current cell.

So now, why does the author decide to go straight down instead of taking an immediate left?

Question2:

After a few moves (After Figure 6) author says:

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 don't understand why it points back to the 1st down from the start. I think it should be pointing left from the 4th cell (away) and the clarification from the author is not sufficient for me to understand. I would really appreciate if someone could verify if the arrow should really be pointing down and possibly explain to me why it's that way.

Don't hesitate to ask for clarification from me if needed.

Thanks a lot for your time.  

[vinheim3]

1. It seems the guy ignores the left square (despite having a lower F) because it is already on the open list

2. It looks like the guy was giving an optional example of what your nodes would look like IF you decide to do constant checking rather than always choosing from tiles adjacent to the closed list. If you did do constant checking, you would have a smaller F if you got to that cell from the N rather than from the E.

Personally, I think you should always do constant checking if you are doing a 2D grid-based game.

[michalko]

Thanks vinheim3 for your quick response.

1. It seems the guy ignores the left square (despite having a lower F) because it is already on the open list

Would this be a rule of thumb then? Always follow the newly discovered nodes and the ones on the opened list have a lower priority?

2. It looks like the guy was giving an optional example of what your nodes would look like IF you decide to do constant checking rather than always choosing from tiles adjacent to the closed list. If you did do constant checking, you would have a smaller F if you got to that cell from the N rather than from the E.

Personally, I think you should always do constant checking if you are doing a 2D grid-based game.

Can you possibly elaborate on "constant checking"? I'm a bit confused by the meaning of it.

[michalko]

I am so stupid ! I get it now

Its a cumulative sum - so from the starting point that one down distance is 10 because it's already on the opened list. Because I have moved already and checked the cumulative (14+10) > current 10 I skip the cell and move on.

God, how could I not see it already...

Question 2 remains opened.

[vinheim3]

Would this be a rule of thumb then? Always follow the newly discovered nodes and the ones on the opened list have a lower priority?

It looks like this particular algorithm's rule of thumb is to not even give those on the open list a priority. I'm guessing this is just for tutorial/demonstration's sake, but I would read his later points on how to improve upon this because this way, you'll have a hard time plotting a path through even simple mazes.

Can you possibly elaborate on "constant checking"? I'm a bit confused by the meaning of it.

If you scroll down to 8. Dijkstra's Algorithm, it's an example of an algorithm that does constant checking. Essentially, from the start, you check the F value of every node around you. Then for each node, you check the F value of nodes around those, and so on until you reach your goal.

Sometimes nodes will share adjacent new nodes. In the example, the node at 1S1E and 1S share an adjacent node at 2S. If you go from start to 1S1E(F=14), then to 2S(F=14+14), you get an F of 28, but if you go from start to 1S(F=10) to 2S (F=10+10), you get an F of 20. So initially 2S would have had a parent of 1S1E, but since it gets a smaller F from 1S (20 rather than 28), it changes its parent node to 1S.

Just that first paragraph should be enough to explain constant checking. This guy's example of non-constant checking is to choose the nearest from the closed list until he gets to the goal rather than considering the open-list, again probably having to do with demonstration, or explaining the basics

EDIT: didn't read the summary, yeah the guy considers the open list in the way I described