Hatena::Grouprubyist

Rubyで遊ぶよ

 | 

2010-01-15

話題のA*とかいうやつ

07:03

A* - Wikipedia を1回読んでから書たけど、この部分は自分の方法とは違った。

  • m の状態に応じて以下の操作を行う
    • m が Openリストにも Closeリストにも含まれていない場合 f*(m) = f '(m) とし m を Openリストに追加する。このとき m の親を n として記録する。
    • m が Openリストにある場合、f '(m) < f*(m) であるなら f*(m) = f '(m) に置き換える。このとき記録してある m の親を n に置き換える。
    • m が Closeリストにある場合、f '(m) < f*(m) であるなら f*(m) = f '(m) として m を Openリストに移動する。また記録してある m の親をn に置き換える。

たぶん自分のやつのほうがメモリを食う気がする。

#!/usr/bin/ruby

class Node
  attr_accessor :x, :y
  attr_accessor :prev
  attr_accessor :accum_cost

  def initialize(x,y,prev)
    @x = x
    @y = y
    @prev = prev || nil
    @accum_cost = prev ? prev.accum_cost + 1 : 0
  end

  def coord
    return [x,y].join(',')
  end
end

class A_star
  def initialize(maze)
    @maze = maze
    start = find_start()
    @open_list = { start.coord => start }
    @closed_list = {}
  end

  def find_start()
    @maze.each_with_index do |row,i|
      j = row.index('S')
      return Node.new(j,i,nil) if j
    end
  end

  def goal?(node)
    return @maze[node.y][node.x] == 'G'
  end

  def movable?(node)
    return @maze[node.y][node.x] != '*'
  end

  def forward(current)
    x = current.x
    y = current.y
    [[1,0],[-1,0],[0,1],[0,-1]].each{|d|
      dx, dy = *d
      next_node = Node.new(x+dx, y+dy, current)
      return next_node if goal?(next_node)
      if movable?(next_node)
        coord = next_node.coord
        next if @closed_list[coord]
        pending = @open_list[coord]
        @open_list[coord] = next_node if !pending || pending.accum_cost > next_node.accum_cost
      end
    }
    @open_list.delete(current.coord)
    @closed_list[ current.coord ] = current
    return nil
  end

  def get_closest()
    next_node = @open_list.first[1]
    @open_list.each_value {|node|
      next_node = node if node.accum_cost < next_node.accum_cost
    }
    return next_node
  end

  def show_result(goal)
    maze = @maze.dup()
    current = goal.prev # no need to mark goal
    while(current)
      maze[current.y][current.x] = '$' if current.prev # no need to mark start
      current = current.prev
    end
    puts maze.map{|row| row.join('')}.join("\n")
  end

  def solve()
    i = 0
    while(true)
      current = get_closest()
      #p [i += 1, current.accum_cost] 
      goal = forward(current)
      return show_result(goal) if goal
    end
  end
end

if $0 == __FILE__
  maze = <<-END.chop.split("\n").map{|row| row.split("")}
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************
  END

  A_star.new(maze).solve()
end

そのあとで↓ ku-ma-me さんのやつを見てちびりそうになった。何やってんのかまったくわからない。。


追記

A* で問いたように思ったけど、もしかしたら↓の部分を激しく読み間違えてたのかも…

  • Openリストに格納されているノードの内、最小の f*(n) を持つノード n を取り出す。

自分のだとむしろダイクストラ法になるっぽい?

トラックバック - http://rubyist.g.hatena.ne.jp/edvakf/20100115
 |