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

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。将选中的单元格标记为已访问的，并将其压入堆栈

源码

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
#!/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 visit_cell(maze_map, x, y, z, cols, rows):
    if maze_map[x][y][z] == CELL_NO_VISIT: 
        maze_map[x][y][z] = CELL_VISIT # 标记访问
    grids = []
    minx = x
    while True:
        if minx > 1 and maze_map[minx-1][y][z] == CELL_NO_VISIT:
            minx -=1
        else:
            break
    maxx = x
    while True:
        if maxx < cols - 2 and maze_map[maxx+1][y][z] == CELL_NO_VISIT:
            maxx+=1
        else:
            break    
    miny=y
    while True:
        if miny > 1 and maze_map[x][miny-1][z] == CELL_NO_VISIT:
            miny -=1
        else:
            break
    maxy=y
    while True:
        if maxy < rows - 2 and maze_map[x][maxy+1][z] == CELL_NO_VISIT:
            maxy +=1
        else:
            break
    for xi in range(minx, maxx+1):
        for yi in range(miny, maxy+1):
            if  maze_map[xi][yi][z] == CELL_NO_VISIT: 
                maze_map[xi][yi][z] = CELL_VISIT
            grids.append((xi,yi,z))
    return grids


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_draw2(levels,rows,cols, 5, 3, 5)
    # 设置起点
    nowx=1
    nowy=1
    nowz=0
    # 起点加入记录
    history = []
    grids = visit_cell(maze_map, nowx, nowy, nowz, cols, rows)
    history.extend(grids)
    # 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:
                grids = visit_cell(maze_map, nowx, nowy, nowz, cols, rows)
                history.extend(grids)

            check = []
            # 可以移动到的位置
            if nowx > 1:
                if maze_map[nowx-2][nowy][nowz] == CELL_NO_VISIT:
                    check.append('L')  
                elif maze_map[nowx-1][nowy][nowz] == WALL_NO_VISIT:
                    # 标记墙已访问(演示用)
                    maze_map[nowx-1][nowy][nowz] = WALL_VISIT
            if nowy > 1 :
                if maze_map[nowx][nowy-2][nowz] == CELL_NO_VISIT:
                    check.append('F')
                elif maze_map[nowx][nowy-1][nowz] == WALL_NO_VISIT:
                    # 标记墙已访问(演示用)
                    maze_map[nowx][nowy-1][nowz] = WALL_VISIT
            if nowx < cols-2:
                if maze_map[nowx+2][nowy][nowz] == CELL_NO_VISIT:
                    check.append('R')
                elif maze_map[nowx+1][nowy][nowz] == WALL_NO_VISIT:
                    # 标记墙已访问(演示用)
                    maze_map[nowx+1][nowy][nowz] = WALL_VISIT
            if nowy < rows-2:
                if maze_map[nowx][nowy+2][nowz] == CELL_NO_VISIT:
                    check.append('B')    
                elif maze_map[nowx][nowy+1][nowz] == WALL_NO_VISIT:
                    maze_map[nowx][nowy+1][nowz] = WALL_VISIT
            if nowz < levels-2:
                if  maze_map[nowx][nowy][nowz+2] == CELL_NO_VISIT:
                    check.append('U') 
                elif maze_map[nowx][nowy][nowz+1] == WALL_NO_VISIT:
                    maze_map[nowx][nowy][nowz+1] = WALL_VISIT
            if nowz > 1:
                if maze_map[nowx][nowy][nowz-2] == CELL_NO_VISIT:
                    check.append('D')   
                elif maze_map[nowx][nowy][nowz-1] == WALL_NO_VISIT:
                    maze_map[nowx][nowy][nowz-1] = WALL_VISIT                 
            # 如果当前单元有任何未被访问的邻居
            if len(check): 
                # 选择一个未被拜访的邻居
                # 移除当前单元格和所选单元格之间的墙
                # 将选中的单元格标记为已访问的，并将其压入堆栈
                # 随机选择邻居
                move_direction = random.choice(check)
                # 打通墙壁
                if move_direction == 'L':
                    maze_map[nowx-1][nowy][nowz] = NOWALL # 打通墙
                    nowx=nowx-2
                if move_direction == 'F':
                    maze_map[nowx][nowy-1][nowz] = NOWALL # 打通墙
                    nowy=nowy-2
                if move_direction == 'R':
                    maze_map[nowx+1][nowy][nowz] = NOWALL # 打通墙
                    nowx=nowx+2
                if move_direction == 'B':
                    maze_map[nowx][nowy+1][nowz] = NOWALL # 打通墙
                    nowy=nowy+2
                if move_direction == 'U':
                    maze_map[nowx][nowy][nowz+1] = NOWALL # 打通墙
                    if maze_map[nowx][nowy][nowz] == STAIRS_D:
                        maze_map[nowx][nowy][nowz] = STAIRS_UD # 标记为上下楼梯
                    else:
                        maze_map[nowx][nowy][nowz] = STAIRS_U # 标记为向上楼梯
                    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':
                    maze_map[nowx][nowy][nowz-1] = NOWALL # 打通墙
                    if maze_map[nowx][nowy][nowz] == STAIRS_U:
                        maze_map[nowx][nowy][nowz] = STAIRS_UD # 标记为上下楼梯
                    else:
                        maze_map[nowx][nowy][nowz] = STAIRS_D # 标记为向下楼梯
                    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
                # 将选中的单元格标记为已访问的，并将其压入堆栈
                grids = visit_cell(maze_map, nowx, nowy, nowz, cols, rows)
                history.extend(grids)
            else: 
                #从堆栈中弹出一个单元格并使其成为当前单元格
                nowx, nowy, nowz = history.pop()
        # 
        draw_maze(maze_map, levels, rows, cols, (nowx,nowy,nowz), not history)
        
        time_passed = clock.tick(200)

        pygame.display.update()
    return 


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

maze_def.py

链接地址
maze_def.py

maze.py

链接地址
maze.py

draw_maze.py

链接地址
draw_maze.py

生成的多层迷宫

3层迷宫

gif演示

3层迷宫