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