【Python】生成二维迷宫的算法
前言
哈里最近因为一个小插曲打算写一个设计迷宫的算法。为了锻炼脑力，特地没有上网搜索而是自己摸索出一个迷宫设计算法。
概述
1、需求
哈里准备实现下图的迷宫。
2、分析
可以看到，图里凡是x和y坐标为单数时，总是白色。于是哈里得到下图：
我将白色区域定义为房间（room），每个房间有四个方向（上下左右）可以连接其它房间。
我将能从绿色（出发点）到达的房间设置其连通（alive）。上图就只有（1，1）的房间连通。
这里哈里思考，如果每个房间都与出发点连通，最后右下角的房间必然就可以和出发点连通。
实际尝试之后，确实获得了一个还不错的迷宫图像，但是会出现下图的问题：
x=1和y=1总是会有大片的空白。
对此，哈里尝试将房间迭代的顺序打乱，最终得到了可以接受的迷宫图。
3、结语
差不多就是这样了……脑子混沌的时候靠直觉直接猜的……不完美但够用就行。
源码
import random
import sysfrom PIL import Image
from pygame import *
import time
import pygame# 方向向量，用于四个方向：上、右、下、左
dirVector = [(0, 1), # 下(1, 0), # 右(-1, 0), # 左(0, -1), # 上
]# 房间类，定义房间的位置和是否激活
class Room:def __init__(self, pos, alive=False):self.pos = pos # 房间位置self.alive = alive # 房间是否激活# 链接房间def Link(self):if self.alive:return # 如果房间已激活，则返回dirs = self.GetCanOpenDirs() # 获取可以打开的方向if not dirs:return # 如果没有可用方向，则返回dirs = random.sample(dirs, 1) # 随机选择一个方向for d in dirs:img.putpixel((self.pos[0] + d[0], self.pos[1] + d[1]), (255, 255, 255)) # 在图像上绘制房间self.alive = True # 激活房间# 获取可以打开的方向def GetCanOpenDirs(self):r = []for d in dirVector:_x, _y = self.pos[0] + d[0], self.pos[1] + d[1] # 计算方向上的位置# 检查是否在图像边界内if _x < 1 or _y < 1 or _x >= img.width - 1 or _y >= img.height - 1:continuep2 = (self.pos[0] + d[0] * 2, self.pos[1] + d[1] * 2) # 计算下一个位置if p2 not in allRoom or not allRoom[p2].alive:continuer.append(d) # 将有效方向添加到列表return r@propertydef isColse(self):for d in dirVector:x, y = self.pos[0] + d[0], self.pos[1] + d[1] # 计算相邻位置if img.getpixel((x, y)) != (0, 0, 0): # 检查相邻像素是否为黑色return Falsereturn True# 判断所有房间是否激活
def JudgeAllAlive():for _room in allRoom.values():if not _room.alive:return Falsereturn True# 初始化pygame
pygame.init()
pygame.display.set_caption('预览') # 设置窗口标题
size = (21, 21) # 图像大小
# screen = pygame.display.set_mode(Vector2(size) * 10) # 缩放图像
screen = pygame.display.set_mode(Vector2(size)) # 创建显示窗口
img = Image.new('RGB', size, (255, 255, 255)) # 创建新图像，背景为白色
endPos = (size[0] - 2, size[1] - 1) # 终点位置
rooms = [] # 房间列表
allRoom = {} # 所有房间字典# 初始化图像上的黑色网格
for y in range(img.height):for x in range(0, img.width, 2):img.putpixel((x, y), (0, 0, 0))for x in range(img.width):for y in range(0, img.height, 2):img.putpixel((x, y), (0, 0, 0))# 添加房间到列表和字典
for x in range(1, img.width, 2):for y in range(1, img.height, 2):rooms.append((x, y))allRoom[(x, y)] = Room((x, y))
allRoom[(1, 1)].alive = True # 激活起点房间random.shuffle(rooms) # 打乱房间顺序
for roomPos in rooms:allRoom[roomPos].Link() # 链接所有房间# 标记起点和终点
img.putpixel((1, 0), (0, 255, 0)) # 起点标记为绿色
img.putpixel(endPos, (255, 0, 0)) # 终点标记为红色
tempImg = img.copy() # 复制图像用于更新显示# 游戏主循环
while 1:for event in pygame.event.get(): # 从Pygame的事件队列中取出事件，并从队列中删除该事件if event.type == pygame.QUIT: # 检查退出事件sys.exit() # 退出程序screen.fill((255, 255, 255)) # 填充背景为白色tempImg = img.copy() # 复制图像用于更新显示if not JudgeAllAlive(): # 检查是否所有房间都激活random.shuffle(rooms) # 打乱房间顺序for roomPos in rooms:allRoom[roomPos].Link() # 链接房间if not allRoom[roomPos].alive:tempImg.putpixel(roomPos, (255, 125, 0)) # 未激活的房间标记为橙色else:break # 如果所有房间都激活，退出循环pygameImg = pygame.image.frombuffer(tempImg.tobytes(), size, 'RGB') # 将图像转换为Pygame格式# pygameImg = pygame.transform.scale(pygameImg, Vector2(size) * 10) # 缩放图像screen.blit(pygameImg, (0, 0)) # 绘制图像到屏幕# time.sleep(0.05) # 延时pygame.display.flip() # 更新显示img.save('mg.png') # 保存图像为文件