CODEWITHSUNDEEP
distancepath-findingshortest-patha-starheuristics
Zik
Zik

Reputation: 1576

A* manhattan distance

I searched for the algorithm/pseudocode of A* I followed it and coded it. I used Manhattan distance for h(n). ( f(n) = g(n) + h(n) ) And this is the result,


(source: uploadir.com)

This always happen when there are no walls blocking the way, but when I put a lot of walls, it seems that it's taking the shortest path. Is this one the shortest path? I mean why is it not like this one below?
(source: uploadir.com)

This one is also A* Manhattan, and they have the same size (19x19). This is from http://qiao.github.com/PathFinding.js/visual/

Upvotes: 6

Views: 21027

Answers (3)

D.R.Bendanillo
D.R.Bendanillo

Reputation: 307

You need to cast a line of sight (pythagorean/euclidean) from starting point to every point(of the manhattan/A* result) until finish. If casting a line to a certain point is blocked/hidden by the obstacle, you use the previous point casted and start casting another line from that blocked point then forward until finish. A Blocked point is when a point is hidden by the line-of-sight of the initial point of the segment/line. So It's like:

First Line: Start--------->S+N(before blocked point)

Second/Middle Line/s:Blocked Point---------->S+N(before another blocked point) repeat again(new line/segment) until it established a line-of-sight to the goal.

Last Line:Blocked Point------------->Goal

Connect all lines and you've got a much shorter shortest path. You can execute again, but in reverse to add another accuracy so the line of sight will begin at the goal until start.

Upvotes: 0

nhkode
nhkode

Reputation: 1414

With the manhattan distance the first one is a shortest path. It simply counts the number of horizontal and vertical steps taken. If you want something that looks more like a shortest path in the euclidian distance you can try changing your algorithm so that when it has the choice to move horizontally or vertically at one point it chooses the horizontal one if the horizontal distance is bigger than the vertical one and vice versa.

Upvotes: 0

gexicide
gexicide

Reputation: 40058

Both paths have the same manhattan distance. Therefore, it is implementation dependant which path is chosen. To tell why this specific part was chosen, we would have to look at the code of this specific A* implementation.

Hint: Every path from a source to a target cell that uses only Von Neumann neighborhood(i.e., does not walk diagonally) and does not take a step into the "wrong" direction (i.e., never walks up or left in your example) has the same manhattan distance. So, if you are in New York, it doesn't matter which crossroads you take to reach a certain place in Manhattan :)

Upvotes: 5

Related Questions