多层迷宫生成

Aldous-Broder algorithm
The Aldous-Broder algorithm also produces uniform spanning trees.

1.Pick a random cell as the current cell and mark it as visited.
2.While there are unvisited cells:

  • 1.Pick a random neighbour.
  • 2.If the chosen neighbour has not been visited:
    • 1.Remove the wall between the current cell and the chosen neighbour.
    • 2.Mark the chosen neighbour as visited.

  • 3.Make the chosen neighbour the current cell.

    Aldous-Broder算法
    Aldous-Broder算法也生成统一的生成树。

    1。选择一个随机的单元格作为当前单元格，并将其标记为已访问的。
    2。当存在未访问细胞时:

  • 1。随机选择一个邻居。
  • 2。如果选中的邻居没有被访问:
    • 1。移除当前单元格和所选邻居之间的墙。
    • 2。标记被选中的邻居已被拜访过。
  • 3。使选择的邻居成为当前单元格。

源码

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
#!/usr/bin/python3.7
# -*- coding: utf-8 -*-
# create by 火苗999℃
import random
from maze import *
from draw_maze import *
#Aldous-Broder algorithm
#The Aldous-Broder algorithm also produces uniform spanning trees.

# 1.Pick a random cell as the current cell and mark it as visited.
# 2.While there are unvisited cells:
#   1.Pick a random neighbour.
#   2.If the chosen neighbour has not been visited:
#       1.Remove the wall between the current cell and the chosen neighbour.
#       2.Mark the chosen neighbour as visited.
#   3.Make the chosen neighbour the current cell.

# Aldous-Broder算法
# Aldous-Broder算法也生成统一的生成树。
# 1。选择一个随机的单元格作为当前单元格，并将其标记为已访问的。
# 2。当存在未访问细胞时:
#   1。随机选择一个邻居。
#   2。如果选中的邻居没有被访问:
#       1。移除当前单元格和所选邻居之间的墙。
#       2。标记被选中的邻居已被拜访过。
#   3。使选择的邻居成为当前单元格。


# 随机格子
def aldous_broder_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)
    # 
    notusegrids = [] # 没有访问过的格子,单数代表格子，双数是墙壁
    for tz in range(0, levels):
        for tx in range(0, cols):
            for ty in range(0, rows):
                if maze_map[tx][ty][tz]==CELL_NO_VISIT:
                    notusegrids.append((tx, ty, tz))
                # 演示用
                elif maze_map[tx][ty][tz] == WALL_NO_VISIT:
                    maze_map[tx][ty][tz] = WALL_VISIT
    # 选择一个随机的单元格作为当前单元格，并将其标记为已访问的。
    nowx,nowy,nowz = random.choice(notusegrids)
    # 标记迷宫
    maze_map[nowx][nowy][nowz]=CELL_VISIT
    notusegrids.remove((nowx,nowy,nowz))
    posx,posy=None,None
    # 当存在未访问细胞时:
    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                return
        # 当存在未访问细胞时:
        if  notusegrids:
            directions = []
            # 可随机方向
            if nowy > 1:
                directions.append('f')
            if nowx > 1:
                directions.append('l')
            if nowy < rows-2:
                directions.append('b')
            if nowx < cols-2:
                directions.append('r')
            if nowz < levels-1:
                directions.append('u')
            if nowz > 0:
                directions.append('d')
            if len(directions):
                # 随机一个方向
                move = random.choice(directions)
                # 如果选中的邻居没有被访问:
                    #   1。移除当前单元格和所选邻居之间的墙。
                    #   2。标记被选中的邻居已被拜访过。
                    #   3。使选择的邻居成为当前单元格。
                if move == 'f':
                    newy = nowy-2
                    newx = nowx
                    newz = nowz
                    opwall=(nowx,nowy-1,nowz)
                if move == 'l':
                    newy = nowy
                    newx = nowx-2
                    newz = nowz
                    opwall=(nowx-1,nowy,nowz)
                if move == 'b':
                    newy = nowy+2
                    newx = nowx
                    newz = nowz
                    opwall=(nowx,nowy+1,nowz)
                if move == 'r':
                    newy = nowy
                    newx = nowx+2
                    newz = nowz
                    opwall=(nowx+1,nowy,nowz)
                if move == 'u':
                    newy = nowy
                    newx = nowx
                    newz = nowz+2
                    opwall=(nowx,nowy,nowz+1)
                if move == 'd':
                    newy = nowy
                    newx = nowx
                    newz = nowz-2
                    opwall=(nowx,nowy,nowz-1)
                # 如果选中的邻居没有被访问:
                if maze_map[newx][newy][newz] == CELL_NO_VISIT:
                    #   1。移除当前单元格和所选邻居之间的墙。
                    if opwall:
                        maze_map[opwall[0]][opwall[1]][opwall[2]] = NOWALL
                    #   2。标记被选中的邻居已被拜访过。
                    if move == '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[newx][newy][newz]=STAIRS_U
                    elif move == '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[newx][newy][newz]=STAIRS_D
                    else:
                        maze_map[newx][newy][newz]=CELL_VISIT
                    #   3。使选择的邻居成为当前单元格。
                    nowx=newx
                    nowy=newy
                    nowz=newz
                    notusegrids.remove((newx,newy,newz))
                else:
                    # 使选择的邻居成为当前单元格。
                    nowx=newx
                    nowy=newy
                    nowz=newz
        # 画
        draw_maze(maze_map, levels, rows, cols, (nowx, nowy, nowz), not notusegrids)
        time_passed = clock.tick(30)
        pygame.display.update()
    return


# main
if __name__ == "__main__":
    '''main'''
    aldous_broder_maze_demo(4, 11, 15)


maze_def.py

链接地址
maze_def.py

maze.py

链接地址
maze.py

draw_maze.py

链接地址
draw_maze.py

GIF演示

2层迷宫

3层迷宫

gif演示

4层迷宫

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