服务器之家

服务器之家 > 正文

教你怎么用Python实现多路径迷宫

时间:2021-10-23 15:44     来源/作者:明年十八岁

一、思路介绍

  • 在已有的单路径迷宫基础上打开一块合适的墙就可以构成2路径的迷宫。
  • 打开的墙不能和已有的路径过近。
  • 1。从开始和终点开始进行广度优先搜索,并为迷宫中的每个单元格记录单元格远离开始和终点的步数。
  • 2。通过将距离开头较近的所有单元格放入 start 集合,并将更接近目标的所有单元格放入end集合来将迷宫分成两个部分。
  • 3。 选择分开两个区域的任意一面墙拆开就可以形成2通路的迷宫。
  • 如想生成最短的通路可以选择相邻格子距离差值最大的那面墙拆开,一般情况下这两条路距离也比较远。

二、图示

教你怎么用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
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 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)

到此这篇关于教你怎么用Python实现多路径迷宫的文章就介绍到这了,更多相关Python实现多路径迷宫内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家!

原文链接:https://blog.csdn.net/defaultbyzt/article/details/116238007

标签:

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
2021年耽改剧名单 2021要播出的59部耽改剧列表
2021年耽改剧名单 2021要播出的59部耽改剧列表 2021-03-05
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部