"Glen F. Pankow" <Glen.F.Pankow / noaa.gov> writes:

> #! /usr/bin/env ruby
> #
> # quiz-98  --  demonstrate the A* search algorithm on a simple map.
> #
> # Glen Pankow       10/15/06        1.1     Original version.
> #
> # Licensed under the Ruby License.
> #

As with most other solutions posted so far, this solution fails on
this simple map: (which is covered in my test scenario)

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

It goes over the mountain.  The culprit is the manhattan distance,
which overestimates the distance to the goal (since diagonal moves are
allowed).  A* only works with an underestimate.

-- 
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]