置信大家都玩过迷宫的游戏，对于简略的迷宫，咱们能够一眼就看出通路，然而对于简单的迷宫，可能要认真寻找良久，甚至消耗数天，而后可能还要别离从入口和进口中间寻找能力找的到通路，甚至也可能找不到通路。

尽管走迷宫问题对于咱们人类来讲比较复杂，但对于计算机来说却是很简略的问题。为什么这样说呢，因为看似简单实则是有规可循的。

咱们能够这么做，携带一根很长的绳子，从入口登程始终走，如果有岔路口就走最右边的岔口，直到走到死胡同或者找到前途。如果是死胡同则退回上一个岔路口，咱们称之为岔口 A，

这时进入右边第二个岔口，进入第二个岔口后反复第一个岔口的步骤，直到找到前途或者死胡同退回来。当把该岔路口所有的岔口都走了一遍，还未找到前途就沿着绳子往回走，走到岔口 A 的前一个路口 B，反复下面的步骤。

不晓得你有没有发现，这其实就是一个一直递归的过程，而这正是计算机所善于的。

下面这种走迷宫的算法就是咱们常说的深度优先遍历算法，与之绝对的是广度优先遍历算法。有了实践根底，上面咱们就来试着用 程序来实现一个走迷宫的小程序。

生成迷宫

生成迷宫有很多种算法，罕用的有递归回溯法、递归宰割法和随机 Prim 算法，咱们明天是用的最初一种算法。

该算法的次要步骤如下：
1、迷宫行和列必须为奇数
2、奇数行和奇数列的交叉点为路，其余点为墙，迷宫周围全是墙
3、选定一个为路的单元格（本例选 [1,1]），而后把它的邻墙放入列表 wall
4、当列表 wall 里还有墙时：
4.1、从列表里随机选一面墙，如果这面墙分隔的两个单元格只有一个单元格被拜访过
4.1.1、那就从列表里移除这面墙，同时把墙买通
4.1.2、将单元格标记为已拜访
4.1.3、将未拜访的单元格的邻墙退出列表 wall
4.2、如果这面墙两面的单元格都曾经被拜访过，那就从列表里移除这面墙

咱们定义一个 Maze 类，用二维数组示意迷宫地图，其中 1 示意墙壁，0 示意路，而后初始化左上角为入口，右下角为进口，最初定义下方向向量。

class Maze:
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.map = [[0 if x % 2 == 1 and y % 2 == 1 else 1 for x in range(width)] for y in range(height)]
        self.map[1][0] = 0  # 入口
        self.map[height - 2][width - 1] = 0  # 进口
        self.visited = []
        # right up left down
        self.dx = [1, 0, -1, 0]
        self.dy = [0, -1, 0, 1]

接下来就是生成迷宫的主函数了。

def generate(self):
    start = [1, 1]
    self.visited.append(start)
    wall_list = self.get_neighbor_wall(start)
    while wall_list:
        wall_position = random.choice(wall_list)
        neighbor_road = self.get_neighbor_road(wall_position)
        wall_list.remove(wall_position)
        self.deal_with_not_visited(neighbor_road[0], wall_position, wall_list)
        self.deal_with_not_visited(neighbor_road[1], wall_position, wall_list)

该函数外面有两个次要函数 get_neighbor_road(point) 和 deal_with_not_visited()，前者会取得传入坐标点 point 的邻路节点，返回值是一个二维数组，后者 deal_with_not_visited() 函数解决步骤 4.1 的逻辑。

