随机迷宫生成[深度/广度]

7408 · 发表于 2015-1-2 21:45:29

加入我们，或者，欢迎回来。

您需要登录才可以下载或查看，没有帐号？注册会员

x

唔我来6R好像没怎么发过东西呢只知道用别人的 ..偶尔还是来一发做做贡献吧不然觉得有点对不起大家呢OTZ
此货为迷宫生成算法，应该算是比较完善了吧
不知道有人写过没有不过由于鄙人阅读脚本的能力甚是太好，别人写的基本都看不懂OTZ Umm..所以还是自己写好了
脚本如下：

RUBY 代码复制

#==============================================================================
# ■ Random_Maze
#------------------------------------------------------------------------------   
#   使用说明书：
#     效果：生成一个随机迷宫数组。(0:地 1:墙)
#     用法：
#        广度优先 --> prim(X最大值,Y最大值,起始X[可省略],起始Y[可省略])
#        深度优先 --> depth(X最大值,Y最大值,起始X[可省略],起始Y[可省略])
#     制作：永远的塞尔达传说(7408) [2015.1.2]
#==============================================================================
class Random_Maze
  #--------------------------------------------------------------------------
  # ● 定义实例变量
  #--------------------------------------------------------------------------
  attr_reader   :pos_x                    # 当前 X 坐标
  attr_reader   :pos_y                    # 当前 Y 坐标
  attr_reader   :list                     # 可通行列表
  attr_reader   :mark                     # 标记列表
  attr_accessor :maze                     # 迷宫
  #--------------------------------------------------------------------------
  # ● 初始化对像
  #--------------------------------------------------------------------------
  def        initialize
                @maze = []
        end
  #--------------------------------------------------------------------------
  # ● 广度优先
  #--------------------------------------------------------------------------
  def prim(xmax,ymax,start_x = nil,start_y = nil)
    # 初始化
    @maze = []
    start_x = rand(xmax + 1) if start_x == nil
    start_y = rand(ymax + 1) if start_y == nil
    for x in 0..xmax
      @maze[x] = []
      for y in 0..ymax
        @maze[x][y] = 1
      end
    end
    @maze[start_x][start_y] = 0
    @list = adjacent_wall(start_x,start_y)
    # 生成迷宫
    while !@list.empty?
      id = rand(@list.size-1)
      x = @list[id][0]
      y = @list[id][1]
      d = @list[id][2]
      new_x = x + (d == 3 ? 1 : (d == 2 ? -1 : 0))
      new_y = y + (d == 1 ? 1 : (d == 4 ? -1 : 0))
      # 如果前面也为墙
      if exist?(new_x,new_y) and @maze[new_x][new_y] == 1
        @maze[x][y] = 0
        @maze[new_x][new_y] = 0
        @list = @list + adjacent_wall(new_x,new_y)
        @list.delete_at(id)
      else
        @list.delete_at(id)
      end
    end
    # 返回迷宫
    return @maze.clone
  end
  #--------------------------------------------------------------------------
  # ● 深度优先
  #--------------------------------------------------------------------------
  def depth(xmax,ymax,pos_x = nil,pos_y = nil)
    # 初始化
    @maze = []
    pos_x = rand(xmax + 1) if pos_x == nil
    pos_y = rand(ymax + 1) if pos_y == nil
    for x in 0..xmax
      @maze[x] = []
      for y in 0..ymax
        @maze[x][y] = 1
      end
    end
    @pos_x = pos_x
    @pos_y = pos_y
    @maze[pos_x][pos_y] = 0
    [url=home.php?mod=space&uid=25204]@mark[/url] = []
    # 生成迷宫
    while not_full?
      all = passage_way(@pos_x,@pos_y)
      if all.empty?
        @pos_x,@pos_y = @mark.pop
      else
        coord = all[rand(all.size) - 1]
        @maze[coord[0]][coord[1]] = 0
        @maze[coord[2]][coord[3]] = 0
        @pos_x = coord[2]
        @pos_y = coord[3]
        @mark.push([@pos_x,@pos_y])
      end
    end
    # 返回迷宫
    return @maze.clone
  end
  #--------------------------------------------------------------------------
  # ● 存在否？
  #--------------------------------------------------------------------------
  def exist?(x,y)
    return false if (x < 0) or (x >= @maze.size) or (y < 0) or (y >= @maze[0].size)
    return true
  end
  #--------------------------------------------------------------------------
  # ● 满否？
  #--------------------------------------------------------------------------
  def not_full?
    delta_x = (@pos_x % 2 == 1 ? 1 : 0)
    delta_y = (@pos_y % 2 == 1 ? 1 : 0)
    xmax = (@maze.size / 2).floor
    ymax = (@maze[0].size / 2).floor
    for x in 0...xmax
      for y in 0...ymax
        return true if @maze[x * 2 + delta_x][y * 2 + delta_y] == 1
      end
    end
    return false
  end
  #--------------------------------------------------------------------------
  # ● Mark中存在此坐标否？
  #--------------------------------------------------------------------------
  def marked_coord?(x,y)
    @mark.each do |this|
      if this[0] == x and this[1] == y
        return true
      end
    end
    return false
  end
  #--------------------------------------------------------------------------
  # ● 取得所有通路
  #--------------------------------------------------------------------------
  def passage_way(x,y)
    result = []
    # 循环四个方向
    for d in 1..4
      new_x_a = x + (d == 3 ? 1 : (d == 2 ? -1 : 0))
      new_y_a = y + (d == 1 ? 1 : (d == 4 ? -1 : 0))
      new_x_b = x + (d == 3 ? 2 : (d == 2 ? -2 : 0))
      new_y_b = y + (d == 1 ? 2 : (d == 4 ? -2 : 0))
      if exist?(new_x_b,new_y_b) and @maze[new_x_b][new_y_b] == 1 and !marked_coord?(new_x_b,new_y_b)
        result.push([new_x_a,new_y_a,new_x_b,new_y_b])
      end
    end
    return result
  end
  #--------------------------------------------------------------------------
  # ● 获取相邻的墙壁
  #--------------------------------------------------------------------------
  def adjacent_wall(x,y)
    result = []
    # 循环四个方向
    for d in 1..4
      new_x = x + (d == 3 ? 1 : (d == 2 ? -1 : 0))
      new_y = y + (d == 1 ? 1 : (d == 4 ? -1 : 0))
      if exist?(new_x,new_y) and @maze[new_x][new_y] == 1
        result.push([new_x,new_y,d])
      end
    end
    # 返回结果
    return result
  end
