【CBL|pca006132】在Mc里造迷宫!随机完美迷宫生成算法 - 游戏技巧

pca006132

本帖最后由 pca006132 于 2015-8-21 22:42 编辑

在这个帖子里，我们会说一下完美迷宫生成的两个算法分别是recursive backtracker以及hunt and kill
选择这两个算法的原因是他们比较容易，而且他们生成的迷宫我最喜欢(这个生成出来的迷宫会让你走了半天才知道是死路XD)
最重要的是他们两个都非常相似，只是在遇到死路的时候解决方法有点不同而已

一个迷宫里面会有很多个"房间"，"房间"就是四面可以有墙壁的

比如这个，它是迷宫一开始的样子，每个格子都是一个"房间"，只要把那些房间连接起来，就是一个迷宫
完美迷宫就是一个迷宫，它从一个地方通往另外一个地方的道路只有一条，例子：

左边那个就是一个"深度优先"的迷宫，生成的算法是recursive backtracker
你可以看到左边的迷宫，你向着任何一边走都是比较长的路(起码比右边的长)

我们现在来讲解一下recursive backtracker的原理
先选择一个"房间"来开始(可以随机，也可以固定一个房间作开始)
然后随机选择隔壁的一个从未选择过的房间，并且把它们之间的墙壁打破不断重复以上的步骤，直到遇上死路
死路就是说，你选择到的房间旁边，不是已经选择了的房间，就是没有房间(简单来说就是旁边没有还没选择的房间)
遇到死路的时候，你就会往回跑，直到找到一个房间旁边有可以选择的房间
以下是一个例子

比如你选择的是红色那点

之后你好像红色的路径一样走，然后遇上死路(红色那点上方一格)
死路的原因就是因为旁边的格子都是已经走过的

然后你就好像那个红色的路径一样往回跑(蓝色的路径就是你之前走过的)
到了蓝色那点右边那一格的时候，你就会发现下方有一个可以选择的格子(以绿色标记的那个)

之后你就向着那个格子跑，然后继续随便乱走，遇到死路的时候就好像之前一样去解决:D (我才不会告诉你是因为我太懒才不继续举例)

以下是在MC里如何做到这个算法
首先，我们要建立两个计分板，分别叫x和count（一个用来储存房间的状态、选择次序，一个用来储存现在选择的格子附近有多少可以选择的房间）
然后，每个格子/房间都是由一个叫cell的盔甲架代表的(在这个系统里，每个房间之间的距离必须是9格，包括墙壁)然后我们随机走，走的同时把那个墙壁打破，并且把那些走过的房间顺序加入到计分板里(最大分数的就是最早的，如此类推)
如果遇到了死路，就把目前那个房间扔到不使用的分数(-1)，因为我们无论怎样退也不会退到死路里。之后就把计分板里分数大于1的全部分数-1，这样子分数=1的房间，就是上一个经过(并且不是死路)的房间。

######命令部分#####
之后，我们需要初始化迷宫(让迷宫变成

这个样子)命令：

execute @e[type=ArmorStand,name=cell] ~ ~ ~ fill ~5 ~-1 ~5 ~-5 ~2 ~-5 stone 0
execute @e[type=ArmorStand,name=cell] ~ ~ ~ fill ~4 ~ ~4 ~-4 ~2 ~-4 air 0
scoreboard players set @e[type=ArmorStand,name=cell] x 0
scoreboard players set @r[type=ArmorStand,name=cell] x 1

复制代码

首先两条命令就是让每个房间中间都会有一个墙壁分隔，以方便我们接下来的工作(这样子我们就只需要拆墙壁就可以)，并且会把中间所有障碍物移除
之后，我们需要把每个盔甲架之前的x分数重设(为什么是set 0而不是reset呢？就是因为我把分数为0的判断为还没选择过的房间)
然后随机找一个房间作开始(分数为1的就是目前选择的)

然后以下的命令会放在一个while 循环里(如果有x分数为0的盔甲架存在，它就不断执行)

scoreboard players reset * count
scoreboard players set @e[type=ArmorStand,name=cell,score_x=1,score_x_min=1] count 0

复制代码

把所有盔甲架的count分数reset(因为我们不希望有其他盔甲架有count分数)之后，我们会把x分数为1的盔甲架的count分数设置为0(如果下一步不成功，那么他最小也会有0分，不然的话就会连0分都没有)

execute @e[type=ArmorStand,name=cell,score_x=1,score_x_min=1] ~ ~ ~ execute @e[r=10,type=ArmorStand,name=cell,score_x=0,score_x_min=0] ~ ~ ~ scoreboard players add @e[type=ArmorStand,name=cell,score_x=1,score_x_min=1] count 1

复制代码

