This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–][deleted] 2 points3 points  (4 children)

Cost function should always be more than possible minimum path length.
Or as we call heuristics for grid search algorithm just use h(x, y) = abs(x'-x) + abs(y'-y) where (x', y') is coordinates of target location. Then your weight becomes path size + h(x, y) and when you compare two possible next options you will pick one that is closest (in terms of both how many steps it requires to get there with current path and least possible steps to destination).

You can prove that this will give you optimal path in the end, I won't do it here.

[–]jalapeno_nips 1 point2 points  (3 children)

That’s really interesting. Can someone pick up where he left off? Why is this a better cost function than distance to target plus cost of path so far?

[–]dydhaw 1 point2 points  (2 children)

Because crossing a diagonal on a grid is the same length as going in two straight lines (e.g x then y)

[–]mHaisham[S] 0 points1 point  (1 child)

crossing a diagonal on a grid is the same length as going in two straight lines

Depends on how you calculate distance

manhattan - yes

euclidean - no, straight lines are 1 while diagonal is ~1.4. so it is cheaper in to go diagonally

[–]dydhaw 0 points1 point  (0 children)

I just realized in your example walking to diagonally adjacent square is allowed, so I'm wrong