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

admin 发表于 2019-07-02 21:33


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

翻一下CC哥做的教学帖子,应该是自动走迷宫这个帖子最受欢迎。不过这个游戏里的迷宫是CC哥在网上下的。当时就想应该自己做个自动生成迷宫的程序,只是一直没动手,这星期终于把这个程序给做出来了,分享给大家。下一讲我们再做如何用新的算法自动走迷宫。https://res.wx.qq.com/mpres/htmledition/images/icon/common/emotion_panel/smiley/smiley_13.png

https://www.china-scratch.com/Uploads/timg/190702/213319EN-1.jpg

是不是很没有动画效果https://res.wx.qq.com/mpres/htmledition/images/icon/common/emotion_panel/smiley/smiley_6.pnghttps://res.wx.qq.com/mpres/htmledition/images/icon/common/emotion_panel/smiley/smiley_6.png,CC哥特意在做的时候把刷屏给关了,所以看着就是秒成地图了。

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

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

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

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

生成一个只有墙的迷宫

https://www.china-scratch.com/Uploads/timg/190702/2133235058-4.jpg

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

https://www.china-scratch.com/Uploads/timg/190702/2133232Y2-5.jpg

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

https://www.china-scratch.com/Uploads/timg/190702/2133235554-6.jpg

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

迷宫生成算法

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

https://www.china-scratch.com/Uploads/timg/190702/2133233553-7.jpg


算法概述:

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

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

https://www.china-scratch.com/Uploads/timg/190702/2133233502-8.jpg

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

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

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

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

https://www.china-scratch.com/Uploads/timg/190702/2133244633-9.jpg

https://www.china-scratch.com/Uploads/timg/190702/2133242606-10.jpg

第四步:

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

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

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

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

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

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

https://www.china-scratch.com/Uploads/timg/190702/2133251503-11.jpg

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

https://www.china-scratch.com/Uploads/timg/190702/2133255063-12.jpg

(有点长就不全部截屏了)

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

https://www.china-scratch.com/Uploads/timg/190702/21332521K-13.jpg

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

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

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

https://www.china-scratch.com/Uploads/timg/190702/213325N33-14.jpg

(当然,这部分代码是在迷宫方块的角色里,用消息来控制克隆体真是一个方便的方法。https://res.wx.qq.com/mpres/htmledition/images/icon/common/emotion_panel/smiley/smiley_13.png

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

输入标题

上次做自动走迷宫其实没什么算法,就是一直沿着左边走的瞎子走法,CC哥一直想做睁着眼睛的走法,也就是用算法来尽量很快的走出迷宫。那么下一讲CC哥就跟大家试试用递归回溯的方法来快速睁着眼睛走出迷宫。https://res.wx.qq.com/mpres/htmledition/images/icon/common/emotion_panel/smiley/smiley_13.png


后记,小编朋友研发了一个游戏化的少儿编程在线课程(5-12岁),游戏化教学结合scratch(一款在线少儿编程工具,类似乐高的积木拼搭),我家娃娃学了几次课,非常喜欢(超预期),16次课才200多块钱,对锻炼孩子的思维能力和动手动力很有帮助。

感兴趣的朋友可以扫描二维码,关注一下,或微信搜索“大耳猴少儿编程”

https://www.china-scratch.com/Uploads/Editor/2018-04-22/5adca08bdc212.jpg