基于 Python 实现「迷宫生成算法」

迷宫生成：基于 Python 的实现

前一阵子看了Blibili上一个UP主的视频，讲解了一下迷宫，这引起了我极大的兴趣，诞生了自己从零开始实现一个迷宫生成的程序的想法。

在Github上浏览了一番，虽然有的写的很强，可以实现复杂图案设计，但是很难结合我观看的视频进行改动。我更应该先实现简单功能，复杂设计理应万变不离其宗。更简单的设计可以加深我对迷宫的理解

迷宫生成 - 基本规则

在基本迷宫设计中，我们把每一个单元格理解成为一个房间；那么迷宫生成实际上就可以理解为：破坏两个房间之间的墙。

1. 从所在的房间的四周，能且只能找到没有去过的房间，破坏中间的墙
2. 当前所在的位置四周不存在可以没有去过的房间，应该从已经去过的房间任意选择一个，再从中找其旁边没有去过的房间
3. 无论当前是否到达终点，只有存在没有去过的房间，都需要重复步骤 2，直到所有房间都具有连通性

对迷宫的理解

迷宫可以理解为一颗树，根节点是入口。迷宫玩法实际上是找到从根节点到目的叶节点最近的距离。

在这次实践中，我同时也把这个迷宫理解成为一个二维数组，方便设计，每条边以及房间都包含在该二维数组中。

实现思路

迷宫生成，我期望值是能返回一个全迷宫二维数组；因为要同时设计GUI，我设计了 GUI 以及 MAZE 两个类。

1. 首先生成二维数组，全部置 1；初始化并让其中房间标记为 0。
   
2. 设计一个方法，接受参数为当前的房间，查询并返回四个方向中可以进行吓一跳的房间。
3. 从步骤 2 返回的房间随机选择一个。

   需要注意的是若当前的房间为终点，或者返回的房间为空，需要在已经去过的房间重新选择一个。重复这个步骤直到所有的房间都到达过。

4. 返回对象为已经生成好的二维数组
   
5. 最后再用 Tkinter 库进行简单绘制即可

Github Address

https://github.com/DioPong/MazeGenerator

语法笔记

1. 返回可用下一跳位置

def get_valid_position(self, x, y):
   valid_pos = [[x + 2, y], ...]
   valid_pos.remove([x + 2, y]) if x == height else ...
   ...

do_sth if x else ...
这是符合 Python 规范的语法。我在写的过程中发觉写多个if区块判别占用了大量的代码行，为了压缩代码行我采用了这种方式。
"..." 实际上是 Python 自带的常量，与 Pass 相似都可以作为占位符，但是在上述语法中 Pass 是不符合规范的写法，会引起报错。

2. 初始化二维数组

# 正常做法
maze = [[1 for x in range(width)] for y in height]

# 错误方法
maze = [[1] * width] * height

我们按照正常理解，在 Python 中 [1]*2=>[1, 1]
但是在这里，当我们尝试把二维数组中的房间置为 0 的时候，会发现每一列都会变成 0。实际上这是因为 Python 中的浅复制导致的，实际上 Python 中当把一个数组乘以一个常数，Python 本身会为该次操作定义为浅复制，后面多出来的元素实际上与原数组公用一个内存空间。

测试