本篇文章禁止转载

(深度优先搜索)

算法介绍

介绍

1。访问起点；
2。依次从起点的未被访问的邻点出发，对迷宫进行深度优先遍历；直至迷宫中起点有路径相通的格子被访问或者找到终点；

编程思路

  • 1。访问起点，起点加入路径表。
  • 2。找可到达且未访问的相邻点。
    • 如果有：
    • 1。移动到相邻的点
    • 2。设置相邻点为当前点
    • 3。当前点加入路径
    • 4。判断是否为终点，否继续循环。
    • 没有：
    • 1。从路径列表中删除当前点
    • 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
#!/usr/bin/python3.7
# -*- coding: utf-8 -*-
import random
import pygame
#import depth_maze
import kruskal_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_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)
# 背景
background=pygame.surface.Surface(size).convert()
background.fill(COLOR[COLOR_BLACK])
# 时间
clock = pygame.time.Clock()

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

# 

# 深度优先寻路演示代码
def depth_pathfinding(rows, cols, walls, startPoint=(0,0), endPoint=None):
    # walls = depth_maze.depth_maze(rows, cols)
    grids=[[ [0] for i in range(cols)]for j in range(rows)]
    # 标记迷宫
    findEndPoint=False
    # 起点
    r = startPoint[0]
    c = startPoint[1]
    # 终点
    if endPoint:
        stopPoint=endPoint
    else:
        stopPoint=(rows-1,cols-1)

    pathList=[(r,c)] # 路径
    grids[r][c][0]=1 # 1标记已经到过格子
    # 当存在未访问细胞时:
    while pathList and not findEndPoint:        
        move=None
        if r>0 and walls[r][c][1] and 1 != grids[r-1][c][0]:
            move = 'u'
            nr=r-1
            nc=c
        elif c>0 and walls[r][c][0] and 1 != grids[r][c-1][0] :
            move='l'
            nr=r
            nc=c-1
        elif c<cols-1 and walls[r][c+1][0] and 1 != grids[r][c+1][0] :
            move='r'
            nr=r
            nc=c+1
        elif r<rows-1 and walls[r+1][c][1] and 1 != grids[r+1][c][0] :
            move='d'
            nr=r+1
            nc=c
        if move:
            # 加入路径
            pathList.append((r,c))
            # move到下个点
            r=nr
            c=nc
            if (r,c) == stopPoint:
                # 终点加入路径
                pathList.append((r,c))
                findEndPoint=True
            else:
                grids[r][c][0]=1
        else:
            (r,c) = pathList.pop()
    return pathList


# 深度优先寻路演示代码
def depth_pathfinding_demo(rows, cols):
    #walls = depth_maze.depth_maze(rows, cols)
    walls = kruskal_maze.kruskal_maze(rows, cols)
    # fpath = depth_pathfinding(rows,cols, walls)
    POSX=40
    POSY=40
    # 墙 [0]表示格子访问标记，左[1]竖墙，上[2]横墙，最右边竖墙和最下边横墙没有记录。
    # (最左和最上墙不能打通，r,c右和r,c+1左共用墙。r,c和r+1,c共用横墙)
    # 初始化未访问，墙未打通
    grids=[[ [0,2,2] for i in range(cols)]for j in range(rows)]
    # 标记迷宫
    r=0
    c=0
    findEndPoint=False
    # 起点
    startPoint=(r,c)
    # 终点
    stopPoint=(rows-1,cols-1)
    pathList=[(r,c)] # 路径
    grids[r][c][0]=1 # 1标记已经到过格子
    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                return
        # 当存在未访问细胞时:
        if  pathList and not findEndPoint:        
            move=None
            if r>0 and walls[r][c][1] and 1 != grids[r-1][c][0]:
                move = 'u'
                nr=r-1
                nc=c
            elif c>0 and walls[r][c][0] and 1 != grids[r][c-1][0] :
                move='l'
                nr=r
                nc=c-1
            elif c<cols-1 and walls[r][c+1][0] and 1 != grids[r][c+1][0] :
                move='r'
                nr=r
                nc=c+1
            elif r<rows-1 and walls[r+1][c][1] and 1 != grids[r+1][c][0] :
                move='d'
                nr=r+1
                nc=c
            if move:
                # 加入路径
                pathList.append((r,c))
                # move到下个点
                r=nr
                c=nc
                if (r,c) == stopPoint:
                    # 终点加入路径
                    pathList.append((r,c))
                    findEndPoint=True
                else:
                    grids[r][c][0]=1
            else:
                (r,c) = pathList.pop()



        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 grids[ry][cx][0]:
                    screen.blit(DIAMOND, (px, py))
                else:
                    screen.blit(DIAMOND_GREY, (px, py))
        
        if pathList:
            # 路径
            for pos in pathList:
                px,py=POSX + 1 + (pos[1]) * DIAMOND_SIZE[0], POSY + 1 + (pos[0]) * DIAMOND_SIZE[1]
                screen.blit(DIAMOND_GREEN, (px, py))
            # 当前r,c 
            px,py=POSX + 1 + (c) * DIAMOND_SIZE[0], POSY + 1 + (r) * DIAMOND_SIZE[1]
            screen.blit(DIAMOND_RED, (px, py))
        # 画外墙
        pygame.draw.rect(screen, COLOR[COLOR_RED], (POSX + 0, POSY + 0, 20*cols+1, 20*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]
                color2 = COLOR[COLOR_GREY]
                color2 = COLOR[COLOR_RED]
                color3 = COLOR[COLOR_GREY]
                if 0 == walls[ry][cx][0]:
                    pygame.draw.line(screen, color, (px, py), (px, py+20), 2)
                if 0 == walls[ry][cx][1]:
                    pygame.draw.line(screen, color, (px, py), (px+20, py), 2)
                #if 2 == walls[ry][cx][0]:
                #    pygame.draw.line(screen, color2, (px, py), (px, py+20), 2)
                #if 2 == walls[ry][cx][1]:
                #    pygame.draw.line(screen, color2, (px, py), (px+20, py), 2)
                #if 1 == walls[ry][cx][0]:
                #    pygame.draw.line(screen, color3, (px, py), (px, py+20), 2)
                #if 1 == walls[ry][cx][1]:
                #    pygame.draw.line(screen, color3, (px, py), (px+20, py), 2)
        # 
        if findEndPoint:
            score_surface = use_font.render("找到终点", True, COLOR[COLOR_BLACK], COLOR[COLOR_GREY])
            screen.blit(score_surface, (POSX+50, POSY+rows*22))
        time_passed = clock.tick(30)

        pygame.display.update()
    return 



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

GIF演示

在这里插入图片描述