这里可能比较复杂，因为牵涉到2个execute，那个用途就是让x为1的盔甲架隔壁的还没有被选择的盔甲架(x=0)为x=1的盔甲架的count分数加分(所以count就是代表了那个盔甲架隔壁的还没有被选择的房间数量)。第一个execute的用途就是把下一个execute的r=10的圆心设置在x=1的盔甲架那里
###这里是死路处理###

scoreboard players set @e[type=ArmorStand,name=cell,score_x=1,score_x_min=1,score_count=0] x -1

复制代码

然后，如果x=1的盔甲架的count分数是0，我们就把他的x分数设置为-1(因为这个我们再也不用管了，他是一个死胡同，而且1这个分数之后需要重新分配，先设置为-1以避免之后会混乱)

execute @e[type=ArmorStand,name=cell,score_x=-1,score_x_min=-1,score_count=0] ~ ~ ~ scoreboard players remove @e[type=ArmorStand,name=cell,score_x_min=2] x 1

复制代码

之后就把所有分数大于2的盔甲架的分数-1
###死路处理完毕###(如果继续是死路的话，以下的命令执行了也是和没有执行一样，所以还是会回到上面去解决的)

execute @e[type=ArmorStand,name=cell,score_x=1,score_x_min=1,score_count_min=1] ~ ~ ~ fill ~-5 ~ ~-5 ~5 ~5 ~5 glass 0 replace stone 0

复制代码

之后，就把分数为1的盔甲架附近的墙壁换为玻璃(接下来会使用一些replace来做到移除墙壁的效果)

execute @e[score_count_min=1] ~ ~ ~ scoreboard players add @e[type=ArmorStand,name=cell,score_x_min=1] x 1

复制代码

把所有分数大于等于1的盔甲架的分数+1(现在选择了的房间的分数是2)

execute @e[type=ArmorStand,name=cell,score_x=2,score_x_min=2,score_count_min=1] ~ ~ ~ scoreboard players set @r[type=ArmorStand,name=cell,r=10,rm=1,score_x_min=0,score_x=0] x 1

复制代码

随机选择一个隔壁的还没有选择过的房间，把他的分数设置为1

execute @e[type=ArmorStand,name=cell,score_x=1,score_x_min=1] ~ ~ ~ fill ~-5 ~ ~-5 ~5 ~5 ~5 air 0 replace glass 0

复制代码

把刚才选择了的房间附近的玻璃墙壁清除(玻璃的部分就是和上一个房间的交界)

execute @e[type=ArmorStand,name=cell,score_x=2,score_x_min=2] ~ ~ ~ fill ~-5 ~ ~-5 ~5 ~5 ~5 stone 0 replace glass 0

复制代码

让上一个房间的玻璃部分变回去石头(因为我们不希望玻璃留下)

呼，真长气，关于recursive backtracker的部分已经解释完毕了，剩下的指令都是一些不是太特别的(关于循环的指令，我会在结尾解释一下)
接下来是hunt and kill
————————————————我是一条分隔线————————————————

hunt and kill其实和recursive backtracker挺接近，他们都是乱走，就是遇到死路的时候那个处理方法有点不一样
recursive backtracker遇到死路的时候，他的解决方法是往回走，可想而知，在一个很大并且完成了很大部分的迷宫里，往回走直到找到非死路的时间可能会很长，所以recursive backtracker会很慢
而hunt and kill就是遇到死路时，搜寻一个还没有选择过的房间(那个房间旁边必须有已经选择了的房间)，从那个开始(先把那个选择过的房间和没有选择过的房间连接起来)，继续乱走
以下是一个例子

比如你从红色点开始走，遇上了死路

这个时候你就会进入"hunt"的模式，去找出还没有选择过的房间(那个房间旁边必须有已经选择了的房间)，那些用绿色标记了的房间就是符合的

然后我为了方(tou)便(lan)，就不是逐行扫描，而是随机找一个符合要求的房间，把他标记

把他和旁边的一个已经选择过的房间连接

然后你就可以继续乱走，直到再遇上死路，然后就再进入hunt模式，如此类推，直到迷宫已经完全探索完

以下是在MC里如何做到这个算法
其实呢，这个大部分的地方都是和recursive backtracker一样的，只是那个遇上死路的时候的做法以及之后的有点不同，所以我只会把那个遇上死路的解决方法以及以后的指令写出来，上面的部分可以参考recursive backtracker部分
命令部分
(上一个指令:....scoreboard players add @e[type=ArmorStand,name=cell,score_x=1,score_x_min=1] count 1)

execute @e[score_count=0,score_x_min=1,score_x=1] ~ ~ ~ execute @e[type=ArmorStand,name=cell,score_x=3,score_x_min=2] ~ ~ ~ scoreboard players set @e[r=10,type=ArmorStand,name=cell,score_x=0,score_x_min=0] x -1

