基于 Python 实现「迷宫生成算法」
迷宫生成:基于 Python 的实现 前一阵子看了Blibili上一个UP主的视频,讲解了一下迷宫,这引起了我极大的兴趣,诞生了自己从零开始实现一个迷宫生成的程序的想法。 在Github上浏览了一番,虽然有的写的很强,可以实现复杂图案设计,但是很难结合我观看的视频进行改动。我更应该先实现简单功能,复杂设计理应万变不离其宗。更简单的设计可以加深我对迷宫的理解 迷宫生成 - 基本规则 在基本迷宫设计中,我们把每一个单元格理解成为一个房间;那么迷宫生成实际上就可以理解为:破坏两个房间之间的墙。 从所在的房间的四周,能且只能找到没有去过的房间,破坏中间的墙 当前所在的位置四周不存在可以没有去过的房间,应该从已经去过的房间任意选择一个,再从中找其旁边没有去过的房间 无论当前是否到达终点,只有存在没有去过的房间,都需要重复步骤 2,直到所有房间都具有连通性 对迷宫的理解 迷宫可以理解为一颗树,根节点是入口。迷宫玩法实际上是找到从根节点到目的叶节点最近的距离。 在这次实践中,我同时也把这个迷宫理解成为一个二维数组,方便设计,每条边以及房间都包含在该二维数组中。 实现思路 迷宫生成,我期望值是能返回一个全迷宫二维数组;因为要同时设计GUI,我设计了 GUI 以及 MAZE 两个类。 首先生成二维数组,全部置 1;初始化并让其中房间标记为 0。 设计一个方法,接受参数为当前的房间,查询并返回四个方向中可以进行吓一跳的房间。 从步骤 2 返回的房间随机选择一个。 需要注意的是若当前的房间为终点,或者返回的房间为空,需要在已经去过的房间重新选择一个。重复这个步骤直到所有的房间都到达过。 返回对象为已经生成好的二维数组 最后再用 Tkinter 库进行简单绘制即可 Github Address https://github.com/PengCheong/MazeGenerator 语法笔记 1. 返回可用下一跳位置 def get_valid_position(self, x, y): valid_pos = [[x + 2, y], ...] valid_pos.remove([x + 2, y]) if x == height else ....