Scratch之自动走迷宫

陈新龙

如何让程序自己走迷宫是一个挺深奥的问题，涉及生成迷宫的prim算法、深度优先算法，走迷宫的广度优先算法、深度优先算法等。不过那些都有一定难度，我们还是先从最简单的一种算法开始吧，这种自动走迷宫的算法其实是把自己当成盲人走迷宫。这就是“左手法则”，这种法则只针对有墙壁且出口在墙壁上的迷宫（如果出口在大厅中心的情况就不适用了），只要顺着墙壁走，都能走出去。因为出口和入口的墙壁都是闭合曲线，所以这种“法则”在这类迷宫中是通用的。不过“左手法则”的效率太低，只适用于小范围的固定迷宫，而大范围的迷宫用这种算法会耗费大量的时间。未来我也会和大家分享“深度优先”等算法和如何自动生成随机迷宫。

最经典的“左（右）手法则”算法：在一张连通的迷宫图中我们用左右任意一只手一直摸着墙就一定可以走出这个迷宫，也称为绕墙走算法（或摸墙算法），是一种迷宫搜索的初级算法。左手法则的关键点：

1. 走到墙边

2. 监测左边是否有墙壁

3. 监测前面是否有墙壁

4. 左右转向

下面我们把左手摸墙的走法用流程图表示出来，更加方便让大家理解。

代码分析：

程序以网上找到的一个简单迷宫为背景，迷宫墙壁为黑色。圆球角色Ball走迷宫，Bell铃铛为迷宫出口。

我们需要自定义三个函数模块积木，对应左手法则的三个判断（走到墙边，判断左边是否有墙，判断前边是否有墙）。

1. 走到墙边

这个功能就是让角色一直沿着既定的方向前进，直到碰到墙壁。这里可以使用侦测中的“碰到颜色”积木来实现。

2. 判断左边是否有墙

根据流程图结合代码，要求角色每行动一步就要判断一次左边是否存在墙壁。在这个自定义函数中，我们还要定义一个“左边是否有墙”的变量，如果左边存在墙壁，就将这个变量设为1，否则这个变量值就是0（一直重复判断直到角色最终走出迷宫）。如何判断左边是否存在墙壁呢？我们可以让角色往左边移动一步，然后再侦测一下是否碰到了墙壁（在本例中，墙壁颜色是黑色的，可以使用“碰到颜色黑”作为检测条件）就可以了。当左移一步碰到墙壁，则说明左侧存在墙壁，如果没有碰到墙壁，则说明左边没有墙壁。

因为左移动作只是为了做侦测，并不能真的移过去，所以在检测完毕后还要将角色进行复位。把移动的步数退回来，转过的角度也要转回来。

3. 判断前方是否有墙

这个功能和判断左边是否有墙的方法一致，也需要添加“前边是否有墙”变量，用“碰到颜色黑”為条件。当前进一步碰到墙壁，则说明前方存在墙壁，变量值为1，如果没有碰到墙壁，则说明左边没有墙壁，变量值为0。并退回到原处。

接下来看分析主程序的代码部分，设置变量初始值为0，恢复角色初始位置，设置角色大小方向。走到墙边，然后开始进行角色移动过程的两种判断，重复执行直到角色到达终点也就是碰到Bell，结束循环。在循环的过程中先判断左边是否有墙壁，当左边没墙时向左转，且角色前进一步。这个前进移动非常重要，如果忘记写前进代码的话，会造成角色原地打转的Bug。当左边有墙时，才可以进行前方是否有墙壁的判断。如果前方存在墙壁，因为这时左边前面都有墙壁，我们只能右转，注意只是右转并没有前进。如果判断前方没有墙壁，那么此时就可以放心地前进一步。最终角色会一直沿自己左边的墙壁运动直到终点，走出迷宫。

今天用最简单的左手法则算法完成了自动走迷宫的目标，对算法有了一点最基础的了解，在未来的时间里，我也会和大家分享深度优先算法和递归的算法，更快地走出迷宫。并学会自动生成随机迷宫地图。