本篇文章禁止转载

算法介绍

英文说明原文

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。使选择的邻居成为当前单元格。

可以随机移到任务格子，生成迷宫时比较花费时间。

生成的迷宫图

在这里插入图片描述

Python代码

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
#!/usr/bin/python3.7
# -*- coding: utf-8 -*-
import random
import pygame

#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(rows, cols):
    # 墙 [0]表示格子访问标记，右[1]竖墙，下[2]横墙
    # (最左和最上墙不能打通，r,c右和r,c+1左共用墙。下墙同理)
    # 初始化未访问，墙未打通
    grids=[[ [0,0,0] for i in range(cols)]for j in range(rows)]
    # Aldous-Broder算法
    # Aldous-Broder算法也生成统一的生成树。
    # 1。选择一个随机的单元格作为当前单元格，并将其标记为已访问的。
    # 2。当存在未访问细胞时:
    #       1。随机选择一个邻居。
    #       2。如果选中的邻居没有被访问:
    #           1。移除当前单元格和所选邻居之间的墙。
    #           2。标记被选中的邻居已被拜访过。
    #       3。使选择的邻居成为当前单元格。

    notusegrids = [] # 没有访问过的格子
    for tr in range(rows):
        for tc in range(cols):
            notusegrids.append((tr,tc))
    # 选择一个随机的单元格作为当前单元格，并将其标记为已访问的。
    r,c = random.choice(notusegrids)
    # 标记迷宫
    grids[r][c][0]=1
    notusegrids.remove((r,c))
    # 当存在未访问细胞时:
    while notusegrids:
        directions = []
        # 可随机方向
        if r > 0:
            directions.append('u')
        if c > 0:
            directions.append('l')
        if r < rows-1:
            directions.append('d')
        if c < cols-1:
            directions.append('r')
        if len(directions):
            # 随机一个方向
            move = random.choice(directions)
            if move == 'u':
                newr = r-1
                newc = c
                nextgrid=(newr, newc)
                opwall=(newr, newc, 2)
            if move == 'l':
                newr = r
                newc = c-1
                nextgrid=(newr, newc)
                opwall=(newr, newc, 1)
            if move == 'd':
                newr = r+1
                newc = c
                nextgrid=(newr, newc)
                opwall=(r, c, 2)
            if move == 'r':
                newr = r
                newc = c+1
                nextgrid=(newr, newc)
                opwall=(r, c, 1)
                
            # 如果选中的邻居没有被访问:
            if grids[newr][newc][0] == 0:
                #   1。移除当前单元格和所选邻居之间的墙。
                #   2。标记被选中的邻居已被拜访过。
                #   3。使选择的邻居成为当前单元格。
                grids[newr][newc][0]=1
                notusegrids.remove((newr,newc))
                grids[opwall[0]][opwall[1]][opwall[2]] = 1
                r=newr
                c=newc   
            else:
                # 使选择的邻居成为当前单元格。
                r=newr
                c=newc 

    return grids


    
# main
if __name__ == "__main__":
    '''main'''
    aldous_broder_maze(20, 30)

演示代码

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
#!/usr/bin/python3.7
# -*- coding: utf-8 -*-
import random
import pygame
#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。使选择的邻居成为当前单元格。

# pygame
pygame.init()  # 初始化pygame
size = width, height = 800, 600  # 设置窗口大小
screen = pygame.display.set_mode(size)  # 显示窗口
# 颜色
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: (100, 100, 100),
}
# 格子大小
DIAMOND_SIZE = (20, 20)
# 蓝格子
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_GREY=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_GREY.fill(COLOR[COLOR_GREY])

# 字体
use_font = pygame.font.Font("FONT.TTF", 16)
# 行列
num_cols=30 #
num_rows=20 #
# 背景
background=pygame.surface.Surface(((num_cols ) * DIAMOND_SIZE[0] + 2 , (num_rows ) * DIAMOND_SIZE[1] + 2)).convert()
background.fill(COLOR[COLOR_BLUE])
# 时间
clock = pygame.time.Clock()

##############################################
#   格子访问标记x,y,0，右墙x,y,1，下墙x,y,2
##############################################


# 
def add2maze(grids, notusegrids, tgrids, twalls):
    for (r,c) in tgrids:
        notusegrids.remove((r,c))
        grids[r][c][0]=1
    for (r,c,x) in twalls:
        grids[r][c][x]=1 
    return 

