本篇文章禁止转载

思路介绍

  • 在已有的单路径迷宫基础上打开一块合适的墙就可以构成2路径的迷宫。

  • 打开的墙不能和已有的路径过近。

  • 1。从开始和终点开始进行广度优先搜索，并为迷宫中的每个单元格记录单元格远离开始和终点的步数。

  • 2。通过将距离开头较近的所有单元格放入 start 集合，并将更接近目标的所有单元格放入end集合来将迷宫分成两个部分。
  • 3。 选择分开两个区域的任意一面墙拆开就可以形成2通路的迷宫。
  • 如想生成最短的通路可以选择相邻格子距离差值最大的那面墙拆开，一般情况下这两条路距离也比较远。

    分区图

    在这里插入图片描述

    分区域演示代码

    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
    256
    257
    258
    259
    260
    261
    262
    263
    264
    265
    266
    267
    268
    269
    270
    271
    272
    273
    274
    275
    276
    277
    278
    279
    280
    281
    282
    283
    284
    285
    286
    287
    288
    289
    290
    291
    292
    293
    294
    295
    296
    297
    298
    299
    300
    301
    302
    303
    304
    305
    306
    307
    308
    309
    310
    311
    312
    313
    314
    315
    316
    317
    318
    319
    320
    321
    322
    323
    324
    325
    326
    327
    328
    329
    330
    331
    332
    333
    334
    335
    #!/usr/bin/python3.7
    # -*- coding: utf-8 -*-
    import random
    import pygame
    #import depth_maze
    import maze
    #import aldous_broder_maze

    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_LEN = 20
    DIAMOND_SIZE = (DIAMOND_LEN, DIAMOND_LEN)
    # 蓝格子
    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)
    use_font12 = pygame.font.Font("FONT.TTF", 12)
    # 背景
    background=pygame.surface.Surface(size).convert()
    background.fill(COLOR[COLOR_BLACK])
    # 文字
    score_surface = use_font.render("找到终点", True, COLOR[COLOR_BLACK], COLOR[COLOR_GREY])
    # 时间
    clock = pygame.time.Clock()

    ##############################################
    #   格子访问标记x,y,0，右墙x,y,1，下墙x,y,2
    ##############################################
    #标记 
    NOWALL=maze.NOWALL # 无墙
    WALL=maze.WALL  # 有墙
    WALL2=maze.WALL2  # 有墙

    VISIT=maze.VISIT # 到访过
    NOVISIT=maze.NOVISIT # 没到过
    VERTICAL = maze.VERTICAL # 垂直的
    HORIZONTAL = maze.HORIZONTAL# 水平的
    INFINITE = maze.INFINITE # 无穷远

    INFINITE = maze.INFINITE # 无穷远

    # 
    def FindNext(pathList, walls, grids, rows, cols):
        nextList = [] # 下一步
        for node in pathList:
            r, c = node
            l = grids[r][c]
            nl=l+1
            # 可以到达的位置
            if r>0 and NOWALL == walls[r][c][1] and INFINITE == grids[r-1][c]:
                # move = 'u'
                nr=r-1
                nc=c
                if (nr,nc) not in nextList:
                    nextList.append((nr,nc))
                    grids[nr][nc] = l+1
            if c>0 and NOWALL == walls[r][c][0] and INFINITE == grids[r][c-1]:
                # move = 'l'
                nr=r
                nc=c-1
                if (nr,nc) not in nextList:
                    nextList.append((nr,nc))
                    grids[nr][nc] = l+1
            if c<cols-1 and NOWALL == walls[r][c+1][0] and INFINITE == grids[r][c+1] :
                # move='r'
                nr=r
                nc=c+1
                if (nr,nc) not in nextList:
                    nextList.append((nr,nc))
                    grids[nr][nc] = l+1
            if r<rows-1 and NOWALL == walls[r+1][c][1] and INFINITE == grids[r+1][c] :
                # move='d'
                nr=r+1
                nc=c
                if (nr,nc) not in nextList:
                    nextList.append((nr,nc))
                    grids[nr][nc] = l+1
        return nextList


    def draw_diamond(r,c, screen, POSX, POSY, diamod):
        px,py=POSX + 1 + (c) * DIAMOND_SIZE[0], POSY + 1 + (r) * DIAMOND_SIZE[1]
        # 标记访问过的格子
        screen.blit(diamod, (px, py))
        return 

    def draw_diamond_and_str(r,c, screen, POSX, POSY, diamod, use_font, string, color, color_back):
        px,py=POSX + 1 + (c) * DIAMOND_SIZE[0], POSY + 1 + (r) * DIAMOND_SIZE[1]
        # 标记访问过的格子
        screen.blit(diamod, (px, py))
        distance_surface = use_font.render(string, True, color, color_back)
        screen.blit(distance_surface, (px, py))
        return 


    # Sample algorithm
    def multipath_maze_demo(rows, cols):
        #walls = maze.aldous_broder_maze(rows, cols)
        #walls = maze.depth_maze(rows, cols)
        #walls = maze.kruskal_maze(rows, cols)
        #walls = maze.prim_maze(rows, cols)
        #walls = maze.wilson_maze(rows, cols)
        walls = maze.wilson_maze(rows, cols)
        POSX=40
        POSY=40
        # 初始化未访问
        grids=[[ INFINITE for i in range(cols)]for j in range(rows)]
        # 起点
        # 标记迷宫
        r=0
        c=0
        findEndPoint=False
        findPath=False
        # 起点
        startPoint=(r,c)
        # 终点
        stopPoint=(rows-1,cols-1)
        # 
        mainList=[] # 主路径

        beginList=[startPoint]
        endList=[stopPoint]
        grids[r][c]=0 # 标记已经到过格子距离
        grids[stopPoint[0]][stopPoint[1]]=0

        # 没有访问过的格子
        notUseGrids = [] 
        for tr in range(rows):
            for tc in range(cols):
                notUseGrids.append((tr,tc))

        beginMap=beginList
        endMap=endList

        while True:
            for event in pygame.event.get():
                if event.type == pygame.QUIT:
                    return
            if notUseGrids:        
                beginNextList = [] # 下一步
                for node in beginList:
                    r, c = node
                    l = grids[r][c]
                    # 可以到达的位置
                    if r>0 and NOWALL == walls[r][c][1] and INFINITE == grids[r-1][c]:
                        # move = 'u'
                        nr=r-1
                        nc=c
                        if (nr,nc) not in beginNextList:
                            beginNextList.append((nr,nc))
                            grids[nr][nc] = l+1
                    if c>0 and NOWALL == walls[r][c][0] and INFINITE == grids[r][c-1]:
                        # move = 'l'
                        nr=r
                        nc=c-1
                        if (nr,nc) not in beginNextList:
                            beginNextList.append((nr,nc))
                            grids[nr][nc] = l+1
                    if c<cols-1 and NOWALL == walls[r][c+1][0] and INFINITE == grids[r][c+1] :
                        # move='r'
                        nr=r
                        nc=c+1
                        if (nr,nc) not in beginNextList:
                            beginNextList.append((nr,nc))
                            grids[nr][nc] = l+1
                    if r<rows-1 and NOWALL == walls[r+1][c][1] and INFINITE == grids[r+1][c] :
                        # move='d'
                        nr=r+1
                        nc=c
                        if (nr,nc) not in beginNextList:
                            beginNextList.append((nr,nc))
                            grids[nr][nc] = l+1
                # 下一圈
                beginList = beginNextList
                beginMap = beginMap + beginNextList
                # end
                endNextList = [] # 下一步
                for node in endList:
                    r, c = node
                    l = grids[r][c]
                    # 可以到达的位置
                    if r>0 and NOWALL == walls[r][c][1] and INFINITE == grids[r-1][c]:
                        # move = 'u'
                        nr=r-1
                        nc=c
                        if (nr,nc) not in endNextList:
                            endNextList.append((nr,nc))
                            grids[nr][nc] = l+1
                    if c>0 and NOWALL == walls[r][c][0] and INFINITE == grids[r][c-1]:
                        # move = 'l'
                        nr=r
                        nc=c-1
                        if (nr,nc) not in endNextList:
                            endNextList.append((nr,nc))
                            grids[nr][nc] = l+1
                    if c<cols-1 and NOWALL == walls[r][c+1][0] and INFINITE == grids[r][c+1] :
                        # move='r'
                        nr=r
                        nc=c+1
                        if (nr,nc) not in endNextList:
                            endNextList.append((nr,nc))
                            grids[nr][nc] = l+1
                    if r<rows-1 and NOWALL == walls[r+1][c][1] and INFINITE == grids[r+1][c] :
                        # move='d'
                        nr=r+1
                        nc=c
                        if (nr,nc) not in endNextList:
                            endNextList.append((nr,nc))
                            grids[nr][nc] = l+1
                # 下一圈
                endList = endNextList
                endMap = endMap + endNextList

            elif findEndPoint and not findPath:
                mainList.append((r,c))
                l = grids[r][c]
                nl=l-1
                # 最近的
                if r>0 and NOWALL == walls[r][c][1] and nl == grids[r-1][c]:
                    # move = 'u'
                    nr=r-1
                    nc=c
                if c>0 and NOWALL == walls[r][c][0] and nl == grids[r][c-1]:
                    # move = 'l'
                    nr=r
                    nc=c-1
                    beginNextList.append((nr,nc))
                if c<cols-1 and NOWALL == walls[r][c+1][0] and nl == grids[r][c+1] :
                    # move='r'
                    nr=r
                    nc=c+1
                if r<rows-1 and NOWALL == walls[r+1][c][1] and nl == grids[r+1][c] :
                    # move='d'
                    nr=r+1
                    nc=c
                # 找到起点
                if 0 == nl:
                    mainList.append((nr,nc))
                    findPath = True
                r,c=nr,nc

            screen.blit(background, (0, 0))
            # 格子
            for cx in range(cols):
                for ry in range(rows):
                    px,py=POSX + 1 + (cx) * DIAMOND_SIZE[0], POSY + 1 + (ry) * DIAMOND_SIZE[1]
                    # 标记访问过的格子
                    if maze.INFINITE == grids[ry][cx]:
                        draw_diamond(ry, cx, screen, POSX, POSY, DIAMOND)
                    else:
                        s = "{}".format(grids[ry][cx])
                        draw_diamond_and_str(ry, cx, screen, POSX,POSY, DIAMOND_GREY, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_GREY]) 
            # 圈地
            for pos in beginMap:
                s = "{}".format(grids[pos[0]][pos[1]])
                draw_diamond_and_str(pos[0], pos[1], screen, POSX,POSY, DIAMOND_GREEN, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_GREEN])
            for pos in endMap:
                s = "{}".format(grids[pos[0]][pos[1]])
                draw_diamond_and_str(pos[0], pos[1], screen, POSX,POSY, DIAMOND_YELLOW, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_YELLOW])
            # 循环外圈
            if beginList and not mainList:
                for pos in beginList:
                    s = "{}".format(grids[pos[0]][pos[1]])
                    draw_diamond_and_str(pos[0], pos[1], screen, POSX,POSY, DIAMOND_RED, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_RED])
                for pos in endList:
                    s = "{}".format(grids[pos[0]][pos[1]])
                    draw_diamond_and_str(pos[0], pos[1], screen, POSX,POSY, DIAMOND_RED, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_RED])
            # 路径
            if mainList:
                for pos in mainList:
                    s = "{}".format(grids[pos[0]][pos[1]])
                    draw_diamond_and_str(pos[0], pos[1], screen, POSX,POSY, DIAMOND_YELLOW, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_YELLOW])
                # r,c
                px,py=POSX + 1 + (c) * DIAMOND_SIZE[0], POSY + 1 + (r) * DIAMOND_SIZE[1]
                screen.blit(DIAMOND_GREEN, (px, py))
                s = "{}".format(grids[r][c])
                distance_surface = use_font12.render(s, True, COLOR[COLOR_BLACK], COLOR[COLOR_GREEN])
                screen.blit(distance_surface, (px, py))

            # 画外墙
            pygame.draw.rect(screen, COLOR[COLOR_RED], (POSX + 0, POSY + 0, DIAMOND_LEN*cols+1, DIAMOND_LEN*rows+1), 2)
            # 画没打通的墙
            for cx in range( cols):
                for ry in range(rows):
                    px,py=POSX + 1 + (cx) * DIAMOND_SIZE[0], POSY + 1 + (ry) * DIAMOND_SIZE[1]
                    color = COLOR[COLOR_BLACK]
                    if maze.WALL == walls[ry][cx][0]:
                        pygame.draw.line(screen, color, (px, py), (px, py+DIAMOND_LEN), 2)
                    if maze.WALL == walls[ry][cx][1]:
                        pygame.draw.line(screen, color, (px, py), (px+DIAMOND_LEN, py), 2)
            # 打印文字提示
            if findEndPoint:
                screen.blit(score_surface, (POSX+50, POSY+rows*22))
            # 帧率
            clock.tick(25)

            pygame.display.update()
        return 



    # main
    if __name__ == "__main__":
        '''main'''
        multipath_maze_demo(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
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
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
#!/usr/bin/python3.7
# -*- coding: utf-8 -*-
import random
import pygame
import maze

pygame.init()  # 初始化pygame
size = width, height = 800, 600  # 设置窗口大小
screen = pygame.display.set_mode(size)  # 显示窗口
# 颜色
diamond_color_size = 12
COLOR_RED, COLOR_BLUE, COLOR_GREEN, COLOR_YELLOW, COLOR_BLACK, COLOR_FLAXEN, COLOR_GOLD, COLOR_GRAY, COLOR_PINK, COLOR_ORANGE, COLOR_WHEAT, COLOR_CYAN = 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_FLAXEN: (250, 240, 230), # 亚麻
    COLOR_GOLD : (255,215,0), # 金
    COLOR_GRAY: (128,128,128), # 灰
    COLOR_PINK:(255,192,203), # 粉
    COLOR_ORANGE: (255,165,0),# 橙
    COLOR_WHEAT: (245,222,179),# 小麦
    COLOR_CYAN : (0,255,255), # 青
}
# 格子大小
DIAMOND_LEN = 20
DIAMOND_SIZE = (DIAMOND_LEN, DIAMOND_LEN)
# 蓝格子
DIAMOND_BULE=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_BULE.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_FLAXEN])

