本帖最后由 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的房间，就是上一个经过(并且不是死路)的房间。

######命令部分#####
之后，我们需要初始化迷宫(让迷宫变成这个样子)命令：
  1. execute @e[type=ArmorStand,name=cell] ~ ~ ~ fill ~5 ~-1 ~5 ~-5 ~2 ~-5 stone 0
  2. execute @e[type=ArmorStand,name=cell] ~ ~ ~ fill ~4 ~ ~4 ~-4 ~2 ~-4 air 0
  3. scoreboard players set @e[type=ArmorStand,name=cell] x 0
  4. scoreboard players set @r[type=ArmorStand,name=cell] x 1
复制代码
首先两条命令就是让每个房间中间都会有一个墙壁分隔，以方便我们接下来的工作(这样子我们就只需要拆墙壁就可以)，并且会把中间所有障碍物移除
之后，我们需要把每个盔甲架之前的x分数重设(为什么是set 0而不是reset呢？就是因为我把分数为0的判断为还没选择过的房间)
然后随机找一个房间作开始(分数为1的就是目前选择的)

然后以下的命令会放在一个while 循环里(如果有x分数为0的盔甲架存在，它就不断执行)
  1. scoreboard players reset * count
  2. 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分都没有)
  1. 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的盔甲架那里
###这里是死路处理###
  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以避免之后会混乱)
  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
###死路处理完毕###(如果继续是死路的话，以下的命令执行了也是和没有执行一样，所以还是会回到上面去解决的)
  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来做到移除墙壁的效果)
  1. execute @e[score_count_min=1] ~ ~ ~ scoreboard players add @e[type=ArmorStand,name=cell,score_x_min=1] x 1
复制代码
把所有分数大于等于1的盔甲架的分数+1(现在选择了的房间的分数是2)
  1. 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
  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
复制代码
把刚才选择了的房间附近的玻璃墙壁清除(玻璃的部分就是和上一个房间的交界)
  1. 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)
  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).
  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)
  1. 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(变回普通的还没选择的房间)
  1. scoreboard players set @e[score_count=0,score_x_min=1,score_x=1] x 3
复制代码
把死路的分数设置为3(3在这里就是已经完成了所有操作的房间)
  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来做到移除墙壁的效果)
  1. 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，其他的不变)
  1. 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
  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
复制代码
把刚才选择了的房间附近的玻璃墙壁清除(玻璃的部分就是和上一个房间的交界)
  1. 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的部分会变回去石头，所以他会重新亮起，从而激活接下来的指令。详见地图里的系统)

  1. execute @e[type=ArmorStand,name=cell] ~ ~ ~ detect ~5 ~ ~ stone 0 fill ~5 ~ ~5 ~5 ~2 ~-5 stone
复制代码
(类似的指令*4)
这个指令就是用来检测4面有没有石头，有的话就把那面fill一堵墙(原因是我之前用的方法，在墙与墙中间会留下一个空隙，不美观，而且也可以算是个bug，所以就在这里去解决了他:P)
  1. /fill 172 4 128 172 6 120 air
  2. /fill 22 4 -20 22 6 -12 air
复制代码
这两个指令就是在迷宫里开个口(出口和入口)而已，所以那个坐标可以换成别的
——————————我是一条分隔线——————————
这里我会说说那个while循环是怎么做到的
整个系统其实只是用了3个fill
第一个fill就是
  1. /fill 3 4 1 11 4 1 redstone_block
复制代码
其实就是用来激活整个系统的
  1. /fill 3 4 1 11 4 1 stone
复制代码
第二个fill是放在那个循环里的，用途就是把循环重置，变成石头，以免之后不能fill红石块；顺便把开头那里重置变为石头，方便下一次使用
  1. 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


[groupid=546]Command Block Logic[/groupid]