6
\$\begingroup\$

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?

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I'm a little confused at this part "MR MM = 14 from BR, 10 + 10 = 20 from MR. Since 14 < 20" I don't understand why you're suddenly calculating the cost from BR as opposed to from MR. Isn't it supposed to be MR MM = 10 + 10 = 20, MR BM = 10 + 14 + 24? And you check if BR MR MM < BR MM and if BR MR BM < BR BM. And since the first is 0 + 10 + 10 = 20 and the second is 0 + 10 + 14 = 24. 20 > 14 and 24 > 10 so you don't do anything? \$\endgroup\$ – Mastrolinie Sep 6 '13 at 21:30
  • \$\begingroup\$ @Mastrolinie I improved the formatting. I hope it's more clear now. I'm not calculating the cost from BR, I already have the cost from BR from the previous iteration. I just compute the cost from MR and see if it's better than what we already have. It's not, so we ignore it. By "MR MM" do you mean "MR to MM" or "MR from MM"? \$\endgroup\$ – luiscubal Sep 6 '13 at 21:40
  • \$\begingroup\$ It's MUCH clearer now, thanks. By "MR MM" I mean from MR to MM. It seems my whole problem was forgetting that when h(n) = 0, the ones on the open list can also be the lowest. I tested it out again with it in mind and you were right. Thank you 100x! One thing, though, regarding the multiplication by 1 as opposed to by 100, I know that it makes it look more like the best-first-search, but I don't understand why. What would be the different in multiplying by 1 as opposed to 100000, if the multiplication applies to all vertices anyway? \$\endgroup\$ – Mastrolinie Sep 6 '13 at 22:17
  • \$\begingroup\$ @Mastrolinie The article you quoted uses the formula g(n) + h(n). if h(n) is very big, then g(n) + h(n) is aproximately equal to h(n) (just like 1 + 1000000 is approximately 1000000). So, in short, if h(n) is too big, the algorithm kind of ignores g(n). \$\endgroup\$ – luiscubal Sep 6 '13 at 22:27
  • \$\begingroup\$ I don't really understand why it would ignore g. What difference would it make if f was 1000014 as opposed to 1000010? \$\endgroup\$ – Mastrolinie Sep 6 '13 at 23:00
7
\$\begingroup\$

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.

enter image description here

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.

\$\endgroup\$
  • \$\begingroup\$ link to paper? Am curious :) Hope its about JPS and stuff. \$\endgroup\$ – Will Sep 6 '13 at 21:48
  • \$\begingroup\$ Can you maybe post a text version of the excerpt? Right now as a picture it won’t show up in searches. \$\endgroup\$ – sam hocevar Sep 6 '13 at 22:10
  • \$\begingroup\$ @Will It was a school paper. I don't have the full paper online as of now. I can paste the actual text though. \$\endgroup\$ – bobobobo Sep 6 '13 at 23:03
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ From curiosity: Why do you use the term cardinally for what I have known for decades as orthogonally? \$\endgroup\$ – Pieter Geerkens Sep 7 '13 at 3:23
  • \$\begingroup\$ I was having trouble remembering the right terminology and could only recall "cardinal directions" (east, north, west, south). \$\endgroup\$ – Sean Middleditch Sep 7 '13 at 4:17
  • \$\begingroup\$ Good deke; I knew what you meant, but it sounded weird. \$\endgroup\$ – Pieter Geerkens Sep 7 '13 at 4:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.