一、思路介绍
- 在已有的单路径迷宫基础上打开一块合适的墙就可以构成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
|
#!/usr/bin/python3.7# -*- coding: utf-8 -*-import randomimport pygame#import depth_mazeimport maze#import aldous_broder_mazepygame.init() # 初始化pygamesize = width, height = 800, 600 # 设置窗口大小screen = pygame.display.set_mode(size) # 显示窗口# 颜色diamond_color_size = 8COLOR_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 = 20DIAMOND_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 nextListdef 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)) returndef 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 algorithmdef 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# mainif __name__ == "__main__": '''main''' multipath_maze_demo(20, 30) |
到此这篇关于教你怎么用Python实现多路径迷宫的文章就介绍到这了,更多相关Python实现多路径迷宫内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！
原文链接：https://blog.csdn.net/defaultbyzt/article/details/116238007
