In A star, how does the heuristic help determine your path?

Question

Say you're using a 4 by 5 grid. The G cost for horizontal and vertical movement is 10, and the G cost for diagonal movement is 14. On this page: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html it says "At one extreme, if h(n) is 0, then only g(n) plays a role, and A* turns into Dijkstra’s algorithm, which is guaranteed to find a shortest path."

Why would it find the shortest path? Wouldn't it find the longest path instead? If the heuristic no longer plays a role then it will never consider going diagonal because the cost of diagonal movement is 14. Previously, even if the G cost was higher than another adjacent node, it could still be chosen if the H cost was a bit lower.

Now, even if the shortest path was by going diagonal, it would never go diagonal because the G cost of diagonal movement will always be higher than the G cost for horizontal/vertical movement. So why exactly would it be guaranteed to find the shortest path if the heuristic was 0?

Another thing, what would be the difference if, let's say we're using the Manhatten method, and after calculating the total number of squares moved horizontally and vertically to reach the target square from the current square the heuristic was multiplied by 1 or if it was multiplied by 100? Wouldn't the path be the same either way?

Answer 1

In short, the heuristic is added to the "cost so far". That's why when h(x) = 0 we have A*=Dijkstra. In Dijkstra we only use the "cost so far", and adding 0 to a number doesn't change it.

In short, the formula is:

cost to reach P from Q = cost to reach Q + cost from P to Q + heuristic

I believe what you are missing is the "cost to reach Q part". Either way, I'll explain how Dijkstra works here so you can see it in action (I'm less familiar with A*, but it shouldn't matter since they're the same in this case).

Say we have nine nodes:

TL TM TR
ML MM MR
BL BM BR

(TR=top-right, BL=bottom-left, etc.)

We start in BR and we want to find the path to TL.

Initially, we set the distance to the three nodes from BR:

MR = 10 from BR
BM = 10 from BR
MM = 14 from BR

Now, we take the node with the lowest cost so far, which is MR or BM. Let's take MR.

From MR we can reach TR, TM, MM, TM and BR. We'll add the costs of these distances to the cost of reaching MR (which is 10). Also, since we've already visited BR, we won't check it again (in Dijkstra, at least).

TR = 10 + 10 = 20 from MR
TM = 10 + 14 = 24 from MR
MM = 14 from BR, 10 + 10 = 20 from MR. Since 14 < 20, we'll keep the path from BR and ignore the path from MR.
BM = 10 from BR, 10 + 14 = 24 from MR. We'll keep 10 from BR.

So we have:

BM = 10 from BR
MM = 14 from BR
TR = 20 from MR
TM = 24 from MR

So next we'll visit BM.

As you can see, the best path to MM the algorithm found so far is the one from BR, not the one from MR.

After we finish the algorithm, we'll have:

(TR = 20 from MR) (TM = 24 from MR or MM) (TL = 28 from MM)
(MR = 10 from BR) (MM = 14 from MM) (ML = 24 from MM or BM)
(BR = 0, start) (BM = 10 from BR) (BL = 20 from BM)

As you can see, the shortest path to TL does use the diagonals

Another thing, what would be the difference if, let's say we're using the Manhatten method, and after calculating the total number of squares moved horizontally and vertically to reach the target square from the current square the heuristic was multiplied by 1 or if it was multiplied by 100? Wouldn't the path be the same either way?

Multiplying the heuristic by 1 would change nothing, since 1 * h(x) = h(x). Multiplying the heuristic by 100 would make the heuristic be bigger relatively to the "distance so far" which, according to the article you quoted, makes A* look more like a Best-first-search and less like Dijkstra.

Answer 2

This is from a paper I wrote, which is why it is so expository.

The popular variant of Dijkstra's algorithm, the A* algorithm, uses a heuristic to "help" Dijkstra's algorithm converge on a solution faster. What A* does really is deter Dijkstra's algorithm from exploring nodes that are in the "wrong direction" from the destination by adding an additional cost (on top of the edge weight cost) to the exploration of nodes that would take us away from the desired destination node. As you can see in the figure below, A* "doesn't bother" expanding nodes that lead away from the solution, hence converging on a solution faster.

Figure: Dijkstra's algorithm (left) and A* algorithm (right) running on the same map as solved by the software accompanying Buckland's text. Red denotes expanded nodes, blue denotes final decision path.

The additional cost added to an edge traversal is called the heuristic function. The cost of reaching a node then becomes f(n) = g(n) + h(n), where g(n) is the accumulated edge weight cost and h(n) is the heuristic function.

The value of h(n) is usually the Euclidean distance sqrt(x^2+y^2) to the destination node. If diagonal moves are not allowed, then its value can be the Manhattan distance to the destination node. The extra cost h(n) will not spoil the correctness of Dijkstra's algorithm so long as h(n) does not ever exceed g(n) (the actual edge‐weight cost of reaching that node), for any node. When h(n) meets this condition h(n) is called admissible. If h(n) is not admissible, then it will prevent A* from finding the shortest path much like a backseat driver prevents an otherwise good driver from taking the best path by assigning incorrectly high costs to otherwise good routes.

Answer 3

The problem is that you're forgetting that the G function by itself is not the cost. The cost of a node is the cost of the parent node plus the G function cost to the new node.

Even if diagonal movements are 14 and cardinal moves are 10, the cost of moving diagonally from a parent close to the start node will be much lower than the cost of moving cardinally from a node far away from the start. That is, moving diagonally from the start node has a total cost of 14 (0 + G:14 = 14) while moving two square away in a straight line has a total cost of 20 (parent node cost of 10, so 10 + G:10 = 20). Hence the diagonal movement will be checked before the linear movement in this scenario as it has a total lower cost.

The H function just helps in that it makes the engine more likely to consider a node closer to the goal. Dijkstra finds the shortest paths leading out from the start node until it happens up on the goal. That is, Dijkstra finds the shortest paths that are 1 unit away, then 2 units away, then 3 units away, etc. A* will lean toward a path that is closer to the goal rather than just the shortest path to a node leading away from the goal.