A*算法实现走迷宫（可应用于游戏人物自动寻路）

环境：win10   语言: Python3.6   编译器：pycharm

先看效果图（红色：终点  黄色：起点   黑色：障碍  绿色路径）

一、A*算法：

A*算法是一种启发式搜索算法，它不需遍历所有节点，只是利用包含问题启发式信息的评价函数对节点进行排序，使搜索方向朝着最有可能找到目标并产生最优解的方向。它的独特之处是检查最短路径中每个可能的节点时引入了全局信息，对当前节点距终点的距离做出估计，并作为评价节点处于最短路径上的可能性度量。

A*算法中引入了评估函数，评估函数为：f（n）=g（n）+h（n） 其中：n是搜索中遇到的任意状态。g(n)是沿路径从起点到n点的移动耗费。h(n)是对n到目标状态代价的启发式估计。即评估函数f ( n) 是从初始节点到达节点n 处已经付出的代价与节点n 到达目标节点的接近程度估价值的总和。 

这里我们定义n点到目标点的最小实际距离为h（n）*，A*算法要满足的条件为：h（n）<=h（n）* 。迷宫走的时候只能往上下左右走，每走一步，代价为1，H值可以用不同的方法估算。我们这里使用的方法被称为曼哈顿方法，它计算从当前格到目的格之间水平和垂直的方格的数量总和，即： h（n）=|endPoint.x – n.x|+ |endpoint.y – n.y|这里endPoint表示迷宫的目标点，n表示当前点，很明显这里h（n）<=h（n）*。

二、类的定义

1、mapPoint  :代表图中的每一个格子，搜索路径的每一个格子，记录的信息有：

self.x = x    self.y = y      当前节点的坐标位置

self.distanceStart = distanceStart    记录下由起点走到该节点的耗散值（由起点走到该节点的路径的距离，该节点的下一个节点会加1）

self.endX = endX self.endY = endY  目标节点

self.parentPoint = parentPoint # 前一个节点

方法：

评价函数：由于该评价函数比较容易计算，我直接放到该类中

def evaluate(self): return self.distanceStart + abs(self.x - self.endX) + abs(self.y - self.endY)

判断两个节点是否是同一个位置的

def isEq(self, point): if point.x == self.x and point.y == self.y: return True else: return False

以下是A*算法