复制代码

这个的用途，就是让探索过(选择过)的房间把隔壁还没有选择过的房间标记出来(把x设置为-1).

execute @e[score_count=0,score_x_min=1,score_x=1] ~ ~ ~ execute @r[type=ArmorStand,score_x=-1,score_x_min=-1] ~ ~ ~ scoreboard players set @e[r=10,score_x=3,score_x_min=3,c=1] x 1

复制代码

由于上一个找到的可能不止一个，所以我们随机找一个标记了的房间(x=-1)，去标记隔壁的一个已经探索过(选择过)的房间(x设置为1)
(原因是当他选择旁边的还没选择过的房间时，他应该会选择回去上一个标记了的房间，就算不是也没有关系，因为这样也是选择了一个还没选择的房间；然而，如果我们直接选择那个上一个标记的房间，我们要把他和隔壁的已选择房间连接就比较麻烦，说到底也是我懒:D)

execute @e[score_count=0,score_x_min=1,score_x=1] ~ ~ ~ scoreboard players set @e[score_x=-1,score_x_min=-1] x 0

复制代码

把所有分数为-1的房间的分数设置为0(变回普通的还没选择的房间)

scoreboard players set @e[score_count=0,score_x_min=1,score_x=1] x 3

复制代码

把死路的分数设置为3(3在这里就是已经完成了所有操作的房间)

execute @e[type=ArmorStand,name=cell,score_x=1,score_x_min=1,score_count_min=1] ~ ~ ~ fill ~-5 ~ ~-5 ~5 ~5 ~5 glass 0 replace stone 0

复制代码

之后，就把分数为1的盔甲架附近的墙壁换为玻璃(接下来会使用一些replace来做到移除墙壁的效果)

execute @e[score_count_min=1] ~ ~ ~ scoreboard players add @e[type=ArmorStand,name=cell,score_x_min=1,score_x=2] x 1

复制代码

把所有分数大于等于1，并且分数小于等于2的盔甲架的分数+1(现在选择了的房间的分数是2，而上一个房间的分数就是3，其他的不变)

execute @e[type=ArmorStand,name=cell,score_x=2,score_x_min=2,score_count_min=1] ~ ~ ~ scoreboard players set @r[type=ArmorStand,name=cell,r=10,rm=1,score_x_min=0,score_x=0] x 1

复制代码

随机选择一个隔壁的还没有选择过的房间，把他的分数设置为1

execute @e[type=ArmorStand,name=cell,score_x=1,score_x_min=1] ~ ~ ~ fill ~-5 ~ ~-5 ~5 ~5 ~5 air 0 replace glass 0

复制代码

把刚才选择了的房间附近的玻璃墙壁清除(玻璃的部分就是和上一个房间的交界)

execute @e[type=ArmorStand,name=cell,score_x=2,score_x_min=2] ~ ~ ~ fill ~-5 ~ ~-5 ~5 ~5 ~5 stone 0 replace glass 0

复制代码

让上一个房间的玻璃部分变回去石头(因为我们不希望玻璃留下)

————————————————我是一条分隔线————————————————
这里的指令是recursive backtracker/hunt and kill循环完成之后才执行的(怎么判断循环完成呢?在这个1gt循环一次的系统里，我们可以在循环的部分里接一个红石火把，由于太快的脉冲他是不会理会的，所以在循环的时候他会是熄灭的，而在循环完成之后，那个fill的部分会变回去石头，所以他会重新亮起，从而激活接下来的指令。详见地图里的系统)

execute @e[type=ArmorStand,name=cell] ~ ~ ~ detect ~5 ~ ~ stone 0 fill ~5 ~ ~5 ~5 ~2 ~-5 stone

复制代码

(类似的指令*4)
这个指令就是用来检测4面有没有石头，有的话就把那面fill一堵墙(原因是我之前用的方法，在墙与墙中间会留下一个空隙，不美观，而且也可以算是个bug，所以就在这里去解决了他:P)

/fill 172 4 128 172 6 120 air
/fill 22 4 -20 22 6 -12 air

复制代码

这两个指令就是在迷宫里开个口(出口和入口)而已，所以那个坐标可以换成别的
——————————我是一条分隔线——————————
这里我会说说那个while循环是怎么做到的
整个系统其实只是用了3个fill
第一个fill就是

/fill 3 4 1 11 4 1 redstone_block

复制代码

其实就是用来激活整个系统的

/fill 3 4 1 11 4 1 stone

复制代码

第二个fill是放在那个循环里的，用途就是把循环重置，变成石头，以免之后不能fill红石块；顺便把开头那里重置变为石头，方便下一次使用

