总体的目录

版权及协议声明

本文章遵循CC BY-NC-SA 4.0协议,即知识共享-署名-非商业性使用-相同方式共享

更加舒服的阅读方式

该文章的pdf版,排版更舒服(其实是因为不会csdn的排版)
链接：https://pan.baidu.com/s/1vl4D__WK-YDyDVWydqdj5Q
提取码：2233

完成后的代码
链接：https://pan.baidu.com/s/1BanSKbRiWTytvByct0fErw
提取码：2233

一. 深度优先算法的原理与思路

首先来看一下算法导论上的解释：

深度优先搜索总是对最近才发现的结点v的出发边进行探索，直到该结点的所有出发边都被发现为止。一但结点v的所有出发边都被发现，搜索则“回溯”到v的前驱结点（v是经过该结点才被发现的），来搜索该前驱结点的出发边。该过程一直持续到从源结点可以达到的所有结点都被发现为止。如果还存在尚未发现的结点，则深度优先搜索将从这些未被发现的结点中任选一个作为新的源点，并重复同样的搜索过程。该算法重复整个过程，直到图中的所有结点都被发现为止。

用人话的方式来说明：

1. 选一个起点
2. 查看周围能够移动的点并随即挑一个移动
3. 重复步骤2直到周围没有可以移动的点
4. 回溯一格，即回到到当前位置的上一个位置，并执行步骤2和3

二．迷宫的制作

知道了这个算法的原理以后就可以开始准备制作迷宫的模型了。
迷宫分为两个部分，一个是路，一个是墙。那么就有两种制作出来的形态：第一种是墙是一条线，路是一个方格。

第二种是墙和路都是方格，墙是实心的路是空心的

两个方式表现出来的特点是显而易见的，第一种的容量在地图的大小相同的情况下是比第二种的容量大的
那么这个代码中创建出来的迷宫则是第二种形态。

迷宫的总体的创建。

首先我们要设定这个迷宫的长和宽。由于我们要保证地图中不会生成2*2的正方形块，以及要保证地图里的每一个陆块都能相互连接，所以我们要让长和宽都为2n+1（n∈Z+）（换一个说法：如果有n条路，那么就一定有n+1个墙，所以就为2n+1个格子）
那么这个地图的框架就出来了：
接下来就是生成路径
首先我们规定:

黄色的方块为当前的位置
绿色为上一个方块的位置
蓝色为黄色的方块可以走的位置
粉色为生成的路径

那么就以左上角的方块为起点:

它可以向两个方向走,即:

之后随机挑选一个,以下面的方块为例:

接下来选择右边的方块:

以此类推…
这就是路径生成的过程

那么我们接下来看我们步骤4所反应的情况:

当遇到这个情况时,就回溯到上一个方格所在的位置,即绿色方格的位置:

那么我们可以看到,回溯一次的时候就有了新的路径,接下来就是继续移动格子,继续创建地图.
当地图中所有的格子均检测过的时候,我们的黄色格子就会回到了左上角
因此,我们可以检测黄色格子的位置来判断地图是否生成完毕.

三.代码的实现

首先,先附上完整的代码:

