vlambda博客
学习文章列表

自动走迷宫(2)--深度优先(非递归)算法

这是我2019年坚持制作的第89次推文


       上一期的‘左手法则’走迷宫我称之为‘感性方式’,局限性很大,而接下来的则是用算法来寻址的‘理性方式‘。这一期用深度优先(DFS)(非递归方式)来完成自动走迷宫。
       简单科普几个概念,官方解释dogedoge自己看吧,说一下我自己的理解: 首先是两个基本算法深度优先遍历(DFS)和广度优先遍历(BFS),对比着比较好理解,深度优先就是‘一个猛子扎到底’,忽略层级的,而广度优先则是按层级一级一级遍历的。还有要用到的两个数据结构:栈与队列,都是存放数据的容器,只是取数据的方式不同;栈为‘后进先出’,要从末尾取数据;队列则是‘先进先出’,要从头部取数据。
       言归正传,用深度优先走迷宫就 遍历生成的地图迷宫列表,寻找一条从起点到终点全是‘0’的路线 。伪代码如下:
(1)从迷宫起点节点V开始访问
(2)访问这个节点V,标记为可行的路径;
(3)从v的未被访问的非"墙"邻接点中选取一个顶点w,重复第二步。 如果v没有未访问的非"墙"邻接点,把这个节点的可行路径标记移除,回溯 至上一节点;
(4)重复上述第(2)、(3)步,直至遍历到迷宫的出口节点。

       逻辑与生成迷宫是一样的,非常简单,只是图像化语言的特点,代码可能会很长,其他语言的话就简洁多了,废话不说了,直接上图!~

    先初始化,设置好起点和终点位置。

自动走迷宫(2)--深度优先(非递归)算法

将起点压栈,然后进入循环:
        取栈顶元素设置为当前单元,标记为已访问;
        如果当前单元周围有‘是路’并且‘未访问’的邻接单元(待处理列表项目数>0),选取第一个,将其压栈。
        否则将当前单元出栈。

注意:返回当前单元周围情况与生成迷宫方法类似,就是寻找有‘是路’并且‘未访问’的单元,并把它们放入待处理列表,基于迷宫寻址方式,加入顺序是“右-下-左-上”。

自动走迷宫(2)--深度优先(非递归)算法


       执行上面的方法后,栈内留下的元素就是从起点到终点各个能够联通的节点,将它们连线就大功告成了!~


————————————————