查看: 7680|回复: 4

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

[复制链接]
梦石
0
星屑
255
在线时间
509 小时
注册时间
2010-10-1
回帖
82
发表于 2015-1-2 21:45:29 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有账号?注册会员

×
唔 我来6R好像没怎么发过东西呢 只知道用别人的 ..偶尔还是来一发做做贡献吧 不然觉得有点对不起大家呢OTZ
此货为迷宫生成算法,应该算是比较完善了吧
不知道有人写过没有 不过由于鄙人阅读脚本的能力甚是太好,别人写的基本都看不懂OTZ Umm..所以还是自己写好了
脚本如下:
[pre lang="ruby" line="1"]#==============================================================================
# ■ 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
    @mark = []
    # 生成迷宫
    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[/pre]

范例: 随机迷宫生成.rar (193.38 KB, 下载次数: 425)
1.png
2.png
3.png
具体看范例吧~嗯嗯 谢谢大家

评分

参与人数 4星屑 +303 收起 理由
chd114 + 3 凑303.。。
kuerlulu + 20 好厉害的样子
taroxd + 140 好厉害的样子
恐惧剑刃 + 140 好厉害的样子

查看全部评分

…あたしは天

梦石
0
星屑
2311
在线时间
4033 小时
注册时间
2010-10-4
回帖
10548

开拓者贵宾

发表于 2015-1-3 16:39:12 | 显示全部楼层
本帖最后由 taroxd 于 2015-1-3 16:44 编辑
不过由于鄙人阅读脚本的能力甚是太好,别人写的基本都看不懂OTZ Umm..所以还是自己写好了


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

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

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

[pre lang="ruby" line="1"]

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)[/pre]

点评

..连大大都来看我,好感动的说~0 0  发表于 2015-1-3 22:21
回复

使用道具 举报

梦石
0
星屑
9292
在线时间
2504 小时
注册时间
2011-5-20
回帖
14521

开拓者

发表于 2015-1-3 16:58:20 | 显示全部楼层
随机生成的迷宫会自动保存到地图文件里吗?

点评

地图名什么的无所谓吧···主要是存一个新的地图文件···  发表于 2015-1-9 22:06
Umm..不会呢 都是临时更改 应该可以把地图直接save_data吧?而且大概..也要改下MapInfos来着  发表于 2015-1-3 22:13
[img]http://service.t.sina.com.cn/widget/qmd/5339802982/c02e16bd/7.png
回复

使用道具 举报

【欧皇】

梦石
3
星屑
2055
在线时间
1004 小时
注册时间
2013-8-19
回帖
3040

开拓者

发表于 2015-1-3 17:45:04 | 显示全部楼层
好东西啊,拥有了va的功能,收藏先

点评

VA看来很强大呢!  发表于 2015-1-5 15:01
QQ:2223942063
Q群:365819625
贪吃方1.4
回复

使用道具 举报

梦石
0
星屑
255
在线时间
509 小时
注册时间
2010-10-1
回帖
82
 楼主| 发表于 2015-1-11 18:35:46 | 显示全部楼层
chd114 发表于 2015-1-3 16:58
随机生成的迷宫会自动保存到地图文件里吗?

Umm..貌似map对象访问不到来着 那就酱紫直接加载吧 不动默认脚本= =
[pre lang="ruby" line="1"]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[/pre]
如果要保存成新的文件大概..就必须改Mapinfo了吧 毕竟编辑器就要靠它啦
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册会员

本版积分规则

Powered by Discuz! X5.0 © 2001-2026 Discuz! Team.

在本版发帖返回顶部