Scratch教程

当前位置:小码王 > 学习教程 > Scratch教程

scratch基础教程:自动生成迷宫
导读:相信大家对于迷宫来说都不陌生,南京小码王少儿编程培训机构小编在小的时候,就喜欢一个人走迷宫,每次都的时候都要走很久,一次走不通,下次就换一个,一直走通为止,现在孩子不仅可以走迷宫,还可以自己弄一个迷宫,小编也是

  相信大家对于迷宫来说都不陌生,南京小码王少儿编程培训机构小编在小的时候,就喜欢一个人走迷宫,每次都的时候都要走很久,一次走不通,下次就换一个,一直走通为止,现在孩子不仅可以走迷宫,还可以自己弄一个迷宫,小编也是非常的项目,现在我们就一起来看下今天的scratch基础教程:自动生成迷宫。

213319EN-1.jpg

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


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


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


  生成一个只有墙的迷宫

2.jpg

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

3.jpg

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

4.jpg

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


  迷宫生成算法


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

5.jpg

  算法概述:


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


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


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


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


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


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


  3)判断相对于A,在B的对侧的方块C是否为墙(假如B在A左侧,就判定A右边的方块;B在A上方,就判定A下方的方块;以此类推……),若为墙,则:


  ①将A、C均置为路。


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


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


  这段算法就是迷宫的生成算法,小编从网上找的,下面我们看看Scratch怎么做:


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


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

6.jpg

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


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


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


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

7.jpg

  第四步:


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


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


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


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


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


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

9.jpg

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

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

10.jpg

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

11.jpg

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


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


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

12.jpg

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


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


  输入标题


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


  今天南京小码王少儿编程小编带给大家的scratch基础教程:自动生成迷宫课程,小朋友要动手做一做哦,这样才能提高自己的编程水平哦,当然如果想了解关于少儿编程更多的知识,也可以和我们南京少儿编程培训机构的老师沟通下哦!