最近对迷宫相关的算法产生了兴趣,可能因为了解了一点点图论和算法,突然发现自己这种菜鸡也能试着实现一下迷宫生成
目前主要打算使用Python实现, 之后还会用Unity实现更加形象的生成过程
主要参考:python_marble_xu的博客-CSDN博客
https://blog.csdn.net/marble_xu/category_8691561.html
和国外热爱迷宫算法的大佬Jamis Buck的书《 Mazes for Programmers 》
目录
一.预演
首先思考如何存储, 当然二维数组比较方便
那如何区分 路与墙 呢? 主要靠如下的映射
灰色的我们会标志为1, 观察白色的点有何特点, 是的, 他们的横纵坐标均为奇数, 达成这种映射我们可以较为方便的初始化所有空地, 接下来要做的就是打通中间的一些墙, (最后输出的时候,0为可行走的空地,1为墙)
开始的时候设为全都是墙,这样我们在构建迷宫的过程中无需另设表示是否访问的标志
map = [[1 for x in range(self.width)] for y in range(self.height)]二. 破壁
这个过程和深度优先走迷宫算是互逆了,这里是在"解放",走迷宫是在"占领"
随机找个横纵坐标奇数的起点开始并设为空
startX, startY = (randint(0, widthLimited - 1), randint(0, heightLimited - 1))
map.setMap(2 * startX + 1, 2 * startY + 1, ITEM_TYPE.EMPTY)checklist用来存坐标对,在之后的一系列过程中, 我们会将随机选择的方向上(且合理)的点存入其中,
if x > 0:
if not map.isVisited(2 * (x - 1) + 1, 2 * y + 1):
directions.append(DIRECTION.LEFT)
if y > 0:
if not map.isVisited(2 * x + 1, 2 * (y - 1) + 1):
directions.append(DIRECTION.UP)
if x < widthLimited - 1:
if not map.isVisited(2 * (x + 1) + 1, 2 * y + 1):
directions.append(DIRECTION.RIGHT)
if y < heightLimited - 1:
if not map.isVisited(2 * x + 1, 2 * (y + 1) + 1):
directions.append(DIRECTION.DOWN)注意:
我们判断的是"奇数对"坐标,
别忘了将中间的墙打通哦
if len(directions):
# 随机选择方向
direction = choice(directions)
if direction == DIRECTION.LEFT:
map.setMap(2 * (x - 1) + 1, 2 * y + 1, ITEM_TYPE.EMPTY)
map.setMap(2 * x, 2 * y + 1, ITEM_TYPE.EMPTY)
waitinglist.append((x - 1, y))
elif direction == DIRECTION.UP:
map.setMap(2 * x + 1, 2 * (y - 1) + 1, ITEM_TYPE.EMPTY)
map.setMap(2 * x + 1, 2 * y, ITEM_TYPE.EMPTY)
waitinglist.append((x, y - 1))
elif direction == DIRECTION.RIGHT:
map.setMap(2 * (x + 1) + 1, 2 * y + 1, ITEM_TYPE.EMPTY)
map.setMap(2 * x + 2, 2 * y + 1, ITEM_TYPE.EMPTY)
waitinglist.append((x + 1, y))
elif direction == DIRECTION.DOWN:
map.setMap(2 * x + 1, 2 * (y + 1) + 1, ITEM_TYPE.EMPTY)
map.setMap(2 * x + 1, 2 * y + 2, ITEM_TYPE.EMPTY)
waitinglist.append((x, y + 1))
return True
else:
return False在无路可通时(即走到某个犄角旮旯,周围的奇数坐标均已开通过), 就返回错误, 并删除 待处理队列waitinglist(整体上看这其实是在模拟栈) 最后一个坐标对, 实现回溯的效果
waitinglist = []
waitinglist.append((startX, startY))
while len(waitinglist):
if not checkPostion(map, waitinglist[-1][0], waitinglist[-1][1], widthLimited, heightLimited, waitinglist):
waitinglist.remove(waitinglist[-1])
三.完整代码
from random import randint, choice
from enum import Enum
class ITEM_TYPE(Enum):
EMPTY = 0,
BLOCK = 1,
class DIRECTION(Enum):
LEFT = 0,
UP = 1,
RIGHT = 2,
DOWN = 3,
class Map():
def __init__(self, width, height):
self.width = width
self.height = height
# 初始化均为墙
self.map = [[1 for x in range(self.width)] for y in range(self.height)]
def resetMap(self, value):
for y in range(self.height):
for x in range(self.width):
self.setMap(x, y, value)
def setMap(self, x, y, value):
if value == ITEM_TYPE.EMPTY:
self.map[y][x] = 0
elif value == ITEM_TYPE.BLOCK:
self.map[y][x] = 1
def isVisited(self, x, y):
return self.map[y][x] == 0
def showMap(self):
for row in self.map:
for item in row:
if item == 0:
print(' ', end='')
elif item == 1:
print('@ ', end='')
print('')
def checkPostion(map, x, y, widthLimited, heightLimited, waitinglist):
directions = []
if x > 0:
if not map.isVisited(2 * (x - 1) + 1, 2 * y + 1):
directions.append(DIRECTION.LEFT)
if y > 0:
if not map.isVisited(2 * x + 1, 2 * (y - 1) + 1):
directions.append(DIRECTION.UP)
if x < widthLimited - 1:
if not map.isVisited(2 * (x + 1) + 1, 2 * y + 1):
directions.append(DIRECTION.RIGHT)
if y < heightLimited - 1:
if not map.isVisited(2 * x + 1, 2 * (y + 1) + 1):
directions.append(DIRECTION.DOWN)
if len(directions):
# 随机选择方向
direction = choice(directions)
if direction == DIRECTION.LEFT:
map.setMap(2 * (x - 1) + 1, 2 * y + 1, ITEM_TYPE.EMPTY)
map.setMap(2 * x, 2 * y + 1, ITEM_TYPE.EMPTY)
waitinglist.append((x - 1, y))
elif direction == DIRECTION.UP:
map.setMap(2 * x + 1, 2 * (y - 1) + 1, ITEM_TYPE.EMPTY)
map.setMap(2 * x + 1, 2 * y, ITEM_TYPE.EMPTY)
waitinglist.append((x, y - 1))
elif direction == DIRECTION.RIGHT:
map.setMap(2 * (x + 1) + 1, 2 * y + 1, ITEM_TYPE.EMPTY)
map.setMap(2 * x + 2, 2 * y + 1, ITEM_TYPE.EMPTY)
waitinglist.append((x + 1, y))
elif direction == DIRECTION.DOWN:
map.setMap(2 * x + 1, 2 * (y + 1) + 1, ITEM_TYPE.EMPTY)
map.setMap(2 * x + 1, 2 * y + 2, ITEM_TYPE.EMPTY)
waitinglist.append((x, y + 1))
return True
else:
return False
def recursive(map, widthLimited, heightLimited):
startX, startY = (randint(0, widthLimited - 1), randint(0, heightLimited - 1))
map.setMap(2 * startX + 1, 2 * startY + 1, ITEM_TYPE.EMPTY)
waitinglist = []
waitinglist.append((startX, startY))
while len(waitinglist):
if not checkPostion(map, waitinglist[-1][0], waitinglist[-1][1], widthLimited, heightLimited, waitinglist):
waitinglist.remove(waitinglist[-1])
# 开始构造迷宫
def startCreateMaze(map):
recursive(map, map.width // 2, map.height // 2)
def run():
WIDTH = 27
HEIGHT = 17
map = Map(WIDTH, HEIGHT)
startCreateMaze(map)
map.showMap()
if __name__ == "__main__":
run()四. 效果展示
注意地图的宽高均设为奇数哦, 可参见(一)中的图, 这样才能形成合理映射
