1,105,578 Community Members

Manhattan vs travelling distance

Member Avatar
drogba123
Junior Poster
170 posts since Mar 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Hi,

Anyone know what is the math for manhattan distance vs travelling distance? and which one is faster? thanks.

Regards,
Anthony

Member Avatar
Taywin
Posting Maven
2,632 posts since Apr 2010
Reputation Points: 134 [?]
Q&As Helped to Solve: 378 [?]
Skill Endorsements: 17 [?]
 
0
 

I believe when you talk about "travelling distance" means "Dijkstra's algorithm"? If so, this will depend on application and how you apply an algorithm to it.

Member Avatar
drogba123
Junior Poster
170 posts since Mar 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Hi,

Nope. i am talking bout A* algorithm. i was wondering for the manhattan distance the calculation would be

distance += Math.abs(state.x - x);
distace += Math.abs(state.y - y);

but for travelling distance,

is it distance = Math.sqrt(Math.pow(x,2)+Math.pow(y,2));

Member Avatar
Taywin
Posting Maven
2,632 posts since Apr 2010
Reputation Points: 134 [?]
Q&As Helped to Solve: 378 [?]
Skill Endorsements: 17 [?]
 
0
 

OK. You may find this link to be interesting for your decision. :) http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html The writer gives some analysis for both algorithm you are talking about.

Member Avatar
drogba123
Junior Poster
170 posts since Mar 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Hey thanks for the link. i read it and it says that for 4 movement, its recommended to use manhattan distance but i am not supposed to do the manhattan but instead use travelling distance. not sure what kind of formula i should use to calculate the algorithm 2 * (travelling distance)

Member Avatar
Taywin
Posting Maven
2,632 posts since Apr 2010
Reputation Points: 134 [?]
Q&As Helped to Solve: 378 [?]
Skill Endorsements: 17 [?]
 
0
 

On the page, it describe as weighing your terrain by multiplying with a constant greater than 1. The example that the author gave is to show that the grass square may cost 2 to move on. If you are doing the distance comparison in heuristic, you may need to consider this terrain weight as well. However, if the whole terrain is the same, you don't need to worry about the weighing.

Member Avatar
drogba123
Junior Poster
170 posts since Mar 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

hmm..but on my task, i am assuming the cost to move is 1.

Member Avatar
drogba123
Junior Poster
170 posts since Mar 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Hi,

My program result show if i use manhattan distance it will be,

Optimal path:
5 1 4 4 1 5 4 1 2 2 3 3 1 3 4
3 4 * 3 4 3 5 1 3 4 4 1 1 2 4
4 3 * * 3 2 5 4 2 2 5 4 4 2 3
4 3 4 * 5 2 3 5 3 1 3 2 2 3 5
3 4 1 * * * 2 3 1 4 1 5 4 2 5
4 1 1 5 4 * 4 4 2 4 5 4 2 5 4
1 2 1 4 1 * 4 1 1 4 4 3 4 5 1
5 4 1 3 2 * 4 5 5 4 2 1 1 1 2
1 4 1 2 1 * 4 3 4 3 5 5 5 3 1
2 1 1 1 4 * 1 4 5 2 2 2 5 1 1
4 1 2 4 5 * 4 1 1 5 4 5 4 5 1
3 1 2 5 2 * 3 5 5 2 4 2 5 5 4
4 1 2 1 4 * * * * * * * * * 5
2 3 2 2 2 2 1 1 3 4 1 1 4 5 2
2 4 5 2 3 2 5 3 3 5 1 4 3 1 3

total cost is 99

but if use euclidian distance the result will be,

Optimal path:
5 1 4 4 1 5 4 1 2 2 3 3 1 3 4
3 4 * 3 4 3 5 1 3 4 4 1 1 2 4
4 3 * * 3 2 5 4 2 2 5 4 4 2 3
4 3 4 * 5 2 3 5 3 1 3 2 2 3 5
3 4 * * 3 3 2 3 1 4 1 5 4 2 5
4 1 * 5 4 3 4 4 2 4 5 4 2 5 4
1 2 * 4 1 2 4 1 1 4 4 3 4 5 1
5 4 * 3 2 3 4 5 5 4 2 1 1 1 2
1 4 * * * 4 * * * * 5 5 5 3 1
2 1 1 1 * * * 4 5 * * 2 5 1 1
4 1 2 4 5 3 4 1 1 5 * 5 4 5 1
3 1 2 5 2 1 3 5 5 2 * 2 5 5 4
4 1 2 1 4 1 2 4 4 5 * * * * 5
2 3 2 2 2 2 1 1 3 4 1 1 4 5 2
2 4 5 2 3 2 5 3 3 5 1 4 3 1 3
Cost: 108;

My prof said travelling distance consider the actual path. so this is saying manhattan distance is faster?

Member Avatar
Taywin
Posting Maven
2,632 posts since Apr 2010
Reputation Points: 134 [?]
Q&As Helped to Solve: 378 [?]
Skill Endorsements: 17 [?]
 
0
 

In your test case, yes because of heuristic. However, there could be other cases that it is slower. You may try different cases like no obstacle at all, medium amount of obstacles, and plenty of obstacles. That way, you would see it clearer. :)

You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
Tags Related to this Article