# 各色的格子
DIAMONDS=[]
for x in range(diamond_color_size):
    diamoand=pygame.surface.Surface(DIAMOND_SIZE).convert()
    diamoand.fill(COLOR[x])
    DIAMONDS.append(diamoand)

# 字体
use_font = pygame.font.Font("FONT.TTF", 16)
use_font12 = pygame.font.Font("FONT.TTF", 12)
# 背景
background=pygame.surface.Surface(size).convert()
background.fill(COLOR[COLOR_BLACK])
# 文字
score_surface = use_font.render("找到终点", True, COLOR[COLOR_BLACK], COLOR[COLOR_FLAXEN])
# 时间
clock = pygame.time.Clock()

#标记 
NOWALL=maze.NOWALL # 无墙
WALL=maze.WALL  # 有墙
WALL2=maze.WALL2  # 有墙
VISIT=maze.VISIT # 到访过
NOVISIT=maze.NOVISIT # 没到过
VERTICAL = maze.VERTICAL # 垂直的
HORIZONTAL = maze.HORIZONTAL# 水平的
INFINITE = maze.INFINITE # 无穷远


# 下一圈
def FindNextCircle(startList, walls, grids, rows, cols):
    startNextList = [] # 下一步
    for node in startList:
        r, c = node
        l = grids[r][c]
        # 可以到达的位置
        if r>0 and NOWALL == walls[r][c][1] and INFINITE == grids[r-1][c]:
            # move = 'u'
            nr=r-1
            nc=c
            if (nr,nc) not in startNextList:
                startNextList.append((nr,nc))
                grids[nr][nc] = l+1
        if c>0 and NOWALL == walls[r][c][0] and INFINITE == grids[r][c-1]:
            # move = 'l'
            nr=r
            nc=c-1
            if (nr,nc) not in startNextList:
                startNextList.append((nr,nc))
                grids[nr][nc] = l+1
        if c<cols-1 and NOWALL == walls[r][c+1][0] and INFINITE == grids[r][c+1] :
            # move='r'
            nr=r
            nc=c+1
            if (nr,nc) not in startNextList:
                startNextList.append((nr,nc))
                grids[nr][nc] = l+1
        if r<rows-1 and NOWALL == walls[r+1][c][1] and INFINITE == grids[r+1][c] :
            # move='d'
            nr=r+1
            nc=c
            if (nr,nc) not in startNextList:
                startNextList.append((nr,nc))
                grids[nr][nc] = l+1
    # 下一圈
    startList.clear()
    startList.extend(startNextList)
    return startList


