【RMVA】自动随机迷宫生成

0newing

前几天突然有了这个想法……
如果做一个类似地下城的游戏，每次进入地图随机生成一个迷宫
那如果迷宫自己画的话永远是有限的，迷宫地图如果能够随机生成就好了……
然后就做了这个…………

效果

每次进入迷宫地图，会随机生成一个迷宫……
emmmm，好像没了
用法的话，首先创建一个地图(迷宫类型)，由于算法的原因，地图的长宽必须是奇数
然后记住你地图的ID，再执行脚本MapGenerator.generate_maze("Data/MapXXX.rvdata2")，XXX就是地图的ID，这样地图文件就会刷新成随机的一个迷宫
（调用脚本时注意续行……）

脚本

[pre lang="ruby"]
#encoding:utf-8
#==============================================================================
# ■ MapGenerator
#------------------------------------------------------------------------------
# 　迷宫生成器模块
#==============================================================================
module MapGenerator
        #--------------------------------------------------------------------------
        # ● 墙的图块对应数组
        #--------------------------------------------------------------------------
        CONDITION_ARR=[3918,3914,3915,3907,3916,3904,3913,3888,3917,3908,3905,3892,3910,3896,3900,3872]
        #--------------------------------------------------------------------------
        # ● 节点类，用于明确图块位置坐标
        #--------------------------------------------------------------------------
        class Node
                def initialize(x,y)
                        @x = x
                        @y = y
                end

                def x
                        @x
                end

                def y
                        @y
                end

                def ==(node)
                        node.instance_of?(self.class) and node.x == @x and node.y == @y
                end
        end


        #--------------------------------------------------------------------------
        # ● 建造者，用于修改地图
        #--------------------------------------------------------------------------
        class Builder
                #--------------------------------------------------------------------------
                # ● 类初始化,读取地图
                #--------------------------------------------------------------------------
                def initialize(map)
                        @visited = []
                        @walls = []
                        @floor = []
                        @all_walls = []
                        for x in 0..map.xsize-1
                                for y in 0..map.ysize-1
                                        if (x%2==0) ^ (y%2==0)
                                                @walls.push(Node.new(x,y))
                                                @all_walls.push(Node.new(x,y))
                                                map[x,y,1] = 1
                                        elsif x%2==0 and y%2==0
                                                node = Node.new(x,y)
                                                @floor.push(node)
                                                map[x,y,1] = 0
                                                @visited.push(node) if x==0 and y==0
                                        else
                                                @all_walls.push(Node.new(x,y))
                                                map[x,y,1] = 1
                                        end
                                end
                        end
                end

                #--------------------------------------------------------------------------
                # ● 构建地图
                #--------------------------------------------------------------------------
                def build(map)
                        list = []
                        handle = []
                        remove = []
                        @visited.each{|v|
                        walls = get_neighbor_walls(v)
                                walls.each{|w|
                                        list.push(w) unless list.include?(w)
                                }
                        }

                        until list.empty?
                                i = rand(list.size)
                                node = list.delete_at(i)
                                handle.push(node) unless handle.include?(node)
                                neighbors = get_neighbor_floor(node)
                                remove.push(node) if need_remove(neighbors)
                                neighbors.each{|v|
                                        walls = get_neighbor_walls(v)
                                        walls.each{|w|
                                                list.push(w) unless (handle.include?(w) or list.include?(w))
                                        }
                                }
                        end
                        remove.each{|site|
                        map[site.x,site.y,1] = 0
                        }
                        map = modify_map(map,remove)
                        return map
                end

                #--------------------------------------------------------------------------
                # ● 修正地图图块(栅栏样式)
                #--------------------------------------------------------------------------
                def modify_map(map,remove)
                        @all_walls .each{|wall|
                                next if remove.include?(wall)
                                a = (map[(wall.x)-1,wall.y,1] == 0 ? 0 : 1)
                                b = (map[wall.x,(wall.y)-1,1] == 0 ? 0 : 1)
                                c = (map[(wall.x)+1,wall.y,1] == 0 ? 0 : 1)
                                d = (map[wall.x,(wall.y)+1,1] == 0 ? 0 : 1)
                                condition = (a<<3)+(b<<2)+(c<<1)+d
                                map[wall.x,wall.y,1] = CONDITION_ARR[condition]
                        }
                        return map
                end

                #--------------------------------------------------------------------------
                # ● 获取通道邻近的墙
                #--------------------------------------------------------------------------
                def get_neighbor_walls(floor)
                        result = []
                        left = Node.new(floor.x-1,floor.y)
                        up = Node.new(floor.x,floor.y+1)
                        down = Node.new(floor.x,floor.y-1)
                        right = Node.new(floor.x+1,floor.y)
                        result.push(left) if @walls.include?(left)
                        result.push(up) if @walls.include?(up)
                        result.push(down) if @walls.include?(down)
                        result.push(right) if @walls.include?(right)
                        return result
                end

                #--------------------------------------------------------------------------
                # ● 判断墙是否需要被移除
                #--------------------------------------------------------------------------
                def need_remove(neighbors)
                        flag = false
                        neighbors.each { |block|
                                flag = true unless @visited.include?(block)
                                @visited.push(block) unless @visited.include?(block)
                        }
                        return flag
                end
                #--------------------------------------------------------------------------
                # ● 获取墙邻近的通道
                #--------------------------------------------------------------------------
                def get_neighbor_floor(node)
                        neighbors = []
                        if node.x%2==0
                                floor1 = Node.new(node.x,node.y+1)
                                floor2 = Node.new(node.x,node.y-1)
                                neighbors.push(floor1) if @floor.include?(floor1)
                                neighbors.push(floor2) if @floor.include?(floor2)
                        elsif node.y%2==0
                                floor1 = Node.new(node.x+1,node.y)
                                floor2 = Node.new(node.x-1,node.y)
                                neighbors.push(floor1) if @floor.include?(floor1)
                                neighbors.push(floor2) if @floor.include?(floor2)
                        end
                        return neighbors
                end
        end

        #--------------------------------------------------------------------------
        # ● 生成地图的方法
        #--------------------------------------------------------------------------
        def self.generate_maze(data_file)
                a = load_data(data_file)
                map = a.data
                builder = Builder.new(map)
                new_map = builder.build(map)
                a.data = new_map
                save_data(a,data_file)
        end