# 随机格子
def aldous_broder_maze_demo(rows, cols):
        # 墙 [0]表示格子访问标记，右[1]竖墙，下[2]横墙
    # (最左和最上墙不能打通，r,c右和r,c+1左共用墙。下墙同理)
    # 初始化未访问，墙未打通
    grids=[[ [0,0,0] for i in range(cols)]for j in range(rows)]
    # Aldous-Broder算法
    # Aldous-Broder算法也生成统一的生成树。
    # 1。选择一个随机的单元格作为当前单元格，并将其标记为已访问的。
    # 2。当存在未访问细胞时:
    #       1。随机选择一个邻居。
    #       2。如果选中的邻居没有被访问:
    #           1。移除当前单元格和所选邻居之间的墙。
    #           2。标记被选中的邻居已被拜访过。
    #           3。使选择的邻居成为当前单元格。

    notusegrids = [] # 没有访问过的格子
    for tr in range(rows):
        for tc in range(cols):
            notusegrids.append((tr,tc))
    # 选择一个随机的单元格作为当前单元格，并将其标记为已访问的。
    r,c = random.choice(notusegrids)
    # 标记迷宫
    grids[r][c][0]=1
    notusegrids.remove((r,c))
    
    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                return
        # 当存在未访问细胞时:
        if  notusegrids:
            directions = []
            # 可随机方向
            if r > 0:
                directions.append('u')
            if c > 0:
                directions.append('l')
            if r < rows-1:
                directions.append('d')
            if c < cols-1:
                directions.append('r')
            if len(directions):
                # 随机一个方向
                move = random.choice(directions)
                if move == 'u':
                    newr = r-1
                    newc = c
                    nextgrid=(newr, newc)
                    opwall=(newr, newc, 2)
                if move == 'l':
                    newr = r
                    newc = c-1
                    nextgrid=(newr, newc)
                    opwall=(newr, newc, 1)
                if move == 'd':
                    newr = r+1
                    newc = c
                    nextgrid=(newr, newc)
                    opwall=(r, c, 2)
                if move == 'r':
                    newr = r
                    newc = c+1
                    nextgrid=(newr, newc)
                    opwall=(r, c, 1)
                    
                # 如果选中的邻居没有被访问:
                if grids[newr][newc][0] == 0:
                    #   1。移除当前单元格和所选邻居之间的墙。
                    #   2。标记被选中的邻居已被拜访过。
                    #   3。使选择的邻居成为当前单元格。
                    grids[newr][newc][0]=1
                    notusegrids.remove((newr,newc))
                    grids[opwall[0]][opwall[1]][opwall[2]] = 1
                    r=newr
                    c=newc   
                else:
                    # 使选择的邻居成为当前单元格。
                    r=newr
                    c=newc 

        screen.blit(background, (0, 0))
        # 格子
        for cx in range(num_cols):
            for ry in range(num_rows):
                px,py=1 + (cx) * DIAMOND_SIZE[0], 1 + (ry) * DIAMOND_SIZE[1]
                # 标记访问过的格子
                if grids[ry][cx][0]:
                    screen.blit(DIAMOND, (px, py))
                else:
                    screen.blit(DIAMOND_GREY, (px, py))
        if notusegrids:
            px,py=1 + (c) * DIAMOND_SIZE[0], 1 + (r) * DIAMOND_SIZE[1]
            screen.blit(DIAMOND_GREEN, (px, py))

        # 画外墙
        pygame.draw.rect(screen, COLOR[COLOR_RED], (0, 0, 20*num_cols+1, 20*num_rows+1), 2)
        # 画没打通的墙
        for cx in range( num_cols):
            for ry in range(num_rows):
                px,py=21 + (cx) * DIAMOND_SIZE[0], 21 + (ry) * DIAMOND_SIZE[1]
                color = COLOR[COLOR_BLACK]
                if not grids[ry][cx][1]:
                    pygame.draw.line(screen, color, (px, py-20), (px, py), 2)
                if not grids[ry][cx][2]:
                    pygame.draw.line(screen, color, (px-20, py), (px, py), 2)

        # 
        if not notusegrids:
            score_surface = use_font.render("生成完成！", True, COLOR[COLOR_BLACK], COLOR[COLOR_GREY])
            screen.blit(score_surface, (50, num_rows*22))
        
        time_passed = clock.tick(30)

        pygame.display.update()
    return 



# main
if __name__ == "__main__":
    '''main'''
    aldous_broder_maze_demo(20, 30)

GIF演示

在这里插入图片描述

参考

https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_depth-first_search

http://weblog.jamisbuck.org/2011/1/17/maze-generation-aldous-broder-algorithm

访问时可能需要梯子

上一篇：迷宫生成算法(Wilson‘s algorithm)

迷宫生成算法(Wilson‘s algorithm)