# 画方块
def draw_diamond(r, c, screen, diamod):
    px,py= 1 + (c) * DIAMOND_SIZE[0], 1 + (r) * DIAMOND_SIZE[1]
    screen.blit(diamod, (px, py))
    return 


# 画方块和字符串string
def draw_diamond_and_str(r, c, screen, diamod, use_font, string, color, color_back):
    px,py= 1 + (c) * DIAMOND_SIZE[0], 1 + (r) * DIAMOND_SIZE[1]
    screen.blit(diamod, (px, py))
    distance_surface = use_font.render(string, True, color, color_back)
    screen.blit(distance_surface, (px, py))
    return 


# 拆分迷宫
def split_maze(walls, grids, startPoint, endPoint, startMap, endMap, rows, cols):
    startList = [startPoint]
    endList = [endPoint]
    startMap.append(startPoint)
    endMap.append(endPoint)
    while startList or endList:
        split_maze_step(walls, grids, startList, endList, startMap, endMap, rows, cols)
    return startMap, endMap


# 一步一步执行
def split_maze_step(walls, grids, startList, endList, startMap, endMap, rows, cols):
    # 起点
    FindNextCircle(startList, walls, grids, rows, cols)
    startMap+=startList
    # 终点
    FindNextCircle(endList, walls, grids, rows, cols)
    endMap+=endList
    return startList, endList



