前言

最近学习了随机生成迷宫的算法，分享学习经验以及碰到的问题点。目前学习两个算法生成随机地图，深度优先算法和广度优先算法来生成迷宫。比较下他们的不同点。

在程序中，我们用数组M表示所有的单元格子的属性，并用turtle 库来画图。用红色单元格来表示当前遍历到单元格。

一、什么是（DFS）深度优先算法？

简单来说它是一头扎到底的玩法。我们选择一条支路，尽可能不断地深入，如果遇到死路就往回退，回退过程中如果遇到没探索过的支路，就进入该支路继续深入。如此循环反复直到把所有的单元格都遍历了。

深度优先算法实现步骤

1.引入库

代码如下：

import random
import numpy as np
from turtle import *
import time

2.初始化参数

代码如下：

#初始化参数
num_rows = 20 # 生成迷宫的行数
num_cols = 20 # 生成迷宫的列数M = np.zeros((num_rows, num_cols, 5), dtype=np.uint8)
# 阵列M将保存每个单元的阵列信息。
# 前四个坐标告诉墙壁在那些边上是否存在
# 和第五个指示在搜索中是否已访问该单元格。
# M【上，右，下，左，是否被访问】# 我们先把第一个单元格最和后一个墙打开。
M[0, 0, 0] = 1
M[num_rows-1, num_cols-1, 2] = 1#如下是turtle模块的初始化
tracer(0)# 最快生成图
ht()# 隐藏画笔
pensize(1)#画笔大小设为1

3.Turtle画方格函数

代码如下：

def pengoto(x, y):up()goto(x, y)down()def drawing(r, c, M):x = 20*c-200y = 200-20*rpengoto(x, y)for i in range(4):if M[i] == 1:pencolor('blue')fd(1)pencolor('white')fd(19)right(90)else:pencolor('blue')fd(20)right(90)

4.开始生成数组并调用Turtle画图

# 设置开始的行和列
r = 0
c = 0
history = [(r, c)]  # 这个是历史访问的单元格列表。
n = 0  # 砸墙的数量。
# 从初始单元个一路开墙并进入下一个单元格，如果无路可走则返回。
# 我们使用while循环来执行此操作，重复该循环直到n=所有的单元格数-1.说明所有的单元格都是通的了。
while history:M[r, c, 4] = 1  #将此位置指定为已访问#检查相邻单元格是否可移动去，注意上下左右的边界。 check = []if c > 0 and M[r, c-1, 4] == 0:check.append('L')if r > 0 and M[r-1, c, 4] == 0:check.append('U')if c < num_cols-1 and M[r, c+1, 4] == 0:check.append('R')if r < num_rows-1 and M[r+1, c, 4] == 0:check.append('D')if len(check): #如果有单元可以去history.append([r, c])n += 1move = random.choice(check)#随机打开一堵墙# 注意数组[上, 右，下，左，1]if move == 'L':  M[r, c, 3] = 1c = c-1M[r, c, 1] = 1if move == 'U':M[r, c, 0] = 1r = r-1M[r, c, 2] = 1if move == 'R':M[r, c, 1] = 1c = c+1M[r, c, 3] = 1if move == 'D':M[r, c, 2] = 1r = r+1M[r, c, 0] = 1else:  #如果发现没有下个单元格可以去，我们要回溯。r, c = history.pop()# 红色显示当前单元格子clear()#清理下，不然内存会被占用fillcolor("red")begin_fill()drawing(r, c, M[r, c])end_fill()# 调用turtle画图显示当前整个地图状态。for i in range(num_rows): for j in range(num_cols):drawing(i, j, M[i, j])update()#更新下，不然turtle会卡死time.sleep(0.5)if n == num_cols*num_rows-1:  # 当砸墙的数量等于单元格子的数量-1时结束循环。breakdone()

二、什么是（BFS）广度优先算法？

广度优先搜索是按层来处理顶点，距离开始点最近的那些顶点首先被访问，而最远的那些顶点则最后被访问，这个和树的层序变量很像，BFS的代码使用了一个队列。Prim

广度优先算法实现步骤

1.引入库

代码如下：

import random
import numpy as np
from turtle import *
import timet

2.初始化参数

代码如下：

#初始化参数
num_rows = 20 # 生成迷宫的行数
num_cols = 20 # 生成迷宫的列数M = np.zeros((num_rows, num_cols, 5), dtype=np.uint8)
# 阵列M将保存每个单元的阵列信息。
# 前四个坐标告诉墙壁在那些边上是否存在
# 和第五个指示在搜索中是否已访问该单元格。
# M【上，右，下，左，是否被访问】# 我们先把第一个单元格最和后一个墙打开。
M[0, 0, 0] = 1
M[num_rows-1, num_cols-1, 2] = 1#如下是turtle模块的初始化
tracer(0)# 最快生成图
ht()# 隐藏画笔
pensize(1)#画笔大小设为1

3.Turtle画方格函数

代码如下：

def pengoto(x, y):up()goto(x, y)down()def drawing(r, c, M):x = 20*c-200y = 200-20*rpengoto(x, y)for i in range(4):if M[i] == 1:pencolor('blue')fd(1)pencolor('white')fd(19)right(90)else:pencolor('blue')fd(20)right(90)

4.开始生成数组并调用Turtle画图

# 设置开始的行和列
r = 0
c = 0
history = [(r, c)]  # 这个是历史访问的单元格列表。
n = 0  # 砸墙的数量。
while history:# 随机选择一个可以敲墙的单元格r, c = random.choice(history)M[r, c, 4] = 1  # 把单元设成以访问history.remove((r, c))check = []
#如果随机选择的单元格具有多个边
#将其连接到现有的迷宫，if c > 0:if M[r, c-1, 4] == 1:check.append('L')elif M[r, c-1, 4] == 0:history.append((r, c-1))M[r, c-1, 4] = 2if r > 0:if M[r-1, c, 4] == 1:check.append('U')elif M[r-1, c, 4] == 0:history.append((r-1, c))M[r-1, c, 4] = 2if c < num_cols-1:if M[r, c+1, 4] == 1:check.append('R')elif M[r, c+1, 4] == 0:history.append((r, c+1))M[r, c+1, 4] = 2if r < num_rows-1:if M[r+1, c, 4] == 1:check.append('D')elif M[r+1, c, 4] == 0:history.append((r+1, c))M[r+1, c, 4] = 2
# 随机前往一个边界墙.if len(check):n+=1move = random.choice(check)if move == 'L':  # [上,右，下，左，1]M[r, c, 3] = 1c = c-1M[r, c, 1] = 1if move == 'U':M[r, c, 0] = 1r = r-1M[r, c, 2] = 1if move == 'R':M[r, c, 1] = 1c = c+1M[r, c, 3] = 1if move == 'D':M[r, c, 2] = 1r = r+1M[r, c, 0] = 1# 红色方格显示当前单元格子位置clear()#清理下，不然内存会一直被占用。fillcolor("red")begin_fill()drawing(r, c, M[r, c])end_fill()# 调用turtle画图显示当前整个地图状态。for i in range(num_rows): for j in range(num_cols):drawing(i, j, M[i, j])update()#需要跟新下，不然会卡死time.sleep(0.5)if n == num_cols*num_rows-1:  # 当砸墙的数量等于单元格子的数量-1时结束循环。breakdone()