使用turtle模块创建迷宫并自动寻找出口

JokerShame

寻找出口的实现，主要是使用递归的方式循环执行如下探索步骤：

• 从起始位置开始，首先向北移动一格，然后在新的位置递归地执行探索步骤。
• 如果第一步向北行不通，就尝试向南移动一格，然后递归地执行探索步骤。
• 如果向南也行不通，就尝试向西移动一格，然后递归地重复执行探索步骤。
• 如果向北、向南、向西都不行，就尝试向东移动一格，然后递归地重复执行探索步骤。
• 如果4个方向都不行，就意味着没有出路。
  

以上5步就是一整套探索步骤，它随着每次移动到新的位置都会执行一遍。

一下是实现的代码：
class Maze:
    def __init__(self, mazeFileName):
        rowsInMaze = 0
        self.mazelist = []
        mazeFile = open(mazeFileName, 'r')
        for line in mazeFile:
            rowList = []
            columnsInMaze = 0
            for ch in line:
                rowList.append(ch)
                if ch == 'S':
                    self.startRow = rowsInMaze
                    self.startCol = columnsInMaze
                columnsInMaze += 1
            rowsInMaze += 1
            self.mazelist.append(rowList)
        self.rowsInMaze = rowsInMaze
        self.columsnInMaze = columnsInMaze
        self.xTranslate = -columnsInMaze / 2
        self.yTranslate = rowsInMaze / 2
        self.t = Turtle(shape='turtle')
        setup(width=600, height=600)
        setworldcoordinates((-columnsInMaze-1) / 2 - .5,
                            -(rowsInMaze-1) / 2 - .5,
                            (columnsInMaze-1) / 2 + .5,
                            (rowsInMaze-1) / 2 + .5)

    def drawMaze(self):
        for y in range(self.rowsInMaze):
            for x in range(self.columsnInMaze):
                if self.mazelist[y][x] == OBSTACLE:
                    self.drawCenteredBox(x + self.xTranslate,
                                         -y + self.yTranslate,
                                         'tan')
        self.t.color('black', 'blue')

    def drawCenteredBox(self, x, y, color):
        tracer(0)
        self.t.up()
        self.t.goto(x - .5, y - .5)
        self.t.color('black', color)
        self.t.setheading(90)
        self.t.down()
        self.t.begin_fill()
        for i in range(4):
            self.t.forward(1)
            self.t.right(90)
        self.t.end_fill()
        update()
        tracer(1)

    def moveTurtle(self, x, y):
        self.t.up()
        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)

    def updatePosition(self, row, col, val=None):
        if val:
            self.mazelist[row][col] = val
        self.moveTurtle(col, row)

        if val == PART_OF_PATH:
            color = 'green'
        elif val == OBSTACLE:
            color = 'red'
        elif val == TRIED:
            color = 'black'
        elif val == DEAD_END:
            color = 'red'
        else:
            color = None

        if color:
            self.dropBreadcrumb(color)

    def isExit(self, row, col):
        return (row == 0 or
                row == self.rowsInMaze or
                col == 0 or
                col == self.columsnInMaze)

    def __getitem__(self, idx):
        return self.mazelist[idx]


def searchFrom(maze, startRow, startColumn):
    maze.updatePosition(startRow, startColumn)
    if maze[startRow][startColumn] == OBSTACLE:
        return False
    if maze[startRow][startColumn] == TRIED:
        return False
    if maze.isExit(startRow, startColumn):
        maze.updatePosition(startRow, startColumn, PART_OF_PATH)
        return True
    maze.updatePosition(startRow, startColumn, TRIED)

    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:
        maze.updatePosition(startRow, startColumn, DEAD_END)
    return found


if __name__ == '__main__':
    from turtle import *

    PART_OF_PATH = '·'
    OBSTACLE = '0'
    TRIED = '*'
    DEAD_END = '#'
    maze = Maze('test.txt')
    maze.drawMaze()
    searchFrom(maze, maze.startRow, maze.startCol)


在这里，test.txt是同目录下传给Maze类的地图文件，里面的内容比如可以写为如下样子：
00000000
00S 0000
000 0000
000      0
000 0000
000 0000
00000000
00000000
（注：这里第四行特意在结尾多写一个0）

代码执行的样式截图如下：