效果展示
基本思想
无论是DFS、BFS还是RFS，由这些算法生成的迷宫本质上是二维矩阵网络形式的生成树，即没有循环，同时从右上的起点开始迷宫中的所有点都有路径，只有一个路径当然，到终点的路径也是唯一的。
深度替代导线测量始终从当前最长路径的末端随机选择可扩展点进行扩展，如果出现循环或到达边界，则可追溯到最近的可扩展分支。 该算法生成的迷宫分支相对较少，路径也较长且曲折。
函数详细信息
一.接口初始化
导入页面
导入系统
导入匹配
导入随机
(1，1 ) ) 1，2 )矩阵
# pygame初始化
pygame.init (
设定#盘的大小。 在DFS中必须是奇数，每个奇数格子都必须是一个节点
chess_number=89
IF_RANDOM_START_END=0#是否为随机终点和起点
TICK=100
BG=(144，136，145 )背景色
线颜色=(112，73，46 ) #网格颜色
开始颜色=(253、176、36 ) #开始网格颜色
结束颜色=(224，90，9 )终点) 224，90，9 )橙色) 252，61，63 )鲜红
wll color=(33，41，48 ) #墙的颜色
#迷宫在画布上显示的位置
start _ pos=(50，50 )
START_POSX=50
START_POSY=50
cell _ length=int (600/chess _ number ) #每个网格的像素大小
LINE_WIDTH=3#行宽度
BIAS=5#取中心偏差、奇数，距起点和终点对角线的距离
#设置背景框大小等pygame初始化操作
size=width，height=2* start _ pos xchess _ number * cell _ length，2 * start _ posy chess _ number * cell _ length
clock=pygame.time.Clock (
screen=pygame.display.set _ mode (size )
pygame.display.set _ caption (acecheneymade ) )。
if IF_RANDOM_START_END==1:
#设定开始位置
start_POSX=random.randint(0，chess_number-1 ) )。
start_posy=random.randint(0，chess_number-1 ) )。
#设定终点的开始位置
end_POSX=random.randint(0，chess_number-1 ) )。
end_posy=random.randint(0，chess_number-1 ) )。
else:
#设定开始位置
start_posx=0 BIAS
start_posy=0 BIAS
#设定终点的开始位置
end_posx=chess_number-1-BIAS
end_posy=chess_number-1-BIAS
startpos=[start_posx，start_posy]
endpos=[end_posx，end_posy]
#设置墙壁网格列表
wallcell=[]
二.绘制网格线和迷宫
值得注意的是，这里要考虑不同层的上下关系。 因为后面画的图层会覆盖前面画的图层。
def draw () :
全球销售点
全球结束标志，结束路径
forIinrange(chess_number1) :
pygame.draw.line(screen，LINECOLOR，) START_POSX，START_POSY i*CELL_LENGTH )，start_posxchess_numbess
pygame.draw.line(screen，LINECOLOR，) START_POSX i*CELL_LENGTH，START_POSY ) _posxI*cell_ling )、ststare
画墙
dawwall(wallcell ) ) ) )。
drawcell(start_POSX，start_
posy, STARTCOLOR)#起点drawcell(end_posx, end_posy, ENDCOLOR) #终点
三、画具体的一个迷宫单元格
一个单元格可以处于四种状态，墙或者路、起点或是终点，颜色也各不相同。
参数是行坐标，列坐标和单元格种类。
def drawcell(i,j,cellkind):
pygame.draw.rect(screen,cellkind,[START_POSX+CELL_LENGTH*j+(LINE_WIDTH-1),START_POSY+CELL_LENGTH*i+(LINE_WIDTH-1),CELL_LENGTH-LINE_WIDTH,CELL_LENGTH-LINE_WIDTH],0)
四、⭐️DFS算法
采用DFS算法生成随机迷宫，输入参数很简单，就是棋盘的大小，因为棋盘是正方形，所有只有一个输入参数。返回的事一个储存全局地图信息的二维数组，0为无墙，1为有墙。
值得注意的是，起点和终点的坐标并不影响，由于DFS算法+完美迷宫的特性，某些特定单元格一定是路，而不是墙，那么只需要任意在路单元格里选两个点，令其为起点或是终点也就可以了。
def DFScreatwall(chess_number):
'''
生成迷宫，有路为0，墙为1
param:chess_number
return:一个储存全局地图信息的二维数组，0为无墙，1为有墙
'''
neighborcell=[]
maincell=[]
#初始状态下，迷宫内所有点都是墙壁，只有满足条件，节点才会由墙壁变成通路，而且节点和相邻选中非节点之间的阻碍打破
wallcell=[[1]*chess_number for i in range(chess_number)]
wallcell[start_posx][start_posy]=0
neighborcell.append(startpos)
con=1
#对一个节点进行选择拓展，规则：选择的拓展节点一定是孤立的
while con:
#在邻居中选择最后的一个，因为最后一个储存的是最深的
[x,y]=neighborcell[-1]
nextcell=[]
#一个潜在的邻居，如果他的上下左右的墙都是未打通的，那么他是符合要求的
if x-2>=1 and wallcell[x-2][y] ==1 and wallcell[x-1][y] == 1 and wallcell[x-3][y]==1 and wallcell[x-2][y+1]==1 and wallcell[x-2][y-1]==1:
nextcell.append([x-2,y])
if x+2<=chess_number-2 and wallcell[x+2][y] ==1 and wallcell[x+1][y] == 1 and wallcell[x+3][y]==1 and wallcell[x+2][y+1]==1 and wallcell[x+2][y-1]==1:
nextcell.append([x+2,y])
if y-2>=1 and wallcell[x][y-2]==1 and wallcell[x][y-3] ==1 and wallcell[x][y-1] == 1 and wallcell[x-1][y-2]==1 and wallcell[x+1][y-2]==1:
nextcell.append([x,y-2])
if y+2<=chess_number-2 and wallcell[x][y+2] ==1 and wallcell[x][y+1] == 1 and wallcell[x][y+3]==1 and wallcell[x-1][y+2]==1 and wallcell[x+1][y+2]==1:
nextcell.append([x,y+2])
try:
#随机选一个符合要求的邻居作为真正的邻居
num=random.randint(0,len(nextcell)-1)
neighborcell.append([nextcell[num][0],nextcell[num][1]])
#邻居和墙均需要被打通
wallcell[nextcell[num][0]][nextcell[num][1]]=0
if nextcell[num]==[x-2,y]:
wallcell[x-1][y]=0
elif nextcell[num]==[x+2,y]:
wallcell[x+1][y]=0
elif nextcell[num]==[x,y-2]:
wallcell[x][y-1]=0
elif nextcell[num]==[x,y+2]:
wallcell[x][y+1]=0
except:
#数组越界
#该路径没有合适的邻居,那就把这个流程再来一次,在此之前必须先去除最后一个不满足要求的
neighborcell.pop()
#当所有的关键点全联通,结束遍历
odd1=0
con=0
for y in wallcell:
if odd1%2==1:
odd2=0
for x in y:
if odd2%2==1:
if x==1:
con=1
break
odd2+=1
if con==1:
break
odd1+=1
return wallcell
五、画墙
输入参数是储存迷宫的全局状态信息，也就是DFS的返回值
def drawwall(wallcell):
for i in range(chess_number):
for j in range(chess_number):
if wallcell[i][j]==1:
drawcell(i, j, WALLCOLOR)
源码链接
敬请期待：基于Astar和Markov算法的迷宫寻路
Markov寻找最短路径
Astar寻找最短路径
Astar走迷宫
Markov走迷宫