execute @e[type=ArmorStand,name=cell,score_x=0,score_x_min=0,c=1] ~ ~ ~ /fill 6 4 1 11 4 1 redstone_block 0

复制代码

这个就是检测有没有任何一个x为0的盔甲架(还没选择的房间)存在，有的话就循环多一次。由于这个是在循环里的，所以只要那个条件一日是满足的，他就会好像一个高频一样不断的循环
————————————————我是一条分隔线————————————————
存档:http://pan.baidu.com/s/1hqpQHyW
使用方法:迷宫入口旁边有两个命令方块和一个拉杆，把那个拉杆拉一下，就会看见两条tellraw信息，一个是用recursive backtracker来生成迷宫，一个是用hunt and kill来生成迷宫，小心的是，生成迷宫的时候会很卡(起码我是这样的)，一般来说，recursive backtracker需要的时间大约是25秒，而hunt and kill需要的时间大约是17秒。
也欢迎大家去拆系统、找bug什么的
存档就送出去了，大家慢慢玩把:D
让我厚颜无耻说一句，求人气啊QAQ

来自群组: Command Block Logic

埃克斯歪

{:10_492:}结果起了个很炫的标题~支持

风梭

没抢到沙发Orz.............前排顶帖~支持

埃克斯歪

埃克斯歪发表于 2015-8-21 22:45
结果起了个很炫的标题~支持

另外……我总是看不了你们的图{:10_514:}

plasma

原版指令做迷宫好厉害。我记得以前Mcedit也有个插件是生成迷宫的

林悦彪

有和我一样刚开始慢慢看然后就直接拉到下面来的么？

chyx

我只想知道你怎么相处这个算法的？

lzs1234

基本看懂了。
算法对于我倒是很新颖，以前都没玩过……不过大概的原理看懂了。
我去拆拆系统，找找bug吧2333333

卡狗

先拜大触！！泡茶！！太厉害了！！

pca006132

chyx 发表于 2015-8-21 23:37
我只想知道你怎么相处这个算法的？

这个嘛，其实想法很简单，就是用fill来做到while
然后用实体的分数来做到list的部分功能(就是那个recursive backtracker的)
然后其他都是很基本的东西了
至于为什么会有这个想法呢，只能说是经验/灵机一动就能想到了23333

卡狗

看完我决定下次发帖一定用伪代码

zbx1425

Randomize Prim不是很好嘛

pca006132

zbx1425 发表于 2015-8-22 20:18
Randomize Prim不是很好嘛

那个感觉比较麻烦:D
(其实是因为我一开始是弄recursive backtracker，然后看到hunt and kill是类似的而且快很多才弄，所以你可以看到两个东西都是很相似的，其他的因为太懒所以就懒得弄了233333)

kongbaiyo

不得不说太强了
编程思想引入MC

可惜一般人根本看不懂
必须要有很好的编程、命令方块和英语基础...233333333333333

1XWJ

林悦彪发表于 2015-8-21 23:19
有和我一样刚开始慢慢看然后就直接拉到下面来的么？

你这签名是像素画，绝对是像素画

1XWJ

pca006132 发表于 2015-8-22 00:01
这个嘛，其实想法很简单，就是用fill来做到while
然后用实体的分数来做到list的部分功能(就是那个recursi ...

直接用几个火焰弹生成就好了。。。

林悦彪

1XWJ 发表于 2015-8-23 11:04
你这签名是像素画，绝对是像素画

不不不，只是游戏里的，Ps也没有，图中有一个黑色羊毛地毯你找到了吗？

C-青皮君

问题的本质：
盔甲架大法好
QAQ

时间time

指令渣，看不懂QAQ

wefcewe3gwg

大神- -
拿回去慢慢研究- -

zbx1425

林悦彪发表于 2015-8-23 12:08
不不不，只是游戏里的，Ps也没有，图中有一个黑色羊毛地毯你找到了吗？

啊哈好想法，那根竖的上面铺着羊毛地毯看起来就重合了

玄素

算法大致看懂了，细节还需要再想想……
然而事实证明pca你电脑的确该换了23333并没有在生成过程中感到明显卡顿

andylizi

这，你知道WorldEdit有一个js可以一键生成迷宫么。。
太复杂了，没耐心看了。。

white_samura

好详细啊

white_samura

我看不懂

机器人WBW

看懂了可是乱走的一部分会不会有点复杂？
话说可以做个原版模组

神仙朵朵开

不错不错就是看不懂{:10_524:}

8080

还是有点看不懂

背着书包丶

佩服，我看俺不懂

Zevn

好厉害的感觉

marcong95

似乎1.9用不了的样子，入口那两个命令放开的Previous Output: Invalid json: malformed JSON at line 1 column 3

gyalo

然而我每次都看不到你们的图片！！！！