RGSS2メモ > 格子状のルート探索メモ


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

とりまごり押して書いてみたもの。

ひどい。

class Field
  attr_reader:h
  attr_reader:w
  def initialize(w,h,fill)
    @w=w
    @h=h
    @data = [fill]*w*h
    @done = [false]*w*h
    @enter = [true]*w*w
  end
  def set(x,y,value)
    #アウトレンジなら何もしない
    if x<0 or x>=@w or y <0 or y>=@h
      return
    end
    @data[x+y*@w]=value
  end
  def get(x,y)
    @data[x+y*@w]
  end
  def done?(x,y)
    @done[x+y*@w]
  end
  def set_done(x,y)
    @done[x+y*@w]=true
  end
  def show
    @h.times do |y|
      @w.times do |x|
        printf('%4d ',(@data[x+y*@w]!=nil ? @data[x+y*@w] : 9999))
      end
      puts ''
    end
  end
  def moveable?(x,y)
    @enter[x+y*@w]
  end
  def setstone(x,y)
    @enter[x+y*@w]=false
  end
end

class Cod
  attr_reader:x
  attr_reader:y
  def initialize(x,y)
    @x=x
    @y=y
  end
end

def search(st_cod,ed_cod,field)
  dir =[[0,-1],[-1,0],[1,0],[0,1]]
  field.set(st_cod.x,st_cod.y,0)

  while field.get(ed_cod.x,ed_cod.y) == nil
    field.h.times do |y|
      field.w.times do |x|
        val = field.get(x,y)
        if val != nil and not field.done?(x,y)
          field.set_done(x,y)
          dir.each do |d|
            if not field.done?(x+d[0],y+d[1]) and field.moveable?(x+d[0],y+d[1])
              field.set(x+d[0],y+d[1],val+1)
            end
          end
        end
      end
    end
  end
  field.show
  print field.get(ed_cod.x,ed_cod.y)
end

f=Field.new(10,10,nil)
9.times do |i|
  f.setstone(3,i)
end

9.times do |i|
  f.setstone(6,9-i)
end

search(
  Cod.new(0,0),
  Cod.new(9,9),
  f)

こっちはスタック。

INF=1.0/0 

class Point
  attr_reader:x
  attr_reader:y
  def initialize(x,y)
    @x=x
    @y=y
  end
  def +(point)
    Point.new(point.x+@x,point.y+@y)
  end
  def ==(point)
    @x==point.x and @y==point.y
  end
end

class Maze
  def initialize(enter,w,h)
    @data=[INF]*w*h
    @enter=enter
    @w=w
    @h=h
  end
  def data(point)
    return @data[point.y*@w+point.x]
  end
  def set_data(point,value)
    @data[point.y*@w+point.x] = value
  end
  def enter?(point)
    return @enter[point.y+@w+point.x]
  end
  def include?(point)
    if point.x < 0 or point.x >= @w or point.y < 0 or point.y >= @h
      return false
    else
      return true
    end
  end
  def show
    puts '==show_data=='
    @h.times{|y|
      @w.times{|x|
        d = @data[y*@w+x] != INF ? @data[y*@w+x] : 99
        printf("%3d",d)
      }
      puts
    }
  end
end

def solve(maze_data,start_point,end_point)
  #幅優先。
  #次回更新はスタックを参照
  stack = []
  dir_list = [
    Point.new(0,1),Point.new(1,0),
    Point.new(-1,0),Point.new(0,-1)]
  maze_data.set_data(start_point,0)
  stack.push start_point
  
  while not stack.empty? do
    point = stack.shift
    dir_list.each do |dir|
      if maze_data.include?(point+dir) and
         maze_data.data(point+dir) > INF and #maze_data.data(point)+1にしてたが、グラフと違って上書きでコストが下がることはありえない、
          maze_data.enter?(point+dir)
        maze_data.set_data(point+dir,maze_data.data(point) + 1)
        stack.push Point.new(point.x+dir.x,point.y+dir.y)
      end
    end
    if maze_data.data(end_point) != INF
      break
    end
  end
  print stack
  return crearing(maze_data)
end

def crearing(maze_data)
  maze_data.show
end

class NonEnterArray
  def [](index)
    return true
  end
end

def test_code
  w = 20
  h = 20
  maze = Maze.new(NonEnterArray.new(),w,h)
  start_point = Point.new(4,3)
  end_point = Point.new(w-1,h-1)
  answer = 6
  solve(maze,start_point,end_point)
end

test_code

だいぶシンプルになったような気がする。