基于A-Star搜索算法的迷宫小游戏的设计

这篇文章是作者人工智能导论课的大作业，发出来供大家学习参考（有完整代码）。想要论文WORD文件的可以在本文资源处下载（可能还在审核）。

摘要： 本文章聚焦于基于A-Star搜索算法的迷宫小游戏设计，通过深入剖析A-Star算法的核心理论，涵盖当前代价、预估代价、启发函数等关键概念，同时结合Pygame技术的实际应用，展示了A-Star算法在路径规划中的高效和准确表现。
关键词： A-Star搜索算法，耗散值，启发函数，曼哈顿距离，Pygame

一、相关理论

A-star搜索算法是一种常用于图搜索和路径规划的启发式搜索算法。它结合了Dijkstra算法的最短路径搜索和贪婪最优化搜索的优势，通过引入一个启发式评估函数来加速搜索过程。A-Star搜索算法是在搜索A算法的基础上，对启发函数进行条件限制得来的。

（一）A搜索算法

1. 为了尽快找到从初始节点到目标节点的一条耗散值比较小的路径，我们希望所选择的节点尽可能在最佳路径上。为了评价一个节点在最佳路径上的可能性，A算法给出了评价函数的定义：$f(n)=g(n)+h(n)$
2. 其中$n$为待评价的节点，$g(n)$为从初始节点$s$到节点$n$的最佳路径耗散值的估计值，也叫做当前代价；$h(n)$为从节点$n$到目标节点$t$的最佳路径耗散值的估计值，也叫做预估代价，$h(n)$即为启发函数。$f(n)$为从初始节点$s$经过节点$n$到达目标节点$t$的最佳路径耗散值的估计值。这里的耗散值指的是路径的代价，根据求解问题的不同，耗散值可以是路径的长度或者是需要的时间等。

（二）A-Star搜索算法

1. 在A搜索算法中，由于没有对启发函数$h(n)$做出任何规定和限制，所以A搜索算法得到的结果并不好评定。在A-Star搜索算法中，对启发函数$h(n)$做出以下规定：$h(n)<h^{\ast }(n)$
2. $h^{\ast }(n)$表示从节点$n$到目标节点$t$的所有路径中的最小耗散值，即最小代价。启发函数满足以上条件的A搜索算法就称作A-Star搜索算法，简称$A^{\ast }$算法。$h^{\ast }(n)$为启发函数的上限值，如果启发函数大于这个上限值，搜索算法就会出现发散，就不能保证总能找到最优解。

（三）曼哈顿距离

1. 曼哈顿距离也称为L1范数，是空间中两点之间的距离度量方式。在二维空间中，曼哈顿距离是两点在水平和垂直方向上的距离总和，而不考虑斜线距离。在三维或更高维空间中，曼哈顿距离是各坐标差的绝对值之和。曼哈顿距离是一种常用的启发函数，对于平面网格地图，曼哈顿距离计算从当前节点到目标节点沿着方格网格的最短路径的步数。
2. 公式：$h(n)=|curren{t}_x-goa{l}_x|+|curren{t}_y-goa{l}_y|$

二、结果展示：

三、详细代码

这里直接附上完整代码，直接放到pycharm里就能运行（要提前下载pygame包）。

import pygame  
import math  
from queue import PriorityQueue  
import tkinter as tk  
from tkinter import messagebox  
  
# pygame初始化  
pygame.init()  
  
# 设置窗口大小  
WIDTH = 900 # 高度与宽度一致  
WIN = pygame.display.set_mode((WIDTH, WIDTH)) # pygame窗口大小  
pygame.display.set_caption("A-star")  
  
# 定义颜色  
RED = (255, 0, 0) # close表  
GREEN = (0, 255, 0) # open表  
BLUE = (0, 0, 255) # end  
YELLOW = (255, 255, 0) # start  
WHITE = (255, 255, 255)  
BLACK = (0, 0, 0) # 障碍  
PURPLE = (128, 0, 128) # A-star算法下的最短路径  
ORANGE = (255, 165, 0) # Start点  
GREY = (128, 128, 128) # 灰色的网格线  
PINK = (255, 0, 255) # End点  
  
# 提示弹窗  
def show_popup_message(message):  
root = tk.Tk()  
root.withdraw() # 隐藏主窗口  
  
