Here's my solution. The request for the unobstructed distance and then
the obstructed distance immediately suggested the A* algorithm (since
the unobstructed distance is clearly an admissible heuristic.) Though
I knew an algorithm to use, I had to look up the algorithm itself.


---[main.rb]
require 'hex_board'

# board = HexBoard.new(9, 9)
# board = HexBoard.new(9, 9) { |row,col| ((4-row).abs <= 1) && (col == 5) }
# board = HexBoard.new(9, 9) { |row,col| [row,col]==[4,4] ? true : rand(6)==0 }
board = HexBoard.new(9, 9) { |row,col| [row,col]==[4,4] ? false : rand(6)==0 }
board.draw
board.draw_map
board.draw_obstructed

---[hex_board.rb]
require 'set'
require 'hex'

class HexBoard
  def initialize(rows=9, cols=9)
    @rows, @cols = rows, cols
    @board = Array.new(@rows) do |row|
      Array.new(@cols) do |col|
        Hex.new(:obstructed => (block_given? && yield(row,col)))
      end
    end
  end

  def distance(start, goal)
    if ((start[0]-goal[0]) < 0) == ((start[1]-goal[1]) < 0)
      [(start[0]-goal[0]).abs, (start[1]-goal[1]).abs].max
    else
      (start[0]-goal[0]).abs+(start[1]-goal[1]).abs
    end
  end

  def neighbors(position)
    [
      [position[0], position[1]-1],
      [position[0]-1, position[1]-1],
      [position[0]-1, position[1]],
      [position[0], position[1]+1],
      [position[0]+1, position[1]+1],
      [position[0]+1, position[1]]
    ].delete_if {|x,y| x<0 || y <0 || x>@rows || y>@cols}
  end

  # Distance between two hexes on the board having to navigate obstructions
  # Obstructions are detected by passing the hex in question into the block
  # block will return true if the yielded hex should be counted as obstructed
  # EX: dist = obstructed_distance(a, b) { |hex| hex.obstructed? }
  def obstructed_distance(start, goal)
    return nil if (yield(@board[goal[0]][goal[1]]) ||
yield(@board[start[0]][start[1]]))
    closed_set = Set.new
    @board.size.times {|row|
      row.size.times {|col|
        if yield @board[row][col]
          closed_set << [row,col]
        end
      }
    }
    open_set = [start]
    actual_distance_to = {start=>0}
    estimated_distance_from = {start=>distance(start,goal)}
    estimated_distance_through = {start=>estimated_distance_from[start]}

    while !(open_set.empty?)
      node = open_set.first
      return actual_distance_to[node] if node == goal
      open_set.delete node
      closed_set << node
      neighbors(node).each { |neighbor|
        next if closed_set.include? neighbor
        distance_this_route = actual_distance_to[node] + 1
        this_route_good = false
        if !open_set.include?(neighbor)
          open_set << neighbor
          estimated_distance_from[neighbor] = distance(neighbor,goal)
          this_route_good = true
        elsif distance_this_route < actual_distance_to[neighbor]
          this_route_good = true
        end
        if this_route_good
          actual_distance_to[neighbor] = distance_this_route
          estimated_distance_through[neighbor] = distance_this_route +
estimated_distance_from[neighbor]
          open_set.sort! {|x,y|
estimated_distance_through[x]<=>estimated_distance_through[y]}
        end
      }
    end
    return nil
  end

  # This will print the board out to the console to let you
  # know if you're on the right track
  def draw
    @rows.times do |row|
      line = ''
      line << "#{row}:"
      (@cols - row).times {line << ' '}

      @cols.times do |col|
        line << (distance([4,4], [row,col]) || 'X').to_s
        line << ' '
      end

      puts line
    end
  end

  def draw_map
    @rows.times do |row|
      line = ''
      line << "#{row}:"
      (@cols - row).times {line << ' '}

      @cols.times do |col|
        line << (@board[row][col].obstructed? ? 'X' : 'O')
        line << ' '
      end

      puts line
    end
  end

  def draw_obstructed
    @rows.times do |row|
      line = ''
      line << "#{row}:"
      (@cols - row).times {line << ' '}

      @cols.times do |col|
        line << (obstructed_distance([4,4], [row,col]) {|hex|
hex.obstructed?} || 'X').to_s
        line << ' '
      end

      puts line
    end
  end

  def [](row)
    @board[row]
  end
end

---[hex.rb]
class Hex
  def initialize(opts={})
    @obstructed = !!opts[:obstructed]
  end

  def obstructed?
    @obstructed
  end
end