def Astart(self): # 将起点放到open表中 self.openList.append(self.startPoint) while (not self.isOK): # 先检查终点是否在open表中 ，没有继续，有则结束 if self.inOpenList(self.endPoint) != -1: # 在open表中 self.isOK = True # self.end = self.openList[self.inOpenList(self.endPoint)] self.route.append(self.end) self.te = self.end while (self.te.parentPoint != 0): self.te = self.te.parentPoint self.route.append(self.te) else: self.sortOpenList() # 将估值最小的节点放在index = 0 current_min = self.openList[0] # 估值最小节点 self.openList.pop(0) self.closeList.append(current_min) # 开拓current_min节点，并放到open 表 if current_min.x - 1 >= 0: # 没有越界 if (self.mapStatus[current_min.y][current_min.x - 1]) != 0: # 非障碍,可开拓 self.temp1 = mapPoint(current_min.x - 1, current_min.y, current_min.distanceStart + 1, self.endPoint.x, self.endPoint.y, current_min) if self.inOpenList(self.temp1) != -1: # open表存在相同的节点 if self.temp1.evaluate() < self.openList[self.inOpenList(self.temp1)].evaluate(): self.openList[self.inOpenList(self.temp1)] = self.temp1 elif self.inCloseList(self.temp1) != -1: # 否则查看close表是否存在相同的节点（存在） if self.temp1.evaluate() < self.closeList[self.inCloseList(self.temp1)].evaluate(): self.closeList[self.inCloseList(self.temp1)] = self.temp1 else: # open 、 close表都不存在 temp1 self.openList.append(self.temp1) if current_min.x + 1 < 15: if (self.mapStatus[current_min.y][current_min.x + 1]) != 0: # 非障碍,可开拓 self.temp2 = mapPoint(current_min.x + 1, current_min.y, current_min.distanceStart + 1, self.endPoint.x, self.endPoint.y, current_min) if self.inOpenList(self.temp2) != -1: # open表存在相同的节点 if self.temp2.evaluate() < self.openList[self.inOpenList(self.temp2)].evaluate(): self.openList[self.inOpenList(self.temp2)] = self.temp2 elif self.inCloseList(self.temp2) != -1: # 否则查看close表是否存在相同的节点（存在） if self.temp2.evaluate() < self.closeList[self.inCloseList(self.temp2)].evaluate(): self.closeList[self.inCloseList(self.temp2)] = self.temp2 else: self.openList.append(self.temp2) if current_min.y - 1 >= 0: if (self.mapStatus[current_min.y - 1][current_min.x]) != 0: # 非障碍,可开拓 self.temp3 = mapPoint(current_min.x, current_min.y - 1, current_min.distanceStart + 1, self.endPoint.x, self.endPoint.y, current_min) if self.inOpenList(self.temp3) != -1: # open表存在相同的节点 if self.temp3.evaluate() < self.openList[self.inOpenList(self.temp3)].evaluate(): self.openList[self.inOpenList(self.temp3)] = self.temp3 elif self.inCloseList(self.temp3) != -1: # 否则查看close表是否存在相同的节点（存在） if self.temp3.evaluate() < self.closeList[self.inCloseList(self.temp3)].evaluate(): self.closeList[self.inCloseList(self.temp3)] = self.temp3 else: self.openList.append(self.temp3) if current_min.y + 1 < 15: if (self.mapStatus[current_min.y + 1][current_min.x]) != 0: # 非障碍,可开拓 self.temp4 = mapPoint(current_min.x, current_min.y + 1, current_min.distanceStart + 1, self.endPoint.x, self.endPoint.y, current_min) if self.inOpenList(self.temp4) != -1: # open表存在相同的节点 if self.temp4.evaluate() < self.openList[self.inOpenList(self.temp4)].evaluate(): self.openList[self.inOpenList(self.temp4)] = self.temp4 elif self.inCloseList(self.temp4) != -1: # 否则查看close表是否存在相同的节点（存在） if self.temp4.evaluate() < self.closeList[self.inCloseList(self.temp4)].evaluate(): self.closeList[self.inCloseList(self.temp4)] = self.temp4 else: self.openList.append(self.temp4) def drawMapBlock(self, event): x, y = event.x, event.y if (30 <= x <= 480) and (30 <= y <= 480): i = int((x // 30) - 1) j = int((y // 30) - 1) # 记录下起止点，并不能选择多个起点或者多个终点 if self.blockcolorIndex == 1 and not self.selectedStart: self.startPoint = mapPoint(i, j, 0, 0, 0, 0) self.selectedStart = True self.canvas.create_rectangle((i + 1) * 30, (j + 1) * 30, (i + 2) * 30, (j + 2) * 30, fill=self.blockcolor[self.blockcolorIndex]) self.blockcolorIndex = 0 elif self.blockcolorIndex == 2 and not self.selectedEnd: self.endPoint = mapPoint(i, j, 0, 0, 0, 0) self.selectedEnd = True self.canvas.create_rectangle((i + 1) * 30, (j + 1) * 30, (i + 2) * 30, (j + 2) * 30, fill=self.blockcolor[self.blockcolorIndex]) self.blockcolorIndex = 0 else: self.canvas.create_rectangle((i + 1) * 30, (j + 1) * 30, (i + 2) * 30, (j + 2) * 30, fill=self.blockcolor[self.blockcolorIndex]) self.mapStatus[j][i] = self.blockcolorIndex # 检查终点是否在open表中 def endInOpenList(self): for i in self.openList: if self.endPoint[0] == i.x and self.endPoint[1] == i.y: return True return False # 将节点加进open表前，检查该节点是否在open表中 def inOpenList(self, p1): for i in range(0, len(self.openList)): if p1.isEq(self.openList[i]): return i return -1 # 将节点加进open表前，检查该节点是否在close表中 # 若在返回索引，不在返回-1 def inCloseList(self, p1): for i in range(0, len(self.closeList)): if p1.isEq(self.closeList[i]): return i return -1 # 将 估值最小的 排在 index = 0 def sortOpenList(self): if len(self.openList) > 0: if len(self.openList) > 1: for i in range(1, len(self.openList)): if self.openList[i].evaluate() < self.openList[0].evaluate(): self.t = self.openList[0] self.openList[0] = self.openList[i] self.openList[i] = self.t

