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

源码

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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import random
import pygame
#
# 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。将选中的单元格标记为已访问的，并将其压入堆栈
# 多层迷宫 

# pygame
pygame.init()  # 初始化pygame
size = width, height = 1024, 768  # 设置窗口大小
screen = pygame.display.set_mode(size)  # 显示窗口
pygame.display.set_caption('火苗999℃')
# 颜色
diamond_color_size = 8
COLOR_RED, COLOR_BLUE, COLOR_GREEN, COLOR_YELLOW, COLOR_BLACK, COLOR_GREY, COLOR_GOLDEN, COLOR_NO_DIAMOND = list(range(
    diamond_color_size))
COLOR = {
    COLOR_RED: (255, 0, 0),
    COLOR_BLUE: (0, 0, 255),
    COLOR_GREEN: (0, 255, 0),
    COLOR_YELLOW: (255, 255, 0),
    COLOR_BLACK: (0, 0, 0),
    COLOR_GREY: (250, 240, 230),
    COLOR_GOLDEN : (255,215,0),
    COLOR_NO_DIAMOND: (160, 160, 160),
}
# 格式边长
DIAMOND_LENGTH = 10
# 格子大小
DIAMOND_SIZE = (DIAMOND_LENGTH, DIAMOND_LENGTH)
# 蓝格子
DIAMOND=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND.fill(COLOR[COLOR_BLUE])
# 绿格子 
DIAMOND_GREEN=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_GREEN.fill(COLOR[COLOR_GREEN])
# 红格子 
DIAMOND_RED=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_RED.fill(COLOR[COLOR_RED])
# 黄格子 
DIAMOND_YELLOW=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_YELLOW.fill(COLOR[COLOR_YELLOW])
# 灰格子 
DIAMOND_GRAY=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_GRAY.fill(COLOR[COLOR_GREY])
# 黑格子
DIAMOND_BLACK=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_BLACK.fill(COLOR[COLOR_BLACK])
# 蓝格子
DIAMOND_BLUE=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_BLUE.fill(COLOR[COLOR_BLUE])
# 3层使用不同颜色
DIAMOND_O=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_O.fill((255,128,0))
DIAMOND_G=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_G.fill((0,102,51))
DIAMOND_R=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_R.fill((102,0,0))

# 字体
use_font = pygame.font.Font("FONT.TTF", 16)
# 背景
background=pygame.surface.Surface(size).convert()
background.fill(COLOR[COLOR_NO_DIAMOND])
# 楼梯
mini_font = pygame.font.Font("FONT.TTF", 8)
DIAMOND_U=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_U.fill(COLOR[COLOR_GREEN])
surface_u = mini_font.render("U", True, COLOR[COLOR_BLACK], COLOR[COLOR_GREEN])
DIAMOND_U.blit(surface_u, (0, 0))

DIAMOND_D=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_D.fill(COLOR[COLOR_GREEN])
surface_d = mini_font.render("D", True, COLOR[COLOR_BLACK], COLOR[COLOR_GREEN])
DIAMOND_D.blit(surface_d, (0, 0))

DIAMOND_UD=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_UD.fill(COLOR[COLOR_GREEN])
surface_ud = mini_font.render("UD", True, COLOR[COLOR_BLACK], COLOR[COLOR_GREEN])
DIAMOND_UD.blit(surface_ud, (0, 0))

# 时间
clock = pygame.time.Clock()

#标记 
NOWALL = 0 # 无墙
WALL = 1  # 墙
STAIRS_U = 2 # 楼梯上
STAIRS_D = 4 # 楼梯下
STAIRS_UD = 6 # 楼梯上下


