A*作ったよ(迷路の最短ルーと)

とても汚い感じだ。

S=<<STR
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************
STR

class Maze
  def initialize(str)
    @map = str.split("\n").map{|line| line.split(//)}
    @height = @map.length
    @width = @map.first.length
    @map.each_with_index do |xs,i|
      xs.each_with_index do |e,j|
        @start = [j,i] if e == "S" #[x,y,fs]
        @goal = [j,i] if e == "G"
      end
    end
    @assoc = {}
  end
  
  def ok?(node)
    x,y = node[0],node[1]
    return false if @map[y][x] == "*"
    x > 0 && x < @width || y > 0 && y < @height
  end

  def h(node)
    x = @goal[0] - node[0]
    y = @goal[1] - node[1]
    x*x + y*y
  end

  def show(*n)
    # sleep 0.02
    sleep 0.1
    x,y = n
    tmp = @map[y][x] 
    @map[y][x] = "&"
    dump
    @map[y][x] = tmp
  end

  def search
    @open, @close = [], []
    @open << (@start.map{|e| e} <<  h(@start))
    loop do 
      return false if @open.empty?
      n = @open.min_by{|x| x[2]} #x[2] = x.fs
      @open.delete(n)
      if n[0,2] == @goal
        return true 
      else
        @close << n
        show(*n) #if annoyed, then kill me
        x,y = n
        cands = [[x+1,y], [x-1,y], [x,y+1], [x,y-1]]
        cands = cands.select{|e|ok?(e)}
        #cost = 1 (magic number)
        cands = cands.map{|m| x,y = m; [x,y, 1 + (n[2] - h(n)) + h(m)]}
        cands.each do |m|
          x0,y0 = m[0], m[1]
          open_index = @open.find_index{|x,y| x==x0 && y==y0}
          if(open_index)
            prev_m = @open[open_index]
            if(m[2] < prev_m[2])
              @open[open_index][2] = m[2]
              @assoc[m[0,2]] = n[0,2]
            end
          end
          close_index = @close.find_index{|x,y| x==x0 && y==y0}
          if(close_index)
            prev_m = @close[close_index]
            if(m[2] < prev_m[2])
              @close.delete(prev_m)
              @open << m
              @assoc[m[0,2]] = n[0,2]
            end
          end
          if(!open_index and !close_index)
            @open << m
            @assoc[m[0,2]] = n[0,2]
          end
        end
      end
    end
  end

  def dump
    puts @map.map{|xs| xs.join("")}.join("\n")
  end
  
  def run
    search
    s = @assoc[@goal]
    loop do
      break if s == @start
      x,y = s
      @map[y][x] = "$"
      s = @assoc[s]
    end
    dump
  end
end

mz = Maze.new(S).run