end
[/pre]

原理解释

其实我并不是很会解释东西啦……XD
算法上利用的是Prim算法随机生成，所以在某些地方必然是墙，某些地方必然是通道
想要深究的话可以看一下代码……
根本什么都没有解释啊喂

整个的思路分为两个部分：Prim迷宫算法和数据库地图的存储方式

Prim算法

- 首先假设一个充满了墙的迷宫
- 我们要做的是打通墙，让玩家可以到达这个迷宫里所有的地面
- 做如下的一个循环
- 首先选择一个初始的地面格子，然后把它相邻的墙放入集合。为了方便,我们叫这个集合邻墙集合。
- 当邻墙集合里还有墙的时候：
  - 从邻墙集合中随机挑一个墙出来(从邻墙集合中移除)，看一看这个墙相邻的两个地面格子有没有被访问过：
    - 如果只有一边的地面被访问过：那就把这面墙打通，并把那个未访问过的地面格子标记为已访问，再把这个地面相邻的格子加入邻墙集合
    - 如果两边都被访问过了：不做操作
    - 注意：以这种处理方式，逻辑上是不存在两边都没有被访问的情况的
- 当我们处理到邻墙集合中没有墙的时候，整个迷宫也就被生成出来了

- 这个逻辑有点像什么呢……打个比方的话，就好像我们往一个初始格子中倒了很多水，水随机向一个方向去流，直到流满所有的地面……(这个比方好像毫无帮助)

- 接下来就是脚本的设计思路：首先我们需要三个集合：邻墙集合和访问过的地面集合以及需要打通的墙的集合，存储的是每个点的坐标。接下来就是按上面介绍过的算法，得出需要打通的墙的集合。
- 最后修改数据库中的地图数据，完成！

数据库地图的存储方式

- 首先地图是一个Table类，也就是一个三维数组，xyz中x和y就是坐标,z是地图的层数，对应的值就是地图上每个格子的图块索引。理解了这一点之后，修改地图就变成了修改这个三维数组。

- 问题来了，到底墙的图块索引是什么？地面的图块索引又是什么？其实这个问题我也不是很明白，只是靠输出把每个图块的索引都在控制台打印出来才知道了对应图块的索引，欢迎补充具体的图块计算方法。

- 那这里就介绍一下这个了解图块内容的方法：

- 首先在地图上画上你想要的的整个图块，记下他的x,y坐标(地图编辑器的右下角有显示)，然后在脚本里的最上面加入这段脚本：

[pre lang="ruby"]a = load_data("Data/Map002.rvdata2")        #这个改成你编辑的地图数据文件
  map = a.data
  p map[x,y,0]
  p map[x,y,1]
  p map[x,y,2]
  p map[x,y,3]        #这里的xy就是刚刚说的坐标[/pre]

- 然后运行测试(记得打开调试窗口)，然后在调试窗口里就会显示刚才的坐标的数字了(是的总共有四层)

范例附件

其实并不需要这个的对吧……
maze.zip (1.43 MB, 下载次数: 203, 售价: 2 星屑)

2019-6-1 03:09 上传

点击文件名下载附件

LigMiceMoon

很棒撒！我拿去参考一下好吗！！！感觉游戏性会提高很多！谢谢楼主！

whitedewxiao

棒呆！就是网站被拦了好几次害得下载断了好几次（划掉）
所以“对应数组”是指？

守護者誓約

看看怎么样

梦路

很有趣，感觉能用在很多地方

黑白虎

问一下，能不能参考不可思议迷宫，设定几个口子必定是门，其余是墙，楼梯随机

yanzhllwc

看起好厉害，不错不错，不过是va的

小枫爷爷

那么敌人怎么设置呢？