Sign in to follow this  
Ronnie TRFC

The Manhattan Distance

Recommended Posts

Ronnie TRFC    122
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 this post


Link to post
Share on other sites
Sneftel    1788
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 this post


Link to post
Share on other sites
Ronnie TRFC    122
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.

Share this post


Link to post
Share on other sites
Sneftel    1788
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 this post


Link to post
Share on other sites
Ronnie TRFC    122
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this