end

#==============================================================================


# ■ Random_Maze


#------------------------------------------------------------------------------   


#   使用说明书：


#     效果：生成一个随机迷宫数组。(0:地 1:墙)


#     用法：


#        广度优先 --> prim(X最大值,Y最大值,起始X[可省略],起始Y[可省略])


#        深度优先 --> depth(X最大值,Y最大值,起始X[可省略],起始Y[可省略])


#     制作：永远的塞尔达传说(7408) [2015.1.2]


#==============================================================================


class Random_Maze


  #--------------------------------------------------------------------------


  # ● 定义实例变量


  #--------------------------------------------------------------------------


  attr_reader   :pos_x                    # 当前 X 坐标


  attr_reader   :pos_y                    # 当前 Y 坐标


  attr_reader   :list                     # 可通行列表


  attr_reader   :mark                     # 标记列表


  attr_accessor :maze                     # 迷宫


  #--------------------------------------------------------------------------


  # ● 初始化对像


  #--------------------------------------------------------------------------


  def        initialize


                @maze = []


        end


  #--------------------------------------------------------------------------


  # ● 广度优先


  #--------------------------------------------------------------------------


  def prim(xmax,ymax,start_x = nil,start_y = nil)


    # 初始化


    @maze = []


    start_x = rand(xmax + 1) if start_x == nil


    start_y = rand(ymax + 1) if start_y == nil


    for x in 0..xmax


      @maze[x] = []


      for y in 0..ymax


        @maze[x][y] = 1


      end


    end


    @maze[start_x][start_y] = 0


    @list = adjacent_wall(start_x,start_y)


    # 生成迷宫


    while !@list.empty?


      id = rand(@list.size-1)


      x = @list[id][0]


      y = @list[id][1]


      d = @list[id][2]


      new_x = x + (d == 3 ? 1 : (d == 2 ? -1 : 0))


      new_y = y + (d == 1 ? 1 : (d == 4 ? -1 : 0))


      # 如果前面也为墙


      if exist?(new_x,new_y) and @maze[new_x][new_y] == 1


        @maze[x][y] = 0


        @maze[new_x][new_y] = 0


        @list = @list + adjacent_wall(new_x,new_y)


        @list.delete_at(id)


      else


        @list.delete_at(id)


      end


    end


    # 返回迷宫


    return @maze.clone


  end


  #--------------------------------------------------------------------------


  # ● 深度优先


  #--------------------------------------------------------------------------


  def depth(xmax,ymax,pos_x = nil,pos_y = nil)


    # 初始化


    @maze = []


    pos_x = rand(xmax + 1) if pos_x == nil


    pos_y = rand(ymax + 1) if pos_y == nil


    for x in 0..xmax


      @maze[x] = []


      for y in 0..ymax


        @maze[x][y] = 1


      end


    end


    @pos_x = pos_x


    @pos_y = pos_y


    @maze[pos_x][pos_y] = 0


    [url=home.php?mod=space&uid=25204]@mark[/url] = []


    # 生成迷宫


    while not_full?


      all = passage_way(@pos_x,@pos_y)


      if all.empty?


        @pos_x,@pos_y = @mark.pop


      else


        coord = all[rand(all.size) - 1]


        @maze[coord[0]][coord[1]] = 0


        @maze[coord[2]][coord[3]] = 0


        @pos_x = coord[2]


        @pos_y = coord[3]


        @mark.push([@pos_x,@pos_y])


      end


    end


    # 返回迷宫


    return @maze.clone


  end


  #--------------------------------------------------------------------------


  # ● 存在否？


  #--------------------------------------------------------------------------


  def exist?(x,y)


    return false if (x < 0) or (x >= @maze.size) or (y < 0) or (y >= @maze[0].size)


    return true


  end


  #--------------------------------------------------------------------------


  # ● 满否？


  #--------------------------------------------------------------------------


  def not_full?


    delta_x = (@pos_x % 2 == 1 ? 1 : 0)


    delta_y = (@pos_y % 2 == 1 ? 1 : 0)


    xmax = (@maze.size / 2).floor


    ymax = (@maze[0].size / 2).floor


    for x in 0...xmax


      for y in 0...ymax


        return true if @maze[x * 2 + delta_x][y * 2 + delta_y] == 1


      end


    end


    return false


  end


  #--------------------------------------------------------------------------


  # ● Mark中存在此坐标否？


  #--------------------------------------------------------------------------


  def marked_coord?(x,y)


    @mark.each do |this|


      if this[0] == x and this[1] == y


        return true


      end


    end


    return false


  end


  #--------------------------------------------------------------------------


  # ● 取得所有通路


  #--------------------------------------------------------------------------


  def passage_way(x,y)


    result = []


    # 循环四个方向


    for d in 1..4


      new_x_a = x + (d == 3 ? 1 : (d == 2 ? -1 : 0))


      new_y_a = y + (d == 1 ? 1 : (d == 4 ? -1 : 0))


      new_x_b = x + (d == 3 ? 2 : (d == 2 ? -2 : 0))


      new_y_b = y + (d == 1 ? 2 : (d == 4 ? -2 : 0))


      if exist?(new_x_b,new_y_b) and @maze[new_x_b][new_y_b] == 1 and !marked_coord?(new_x_b,new_y_b)


        result.push([new_x_a,new_y_a,new_x_b,new_y_b])


      end


    end


    return result


  end


  #--------------------------------------------------------------------------


  # ● 获取相邻的墙壁


  #--------------------------------------------------------------------------


  def adjacent_wall(x,y)


    result = []


    # 循环四个方向


    for d in 1..4


      new_x = x + (d == 3 ? 1 : (d == 2 ? -1 : 0))


      new_y = y + (d == 1 ? 1 : (d == 4 ? -1 : 0))


      if exist?(new_x,new_y) and @maze[new_x][new_y] == 1


        result.push([new_x,new_y,d])


      end


    end


    # 返回结果


    return result


  end


