迷宫寻路算法 深度优先算法(的魔改版)(基于python)

2022-08-30 14:49:37

总体目录

  1. 这篇文章里用到的迷宫生成算法的讲解:迷宫生成算法—深度优先算法(基于python)_ghost_him的博客-CSDN博客
    建议先看上面的那一篇文章,这篇文章在上面的文章的基础上写的

  2. 首先你能用上文的代码生成这样子的迷宫在这里插入图片描述
    ,那么接下来就开始了.

版权及协议声明

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

更加舒服的阅读方式

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

一. 深度优先算法的原理与思路(上一篇文章的原话,看过的可以直接跳过)

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

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

用人话的方式来说明:

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

二. 在迷宫中的实现

寻路算法与生成算法是有不同的,生成算法找的是”墙”,而寻路算法找的是路,而且是紧密相连的路.
众所周知,在一个已经生成好的迷宫中,1.每一条路都是与周围的路紧密相连的2.每一条路都有且仅有一条途径到另一条路上

因此在代码中,我们只需要检测路周围四周的格子,如果周围有两条路那么就在探测出来的新的路(即之前未被检测过的路)上重复这个动作,直到周围只有一条路的时候停止这个动作.

以下图为例:
在这里插入图片描述
蓝色为当前执行代码的方块,绿色为回溯的方块(即上一个方块),黄色为检测到的方块
首先从起点开始在这里插入图片描述
蓝色周围有一个未被检测过的方块,
那么接下来就应该在黄色的方块上执行这个相同的操作:在这里插入图片描述
直到碰到岔路口,那么就是一种新的情况:在这里插入图片描述
这部分就是我的算法与深度优先算法的不同之处了:

在这个情况下,我是同时在两个黄色的方块上执行相同的操作,而不是从中挑一条先走到底再挑两外的一条路走:在这里插入图片描述

接下来就是相当于运行了两个方法来继续运行,直到每条路都走到尽头了:在这里插入图片描述
那么就有一个问题:如果遇到了终点怎么办?

我们先设迷宫的终点在右下角:在这里插入图片描述
由于边界处的墙最多只能与一条路紧密连接,因此只需要设这个终点旁边的路为终点方块即可.

由上面的寻路的过程中,我们可以知道,每个路都是指向上一条路的,从而最终指向起点在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
因此只需要一个递归,就能够将这些路的属性全部设置好,最后就能输出了.

三. 用代码来实现

完整的代码

import timeimport randomimport sys#===setting==========
width_set=int(input("请输入宽度"))
height_set=int(input("请输入高度"))
Ischeck=str(input("是否要查看生成过程(Y/N)"))
IsFind=str(input("是否要寻找路径(Y/N)"))
sys.setrecursionlimit(3000)#=====test=======if Ischeck!='Y'and Ischeck!='N':print("你输入的是:"+Ischeck)print("请重新输入Y/N")
    sys.exit()if IsFind!='Y'and IsFind!='N':print("你输入的是:"+IsFind)print("请重新输入Y/N")
    sys.exit()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))classcube:
    loc_x=0#当前的x坐标
    loc_y=0#当前的y坐标
    from_x=0
    from_y=0
    IsEndpoints=False
    IsWay=False
    Iswall=True#是否是墙
    Iscalled=False#是否被使用过

