int GetManhattan ( int x1, int x2, int y1, int y2 )
{
return abs( ( x1 - x2 ) + ( y1 - y2 ) );
}
The Manhattan Distance
Author
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:
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.
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?
Author
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.
Thanks for your time.
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.
Thanks for your time.
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?
Author
I have just adjusted the values as Diosces said like so:
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