# 弹出窗口  
messagebox.showinfo("A-star最短路径搜索·操作介绍", message)  
  
# 文字内容  
message_content = "1. 第一次点击鼠标左键，放置“Sta”方块\n2. 第二次点击鼠标左键，放置“End”方块\n3. 继续点击鼠标左键，放置“障碍物”方块\n4. 选中方块点击鼠标右键，清除方块\n5. 按下空格开始寻找最短路径\n6. 按下q键清空当前页面"  
  
# 创建方格类  
class Spot:  
def __init__(self, row, col, width, total_rows):  
self.row = row # 行  
self.col = col # 列  
self.x = row * width # 行坐标  
self.y = col * width # 列坐标  
self.color = WHITE  
self.neighbors = [] # 相邻点的列表  
self.width = width  
self.total_rows = total_rows  
self.text = "" # 用于存储文字内容  
  
def get_pos(self):  
return self.row, self.col  
  
def is_closed(self):  
return self.color == RED # close表  
  
def is_open(self):  
return self.color == GREEN # open表  
  
def is_barrier(self):  
return self.color == BLACK # 障碍  
  
def is_start(self):  
return self.color == ORANGE # 起点  
  
def is_end(self):  
return self.color == TURQUOISE # 终点  
  
def make_start(self):  
self.color = ORANGE  
  
def make_closed(self):  
self.color = RED  
  
def make_open(self):  
self.color = GREEN  
  
def make_barrier(self):  
self.color = BLACK  
self.text = "" # 用来清除原先留下的文本  
  
def make_end(self):  
self.color = PINK  
  
def make_path(self): # 回溯路径使用  
self.color = PURPLE  
  
def make_clear(self):# 重置对应方格（重置为WHITE）  
self.color = WHITE  
self.text = "" # 用来清除原先留下的文本  
  
def set_text(self, text): # 标记文本  
self.text = text  
  