import randomimport sys
sys.setrecursionlimit(5000)
width_set=int(input("请输入宽度"))
height_set=int(input("请输入高度"))if width_set<4or height_set<4:
    width_set=11
    height_set=11print("输入的尺寸过小,已自动调节成,宽度:11,高度:11")if width_set%2!=1:
    width_set+=1print("宽度请输入奇数,已自动矫正为:"+str(width_set))if height_set%2!=1:
    height_set+=1print("高度请输入奇数,已自动矫正为:"+str(height_set))map=[[0for widthinrange(width_set)]for heightinrange(height_set)]classcube:
    loc_x=0#当前的x坐标
    loc_y=0#当前的y坐标
    from_x=0#上一个格子的x坐标
    from_y=0#上一个格子的y坐标
    Iswall=True#是否是墙for heightinrange(0,height_set):for widthinrange(width_set):map[height][width]= cube()map[height][width].loc_y= heightmap[height][width].loc_x= widthdefspawn(local_map=[]):
    Waypoints_ing=[]#当函数运行时用来添加备选路点
    width= local_map.loc_x
    height= local_map.loc_ymap[height][width].Iswall=Falseif width>2:#判断左边的格子ifmap[height][width-2].Iswall==True:
            Waypoints_ing.append(map[height][width-2])map[height][width-2].from_x= widthmap[height][width-2].from_y= heightif height>2:#判断上边的格子ifmap[height-2][width].Iswall==True:
            Waypoints_ing.append(map[height-2][width])map[height-2][width].from_x= widthmap[height-2][width].from_y= heightif width<width_set-2:#判断下边的格子ifmap[height][width+2].Iswall==True:
            Waypoints_ing.append(map[height][width+2])map[height][width+2].from_x= widthmap[height][width+2].from_y= heightif height<height_set-2:#判断上边的格子ifmap[height+2][width].Iswall==True:
            Waypoints_ing.append(map[height+2][width])map[height+2][width].from_x= widthmap[height+2][width].from_y= heightif(local_map.from_x!=0and local_map.from_y!=0):map[int((local_map.from_y+height)/2)][int((local_map.from_x+width)/2)].Iswall=Falseif(len(Waypoints_ing)>0):#如果有元素
        targetnum= random.randint(0,len(Waypoints_ing)-1)#生成一个关于Waypoints_ing的随机的下标
        spawn(Waypoints_ing[targetnum])#进行下一次的递归else:ifmap[height][width].from_y==1andmap[height][width].from_x==0:#如果回溯的目标为初始点的时候return#从递归中跳出
        spawn(map[map[height][width].from_y][map[height][width].from_x])#如果不是初始点,那么就在回溯目标的格子上继续递归defprintmap():
    out=""for heightinrange(height_set):for widthinrange(width_set):ifmap[height][width].Iswall==True:
                out= out+"■ "else:
                out= out+"  "if width== width_set-1:
                out= out+"\n"print(out)map[1][0].Iswall=Falsemap[1][1].from_x=0map[1][1].from_y=1
spawn(map[1][1])#从坐标为(1,1)的格子开始做递归
printmap()

那么接下来我们来一步一步的完成这个代码的构建

首先,我们要能创建指定长宽的矩形点阵:
那么就需要检测用户的输入:

width_set=int(input("请输入宽度"))
height_set=int(input("请输入高度"))

width_set就是我们设置的宽度
height_set则是我们设置的高度
接下来就是要一个矩形的点阵,那么我们就能想到,可以通过二维列表来建立相应的结构

map=[[0for widthinrange(width_set)]for heightinrange(height_set)]

先创建总行数,再创建总列数,所以要选择里面的元素的时候要先写这个元素所在的行数再输入所在的列数
那么这个地图里的任意一点(x,y)都可以表示为map[y][x]
至于为什么要用生成器而不是直接用*的方式来创建可以参考这个文章https://zhuanlan.zhihu.com/p/88197389

接下来我们要让二维列表中的每一个元素都有相对于自身的属性(比如当前的位置,是不是墙,有没有检测过等)
所以我们需要创建一个关于方格的类来存放这些东西

classcube:
    loc_x=0#当前的x坐标
    loc_y=0#当前的y坐标
    from_x=0#上一个格子的x坐标
    from_y=0#上一个格子的y坐标
    Iswall=True#是否是墙

当然,从总代码中可以看到不是只有这些属性,其他的属性会在接下来需要的时候添加上去.
那么已经设置好了格子的属性以后就要让二维列表中的元素成为这个类的对象.
用两个for循环来实现所有元素的实例化并且记录当前的位置

for heightinrange(0,height_set):for widthinrange(width_set):map[height][width]= cube()map[height][width].loc_y= heightmap[height][width].loc_x= width

那么我们可以来看一下目前为止的成果了.我们现在来输出已经创建好的地图:

defprintmap():
    out=""for heightinrange(height_set):#遍历行for widthinrange(width_set):#遍历列ifmap[height][width].Iswall==True:
                out= out+"■ "else:
                out= out+"  "if width== width_set-1:
                out= out+"\n"print(out)

由代码可以看到,我把这个过程进行了一个封装,将它变成了一个方法
这个代码的原理是,先设立一个空的字符串out,接下来一行一行的判断应该输出的究竟是墙还是路,如果是路那么就在字符串的结尾加上两个空格,如果是墙就加上一个方块和一个空格,如果要换行了,就加上\n(在print的时候会换行).

那么之后要用这个方法的时候只需要调用一下就可以了.

接下来我们就要开始写整个代码中最重要的部分,即迷宫生成的部分.

首先先将height指定为当前的y值,将width指向当前的x值

width= local_map.loc_x
height= local_map.loc_y

