使用随机深度优先搜索算法生成多层迷宫

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#!/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.py

链接地址
maze.py

draw_maze.py

链接地址
draw_maze.py

生成的多层迷宫

2层迷宫

3层迷宫

gif演示

3层迷宫