定义的数据结构有：

self.openList = [] # open表 self.closeList = [] # close表 self.route = [] # 路径列表

A*算法的主要过程：

1、先将起点放进open表中

2、检查终点是否在open表中，否的话，从open表中取出评价值最低的节点作为当前节点，并向四周探索，将上、下、左、右 里面非障碍的子节点，并检查子节点是否已经存在于open表或close表，若是存在open表中，则比较两个子节点与open表中的节点的评价值，若是open表中的比较大，则将open表中的替换，否则不操作；若是close表中存在且close表的节点的评价值比较大，则放进该子节点open表，否则不做操作。 然后将当前节点移出open表，并放进close表。

3、循环第2点，知道检测到终点在open 表中，然后将终点记录在路径列表中route = [] 中，并通过循环不断得到前一个节点，一直记录下来，直达没有前一个节点为止。

所有代码：

# -*- coding: utf-8 -*- from tkinter import Button from tkinter import Tk from tkinter import Canvas import numpy as np class Maze(object): def __init__(self): self.blockcolorIndex = 0 self.blockcolor = ['black', 'yellow', 'red', 'green'] # 障碍颜色为黑色、起点黄色 终点红色、路径绿色 self.mapStatus = np.ones((15, 15), dtype=int) # 地图状态数组（全0数组） 1无障碍 0障碍 self.startPoint = 'start' # 起点 self.endPoint = 'end' # 终点 self.selectedStart = False # 是否选了起点 默认否 self.selectedEnd = False # 是否选了终点 默认否 self.openList = [] # open表 self.closeList = [] # close表 self.isOK = False # 是否已经结束 self.route = [] # 路径列表 # UI self.root = Tk() self.root.title('走迷宫(A*算法)') self.root.geometry("800x800+300+0") self.btn_obstacle = Button(self.root, text="选择障碍", command=self.selectobstacle) self.btn_obstacle.pack() self.btn_start = Button(self.root, text="选择起点", command=self.selectstart) self.btn_start.pack() self.btn_end = Button(self.root, text="选择终点", command=self.selectend) self.btn_end.pack() self.btn_action = Button(self.root, text="开始寻路", command=self.selectaction) self.btn_action.pack() self.btn_restart = Button(self.root, text="重新开始", command=self.selectrestart) self.btn_restart.pack() self.canvas = Canvas(self.root, width=500, height=500, bg="white") self.canvas.pack() for i in range(1, 17): self.canvas.create_line(30, 30 * i, 480, 30 * i) # 横线 self.canvas.create_line(30 * i, 30, 30 * i, 480) # 竖线 self.canvas.bind("<Button-1>", self.drawMapBlock) self.root.mainloop() def selectrestart(self): self.mapStatus = np.ones((15, 15), dtype=int) # 地图状态数组（全0数组） 1无障碍 0障碍 self.startPoint = 'start' self.endPoint = 'end' self.selectedStart = False # 是否选了起点 默认否 self.selectedEnd = False # 是否选了终点 默认否 self.openList = [] # open表 self.closeList = [] # close表 self.isOK = False # 是否已经结束 self.route = [] self.canvas.destroy() self.canvas = Canvas(self.root, width=500, height=500, bg="white") self.canvas.pack() for i in range(1, 17): self.canvas.create_line(30, 30 * i, 480, 30 * i) # 横线 self.canvas.create_line(30 * i, 30, 30 * i, 480) # 竖线 self.canvas.bind("<Button-1>", self.drawMapBlock) def selectobstacle(self): self.blockcolorIndex = 0 # 'black' def selectstart(self): if not self.selectedStart: self.blockcolorIndex = 1 # yellow else: self.blockcolorIndex = 0 # black def selectend(self): if not self.selectedEnd: self.blockcolorIndex = 2 # red else: self.blockcolorIndex = 0 # black def selectaction(self): self.blockcolorIndex = 3 # 'green' self.Astart() self.route.pop(-1) self.route.pop(0) for i in self.route: self.canvas.create_rectangle((i.x + 1) * 30, (i.y + 1) * 30, (i.x + 2) * 30, (i.y + 2) * 30, fill='green') def Astart(self): # 将起点放到open表中 self.openList.append(self.startPoint) while (not self.isOK): # 先检查终点是否在open表中 ，没有继续，有则结束 if self.inOpenList(self.endPoint) != -1: # 在open表中 self.isOK = True # self.end = self.openList[self.inOpenList(self.endPoint)] self.route.append(self.end) self.te = self.end while (self.te.parentPoint != 0): self.te = self.te.parentPoint self.route.append(self.te) else: self.sortOpenList() # 将估值最小的节点放在index = 0 current_min = self.openList[0] # 估值最小节点 self.openList.pop(0) self.closeList.append(current_min) # 开拓current_min节点，并放到open 表 if current_min.x - 1 >= 0: # 没有越界 if (self.mapStatus[current_min.y][current_min.x - 1]) != 0: # 非障碍,可开拓 self.temp1 = mapPoint(current_min.x - 1, current_min.y, current_min.distanceStart + 1, self.endPoint.x, self.endPoint.y, current_min) if self.inOpenList(self.temp1) != -1: # open表存在相同的节点 if self.temp1.evaluate() < self.openList[self.inOpenList(self.temp1)].evaluate(): self.openList[self.inOpenList(self.temp1)] = self.temp1 elif self.inCloseList(self.temp1) != -1: # 否则查看close表是否存在相同的节点（存在） if self.temp1.evaluate() < self.closeList[self.inCloseList(self.temp1)].evaluate(): self.closeList[self.inCloseList(self.temp1)] = self.temp1 else: # open 、 close表都不存在 temp1 self.openList.append(self.temp1) if current_min.x + 1 < 15: if (self.mapStatus[current_min.y][current_min.x + 1]) != 0: # 非障碍,可开拓 self.temp2 = mapPoint(current_min.x + 1, current_min.y, current_min.distanceStart + 1, self.endPoint.x, self.endPoint.y, current_min) if self.inOpenList(self.temp2) != -1: # open表存在相同的节点 if self.temp2.evaluate() < self.openList[self.inOpenList(self.temp2)].evaluate(): self.openList[self.inOpenList(self.temp2)] = self.temp2 elif self.inCloseList(self.temp2) != -1: # 否则查看close表是否存在相同的节点（存在） if self.temp2.evaluate() < self.closeList[self.inCloseList(self.temp2)].evaluate(): self.closeList[self.inCloseList(self.temp2)] = self.temp2 else: self.openList.append(self.temp2) if current_min.y - 1 >= 0: if (self.mapStatus[current_min.y - 1][current_min.x]) != 0: # 非障碍,可开拓 self.temp3 = mapPoint(current_min.x, current_min.y - 1, current_min.distanceStart + 1, self.endPoint.x, self.endPoint.y, current_min) if self.inOpenList(self.temp3) != -1: # open表存在相同的节点 if self.temp3.evaluate() < self.openList[self.inOpenList(self.temp3)].evaluate(): self.openList[self.inOpenList(self.temp3)] = self.temp3 elif self.inCloseList(self.temp3) != -1: # 否则查看close表是否存在相同的节点（存在） if self.temp3.evaluate() < self.closeList[self.inCloseList(self.temp3)].evaluate(): self.closeList[self.inCloseList(self.temp3)] = self.temp3 else: self.openList.append(self.temp3) if current_min.y + 1 < 15: if (self.mapStatus[current_min.y + 1][current_min.x]) != 0: # 非障碍,可开拓 self.temp4 = mapPoint(current_min.x, current_min.y + 1, current_min.distanceStart + 1, self.endPoint.x, self.endPoint.y, current_min) if self.inOpenList(self.temp4) != -1: # open表存在相同的节点 if self.temp4.evaluate() < self.openList[self.inOpenList(self.temp4)].evaluate(): self.openList[self.inOpenList(self.temp4)] = self.temp4 elif self.inCloseList(self.temp4) != -1: # 否则查看close表是否存在相同的节点（存在） if self.temp4.evaluate() < self.closeList[self.inCloseList(self.temp4)].evaluate(): self.closeList[self.inCloseList(self.temp4)] = self.temp4 else: self.openList.append(self.temp4) def drawMapBlock(self, event): x, y = event.x, event.y if (30 <= x <= 480) and (30 <= y <= 480): i = int((x // 30) - 1) j = int((y // 30) - 1) # 记录下起止点，并不能选择多个起点或者多个终点 if self.blockcolorIndex == 1 and not self.selectedStart: self.startPoint = mapPoint(i, j, 0, 0, 0, 0) self.selectedStart = True self.canvas.create_rectangle((i + 1) * 30, (j + 1) * 30, (i + 2) * 30, (j + 2) * 30, fill=self.blockcolor[self.blockcolorIndex]) self.blockcolorIndex = 0 elif self.blockcolorIndex == 2 and not self.selectedEnd: self.endPoint = mapPoint(i, j, 0, 0, 0, 0) self.selectedEnd = True self.canvas.create_rectangle((i + 1) * 30, (j + 1) * 30, (i + 2) * 30, (j + 2) * 30, fill=self.blockcolor[self.blockcolorIndex]) self.blockcolorIndex = 0 else: self.canvas.create_rectangle((i + 1) * 30, (j + 1) * 30, (i + 2) * 30, (j + 2) * 30, fill=self.blockcolor[self.blockcolorIndex]) self.mapStatus[j][i] = self.blockcolorIndex # 检查终点是否在open表中 def endInOpenList(self): for i in self.openList: if self.endPoint[0] == i.x and self.endPoint[1] == i.y: return True return False # 将节点加进open表前，检查该节点是否在open表中 def inOpenList(self, p1): for i in range(0, len(self.openList)): if p1.isEq(self.openList[i]): return i return -1 # 将节点加进open表前，检查该节点是否在close表中 # 若在返回索引，不在返回-1 def inCloseList(self, p1): for i in range(0, len(self.closeList)): if p1.isEq(self.closeList[i]): return i return -1 # 将 估值最小的 排在 index = 0 def sortOpenList(self): if len(self.openList) > 0: if len(self.openList) > 1: for i in range(1, len(self.openList)): if self.openList[i].evaluate() < self.openList[0].evaluate(): self.t = self.openList[0] self.openList[0] = self.openList[i] self.openList[i] = self.t class mapPoint(object): def __init__(self, x, y, distanceStart, endX, endY, parentPoint): self.x = x self.y = y self.distanceStart = distanceStart self.endX = endX self.endY = endY self.parentPoint = parentPoint # 前一个节点 def evaluate(self): return self.distanceStart + abs(self.x - self.endX) + abs(self.y - self.endY) def isEq(self, point): if point.x == self.x and point.y == self.y: return True else: return False def main(): Maze() if __name__ == '__main__': main()