我们以这个图为例,当前的width_set为7,height_set也为7
那么我们现在选中的格子的坐标是(1,1)
那么我们要向这个方块的四周进行检测首先我们先向下面进行检测.那么这个手就会有一个问题:什么时候应该停止
通过上面的图就可以发现当当前的y轴坐标大于等于height_set-2的时候就应该停止,或者说:当当前的y轴坐标小于height_set-2的时候就可以检测.
那么为什么一定要是这样呢?当y的坐标大于或等于height_set-2时,下一个目标的位置就在边界上或者是在地图以外的位置了.
在代码中的体现:

if height<height_set-2:

现在就完成了一个方向的判断,其余的四个方向也是这样判断的

现在已经保证了选的格子是在地图的范围以内的
那么现在就要来判断备选的目标是否是墙:

ifmap[height+2][width].Iswall==True:

比如当前目标格子的下面的格子(3,1),如果是墙,那么就将这个点添加到备选的点:

Waypoints_ing.append(map[height+2][width])

并且将下面格子的回溯格子的坐标的指向当前的格子的坐标:

map[height+2][width].from_x= widthmap[height+2][width].from_y= height

接下来的三个方向都是相同的处理:

if width>2:#判断左边的格子ifmap[height][width-2].Iswall==True:
            Waypoints_ing.append(map[height][width-2])map[height][width-2].from_x= widthmap[height][width-2].from_y= heightif height>2:#判断上边的格子ifmap[height-2][width].Iswall==True:
            Waypoints_ing.append(map[height-2][width])map[height-2][width].from_x= widthmap[height-2][width].from_y= heightif width<width_set-2:#判断下边的格子ifmap[height][width+2].Iswall==True:
            Waypoints_ing.append(map[height][width+2])map[height][width+2].from_x= widthmap[height][width+2].from_y= heightif height<height_set-2:#判断上边的格子ifmap[height+2][width].Iswall==True:
            Waypoints_ing.append(map[height+2][width])map[height+2][width].from_x= widthmap[height+2][width].from_y= height

其中Waypoints_ing的创建(要放在上面的代码的前面)

Waypoints_ing=[]#当函数运行时用来添加备选路点

当完成对四个方向的判断以后Waypoints_ing里面就包含了可以移动的目标格子
接下来就要判断Waypoints_ing里面的元素,如果Waypoints_ing里面了元素,即当前的格子周围没有可以移动的格子,那么就回溯想一个格子,如果有可以移动的格子,那么就从中随机挑选一个,做下一次的递归.
由于我们要用到random函数,所以需要引用random库

import randomif(local_map.from_x!=0and local_map.from_y!=0):map[int((local_map.from_y+height)/2)][int((local_map.from_x+width)/2)].Iswall=Falseif(len(Waypoints_ing)>0):#如果有元素
        targetnum= random.randint(0,len(Waypoints_ing)-1)#生成一个关于Waypoints_ing的随机的下标
        spawn(Waypoints_ing[targetnum])#进行下一次的递归else:ifmap[width][height].from_y==1andmap[height][width].from_x==0:#如果回溯的目标为初始点的时候return#从递归中跳出
        spawn(map[map[height][width].from_y][map[height][width].from_x])#如果不是初始点,那么就在回溯目标的格子上继续递归

接下来,我们对以上的代码进行一个整理,将他放进一个方法里:

defspawn(local_map=[]):
    Waypoints_ing=[]#当函数运行时用来添加备选路点
    width= local_map.loc_x
    height= local_map.loc_y########空槽1##################if width>2:#判断左边的格子ifmap[height][width-2].Iswall==True:
            Waypoints_ing.append(map[height][width-2])map[height][width-2].from_x= widthmap[height][width-2].from_y= heightif height>2:#判断上边的格子ifmap[height-2][width].Iswall==True:
            Waypoints_ing.append(map[height-2][width])map[height-2][width].from_x= widthmap[height-2][width].from_y= heightif width<width_set-2:#判断下边的格子ifmap[height][width+2].Iswall==True:
            Waypoints_ing.append(map[height][width+2])map[height][width+2].from_x= widthmap[height][width+2].from_y= heightif height<height_set-2:#判断上边的格子ifmap[height+2][width].Iswall==True:
            Waypoints_ing.append(map[height+2][width])map[height+2][width].from_x= widthmap[height+2][width].from_y= height############空槽2########################if(len(Waypoints_ing)>0):#如果有元素
        targetnum= random.randint(0,len(Waypoints_ing)-1)#生成一个关于Waypoints_ing的随机的下标
        spawn(Waypoints_ing[targetnum])#进行下一次的递归else:ifmap[height][width].from_y==1andmap[height][width].from_x==0: