探索迷宫
探讨一个与蓬勃发展的机器人领域相关的问题：走出迷宫。如果你有一个Roomba扫地机器人，或许
能利用学到的知识对它进行重新编程。我们要解决的问题是帮助小乌龟走出虚拟的迷宫。迷宫问题源自忒修
斯大战牛头怪的古希腊神话传说。相传，在迷宫里杀死牛头怪之后，忒修斯用一个线团找到了迷宫的出口。
假设小乌龟被放置在迷宫里的某个位置，我们要做的是帮助它爬出迷宫，如图所示
为简单起见，假设迷宫被分成许多格，每一格要么是空的，要么被墙堵上。小乌龟只能沿着空的
格子爬行，如果遇墙，就必须转变方向。它需要如下的系统化过程来找到出路。
（1）从起始位置开始，寿险向北移动一格，然后在新的位置再递归地重复本过程。
（2）如果第一步往北行不通，就尝试向南移动一格，然后在递归重复本过程。
（3）如果向南也行不通，就尝试向西移动一格，然后递归地重复本过程。
（4）如果向北、向南、向西都不行，就尝试向东移动一格，然后递归地重复本过程。
（5）如果四个方向都不行，就意味着没有出路。
整个过程看上去非常简单，但是有许多细节需要讨论。假设递归过程的第一步是向北移动一格。
根据上述过程，下一步也是向北移动一格。但是，如果北面有墙，必须根据递归过程的第二步向南移
动一格。不行的是向南移动一格之后回到起点。如果继续执行该递归过程，就会又向北移动一格，然
后又退回来，从而陷入无限循环中。所以，必须通过一格策略来记住到过的地方，本例假设小乌龟一
边爬，一边丢面包屑。如果往某个方向走一格之后发现有面包屑，就知道应该退回去，然后尝试递归
过程的下一步。查看这个算法的代码时会发现，退回去就是从递归函数调用中返回。
和考察其他递归算法时一样，让我们来看看上述算法的基本情况，其中一些可以根据之前的描述
猜到。这个算法需要考虑以下4种基本情况。
（1）小乌龟遇到墙。由于格子被墙堵上，因此无法再继续探索。
（2）小乌龟遇到了已经走过的格子。在这种情况下，我们不希望它继续探索，不然会陷入循环。
（3）小乌龟找到了出口。
（4）四个方向都行不通。
为了使程序运行起来，需要通过一种方式标识迷宫。我们使用turtle模块来绘制和探索迷宫，以增
加趣味性。迷宫对象提供下列方法，可用编写搜索算法。
--init--读入一个代表迷宫数据文件，初始化迷宫的内部表示，并且找到小乌龟的起始位置。
drawMaze在屏幕上的一个窗口中绘制迷宫。
updatePosition更新迷宫的内部表示，并且修改小乌龟在迷宫中的位置。
isExit检查小乌龟的当前位置是否为迷宫的出口。
除此之外，Maze类还重载了索引运算符[ ]，以便算法访问任一格的状态。
以下代买清单展示了搜索函数searchFrom的代码。该函数接受3个参数：迷宫对象、起始行，以及
起始列。由于该函数的每一次递归调用在逻辑上都是重新开始搜索的，因此定义接受3个参数非常重要。
def searchFrom(maze, startRow, startColumn): # 从初始位置开始尝试四个方向，直到找到出路。 # 1. 遇到障碍 if maze[startRow][startColumn] == OBSTACLE: return False # 2. 发现已经探索过的路径或死胡同 if maze[startRow][startColumn] == TRIED or maze[startRow][startColumn]== DEAD_END: return False # 3. 发现出口 if maze.isExit(startRow, startColumn): maze.updatePosition(startRow, startColumn, PART_OF_PATH)#显示出口位置，注释则不显示此点 return True maze.updatePosition(startRow, startColumn, TRIED)#更新迷宫状态、设置海龟初始位置并开始尝试 # 4. 依次尝试每个方向 found = searchFrom(maze, startRow - 1, startColumn) or searchFrom(maze, startRow + 1, startColumn) or searchFrom(maze, startRow, startColumn - 1) or searchFrom(maze, startRow, startColumn + 1) if found: #找到出口 maze.updatePosition(startRow, startColumn, PART_OF_PATH)#返回其中一条正确路径 else: #4个方向均是死胡同 maze.updatePosition(startRow, startColumn, DEAD_END) return found
该函数做的第一件事就是调用updatePosition（第2行）。这样做是为了对算法进行可视化，以便我们
看到小乌龟如何在迷宫中寻找出口。接着，该函数检查前3中基本情况：是否遇到了墙（第5行）是否遇到
了已经走过的格子（第8行）是否找到了出口（第11行）如果没有一种情况符合，则继续递归搜索。
递归搜素调用了4个searchFrom。很难预测一共会进行多少个递归调用，这是因为它们都是用布尔运
算符or连接起来的。如果第一次调用searchFrom后返回Ture，那么就不必进行后续的调用。可以这样理解：
向北移动一格是离开迷宫的路径的一步。如果向北没有能够走出迷宫，那么尝试下一个递归调用，即向南移
动。如果向南失败了，就尝试向西，最后向东。如果所有的递归调用都失败了，就说明遇到了死胡同。请下
载或自己输入代码，改变4个递归调用的顺序，看看结果如何。
Maze类的方法定义，--init--方法只接受一个参数，即文件名。该文本文件包含迷宫的信息，其中+代表
墙，空格代表空格子，S代表起始位置。迷宫内部表示是一个列表，其元素也是列表。实例变量mazelist的每
一行是一个列表，其中每一格包含一个字符。其内部如下。
drawMaze方法使用以上内部表示在屏幕上绘制初始迷宫。
updatePosition方法使用相同的内部表示检查小乌龟是否遇到墙。同时，它会更改内部表示，使用.和-来分
别表示小乌龟遇到了走过的格子和死胡同。此外，updatePosition方法还使用辅助函数moveTurtle和dropBread
crumb来更新屏幕上的信息。
isExit方法检查小乌龟的当前位置是否为出口，条件是小乌龟已经爬到迷宫边缘：第0行、第0列、最后一行
或者最后一列。
import turtle # 迷宫类 class Maze(object): # 读取迷宫数据，初始化迷宫内部，并找到海龟初始位置。 def __init__(self, mazeFileName): rowsInMaze = 0 #初始化迷宫行数 columnsInMaze = 0 #初始化迷宫列数 self.mazelist = [] #初始化迷宫列表 mazeFile = open(mazeFileName, 'r') #读取迷宫文件 for line in mazeFile: #按行读取 rowList = [] #初始化行列表 col = 0 #初始化列 for ch in line[:-1]: #这样会丢失最后一列 rowList.append(ch) #添加到行列表 if ch == 'S': #S为乌龟初始位置，即迷宫起点 self.startRow = rowsInMaze #乌龟初始行 self.startCol = col #乌龟初始列 col = col + 1 #下一列 rowsInMaze = rowsInMaze + 1 #下一行 self.mazelist.append(rowList) #行列表添加到迷宫列表 columnsInMaze = len(rowList) #获取迷宫总列数 print(self.mazelist) self.rowsInMaze = rowsInMaze #设置迷宫总行数 self.columnsInMaze = columnsInMaze #设置迷宫总列数 self.xTranslate = -columnsInMaze/2 #设置迷宫左上角的初始x坐标 self.yTranslate = rowsInMaze/2 #设置迷宫左上角的初始y坐标 self.t = turtle.Turtle() #创建一个海龟对象 #给当前指示点设置样式(类似鼠标箭头)，海龟形状为参数指定的形状名，指定的形状名应存在于TurtleScreen的shape字典中。多边形的形状初始时有以下几种："arrow", "turtle", "circle", "square", "triangle", "classic"。 self.t.shape('turtle') self.wn = turtle.Screen() #创建一个能在里面作图的窗口 # 设置世界坐标系，原点在迷宫正中心。参数依次为画布左下角x轴坐标、左下角y轴坐标、右上角x轴坐标、右上角y轴坐标 self.wn.setworldcoordinates(-(columnsInMaze -1)/2 - 0.5, -(rowsInMaze - 1)/2 - 0.5, (columnsInMaze - 1)/2 + 0.5, (rowsInMaze - 1)/2 + 0.5) # 在屏幕上绘制迷宫 def drawMaze(self): self.t.speed(20) #绘图速度 for y in range(self.rowsInMaze): #按单元格依次循环迷宫 for x in range(self.columnsInMaze): if self.mazelist[y][x] == OBSTACLE: #如果迷宫列表的该位置为障碍物，则画方块 self.drawCenteredBox(x + self.xTranslate, -y + self.yTranslate, 'orange') # 画方块 def drawCenteredBox(self, x, y, color): self.t.up() #画笔抬起 self.t.goto(x - 0.5, y - 0.5) #前往参数位置，此处0.5偏移量的作用是使乌龟的探索路线在单元格的正中心位置 self.t.color(color) #方块边框为橙色 self.t.fillcolor('green') #方块内填充绿色 self.t.setheading(90) #设置海龟的朝向，标准模式：0 - 东，90 - 北，180 - 西，270 - 南。logo模式：0 - 北，90 - 东，180 - 南，270 - 西。 self.t.down() #画笔落下 self.t.begin_fill() #开始填充 for i in range(4): #画方块边框 self.t.forward(1) #前进1个单位 self.t.right(90) #右转90度 self.t.end_fill() #结束填充 # 移动海龟 def moveTurtle(self, x, y): self.t.up() #画笔抬起 # setheading()设置海龟朝向，towards()从海龟位置到由(x, y)，矢量或另一海龟位置连线的夹角。此数值依赖于海龟初始朝向，由"standard"、"world"或"logo" 模式设置所决定。 self.t.setheading(self.t.towards(x + self.xTranslate, -y + self.yTranslate)) self.t.goto(x + self.xTranslate, -y + self.yTranslate) #前往目标位置 # 画路径圆点 def dropBreadcrumb(self, color): self.t.dot(color) #dot(size=None, color)画路径圆点 # 用以更新迷宫内的状态及在窗口中改变海龟位置，行列参数为乌龟的初始坐标。 def updatePosition(self, row, col, val): self.mazelist[row][col] = val #设置该标记状态为当前单元格的值 self.moveTurtle(col, row) #移动海龟 if val == PART_OF_PATH: #其中一条成功路径的圆点的颜色 color = 'green' elif val == TRIED: #尝试用的圆点的颜色 color = 'black' elif val == DEAD_END: #死胡同用的圆点的颜色 color = 'red' self.dropBreadcrumb(color) #画路径圆点并上色 # 用以判断当前位置是否为出口。 def isExit(self, row, col): return (row == 0 or row == self.rowsInMaze - 1 or col == 0 or col == self.columnsInMaze - 1) #根据海龟位置是否在迷宫的4个边线位置判断 # 返回键对应的值，影响searchFrom()中maze[startRow][startColumn]值的获取 def __getitem__(self, key): return self.mazelist[key] if __name__ == '__main__': PART_OF_PATH = 'O' #部分路径 TRIED = '.' #尝试 OBSTACLE = '+' #障碍 DEAD_END = '-' #死胡同 myMaze = Maze('maze.txt')#实例化迷宫类，maze文件是使用“+”字符作为墙壁围出空心正方形空间，并用字母“S”来表示起始位置的迷宫文本文件。 myMaze.drawMaze() #在屏幕上绘制迷宫。 searchFrom(myMaze, myMaze.startRow, myMaze.startCol) #探索迷宫