def find_partition_walls(walls, grids, startMap, endMap, rows, cols):
    tmp_grids=[[ 'e' for i in range(cols)]for j in range(rows)]
    for s in startMap:
        tmp_grids[s[0]][s[1]] = 's'
    part = []
    # 找到分隔两部分的墙
    for r in range(rows):
        for c in range(cols):
            if WALL == walls[r][c][0] and c > 0:
                if tmp_grids[r][c-1] != tmp_grids[r][c]:
                    part.append((r,c,0))
            if WALL == walls[r][c][1] and r > 0:
                if tmp_grids[r-1][c] != tmp_grids[r][c]:
                    part.append((r,c,1))
    return part


# 随机拆一个合适的墙
def random_down_wall(walls, grids, startMap, endMap, rows, cols):
    # 找到墙
    parts = find_partition_walls(walls, grids, startMap, endMap, rows, cols)
    swr, swc, swd = random.choice(parts)
    walls[swr][swc][swd] = NOWALL
    parts.remove((swr, swc, swd))
    return walls


# 差值最大的墙
def find_diff_partition_wall(walls, grids, startMap, endMap, rows, cols):
    tmp_grids=[[ 'e' for i in range(cols)]for j in range(rows)]
    for s in startMap:
        tmp_grids[s[0]][s[1]] = 's'
    wall = None
    l = 0
    # 找到分隔两部分的墙
    for r in range(rows):
        for c in range(cols):
            if WALL == walls[r][c][0] and c > 0:
                if tmp_grids[r][c-1] != tmp_grids[r][c]:
                    if l < abs(grids[r][c-1] - grids[r][c]):
                        wall = (r,c,0)
                        l = abs(grids[r][c-1] - grids[r][c])
            if WALL == walls[r][c][1] and r > 0:
                if tmp_grids[r-1][c] != tmp_grids[r][c]:
                    if l < abs(grids[r-1][c] - grids[r][c]):
                        wall = (r,c,1)
                        l = abs(grids[r-1][c] - grids[r][c])
    return wall

