Manhattan vs travelling distance

[drogba123]

Hi,

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

Regards,
Anthony

[Taywin]

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.

[drogba123]

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));

[Taywin]

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.

[drogba123]

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)

[Taywin]

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.

[drogba123]

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

[drogba123]

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?

[Taywin]

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. :)