end

范例：

随机迷宫生成.rar (193.38 KB, 下载次数: 431)

具体看范例吧~嗯嗯谢谢大家

taroxd · 发表于 2015-1-3 16:39:12

本帖最后由 taroxd 于 2015-1-3 16:44 编辑

不过由于鄙人阅读脚本的能力甚是太好，别人写的基本都看不懂OTZ Umm..所以还是自己写好了

十分赞同楼主这一观点，于是我也写了一个玩了玩

果然 Ruby 写类似伪代码的东西就是舒爽

（暂时还没有定义访问方法和 each 系列的迭代方法，不过有了转成字符串的 to_s ，能输出就能凑合着玩了）

RUBY 代码复制

class Maze
 
  def initialize(xsize, ysize, ox = rand(xsize), oy = rand(ysize))
    @xsize = xsize
    @ysize = ysize
    prim(ox, oy)
  end
 
  # 生成迷宫
  def prim(ox, oy)
    init_maze
    init_list
    remove_wall(ox, oy)
    add_adjacent_wall_to_list(ox, oy)
    while (pos_data = list_sample)
      (x, y), (new_x, new_y) = pos_data
 
      if wall?(new_x, new_y)
        remove_wall(x, y)
        remove_wall(new_x, new_y)
        add_adjacent_wall_to_list(new_x, new_y)
      end
 
      remove_from_list(x, y)
    end
  end
 
  def wall?(x, y)
    exist?(x, y) && !@maze[x][y]
  end
 
  def to_s
    @xsize.times.map { |x|
      @ysize.times.map { |y| wall?(x, y) ? '●' : '○' }.join
    }.join("\n")
  end
 
  private
 
  def init_maze
    @maze = Array.new(@xsize) { Array.new(@ysize) }
  end
 
  def init_list
    @list = {}
  end
 
  def remove_wall(x, y)
    @maze[x][y] = true if exist?(x, y)
  end
 
  # 返回 [[墙X，墙Y], [前方X, 前方Y]]
  def list_sample
    @list.to_a.sample
  end
 
  def add_adjacent_wall_to_list(x, y)
    each_dx_dy do |dx, dy|
      new_x = x + dx
      new_y = y + dy
      add_to_list(new_x, new_y, new_x + dx, new_y + dy) if wall?(new_x, new_y)
    end
  end
 
  def each_dx_dy
    yield -1, 0
    yield 1, 0
    yield 0, -1
    yield 0, 1
  end
 
  def add_to_list(x, y, new_x, new_y)
    @list[[x, y]] = [new_x, new_y] if exist?(x, y)
  end
 
  def remove_from_list(x, y)
    @list.delete [x, y]
  end
 
  def exist?(x, y)
    x.between?(0, @xsize - 1) && y.between?(0, @ysize - 1)
  end
 
