Scratch第五十三讲：自动生成迷宫

想免费学编程，就请点击上面的蓝字：跟我学Scratch编程，关注CC哥。

翻一下CC哥做的教学帖子，应该是自动走迷宫这个帖子最受欢迎。不过这个游戏里的迷宫是CC哥在网上下的。当时就想应该自己做个自动生成迷宫的程序，只是一直没动手，这星期终于把这个程序给做出来了，分享给大家。下一讲我们再做如何用新的算法自动走迷宫。

是不是很没有动画效果，CC哥特意在做的时候把刷屏给关了，所以看着就是秒成地图了。

红色的方块表示起点。终点我们可以假设在右下角。

自动画迷宫最关键的就是算法，CC哥用的是Prim算法做的迷宫算法，这种算法画出来的迷宫更适合游戏使用。

在这个游戏里我们把绿色当成路，把浅红色当成墙。也就是一个角色的两种造型。我还是喜欢用克隆做，而不是用画图的形式去做。其实区别不大，因为所有的计算都是通过算法完成的，角色之间没什么互动，我们可以根据算法计算出来的迷宫结果，用克隆去画这个迷宫，也可以用图章去画。每个人习惯不同。

让我们看看程序怎么做的吧：

生成一个只有墙的迷宫

这个简单，代码也不用讲了，大家把位置和坐标只要确定好，画得漂亮一些就行。在克隆的时候要注意，我引入了一个编号的私有变量，也就是要标明每一个克隆体的编号。确保后面的行动能找到对应的克隆体。我之所以用自定义命令去生成方阵，主要的目的还是不想有刷屏效果，这样方阵可以秒成。这个技巧前面的帖子里反复都讲过，就不重复了。

另外我还引入了一个列表，标明每一个克隆体的状态，是墙还是路，列表的顺序号对应的就是克隆体的编号，列表的内容对应的是墙还是路，墙为零，路为1。

全部都是墙，所以都是零。

迷宫生成算法

下面就是本次讲座的关键部分，就是迷宫的算法。CC哥另外导入一个角色，用来做算法的程序，没有放到迷宫方块的角色里。

算法概述：

1.建立两个数组，一个是用于存储地图的二维数组α，另一个是用于存储待处理的墙的数组β。

2.将α的所有方格全部初始化为墙。

      3.选定起点，并将该位置的墙变为路，将其四周的四块置入β数组中（出界的直接筛掉，就不说了）。

4.当β数组不为空时，循环以下步骤

1）从β数组中随机选择一块，暂且叫他A。

2）遍历该方块四周，并选定其中的某一块为路的方块，暂且叫他B。

3）判断相对于A，在B的对侧的方块C是否为墙（假如B在A左侧，就判定A右边的方块；B在A上方，就判定A下方的方块；以此类推……），若为墙，则：

        ①将A、C均置为路。

        ②将C周围是墙的所有方块，均置入β数组中。

 4）将A从β数组中去掉。

这段算法就是迷宫的生成算法，CC哥从网上找的，下面我们看看Scratch怎么做：

1和2步刚才基本上已经做了，我们设置了一个列表，用来存储迷宫地图上所有的方块，另外我也把这个列表里的每一个变量设置成零，代表全部初始化成墙。同时另外再建临时待处理的墙的列表。

所以关键是第三步和第四步：

第三步：选定起点，起点我们定为第一个方块，然后把周边的方块放到待处理的墙列表中。

这里面有一个自定义的命令，“返回周边情况”，这个命令是用来检测指定的方块周边的路和墙的状况。会将周边的墙和路分别放到两个临时的列表中：“周边墙”和“周边路”这两个列表。

我们把第一个方块进行检测，然后把返回都周边墙的数据填入到待处理墙列表中。

（这个返回周边情况的代码有点长，主要是要测试上下左右的四个方块是路还是墙，同时还要对方块的位置进行判断，处理好当方块位于边界的情况。代码并不复杂，就是找到四边的方块的编号，然后去全路径状态列表里读取这个方块是墙还是路，分别放到不同的列表里。）

第四步：

接下来就是做算法中的第四步，也是关键的一步：

为了跟算法描述对应，我也用了ABC三个变量来对应算法描述，方便大家阅读代码。

1：先从待处理的墙列表中随机抽取一个数据，也就是随机选一个方块A。

2：对这个方块的四周进行检测，返回这个方块周边为路的列表。

3：从方块A周边路的列表中随机选择一个路的方块定义为B。

4：然后根据算法描述，找到C的位置，判断C是否为墙，如果为墙，就把他四周的所有的墙都放到待处理的墙列表中去，同时把A和C都设置成路。如果不是就什么也不做。

为了找C的位置，我单独做了一条命令，代码有点长，其实就是判断A和B的位置的特殊情况，比如B在A的左边，而又A在最后面一列，那就没有C了。

（有点长就不全部截屏了）

找到C的位置后，我又做了一条自定义的命令来处理剩下的操作。

5：处理完了C，然后就把A从待处理列表中删除掉。

重复这5步过程，直到待处理的列表中没有数据，那么迷宫就生成完毕了。

通过迷宫算法，最后的全路径状态列表中就有了整个迷宫的数据，每一个方块应该是路还是墙都清清楚楚。随后，我们只需要发一条消息刷新一下克隆体的状态，让克隆体的造型跟我们的迷宫列表一一对应就好了。

（当然，这部分代码是在迷宫方块的角色里，用消息来控制克隆体真是一个方便的方法。）

今天的程序相对来说不复杂，关键是让大家知道有这么一套自动生成迷宫的算法，用这个方法可以自由的生成各种难度的迷宫，是不是很有意思。

输入标题

上次做自动走迷宫其实没什么算法，就是一直沿着左边走的瞎子走法，CC哥一直想做睁着眼睛的走法，也就是用算法来尽量很快的走出迷宫。那么下一讲CC哥就跟大家试试用递归回溯的方法来快速睁着眼睛走出迷宫。

声明：本文章由网友投稿作为教育分享用途，如有侵权原作者可通过邮件及时和我们联系删除