def draw(self, win):  
pygame.draw.rect(win, self.color, (self.x, self.y, self.width, self.width))  
if self.text:  
font = pygame.font.Font(None, 24)  
text_surface = font.render(self.text, True, WHITE)  
text_rect = text_surface.get_rect(center=(self.x + self.width // 2, self.y + self.width // 2))  
win.blit(text_surface, text_rect)  
  
def update_neighbors(self, grid):  
self.neighbors = []  
if self.row < self.total_rows - 1 and not grid[self.row + 1][self.col].is_barrier(): # 向下搜索，添加下方格到neighbors  
self.neighbors.append(grid[self.row + 1][self.col])  
  
if self.row > 0 and not grid[self.row - 1][self.col].is_barrier(): # 向上搜索，添加上方格到neighbors  
self.neighbors.append(grid[self.row - 1][self.col])  
  
if self.col < self.total_rows - 1 and not grid[self.row][self.col + 1].is_barrier(): # 向右搜索，添加右方格到neighbors  
self.neighbors.append(grid[self.row][self.col + 1])  
  
if self.col > 0 and not grid[self.row][self.col - 1].is_barrier(): # 向左搜索，添加左方格到neighbors  
self.neighbors.append(grid[self.row][self.col - 1])  
  
def __lt__(self, other):  
return False  
  
# 计算两个点的曼哈顿距离  
def Mh(p1, p2):  
x1, y1 = p1  
x2, y2 = p2  
return abs(x1 - x2) + abs(y1 - y2)  
  
# 构造路径  
def reconstruct_path(came_from, current, draw):  
while current in came_from:  
current = came_from[current]  
current.make_path()  
draw()  
  
# A* 算法实现  
# 参考链接：https://www.redblobgames.com/pathfinding/a-star/introduction.html#graphs（写的很好）  
def A_star_algorithm(draw, grid, start, end):  
count = 0  
open_set = PriorityQueue() # open表，用于存储待探索的节点  
open_set.put((0, count, start)) # 将起点放入优先队列，优先级为0  
came_from = {} # 当前方块到之前方块的映射  
g_score = {spot: float("inf") for row in grid for spot in row} # 当前代价，预估代价为曼哈顿距离  
g_score[start] = 0  
f_score = {spot: float("inf") for row in grid for spot in row} # 总代价  
f_score[start] = Mh(start.get_pos(), end.get_pos())  
  
open_set_hash = {start} # keep trace of the nodes  
  
while not open_set.empty(): # open表非空  
  
current = open_set.get()[2]  
open_set_hash.remove(current) # 移出open表  
  
if current == end:  
reconstruct_path(came_from, end, draw)  
end.make_end()  
start.make_start()  
return True  
  
for neighbor in current.neighbors:  
temp_g_score = g_score[current] + 1  
  
if temp_g_score < g_score[neighbor]:  
came_from[neighbor] = current  
g_score[neighbor] = temp_g_score  
f_score[neighbor] = temp_g_score + Mh(neighbor.get_pos(), end.get_pos())  
if neighbor != start and neighbor != end :  
neighbor.set_text(str(f_score[neighbor])) # 标记总代价  
if neighbor not in open_set_hash:  
count += 1  
open_set.put((f_score[neighbor], count, neighbor))  
open_set_hash.add(neighbor)  
neighbor.make_open()  
  
draw()  
  
if current != start:  
current.make_closed()  
  
return False  
  
# 创建方格网格  
def make_grid(rows, width):  
grid = [] # 创建一个空列表，用于存储方格  
gap = width // rows # 一个单元格的大小  
for i in range(rows):  
grid.append([])  
for j in range(rows):  
spot = Spot(i, j, gap, rows)  
grid[i].append(spot)  
return grid # 返回创建的列表  
  
# 绘制网格线  
def draw_grid(win, rows, width):  
gap = width // rows  
for i in range(rows):  
pygame.draw.line(win, GREY, (0, i * gap), (width, i * gap))  
for j in range(rows):  
pygame.draw.line(win, GREY, (j * gap, 0), (j * gap, width))  
  
# 绘制最优路径  
def draw(win, grid, rows, width):  
win.fill(WHITE)  
  
for row in grid:  
for spot in row:  
spot.draw(win)  
  
draw_grid(win, rows, width)  
pygame.display.update()  
  
# 获取鼠标点击的位置  
def get_clicked_pos(pos, rows, width):  
gap = width // rows  
y, x = pos  
  
row = y // gap  
col = x // gap  
  
return row, col  
  
# 主函数  
def main(win, width):  
ROWS = 25 # 一列中方格的个数  
grid = make_grid(ROWS, width)  
# clear_flag = False # 按下空格清屏  
  
start = None  
end = None  
  
run = True  
started = False  
  
show_popup_message(message_content)  
while run:  
  
draw(win, grid, ROWS, width)  
for event in pygame.event.get():  
if event.type == pygame.QUIT:  
run = False  
  
if started:  
continue  
  
if pygame.mouse.get_pressed()[0]: # 左键  
pos = pygame.mouse.get_pos()  
row, col = get_clicked_pos(pos, ROWS, width)  
spot = grid[row][col]  
if not start and spot != end: # 第一次按下对应的是Star  
start = spot  
start.make_start()  
start.set_text("Sta") # 标记Start点  
  
elif not end and spot != start: # 第二次按下对应的是End  
end = spot  
end.make_end()  
end.set_text("End") # 标记End点  
  
elif spot != end and spot != start: # 之后按下的对应的是障碍  
spot.make_barrier()  
  
elif pygame.mouse.get_pressed()[2]: # 右键  
pos = pygame.mouse.get_pos()  
row, col = get_clicked_pos(pos, ROWS, width)  
spot = grid[row][col]  
spot.make_clear()  
if spot == start:  
start = None  
elif spot == end:  
end = None  
  
if event.type == pygame.KEYDOWN: # 检测按键按下  
if event.key == pygame.K_SPACE and start and end : # 空格键对应开始寻找最短路径  
for row in grid:  
for spot in row:  
if spot != start and spot != end and spot.color != BLACK:  
spot.make_clear()  
  
for row in grid:  
for spot in row:  
spot.update_neighbors(grid)  
  
A_star_algorithm(lambda: draw(win, grid, ROWS, width), grid, start, end)  
  
elif event.key == pygame.K_q: # 按下英文字母q键对应清空屏幕  
start = None  
end = None  
grid = make_grid(ROWS, width)  
pygame.event.clear()  
  
pygame.quit()  
  
# 运行主函数  
main(WIN, WIDTH)
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