Can't understand A* Pathfinding algorithm when two paths seem to return the same "length" but one would send me in a completely wrong direction

Question

I am reading about A* pathfinding using heuristics and manhattan method and I am struggling with understanding the logic in one specific place in the article.

I am stuck right after where the below image is

and to better understand here's a quote

This time, when we check the adjacent squares we find that the one to the immediate right is a wall square, so we ignore that. The same goes for the one just above that. We also ignore the square just below the wall. Why? Because you can’t get to that square directly from the current square without cutting across the corner of the nearby wall. You really need to go down first and then move over to that square, moving around the corner in the process. (Note: This rule on cutting corners is optional. Its use depends on how your nodes are placed.)

and - I have highlighted the part which confuses me

That leaves five other squares. The other two squares below the current square aren’t already on the open list, so we add them and the current square becomes their parent. Of the other three squares, two are already on the closed list (the starting square, and the one just above the current square, both highlighted in blue in the diagram), so we ignore them. And the last square, to the immediate left of the current square, is checked to see if the G score is any lower if you go through the current square to get there. No dice. So we’re done and ready to check the next square on our open list.

So the author assumes that the F ( G + H ) to the immediate left is now greater than the F to the one right below. Logically, by looking at it YES, even a child will agree you should be going towards the RED so go down and across the BLUE wall, but mathematically (unless there is something obvious that I have missed) I see it this way at this point

So if I was writing out this algorithm in C# I would be stuck because both the left and bottom from "here now" would return the same number, 60? How would I know which one would I benefit from going into the most?

Even in this scenario the number would still IMO equal 60

• 10 to go directly left + 50 (H)

• 10 to go directly down + 50 (H)

Have I missed something here? What am I doing wrong?

Answer 1

This is what you think the algorithm is describing:

 ___ ___ ___ ___ ___
|   |   |xxx|   |   |  p = parent
|___|___|xxx|___|___|  c = current
| p |   |xxx|   | e |  e = end
|___\___|xxx|___|___|
| <---c |xxx|   |   |
|___|_|_|xxx|___|___|
|   | v |   |   |   |
|___|___|___|___|___|

But this is what's really happening:

 ___ ___ ___ ___ ___
|   |   |xxx|   |   |  p = parent
|___|___|xxx|___|___|  c = current
| p |   |xxx|   | e |  e = end
|_|_\___|xxx|___|___|
| v | c |xxx|   |   |
|___|_|_|xxx|___|___|
|   | v |   |   |   |
|___|___|___|___|___|

A* doesn't necessarily evaluate one path at a time. It evaluates multiple paths simultaneously while having a bias to process the more likely paths first. This is a good thing as a naive depth first search will be costly if the first path you decide to investigate turns out to be a dead end. Searching multiple paths statistically reduces this cost.

From the description it looks like the next move is this:

 ___ ___ ___ ___ ___
|   |   |xxx|   |   |  p = parent
|___|___|xxx|___|___|  c = current
| p |   |xxx|   | e |  e = end
|_|_\___|xxx|___|___|
| c |\  |xxx|   |   |
|_|_\_|_|xxx|___|___|
| v | v |   |   |   |
|___|___|___|___|___|

Which as you can see will reach the same conclusion of reaching the corner square. In fact, the cost of going diagonally first or down first is the same - it takes two steps either way to reach the corner square.

Answer 2

The G cost is cumulative.

From the starting point, going south-east costs 14. From the south-east square (your "here now" square) going south costs 10, this makes for a cumulative G cost of 10+14 = 24.

Again, from the south-east square (your "here now" square) going west would cost 10 points (G) which gives us again 24 (since we already paid 14 to get to that square). But this square is already in your open list so you check if the result you just got is better. Your open list shows a G of 10 for that square and since 24 is worse you don't update it. (this is what the bold part means)

Answer 3

Yes you are missing something. I'm not sure what exactly though.

The passage in bold refers to updating a node which is already in the open set.

If the path through the current node is cheaper than the one that is already computed, you update that node. If it's more expensive, you do not. If the cost is equal, you may do either.

Note that's the actual cost, not estimated, of two different paths to one single node. Cost of any other node doesn't play a role here.

Now it looks like you don't know what to do if you have two different nodes with the same cost. This is a different part of the algorithm, the one where you add nodes to the open set.

The answer is, you add them both to the open set. Actually you add all possible nodes to the open set, regardless of the cost. Since the open set is ordered by estimated cost, you will process the most promising nodes first, and hopefully never arrive to the worst ones.