def depth_maze_demo(levels, rows, cols):
    if 0 == rows % 2:
        rows+=1
    if 0 == cols % 2:
        cols+=1
    # 墙0通路1。x,y是墙的坐标。
    # 初始化全为墙
    wall=[[[ WALL for i in range(cols)]for i in range(rows)]for i in range(levels)]
    # 设置起点
    l=0
    r=1
    c=1
    # 起点加入记录
    history = [(l, r, c)]
    # 1。选择初始单元格，将其标记为已访问，并将其压入堆栈
    # 2。堆栈不是空的
    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                return
        if history:
            if wall[l][r][c] == WALL:
                wall[l][r][c] = NOWALL # 打通格子
            check = []
            # 可以移动到的位置
            if c > 1 and wall[l][r][c-2] == WALL:
                check.append('L')  
            if r > 1 and wall[l][r-2][c] == WALL:
                check.append('F')
            if c < cols-2 and wall[l][r][c+2] == WALL:
                check.append('R')
            if r < rows-2 and wall[l][r+2][c] == WALL:
                check.append('B')    
            if l < levels-1 and wall[l+1][r][c] == WALL:
                check.append('U')    
            if l > 0 and wall[l-1][r][c] == WALL:
                check.append('D')                    
            # 如果当前单元有任何未被访问的邻居
            if len(check): 
                # 选择一个未被拜访的邻居
                # 移除当前单元格和所选单元格之间的墙
                # 将选中的单元格标记为已访问的，并将其压入堆栈
                history.append((l, r, c))
                # 随机移动
                move_direction = random.choice(check)
                # 打通墙壁
                if move_direction == 'L':
                    wall[l][r][c-1] = NOWALL # 打通墙
                    wall[l][r][c-2] = NOWALL # 打通格子
                    c=c-2
                if move_direction == 'F':
                    wall[l][r-1][c] = NOWALL # 打通墙
                    wall[l][r-2][c] = NOWALL # 打通格子
                    r=r-2
                if move_direction == 'R':
                    wall[l][r][c+1] = NOWALL # 打通墙
                    wall[l][r][c+2] = NOWALL # 打通格子
                    c=c+2
                if move_direction == 'B':
                    wall[l][r+1][c] = NOWALL # 打通墙
                    wall[l][r+2][c] = NOWALL # 打通格子
                    r=r+2
                if move_direction == 'U':
                    if wall[l][r][c] == STAIRS_D:
                        wall[l][r][c] = STAIRS_UD # 标记为上下楼梯
                    else:
                        wall[l][r][c] = STAIRS_U # 标记为向上楼梯
                    if wall[l+1][r][c] == STAIRS_U:
                        wall[l+1][r][c] = STAIRS_UD # 标记为上下楼梯
                    else:
                        wall[l+1][r][c] = STAIRS_D # 标记为向下楼梯
                    l=l+1
                if move_direction == 'D':
                    if wall[l][r][c] == STAIRS_U:
                        wall[l][r][c] = STAIRS_UD # 标记为上下楼梯
                    else:
                        wall[l][r][c] = STAIRS_D # 标记为向下楼梯
                    if wall[l-1][r][c] == STAIRS_D:
                        wall[l-1][r][c] = STAIRS_UD # 标记为上下楼梯
                    else:
                        wall[l-1][r][c] = STAIRS_U # 标记为向上楼梯
                    l=l-1
            else: 
                #从堆栈中弹出一个单元格并使其成为当前单元格
                l, r, c = history.pop()
        # 
        screen.blit(background, (0, 0))
        # 格子
        for z in range(levels):
            for x in range(cols):
                for y in range(rows):
                    a = z % 2
                    b = z // 2
                    px, py = 1 + x * DIAMOND_SIZE[0] + a * (cols*DIAMOND_LENGTH+10),  1 + y * DIAMOND_SIZE[1] + b*(rows*DIAMOND_LENGTH+10)
                    s = (z)%3
                    # 向上楼梯使用上层颜色表示，向下楼梯使用下层颜色表示，上下楼梯使用蓝色表示
                    if 0 == s:
                        color_c = DIAMOND_G
                        color_u = DIAMOND_O
                        color_d = DIAMOND_R
                        color_ud = DIAMOND_BLUE
                    elif 1 == s:
                        color_c = DIAMOND_O
                        color_u = DIAMOND_R
                        color_d = DIAMOND_G
                        color_ud = DIAMOND_BLUE
                    else:
                        color_c = DIAMOND_R
                        color_u = DIAMOND_G
                        color_d = DIAMOND_O
                        color_ud = DIAMOND_BLUE
                    if NOWALL == wall[z][y][x]:
                        screen.blit(color_c, (px, py))
                    elif WALL == wall[z][y][x]:
                        screen.blit(DIAMOND_GRAY, (px, py))
                    elif STAIRS_U == wall[z][y][x]:
                        screen.blit(color_u, (px, py))
                    elif STAIRS_D == wall[z][y][x]:
                        screen.blit(color_d, (px, py))
                    elif STAIRS_UD == wall[z][y][x]:
                        screen.blit(color_ud, (px, py))
                    else:
                        screen.blit(DIAMOND_YELLOW, (px, py))
        # 
        if history:
            a = l % 2
            b = l // 2
            px, py = 1 + c * DIAMOND_SIZE[0] + a * (cols*DIAMOND_LENGTH+10),  1 + r * DIAMOND_SIZE[1] + b*(rows*DIAMOND_LENGTH+10)
            screen.blit(DIAMOND_RED, (px, py))
        if not history:
            score_surface = use_font.render("生成完成！", True, COLOR[COLOR_BLACK], COLOR[COLOR_GREY])
            screen.blit(score_surface, (20, ((levels+ 1) // 2 )*(rows*DIAMOND_LENGTH+10)))
        
        time_passed = clock.tick(30)

        pygame.display.update()
    return 


# main
if __name__ == "__main__":
    '''main'''
    depth_maze_demo(3, 21, 31)

生成的多层迷宫

2层迷宫

3层迷宫

gif演示

4层迷宫

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