time_before= time.time()map=[[0for widthinrange(width_set)]for heightinrange(height_set)]definitial():#初始化地图并记录自身的坐标for heightinrange(0,height_set):for widthinrange(width_set):map[height][width]= cube()map[height][width].loc_y= heightmap[height][width].loc_x= width#初始化起始点map[1][0].Iswall=Falsemap[1][1].from_x=0map[1][1].from_y=1#=======================初始化边框=========================for heightinrange(0,height_set-1):for widthinrange(width_set-1):if(height==0or height== width_set-1):map[height][width].Iscalled=Trueelse:map[height][0].Iscalled=Truemap[height][width_set-1].Iscalled=Truedefprintmap():
    out=""for heightinrange(height_set):for widthinrange(width_set):ifmap[height][width].Iswall==True:
                out= out+"■ "elifmap[height][width].IsWay==True:
                out= out+". "elifmap[height][width].IsEndpoints==True:
                out= out+"* "else:
                out= out+"  "if width== width_set-1:
                out= out+"\n"print(out)defspawn(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):#如果有元素if Ischeck=="Y":
            printmap()
        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])#如果不是初始点,那么就在回溯目标的格子上继续递归defDoFindway(local_map=[]):
    width= local_map.loc_x
    height= local_map.loc_ymap[height][width].Iscalled=Trueif width>0:ifmap[height][width-1].IsEndpoints==True:
            spawmWay(map[height][width])ifmap[height][width-1].Iswall==Falseandmap[height][width-1].Iscalled==False:map[height][width-1].from_y= heightmap[height][width-1].from_x= width
            DoFindway(map[height][width-1])if height>0:ifmap[height-1][width].IsEndpoints==True:
            spawmWay(map[height][width])ifmap[height-1][width].Iswall==Falseandmap[height-1][width].Iscalled==False:map[height-1][width].from_y= heightmap[height-1][width].from_x= width
            DoFindway(map[height-1][width])if width<width_set-1:ifmap[height][width+1].IsEndpoints==True:
            spawmWay(map[height][width])ifmap[height][width+1].Iswall==Falseandmap[height][width+1].Iscalled==False:map[height][width+1].from_y= heightmap[height][width+1].from_x= width
            DoFindway(map[height][width+1])if height<height_set-1:ifmap[height+1][width].IsEndpoints==True:
            spawmWay(map[height][width])ifmap[height+1][width].Iswall==Falseandmap[height+1][width].Iscalled==False:map[height+1][width].from_y= heightmap[height+1][width].from_x= width
            DoFindway(map[height+1][width])#记录路径点defspawmWay(local_map=[]):
    width= local_map.loc_x
    height= local_map.loc_ymap[height][width].IsWay=True'''
    print("跟踪:("+str(height)+","+str(width)+")")
    print("跟踪from:("+str(local_map.from_y)+","+str(local_map.from_x)+")")
    '''if local_map.from_x!=0or local_map.from_y!=1:
        spawmWay(map[local_map.from_y][local_map.from_x])deffindWay():for heightinrange(1,height_set-1):for widthinrange(1,width_set-1):map[height][width].Iscalled=Falseprint("寻找路径中")
    DoFindway(map[1][1])print("路径寻找完毕")print(map)
initial()
spawn(map[1][1])
printmap()if IsFind=="Y":map[1][1].IsWay=Truemap[height_set-2][width_set-1].IsEndpoints=Truemap[height_set-2][width_set-1].Iswall=False
    findWay()
printmap()

首先,根据以上的分析,我们需要对格子添加一些新的属性:是否是墙,是否被使用过,是否是终点
因此要在class类里添加三个属性

classcube:
    loc_x=0#当前的x坐标
    loc_y=0#当前的y坐标
    from_x=0
    from_y=0
    IsEndpoints=False#是否是终点
    IsWay=False
    Iswall=True#是否是墙
    Iscalled=False#是否被使用过

检测路的存在与否

首先是与之前的思路一样的:
以检测左边的格子是不是路为例:
如果,要保证检测左边的格子不会报错,那么就说明左边是有格子可以检测的,那么就可以推断出:当前的位置不在地图的最左侧,即:width>0
那么,我们要检测左边的格子的时候就要保证当前的格子不是最左边的格子,那么就需要一下的代码进行判断

if width>0:

好,现在已经说明了当前的格子不是最左边的格子了,那么我们就可以开始检测左边的格子是不是终点,如果是,那么就直接做路径的回溯:

ifmap[height][width-1].IsEndpoints==True:
         spawmWay(map[height][width])#在接下来会讲到,这个函数是用来做路径的回溯的

如果不是终点,那么就要判断左边的格子是不是墙,如果是墙就直接跳过,如果不是墙,那么就要判断左边的路有没有被检测过(即是不是刚才的路,要避免死循环),如果没有被检测过,那么就在这个没被检测过的路上进行检测

ifmap[height][width-1].Iswall==Falseandmap[height][width-1].Iscalled==False:#将左边方块的回溯方块的坐标指向当前的方块,说明是从当前的方块传递到左边的方块的map[height][width-1].from_y= heightmap[height][width-1].from_x= width
       DoFindway(map[height][width-1])#这个方法就是现在在讲的方法,当前的代码会在最后封装成DoFindway()方法

其余三向的检测都是一个道理

if width>0:#检测左边的格子ifmap[height][width-1].IsEndpoints==True:
            spawmWay(map[height][width])ifmap[height][width-1].Iswall==Falseandmap[height][width-1].Iscalled==False:#将左边方块的回溯方块的坐标指向当前的方块,说明是从当前的方块传递到左边的方块的map[height][width-1].from_y= heightmap[height][width-1].from_x= width
            DoFindway(map[height][width-1])if height>0:#检测上面的格子ifmap[height-1][width].IsEndpoints==True:
            spawmWay(map
  • 作者:ghost_him
  • 原文链接:https://blog.csdn.net/ghost_him/article/details/116309224
    更新时间:2022-08-30 14:49:37