如何高效地判断地图某处能否抵达？

受pia专用ID

RUBY 代码复制

class Map
  def initialize
    @things = {}
    @width = 1
    @height = 1
  end
  attr_reader :width, :height
  def set_point(x, y, obj)
    @width = [x + 1, @width].max
    @height = [y + 1, @height].max
    @things[[x,y]] = obj
  end
  def get_point(x, y)
    return @things[[x,y]]
  end
  def passable?(x, y)
    return @things[[x,y]] == nil
  end
  def expand_from(x, y, create = false) #create是否重新生成一个区域
    @area = Map.new if create
    @area.set_point(x, y, true)
    if x > 0 #不是靠在左侧
      nx = x-1 ; ny = y
      if @area.get_point(nx, ny) == nil and @things[[nx, ny]] == nil
        expand_from(nx, ny)
      end
    end
    if x < @width - 1 #不是靠在右侧
      nx = x+1 ; ny = y
      if @area.get_point(nx, ny) == nil and @things[[nx, ny]] == nil
        expand_from(nx, ny)
      end
    end
    if y > 0 #不是靠在上侧
      nx = x ; ny = y-1
      if @area.get_point(nx, ny) == nil and @things[[nx, ny]] == nil
        expand_from(nx, ny)
      end
    end
    if y < @height - 1 #不是靠在下侧
      nx = x  ; ny = y+1
      if @area.get_point(nx, ny) == nil and @things[[nx, ny]] == nil
        expand_from(nx, ny)
      end
    end
  end
  def set_up_map(obj)#以array直接设定
    @width = obj[0].size
    @height = obj.size
    for y in 0...obj.size
      for x in 0...obj[0].size
        set_point(x, y, obj[y][x])
      end
    end
  end
  def test
    return @area
  end
  def reachable?(fx, fy, x, y)
    expand_from(fx, fy)
    if @area.get_point(x, y) == true
      return true
    else
      return false
    end
  end
end

class Map


  def initialize


    @things = {}


    @width = 1


    @height = 1


  end


  attr_reader :width, :height


  def set_point(x, y, obj)


    @width = [x + 1, @width].max


    @height = [y + 1, @height].max


    @things[[x,y]] = obj


  end


  def get_point(x, y)


    return @things[[x,y]]


  end


  def passable?(x, y)


    return @things[[x,y]] == nil


  end


  def expand_from(x, y, create = false) #create是否重新生成一个区域


    @area = Map.new if create


    @area.set_point(x, y, true)


    if x > 0 #不是靠在左侧


      nx = x-1 ; ny = y


      if @area.get_point(nx, ny) == nil and @things[[nx, ny]] == nil


        expand_from(nx, ny)


      end


    end


    if x < @width - 1 #不是靠在右侧


      nx = x+1 ; ny = y


      if @area.get_point(nx, ny) == nil and @things[[nx, ny]] == nil


        expand_from(nx, ny)


      end


    end


    if y > 0 #不是靠在上侧


      nx = x ; ny = y-1


      if @area.get_point(nx, ny) == nil and @things[[nx, ny]] == nil


        expand_from(nx, ny)


      end


    end


    if y < @height - 1 #不是靠在下侧


      nx = x  ; ny = y+1


      if @area.get_point(nx, ny) == nil and @things[[nx, ny]] == nil


        expand_from(nx, ny)


      end


    end


  end


  def set_up_map(obj)#以array直接设定


    @width = obj[0].size


    @height = obj.size


    for y in 0...obj.size


      for x in 0...obj[0].size


        set_point(x, y, obj[y][x])


      end


    end


  end


  def test


    return @area


  end


  def reachable?(fx, fy, x, y)


    expand_from(fx, fy)


    if @area.get_point(x, y) == true


      return true


    else


      return false


    end


  end


end

上面是我定义的Map类，以hash表储存。nil表示可以通过，否则不能通过。我定义了reachable?(fx, fy, x, y)，意思是判断从fx， fy点能否抵达x，y点，大概意思就是自动寻路。不过我希望找到效率更高的方案。

dant

把能走到的地方记录下来