使用随机深度优先搜索算法生成多层迷宫
使用随机深度优先搜索算法生成多层迷宫
源码
#!/usr/bin/python3
# -*- coding: utf-8 -*-
# create by 火苗999℃
import random
from draw_maze import *
from maze_def import *
from maze import *
#
# Randomized depth-first search
# Recursive implementation
#1。Choose the initial cell, mark it as visited and push it to the stack
#2。While the stack is not empty
# 1。Pop a cell from the stack and make it a current cell
# 2。If the current cell has any neighbours which have not been visited
# 1。Push the current cell to the stack
# 2。Choose one of the unvisited neighbours
# 3。Remove the wall between the current cell and the chosen cell
# 4。Mark the chosen cell as visited and push it to the stack
#随机深度优先搜索
#递归实现
#1。选择初始单元格，将其标记为已访问，并将其压入堆栈
#2。而堆栈不是空的
# 1。从堆栈中弹出一个单元格并使其成为当前单元格
# 2。如果当前单元有任何未被访问的邻居
# 1。将当前单元格压入堆栈
# 2。选择一个未被拜访的邻居
# 3。移除当前单元格和所选单元格之间的墙
# 4。将选中的单元格标记为已访问的，并将其压入堆栈
# 多层迷宫
def depth_maze_demo(levels, rows, cols):
if 0 == levels % 2:
levels+=1
if 0 == rows % 2:
rows+=1
if 0 == cols % 2:
cols+=1
# 初始化全为墙
maze_map = maze_init_draw(levels,rows,cols)
# 设置起点
nowx=1
nowy=1
nowz=0
# 起点加入记录
history = [(nowx, nowy, nowz)]
# 1。选择初始单元格，将其标记为已访问，并将其压入堆栈
# 2。堆栈不是空的
while True:
for event in pygame.event.get():
if event.type == pygame.QUIT:
return
if history:
if maze_map[nowx][nowy][nowz] == CELL_NO_VISIT:
maze_map[nowx][nowy][nowz] = NOWALL # 打通格子
check = []
# 可以移动到的位置
if nowx > 1 and maze_map[nowx-2][nowy][nowz] == CELL_NO_VISIT:
check.append('L')
if nowy > 1 and maze_map[nowx][nowy-2][nowz] == CELL_NO_VISIT:
check.append('F')
if nowx < cols-2 and maze_map[nowx+2][nowy][nowz] == CELL_NO_VISIT:
check.append('R')
if nowy < rows-2 and maze_map[nowx][nowy+2][nowz] == CELL_NO_VISIT:
check.append('B')
if nowz < levels-2 and maze_map[nowx][nowy][nowz+2] == CELL_NO_VISIT:
check.append('U')
if nowz > 1 and maze_map[nowx][nowy][nowz-2] == CELL_NO_VISIT:
check.append('D')
# 如果当前单元有任何未被访问的邻居
if len(check):
# 选择一个未被拜访的邻居
# 移除当前单元格和所选单元格之间的墙
# 将选中的单元格标记为已访问的，并将其压入堆栈
history.append((nowx, nowy, nowz))
# 随机移动
move_direction = random.choice(check)
# 打通墙壁
if move_direction == 'L':
maze_map[nowx-1][nowy][nowz] = NOWALL # 打通墙
maze_map[nowx-2][nowy][nowz] = NOWALL # 打通格子
nowx=nowx-2
if move_direction == 'F':
maze_map[nowx][nowy-1][nowz] = NOWALL # 打通墙
maze_map[nowx][nowy-2][nowz] = NOWALL # 打通格子
nowy=nowy-2
if move_direction == 'R':
maze_map[nowx+1][nowy][nowz] = NOWALL # 打通墙
maze_map[nowx+2][nowy][nowz] = NOWALL # 打通格子
nowx=nowx+2
if move_direction == 'B':
maze_map[nowx][nowy+1][nowz] = NOWALL # 打通墙
maze_map[nowx][nowy+2][nowz] = NOWALL # 打通格子
nowy=nowy+2
if move_direction == 'U':
if maze_map[nowx][nowy][nowz] == STAIRS_D:
maze_map[nowx][nowy][nowz] = STAIRS_UD # 标记为上下楼梯
else:
maze_map[nowx][nowy][nowz] = STAIRS_U # 标记为向上楼梯
maze_map[nowx][nowy][nowz+1] = NOWALL # 打通墙
if maze_map[nowx][nowy][nowz+2] == STAIRS_U:
maze_map[nowx][nowy][nowz+2] = STAIRS_UD # 标记为上下楼梯
else:
maze_map[nowx][nowy][nowz+2] = STAIRS_D # 标记为向下楼梯
nowz=nowz+2
if move_direction == 'D':
if maze_map[nowx][nowy][nowz] == STAIRS_U:
maze_map[nowx][nowy][nowz] = STAIRS_UD # 标记为上下楼梯
else:
maze_map[nowx][nowy][nowz] = STAIRS_D # 标记为向下楼梯
maze_map[nowx][nowy][nowz-1] = NOWALL # 打通墙
if maze_map[nowx][nowy][nowz-2] == STAIRS_D:
maze_map[nowx][nowy][nowz-2] = STAIRS_UD # 标记为上下楼梯
else:
maze_map[nowx][nowy][nowz-2] = STAIRS_U # 标记为向上楼梯
nowz=nowz-2
else:
#从堆栈中弹出一个单元格并使其成为当前单元格
nowx, nowy, nowz = history.pop()
#
draw_maze(maze_map, levels, rows, cols, (nowx,nowy,nowz), not history)
time_passed = clock.tick(30)
pygame.display.update()
return
# main
if __name__ == "__main__":
'''main'''
depth_maze_demo(5, 11, 21)
maze_def.py
maze_def.py
链接地址
maze_def.py
maze.py
maze.py
链接地址
maze.py
draw_maze.py
draw_maze.py
链接地址
draw_maze.py
生成的多层迷宫
gif演示
