Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I have a square-based map. Only horizontal and vertical movement is allowed (no diagonals). Movement cost is always 1.

I'm implementing an A* algorithm on that map, using the Manhattan distance as a distance heuristic. Is this heuristic consistent? Can I can avoid checking g(node) against nodes that are in the CLOSED set?

Edit: By consistent I mean monotonic.

share|improve this question
1  
If your movement cost is uniform across every tile, you could replace A* with Jump Point Search –  Nick Caplinger Jun 26 '13 at 0:32
    
Hey, that's nice! –  Emiliano Jun 27 '13 at 11:31
add comment

4 Answers

up vote 9 down vote accepted

To actually answer your question: the manhatten distance is consistent when you're constrained to moving vertically/horizonally along an unweighted grid (this can be easily shown by the definition on wikipedia). So yes, in your case you can avoid rechecking nodes in the closed set.

However, once you allow diagonal or any-angle movement, manhatten distance becomes nonadmissible because it overestimates diagonal costs, which necessarily means it's not consistent.

share|improve this answer
    
Yes, this is exactly the kind of answer I was looking for. It would be nice to know what happens if the heuristic function is h(x) = min(manhattan(p1), manhattan(p2)) (i.e. either p1 or p2 are good ending point and I want to reach the nearest one). Is this h(x) still monotonic? –  Emiliano Jun 6 '13 at 14:01
    
@happy_emi: Yes, if h(x, p1) and h(x, p2) are consistent, then min(h(x,p1), h(x,p2)) will also be consistent. This is easy to show from the definition on wikipedia (we would need to show that min(h(x, p1), h(x, p2)) <= distance(x,y) + min(h(y, p1), h(y, p2)) for all nodes x and y with an edge between them. Now assume that h(x, p1) is the minimum; can you show that it's definitely <= the right-hand side, using the fact that both heuristics are consistent?) –  BlueRaja - Danny Pflughoeft Jun 6 '13 at 14:31
add comment

Yes, the Manhattan distance between two points is always the same, just like the regular distance between them. You can think of the Manhattan distance being the X and Y components of a line running between the two points.

This image (from Wikipedia) illustrates this well:

Manhattan distances

The green line is the actual distance.

The blue, red and yellow lines all represent the same Manhattan distance (12 units). No matter what combination of movements up and right you draw from the bottom-left point to the bottom-right, you'll get the same total Manhattan distance.

share|improve this answer
4  
Thanks for the edits Anko, looks better than before! –  Byte56 Jun 3 '13 at 14:36
1  
Great answer: short, sweet, to the point and with a pretty picture. –  Blue Jun 3 '13 at 15:34
2  
I believe by the definition you linked, the Manhattan distance is consistent. The green line distance would be using a different heuristic. The Red, Blue and Yellow lines show that the distance between the two nodes remains the same (when using the same heuristic). Moving closer reduces the heuristic and moving farther away increases the heuristic. This meets the monotonic requirement of the OP. As the graph is constructed, with a node at each "intersection", the Manhattan distance is consistent. If it were a different scenario (like allowing diagonal movement), the heuristic would be bad. –  Byte56 Jun 3 '13 at 20:30
2  
I already said that Manhatten Distance is consistent, but not for the reasons you mention. Your answer does not show consistency, nor does your argument in the comments. "Consistent/monotone heuristic" has a precise definition (given in my above link), which is not the same as a monotone function which you seem to be confusing it for. Stating "moving closer reduces the heuristic and moving farther away increases the heuristic" is not sufficient to show it's consistent, eg. 2*manhatten satisfies that, but is not consistent. –  BlueRaja - Danny Pflughoeft Jun 3 '13 at 20:47
3  
I don't know why you say it's incorrect, you appear to be insisting this answer is incomplete. The proof in your answer appears to be just as weak: "the manhatten distance is consistent...", you then go on to reiterate the original specifications of the question, following with how it would be non-admissible if the scenario were different. I didn't feel as though the answer warranted a full mathematical proof. If you feel this question requires that, then please include it in your answer and I will up vote it. Thanks for the constructive criticism. –  Byte56 Jun 3 '13 at 21:10
show 1 more comment

In extension of Byte56's answer I would like to point out, that in your specific data set, using the Manhattan Distance as your heuristic function will actually always be a perfect heuristic in the sense that it will always return the actual path cost (assuming there is nothing "blocking" the paths).

You should also note, that all nodes in the correct direction (either horisontally or vertically) will yield the same expected distance (because there are many equally short paths to the goal). You should be aware that your priority queue (open set) should, in case of tied priorities, dequeue the latest added node first (LIFO - Last In First Out). By doing so you will only examine the nodes which will end up in the optimal path. If you examine equally suitable nodes in a FIFO (First In First Out) manner, you will effectively be examining all nodes which are part of a best path. This problem arises because there are multiple equally good paths to the goal node.

share|improve this answer
    
"(assuming there is nothing blocking the path)" - that's a pretty big assumption. If there's nothing blocking the path, there is no need for a path-finding algorithm to begin with! –  BlueRaja - Danny Pflughoeft Jun 3 '13 at 19:31
    
@BlueRaja-DannyPflughoeft: That is true, it was just a thought popping up when looking at Byte56's image. The rest is true nonetheless. –  tahatmat Jun 3 '13 at 19:57
add comment

I'm not sure what do you mean by "always" consistent. Is the Manhattan distance on a fixed grid independent of the path taken? Yes, as Byte56's answer said.

However, for example, Manhattan distance is not invariant under rotations. E.g., the Manhattan distance (L1-norm) between the origin and a point (10,10) is |10-0| + |10-0| = 20. However, if you rotate your coordinates by 45 degrees (so now your fixed point lies along one of the directions of the grid), you'll now find the same point is now at (10sqrt(2),0), so has a Manhattan distance to the origin of 10sqrt(2)~14.14.

share|improve this answer
    
+1 for pointing this out; OTOH, Manhattan distance is invariant under 90-degree rotations, which are really the only ones that can be made 'consistently' on a discrete grid. –  Steven Stadnicki Jun 3 '13 at 18:23
1  
Good catch, though he did mention that only horizontal and vertical movement is allowed. –  tahatmat Jun 3 '13 at 18:25
1  
The original question was about consistent as in monotonic. –  Emiliano Jun 3 '13 at 18:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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