Ruby Quiz <james / grayproductions.net> writes:

> Step 3:  Determine the distance from the choice tiles to the goal and add that
> to the cost from Step 2 to find the score for each tile.
>
> You can calculate the distance from the tile to the goal using Manhattan
> distance formula |x1 - x2| + |y1 - y2|.  For our example that is:

No you can't.  A* works IF AND ONLY IF the estimation function is
guaranteed to be less than or equal to the true cost of following a
particular choice.  In this quiz, the estimation function we're using
is basically to use what the cost would be if we could travel the rest
of the way on the best terrain possible.  Since the easiest terrain
has a cost of 1, this is just the distance.

This would be fine, except that since apparently in this game you can
travel by diagonal moves, the distance used CAN'T be the manhattan
distance, but rather
max(|x1 - x2|, |y1 - y2|)

As a simple example where using the manhattan distance leads one
astray, consider this:

..*..
..~..
@.^.X

Now, clearly the best path is:

..#..
.#~#.
#.^.#

Since it costs less to move through a forest than a mountain, and it's
the same number of steps either way.  However, if you use Manhattan
distance, the mountain appears more attractive because it appears that
the forest is 4 steps away from the goal (when in reality it's only
two away, just as the mountain is).

--
s=%q(  Daniel Martin -- martin / snowplow.org
puts "s=%q(#{s})",s.map{|i|i}[1]       )
puts "s=%q(#{s})",s.map{|i|i}[1]