因为 Prim 随机算法是随机的从列表中的所有的单元格进行随机抉择，新退出的单元格和旧退出的单元格被选中的概率是一样的，因而其分支较多，生成的迷宫较简单，难度较大，当然看起来也更天然些。生成的迷宫。

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1]
[1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1]
[1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1]
[1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

走出迷宫

失去了迷宫的地图，接下来就依照咱们文首的思路来走迷宫即可。次要函数逻辑如下：

def dfs(self, x, y, path, visited=[]):
    # outOfIndex
    if self.is_out_of_index(x, y):
        return False

    # visited or is wall
    if [x, y] in visited or self.get_value([x, y]) == 1:
        return False

    visited.append([x, y])
    path.append([x, y])

    # end...
    if x == self.width - 2 and y == self.height - 2:
        return True

    # recursive
    for i in range(4):
        if 0 < x + self.dx[i] < self.width - 1 and 0 < y + self.dy[i] < self.height - 1 and 
                self.get_value([x + self.dx[i], y + self.dy[i]]) == 0:
            if self.dfs(x + self.dx[i], y + self.dy[i], path, visited):
                return True
            elif not self.is_out_of_index(x, y) and path[-1] != [x, y]:
                path.append([x, y])

很显著，这就是一个典型的递归程序。当该节点坐标越界、该节点被拜访过或者该节点是墙壁的时候，间接返回，因为该节点必定不是咱们要找的门路的一部分，否则就将该节点退出被拜访过的节点和门路的汇合中。

而后如果该节点是进口则示意程序执行完结，找到了通路。不然就遍历四个方向向量，将节点的邻路传入函数 dfs 持续以上步骤，直到找到前途或者程序所有节点都遍历实现。

来看看咱们 dfs 得出的门路后果：

[[0, 1], [1, 1], [2, 1], [3, 1], [4, 1], [5, 1], [6, 1], [7, 1], [8, 1], [9, 1], [9, 1], [8, 1], [7, 1], [6, 1], [5, 1], [5, 2], [5, 3], [6, 3], [7, 3], [8, 3], [9, 3], [9, 4], [9, 5], [9, 5], [9, 4], [9, 3], [8, 3], [7, 3], [7, 4], [7, 5], [7, 5], [7, 4], [7, 3], [6, 3], [5, 3], [4, 3], [3, 3], [2, 3], [1, 3], [1, 3], [2, 3], [3, 3], [3, 4], [3, 5], [2, 5], [1, 5], [1, 6], [1, 7], [1, 8], [1, 9], [1, 9], [1, 8], [1, 7], [1, 6], [1, 5], [2, 5], [3, 5], [3, 6], [3, 7], [3, 8], [3, 9], [3, 9], [3, 8], [3, 7], [3, 6], [3, 5], [3, 4], [3, 3], [4, 3], [5, 3], [5, 4], [5, 5], [5, 6], [5, 7], [6, 7], [7, 7], [8, 7], [9, 7], [9, 8], [9, 9], [10, 9]]

可视化

有了迷宫地图和通路门路，剩下的工作就是将这些坐标点渲染进去。明天咱们用的可视化库是 pyxel，这是一个用来写像素级游戏的 Python 库，

当然应用前须要先装置下这个库。

Win 用户间接用 pip install -U pyxel 命令装置即可。

Mac 用户应用以下命令装置：

brew install python3 gcc sdl2 sdl2_image gifsicle
pip3 install -U pyxel 

先来看个简略的 Demo。

class App:
    def __init__(self):
        pyxel.init(160, 120)
        self.x = 0
        pyxel.run(self.update, self.draw)

    def update(self):
        self.x = (self.x + 1) % pyxel.width

    def draw(self):
        pyxel.cls(0)
        pyxel.rect(self.x, 0, 8, 8, 9)

App()

类 App 的执行逻辑就是一直的调用 update 函数和 draw 函数，因而能够在 update 函数中更新物体的坐标，而后在 draw 函数中将图像画到屏幕即可。

如此咱们就先把迷宫画进去，而后在渲染 dfs 遍历动画。

width, height = 37, 21
my_maze = Maze(width, height)
my_maze.generate()

class App:
    def __init__(self):
        pyxel.init(width * pixel, height * pixel)
        pyxel.run(self.update, self.draw)

    def update(self):
        if pyxel.btn(pyxel.KEY_Q):
            pyxel.quit()

        if pyxel.btn(pyxel.KEY_S):
            self.death = False

    def draw(self):
        # draw maze
        for x in range(height):
            for y in range(width):
                color = road_color if my_maze.map[x][y] is 0 else wall_color
                pyxel.rect(y * pixel, x * pixel, pixel, pixel, color)
        pyxel.rect(0, pixel, pixel, pixel, start_point_color)
        pyxel.rect((width - 1) * pixel, (height - 2) * pixel, pixel, pixel, end_point_color)

App()

看起来还能够，这里的宽和高我别离用了 37 和 21 个像素格来生成，所以生成的迷宫不是很简单，如果像素点很多的话就会盘根错节了。

接下里来咱们就须要批改 update 函数和 draw 函数来渲染门路了。为了不便操作，咱们在 init 函数中新增几个属性。

self.index = 0
self.route = [] # 用于记录待渲染的门路
self.step = 1  # 步长，数值越小速度越快，1：每次一格；10：每次 1/10 格
self.color = start_point_color
self.bfs_route = my_maze.bfs_route()

其中 index 和 step 是用来管制渲染速度的，在 draw 函数中 index 每次自增 1，而后再对 step 求余数失去以后的实在下标 real_index，简言之就是 index 每减少 step，real_index 才会加一，渲染门路向前走一步。

def draw(self):
    # draw maze
    for x in range(height):
        for y in range(width):
            color = road_color if my_maze.map[x][y] is 0 else wall_color
            pyxel.rect(y * pixel, x * pixel, pixel, pixel, color)
    pyxel.rect(0, pixel, pixel, pixel, start_point_color)
    pyxel.rect((width - 1) * pixel, (height - 2) * pixel, pixel, pixel, end_point_color)

    if self.index > 0:
        # draw route
        offset = pixel / 2
        for i in range(len(self.route) - 1):
            curr = self.route[i]
            next = self.route[i + 1]
            self.color = backtrack_color if curr in self.route[:i] and next in self.route[:i] else route_color
            pyxel.line(curr[0] + offset, (curr[1] + offset), next[0] + offset, next[1] + offset, self.color)
        pyxel.circ(self.route[-1][0] + 2, self.route[-1][1] + 2, 1, head_color) 

def update(self):
    if pyxel.btn(pyxel.KEY_Q):
        pyxel.quit()

    if pyxel.btn(pyxel.KEY_S):
        self.death = False

    if not self.death:
        self.check_death()
        self.update_route()

def check_death(self):
    if self.dfs_model and len(self.route) == len(self.dfs_route) - 1:
        self.death = True
    elif not self.dfs_model and len(self.route) == len(self.bfs_route) - 1:
        self.death = True

def update_route(self):
    index = int(self.index / self.step)
    self.index += 1
    if index == len(self.route):  # move
        if self.dfs_model:
            self.route.append([pixel * self.dfs_route[index][0], pixel * self.dfs_route[index][1]])
        else:
            self.route.append([pixel * self.bfs_route[index][0], pixel * self.bfs_route[index][1]])

App()

至此，咱们残缺的从迷宫生成，到寻找门路，再到门路可视化已全副实现。间接调用主函数 App() 而后按 S 键盘开启游戏

总结

明天咱们用深度优先算法实现了迷宫的遍历，对于老手来说，递归这思路可能比拟难了解，但这才是合乎计算机思维的，随着教训的加深会了解越来越粗浅的。

其次咱们用 pyxel 库来实现门路可视化，难点在于坐标的计算更新，细节比拟多且繁琐，当然读者也能够用其余库或者间接用网页来实现也能够。