The Manhattan Distance

Recommended Posts

Hello, As part of an AI demo i am writing i use the manhattan distance in a best-first search. However i think that my calculations for the manhattan distance may be wrong. Could anyone give me there thoughts on my maths. Here is the function i have used:
int GetManhattan ( int x1, int x2, int y1, int y2 )
{
return abs( ( x1 - x2 ) + ( y1 - y2 ) );
}


x1 being my start node x x2 being my finish node x y1 being my start node y y2 being my finish node y Thank you for looking.

Share on other sites
Consider: what is the manhattan distance between (0,1) and (1,0)? What is the distance in each dimension? What would your function calculate it as?

Share on other sites
Thank you for replying so quickly.

In response to your questions, i have to admit i don't think i know the answer. Would the distance between point (0,1) and point (1,0) be a manhattan distance of 2?

Using my calculation the answer would return as -2 but then because i have the absolute value i assumed this would make the value positive therefore correct?

Does this mean my claculation is correct and it's possibly another element of my code that is causing me problems.

Share on other sites
(0 - 1) + (1 - 0) = -1 + 1 = 0

Share on other sites
If you have correctly copied and pasted code then your formula is wrong.

Share on other sites
Sorry, i'm getting confused. So is my formula incorrect?

Share on other sites
You need absolutes of both variables before the addition

Share on other sites
Yes, your formula is incorrect. The manhattan distance between (0,1) and (1,0) should be 2, but your program calculates it as 0. Why is that?

Share on other sites
I have just adjusted the values as Diosces said like so:

return ( abs( x1 - x2 ) + abs( y1 - y2 ) )

And it calculates it as 2.

Funny thing is when i calculated the points (0,1) and (1,0) after Sneftel posed the question, i actually did the maths on paper and made the values absolute before the addition without realising myself!! haha.

Thank you for your help people and thank you Sneftel for not immediatley giving me the answer. I much prefer it when people pose me questions and make me question my own code, it helps me progress a lot more.

Thank you.

Create an account

Register a new account

• Forum Statistics

• Total Topics
628370
• Total Posts
2982300

• 10
• 9
• 13
• 24
• 11