end
 
# puts Maze.new(15, 15)

class Maze


 


  def initialize(xsize, ysize, ox = rand(xsize), oy = rand(ysize))


    @xsize = xsize


    @ysize = ysize


    prim(ox, oy)


  end


 


  # 生成迷宫


  def prim(ox, oy)


    init_maze


    init_list


    remove_wall(ox, oy)


    add_adjacent_wall_to_list(ox, oy)


    while (pos_data = list_sample)


      (x, y), (new_x, new_y) = pos_data


 


      if wall?(new_x, new_y)


        remove_wall(x, y)


        remove_wall(new_x, new_y)


        add_adjacent_wall_to_list(new_x, new_y)


      end


 


      remove_from_list(x, y)


    end


  end


 


  def wall?(x, y)


    exist?(x, y) && !@maze[x][y]


  end


 


  def to_s


    @xsize.times.map { |x|


      @ysize.times.map { |y| wall?(x, y) ? '●' : '○' }.join


    }.join("\n")


  end


 


  private


 


  def init_maze


    @maze = Array.new(@xsize) { Array.new(@ysize) }


  end


 


  def init_list


    @list = {}


  end


 


  def remove_wall(x, y)


    @maze[x][y] = true if exist?(x, y)


  end


 


  # 返回 [[墙X，墙Y], [前方X, 前方Y]]


  def list_sample


    @list.to_a.sample


  end


 


  def add_adjacent_wall_to_list(x, y)


    each_dx_dy do |dx, dy|


      new_x = x + dx


      new_y = y + dy


      add_to_list(new_x, new_y, new_x + dx, new_y + dy) if wall?(new_x, new_y)


    end


  end


 


  def each_dx_dy


    yield -1, 0


    yield 1, 0


    yield 0, -1


    yield 0, 1


  end


 


  def add_to_list(x, y, new_x, new_y)


    @list[[x, y]] = [new_x, new_y] if exist?(x, y)


  end


 


  def remove_from_list(x, y)


    @list.delete [x, y]


  end


 


  def exist?(x, y)


    x.between?(0, @xsize - 1) && y.between?(0, @ysize - 1)


  end


 


end


 


# puts Maze.new(15, 15)

chd114 · 发表于 2015-1-3 16:58:20

随机生成的迷宫会自动保存到地图文件里吗？

欧买歌 · 发表于 2015-1-3 17:45:04

好东西啊，拥有了va的功能，收藏先

7408 · 发表于 2015-1-11 18:35:46

chd114 发表于 2015-1-3 16:58
随机生成的迷宫会自动保存到地图文件里吗？

Umm..貌似map对象访问不到来着那就酱紫直接加载吧不动默认脚本= =

RUBY 代码复制

def save_map
  map = load_data(sprintf("Data/Map%03d.rxdata", $game_map.map_id))
  map.data = $game_map.data.clone
  save_data(map,sprintf("Data/Map%03d.rxdata",$game_map.map_id))
end

def save_map


  map = load_data(sprintf("Data/Map%03d.rxdata", $game_map.map_id))


  map.data = $game_map.data.clone


  save_data(map,sprintf("Data/Map%03d.rxdata",$game_map.map_id))


end

如果要保存成新的文件大概..就必须改Mapinfo了吧毕竟编辑器就要靠它啦

帐号		自动登录	找回密码
密码			注册会员

[原创发布] 随机迷宫生成[深度/广度]

加入我们，或者，欢迎回来。

评分

点评

点评

点评

开拓者

贵宾