# 拆两边差值最大的墙
def diff_down_wall(walls, grids, startMap, endMap, rows, cols):
    # 找到墙
    wall = find_diff_partition_wall(walls, grids, startMap, endMap, rows, cols)
    swr, swc, swd = wall
    walls[swr][swc][swd] = NOWALL
    return walls



# Sample algorithm
def multipath_maze_demo(rows, cols):
    maze_h = rows * DIAMOND_SIZE[0] + 1
    maze_w = cols * DIAMOND_SIZE[0] + 1
    size = (maze_w, maze_h)
    maze_surface=pygame.surface.Surface(size).convert()
    #walls = maze.aldous_broder_maze(rows, cols)
    #walls = maze.depth_maze(rows, cols)
    #walls = maze.kruskal_maze(rows, cols)
    #walls = maze.prim_maze(rows, cols)
    #walls = maze.wilson_maze(rows, cols)
    walls = maze.wilson_maze(rows, cols)
    POSX=40
    POSY=40
    # 初始化未访问
    grids=[[ INFINITE for i in range(cols)]for j in range(rows)]
    # 起点
    # 标记迷宫
    r=0
    c=0
    findEndPoint=False
    findPath=False
    secondWay=False
    # 起点
    startPoint=(r,c)
    # 终点
    endPoint=(rows-1,cols-1)
    mainList=[] # 主路径
    # 
    startList=[startPoint]
    endList=[endPoint]
    grids[startPoint[0]][startPoint[1]]=0 # 标记已经到过格子距离
    grids[endPoint[0]][endPoint[1]]=0
    # 没有访问过的格子
    notUseGrids = [] 
    for tr in range(rows):
        for tc in range(cols):
            notUseGrids.append((tr,tc))
    # 
    startMap=[]
    endMap=[]
    startMap += startList
    endMap += endList
    # 
    parts = []
    rand_wall = None
    diff_wall = None
    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                return
        if startList or endList:    
            # 分区
            # python 传参是引用传递 （不可改变参数指向，可改变参数的内部值。）
            # 可变对象：列表，字典（当参数时，函数内部的修改可以带出外部；但是赋值操作不能带出，此时的赋值操作相当于不可变对象的赋值）
            # 不可变的对象：数字，元组，字符串（当参数时，函数内部的修改不能带出；不可变对象修改值时相当于修改指向地址。）
            split_maze_step(walls, grids, startList, endList, startMap, endMap, rows, cols)
            # 
            # split_maze(walls, grids, startPoint, endPoint, startMap, endMap, rows, cols)
        elif not secondWay:
            parts = find_partition_walls(walls, grids, startMap, endMap, rows, cols)
            # 拆近路
            # diff_down_wall(walls, grids, startMap, endMap, rows, cols)
            diff_wall = find_diff_partition_wall(walls, grids, startMap, endMap, rows, cols)
            swr, swc, swd = diff_wall
            parts.remove((swr, swc, swd))
            # walls[swr][swc][swd] = NOWALL

            # 随机拆
            # random_down_wall(walls, grids, startMap, endMap, rows, cols)
            # parts = find_partition_walls(walls, grids, startMap, endMap, rows, cols)
            rand_wall = random.choice(parts)
            swr, swc, swd = rand_wall
            parts.remove((swr, swc, swd))
            # walls[swr][swc][swd] = NOWALL
            secondWay = True
        else:
            findPath
        # 背景
        screen.blit(background, (0, 0))
        # maze_surface
        # 格子
        for cx in range(cols):
            for ry in range(rows):
                # 标记访问过的格子
                if maze.INFINITE == grids[ry][cx]:
                    draw_diamond(ry, cx, maze_surface, DIAMONDS[COLOR_GRAY])
                else:
                    s = "{}".format(grids[ry][cx])
                    draw_diamond_and_str(ry, cx, maze_surface, DIAMOND_GRAY, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_FLAXEN]) 
        # 圈地
        for pos in startMap:
            s = "{}".format(grids[pos[0]][pos[1]])
            draw_diamond_and_str(pos[0], pos[1], maze_surface, DIAMONDS[COLOR_WHEAT], use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_WHEAT])
        for pos in endMap:
            s = "{}".format(grids[pos[0]][pos[1]])
            draw_diamond_and_str(pos[0], pos[1], maze_surface, DIAMONDS[COLOR_FLAXEN], use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_FLAXEN])
        # 循环外圈
        if startList and not mainList:
            for pos in startList:
                s = "{}".format(grids[pos[0]][pos[1]])
                draw_diamond_and_str(pos[0], pos[1], maze_surface, DIAMOND_RED, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_RED])
            for pos in endList:
                s = "{}".format(grids[pos[0]][pos[1]])
                draw_diamond_and_str(pos[0], pos[1], maze_surface, DIAMOND_RED, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_RED])
        # 路径
        if mainList:
            for pos in mainList:
                s = "{}".format(grids[pos[0]][pos[1]])
                draw_diamond_and_str(pos[0], pos[1], maze_surface, DIAMOND_YELLOW, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_YELLOW])
            # r,c
            s = "{}".format(grids[pos[0]][pos[1]])
            draw_diamond_and_str(r, c, maze_surface, DIAMOND_GREEN, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_GREEN])
        # 画外墙
        pygame.draw.rect(maze_surface, COLOR[COLOR_RED], (0, 0, DIAMOND_LEN*cols+1, DIAMOND_LEN*rows+1), 2)
        # 画没打通的墙
        DrawWalls(maze_surface, DIAMOND_SIZE, walls, rows, cols)
        # 
        if parts:
            DrawWallList(maze_surface, COLOR[COLOR_RED], DIAMOND_SIZE, parts, rows, cols)
            DrawWallList(maze_surface, COLOR[COLOR_GREEN], DIAMOND_SIZE, [rand_wall], rows, cols)
            DrawWallList(maze_surface, COLOR[COLOR_CYAN], DIAMOND_SIZE, [diff_wall], rows, cols)

        # 贴maze
        screen.blit(maze_surface, (POSX, POSY))

        # 打印文字提示
        if findEndPoint:
            screen.blit(score_surface, (POSX+50, POSY+rows*22))
        # 帧率
        clock.tick(25)

        pygame.display.update()
    return 

# 
def DrawWalls(screen, DIAMOND_SIZE, walls, rows, cols):
    for cx in range( cols):
        for ry in range(rows):
            px,py = 1 + (cx) * DIAMOND_SIZE[0], 1 + (ry) * DIAMOND_SIZE[1]
            color = COLOR[COLOR_BLACK]
            if maze.WALL == walls[ry][cx][0]:
                pygame.draw.line(screen, color, (px, py), (px, py+DIAMOND_LEN), 2)
            if maze.WALL == walls[ry][cx][1]:
                pygame.draw.line(screen, color, (px, py), (px+DIAMOND_LEN, py), 2)
    return 

# 
def DrawWallList(screen, color, DIAMOND_SIZE, wlist, rows, cols):
    for r,c,d in wlist:
        px,py = 1 + (c) * DIAMOND_SIZE[0], 1 + (r) * DIAMOND_SIZE[1]
        if d == 0:
            pygame.draw.line(screen, color, (px, py), (px, py+DIAMOND_LEN), 2)
        if d == 1:
            pygame.draw.line(screen, color, (px, py), (px+DIAMOND_LEN, py), 2)
    return 


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

多通路迷宫寻路(寻路加找宝箱)

多通路迷宫寻路(寻路加找宝箱)