| 迷宫生成算法 | 您所在的位置：网站首页 › 迷宫的代码pytion › 迷宫生成算法 |
迷宫生成算法
|
迷宫生成算法---深度优先算法
总体的目录版权及协议声明更加舒服的阅读方式一. 深度优先算法的原理与思路二．迷宫的制作迷宫的总体的创建。三.代码的实现
总体的目录
版权及协议声明
本文章遵循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是经过该结点才被发现的），来搜索该前驱结点的出发边。该过程一直持续到从源结点可以达到的所有结点都被发现为止。如果还存在尚未发现的结点，则深度优先搜索将从这些未被发现的结点中任选一个作为新的源点，并重复同样的搜索过程。该算法重复整个过程，直到图中的所有结点都被发现为止。 用人话的方式来说明： 选一个起点查看周围能够移动的点并随即挑一个移动重复步骤2直到周围没有可以移动的点回溯一格，即回到到当前位置的上一个位置，并执行步骤2和3 二．迷宫的制作知道了这个算法的原理以后就可以开始准备制作迷宫的模型了。 迷宫分为两个部分，一个是路，一个是墙。那么就有两种制作出来的形态：第一种是墙是一条线，路是一个方格。
首先我们要设定这个迷宫的长和宽。由于我们要保证地图中不会生成2*2的正方形块，以及要保证地图里的每一个陆块都能相互连接，所以我们要让长和宽都为2n+1（n∈Z+）（换一个说法：如果有n条路，那么就一定有n+1个墙，所以就为2n+1个格子） 那么这个地图的框架就出来了： 黄色的方块为当前的位置 绿色为上一个方块的位置 蓝色为黄色的方块可以走的位置 粉色为生成的路径 那么就以左上角的方块为起点: 那么我们接下来看我们步骤4所反应的情况: 首先,先附上完整的代码: import random import sys sys.setrecursionlimit(5000) width_set =int(input("请输入宽度")) height_set = int(input("请输入高度")) if width_set2:#判断上边的格子 if map[height-2][width].Iswall == True: Waypoints_ing.append(map[height-2][width]) map[height-2][width].from_x = width map[height-2][width].from_y = height if width2:#判断上边的格子 if map[height-2][width].Iswall == True: Waypoints_ing.append(map[height-2][width]) map[height-2][width].from_x = width map[height-2][width].from_y = height if width2:#判断左边的格子 if map[height][width-2].Iswall == True: Waypoints_ing.append(map[height][width-2]) map[height][width-2].from_x = width map[height][width-2].from_y = height if height>2:#判断上边的格子 if map[height-2][width].Iswall == True: Waypoints_ing.append(map[height-2][width]) map[height-2][width].from_x = width map[height-2][width].from_y = height if width |
第二种是墙和路都是方格，墙是实心的路是空心的
两个方式表现出来的特点是显而易见的，第一种的容量在地图的大小相同的情况下是比第二种的容量大的 那么这个代码中创建出来的迷宫则是第二种形态。
接下来就是生成路径 首先我们规定:
它可以向两个方向走,即: 
之后随机挑选一个,以下面的方块为例: 
接下来选择右边的方块: 
以此类推… 这就是路径生成的过程
当遇到这个情况时,就回溯到上一个方格所在的位置,即绿色方格的位置: 
那么我们可以看到,回溯一次的时候就有了新的路径,接下来就是继续移动格子,继续创建地图. 当地图中所有的格子均检测过的时候,我们的黄色格子就会回到了左上角
因此,我们可以检测黄色格子的位置来判断地图是否生成完毕.【本文地址】